Leetcode 560: Subarray Sum Equals K

发表于 2018-04-14 更新于 2019-05-06 分类于 Algorithms

Problem

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2

Output: 2

Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution

解题思路

本题不属于某类经典类型的算法题。本题的解题关键在于深刻理解子数组和的计算方法，以及和为K的子数组和个数的求解技巧。

首先，需要求得长度为n的数组的和为K的连续子数组的个数，设为A(n)。统计连续子数组的和，以及和的分布则成为解题的前提条件。在统计连续子数组的和的过程中，我们可以采用穷举法，将所有子数组的和都进行一次统计，也能运用一些巧妙的方法，只统计部分子数组的和的个数，计算出和为K的子数组和的个数。

为了达到优化子数组和统计的方法，可以仔细思考子数组和的计算方法。不难得出，子数组和的计算方法其实源于两个从零开始的数组和之差。也就是说，假设从A[m]到A[n]之间的子数组和S[m~~n] = S[0~~n] - S[0-m]。如果在已知S[0~i] (i=0,…,n-1)的值，就能轻松求解出所有子数组的和。

然而，这样的方法用于求所有的子数组的和，并不能简化计算复杂度。要找到和为K的子数组的个数，就等于需要便利S[0~~i] (i=0,…,n)，并且找出末尾为第i个元素的子数组序列和为K的个数。由此不难推出，末尾为第i个元素的子数组序列和为K的个数，等价于S[m~~i] (m=1,…,i-1)中和为K的个数，也等价于S[0~~m] (m=1,…,i-1)中和为S[0~~i]-K的子数组个数。

1
2
3

Number(末尾为第i个元素的子数组序列和为K的个数)=Number(S[0~m] (m=1,...,i-1)中和为S[0~i]-K的子数组个数);

Number(n长数组子数组序列和为K的个数)=sigma(Number(末尾为第i个元素的子数组序列和为K的个数)) (i=0,...n-1)

程序设计

本题解的优劣则取决于统计子数组和的计算量。

运用hashmap数据结构存取所有的子数组和，经过两次for循环遍历得出所有子数组可能性下的和的值，并统计入hashmap中。本解法的时间复杂度是O(n^2)。
优化后的算法采用hashmap数据结构存取S[0~i] (i=0,…n-1)，并且在每次计算后计算以i结尾的连续子数组和为K的个数。将所有数字相加则为综合。本解法的时间复杂度是O(n)。

实现技巧

边界条件考虑：

K=0的情况。

K=S[0~i] (i=0,…,n-1)中的任意一个情况

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
        int sum = 0;
        int total =0;
        for(int i = 0; i< nums.length; ++i){
            sum += nums[i];  
            // don't forget margin k = 0, check previous count before adding this count to avoid confustion.
            if( map.containsKey(sum-k))
                total += map.get(sum-k);
            if(k == sum)
                total += 1;
               
            if(map.containsKey(sum))
                map.put(sum, map.get(sum)+1);
            else
                map.put(sum, 1);                
        }
        return total;
    }
}

Ubuntu-subsystem

发表于 2018-04-14 更新于 2021-06-22 分类于 Runbooks

Ubuntu on Windows 10

Enable Developer mode for Win 10
Add Windows Linux subsystem
Install Ubuntu/SUSE/*** from App Store

Update package sources

Edit /etc/apt/source.list

#中国数学物理大学源

deb http://debian.ustc.edu.cn/ubuntu/ vivid main multiverse restricted universe

deb http://debian.ustc.edu.cn/ubuntu/ vivid-backports main multiverse restricted universe

deb http://debian.ustc.edu.cn/ubuntu/ vivid-proposed main multiverse restricted universe

deb http://debian.ustc.edu.cn/ubuntu/ vivid-security main multiverse restricted universe

deb http://debian.ustc.edu.cn/ubuntu/ vivid-updates main multiverse restricted universe

deb-src http://debian.ustc.edu.cn/ubuntu/ vivid main multiverse restricted universe

deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-backports main multiverse restricted universe

deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-proposed main multiverse restricted universe

deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-security main multiverse restricted universe

deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-updates main multiverse restricted universe

#阿里云的源：

deb http://mirrors.aliyun.com/ubuntu/ vivid main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ vivid-security main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ vivid-updates main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ vivid-proposed main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ vivid-backports main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ vivid main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ vivid-security main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ vivid-updates main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ vivid-proposed main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ vivid-backports main restricted universe multiverse

作者：sarleon
链接：https://www.zhihu.com/question/41311332/answer/90517838

Run apt to udpate
1
$ sudo apt-get update

Intall Nodejs and npm

Install from Ubuntu apt tool

1	$ sudo apt install nodejs nodejs-legacy npm

npm self update for npm
1
$ sudo npm install -g npm@latest

npm update nodejs using package n

1
2
3

$ sudo npm install -g n
$ sudo n stable #get latest stable
$ sudo n latest #get latest version

Leetcode 60: Permutation Sequence

发表于 2018-04-12 更新于 2019-05-06 分类于 Algorithms

Problem

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

“123”

“132”

“213”

“231”

“312”

“321”

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution

解题思路

寻找排列顺序规律，可以得出如下排序规律：

整个排序可以划分成n个小排序。以1为首，[2, 3]的子序列排序。以2为首，[1, 3]的子序列排序，以3为首，[1, 2]的子序列排序。
再次划分，则可以将以1为首的排序中，分成以2为第二位， [3]的全排列，和以3为第二位，[2]的全排列。
逐次划分，分别能将长度为n的序列分解成n个(n-1)全排列，n*(n-1)个(n-2)的全排列，…n!个(1)的全排列。

程序设计

在知晓序列排序规律后，可以着手考虑将第k个元素找到。搜索定位的思想类似于一棵树的节点查找，这棵树的结构已经找到：第一层儿子有n个，第二层的孙子节点共有n*(n-1)个，且每个儿子拥有(n-1)个儿子，以此类推。

而第k个元素对应的元素如何计算出呢？根据这棵树的特点，我们可以做出如下设计，使得从树根到第k个节点的路径就是我们所需要的元素。

假设树根节点是个空节点，其的n个儿子分别为1, 2, 3, 4, 5,…, n。
第一层的节点1拥有(n-1)个儿子，分别为2, 3, 4, 5,…n。
第二层节点2拥有(n-2)个儿子，分别为3, 4, 5,…n。而第二层节点3拥有N(n-2)个儿子，分别为2, 4, 5,…n。尤其需要注意，儿子的顺序是除开父亲节点后的顺序结构。

时间复杂度树的高度，为O(n)。

实现技巧

从1到n的全排列值计算具有较高的代码重复性，可以用如下算法进行缓存，从而减少反复计算产生的时间消耗。

// dynamic length int array declaration!!!
int[] factorial = new int[n+1];
// create an array of factorial lookup
    int sum = 1;
    factorial[0] = 1;
    for(int i=1; i<=n; i++){
        sum *= i;
        factorial[i] = sum;
    }

对于元素生成，可以运用List类型的灵活性而避免在元素中挪动数字造成的时间开销。即使int array也可以作为一种高效的数据结构。

在程序实现中，递归算法会产生较高的空间开销，在for循环可以完成计算的情况下，优先采用后者。

List<Integer> numbers = new ArrayList<>();
StringBuilder sb = new StringBuilder();

// create a list of numbers to get indices
for(int i=1; i<=n; i++){
    numbers.add(i);
}
// numbers = {1, 2, 3, 4}

k--;

for(int i = 1; i <= n; i++){
        int index = k/factorial[n-i];
        sb.append(String.valueOf(numbers.get(index)));
        numbers.remove(index);
        k-=index*factorial[n-i];
    }
    
    return String.valueOf(sb);

How to use Hexo on github pages.

发表于 2018-04-08 更新于 2021-06-22 分类于 Runbooks

Welcome to Sunny’s hexo post

本文主要介绍一种常见的个人博客管理方式，利用现有的Hexo静态博客模板管理和生成静态博客文档，和github pages对git repo页面的原生发布功能进行博客展示。同时，博客文档也能在本地生成，部署，存档，较于现有的博客工具具有更好的功能扩展。

Prepare Node.js

Hexo is Node.js based npm plugin, which provides many extensions and powerful blog management functionality.

Use Hexo to manage blogs

$ npm install hexo --save
$ hexo init
$ hexo new "My New Post" # hexo new draft "My New Draft"
$ hexo server

Use SSH git management

1 2	$ ssh-keygen -t rsa -C "{yourgithubaddress}" $ ssh -T git@github.com

Create {username}.github.io repo for statics hexo pages

Configure _config.yml file for hexo blogs and deployments

# URL
## If your site is put in a subdirectory, set url as 'http://yoursite.com/child' and root as '/child/'
url: https://{username}.github.io/

# Deployment
## Docs: https://hexo.io/docs/deployment.html
deploy:
  type: git
  repo: git@github.com:{username}/{username}.githubm.io.git
  branch: master
  message: "Site updated: {{ now('YYYY-MM-DD HH:mm:ss') }}"

Deploy hexo static files to target repo

1
2
3

$ hexo clean
$ hexo generate
$ hexo deploy

Useful links:
Hexo with pictures,
Hexo Deployment,
Jekyll vs Hexo,
Markdown,
Markdown brief,
Markdown highlights

Hello World

发表于 2018-04-01 更新于 2025-03-24 分类于 Runbooks

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

Nodejs and NPM requirement

Nodejs higher than 6.0.0 and NPM higher than 5. Otherwise, Hexo might not work with some strange error!!

Hexo Mermaid for graph

More info: Here

Flow chart

graph TD;
  A-->B;
  A-->C;
  B-->D;
  C-->D;

graph TD;
    交易合同TradeContract--contains-->仓位Position;
    仓位Position--scales-->资产Asset;
    资产Asset--references-->价值的票据InstrumentOfValue;

Gannt diagram

gantt
    dateFormat  YYYY-MM-DD
    title       Adding GANTT diagram functionality to mermaid
    excludes    weekends
    %% (`excludes` accepts specific dates in YYYY-MM-DD format, days of the week ("sunday") or "weekends", but not the word "weekdays".)

    section A section
    Completed task            :done,    des1, 2014-01-06,2014-01-08
    Active task               :active,  des2, 2014-01-09, 3d
    Future task               :         des3, after des2, 5d
    Future task2              :         des4, after des3, 5d

    section Critical tasks
    Completed task in the critical line :crit, done, 2014-01-06,24h
    Implement parser and jison          :crit, done, after des1, 2d
    Create tests for parser             :crit, active, 3d
    Future task in critical line        :crit, 5d
    Create tests for renderer           :2d
    Add to mermaid                      :1d

    section Documentation
    Describe gantt syntax               :active, a1, after des1, 3d
    Add gantt diagram to demo page      :after a1  , 20h
    Add another diagram to demo page    :doc1, after a1  , 48h

    section Last section
    Describe gantt syntax               :after doc1, 3d
    Add gantt diagram to demo page      :20h
    Add another diagram to demo page    :48h

Hexo simple mindmap

Hexo simple mindmap插件提供了对脑图的可视化支持，相较于mermaid插件的流程图，能够提供更加原生的脑图体验。

More info：here

Example

软件架构师思维导图

代码规范

设计模式

重构

源码学习与分析

复杂系统面向对象模型设计

Hexo search功能

随着文章数量增加，每一页寻找文档变得耗时间，所以增加了search功能来支持快速文章定位功能。

More info: here

下载插件

1	npm install hexo-generator-searchdb --save

配置_config.yaml文件( “hexo-generator-searchdb”: “^1.4.1”后需要更新配置)

search:
  path: search.xml
  field: post
  content: true
  format: html

配置next主题的_config.yaml文件

# Local search
# Dependencies: https://github.com/flashlab/hexo-generator-search
local_search:
  enable: true
  # if auto, trigger search by changing input
  # if manual, trigger search by pressing enter key or search button
  trigger: auto
  # show top n results per article, show all results by setting to -1
  top_n_per_article: 1

hexo UML图绘制

顺序图(Sequence Diagram)

类图（Class Diagram）

强耦合关系

弱耦合关系

Hexo post asset image 管理

自带的hexo-renderer-marked的postAsset无法正常工作
使用hexo-asset-link可以动态生成基于post_dir的图片link，同时在local/remote正常工作
不要在code中写入encoded path或者linux slash /，虽然预览没有问题，但是生成的Link会出问题

Hexo blog encrypt 支持TOC

完美修复
https://www.itfanr.cc/2021/04/16/hexo-blog-article-encryption/
UX修复


# node_modules\hexo-theme-next\layout\_macro\sidebar.njk

{%- if display_toc %}
       {%- if (page.encrypt) %}
        {%- set toc = toc(page.origin, { class: "nav", list_number: page.toc.number, max_depth: page.toc.max_depth }) %}
      {%- else %}
        {%- set toc = toc(page.content, { class: "nav", list_number: page.toc.number, max_depth: page.toc.max_depth }) %}
      {%- endif %}
      {%- set display_toc = toc.length > 1 and display_toc %}
    {%- endif %}

<!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
          {%- if display_toc %}
            <!--- For hide TOC in encryption -->
            {%- if (page.encrypt) %}
              <div id="toc-div" style="display:none">
            {%- else %}
              <div id="toc-div">
            {%- endif %}
            <div class="post-toc animated">{{ toc }}</div>
            </div><!-- end of hide -->
          {%- endif %}
        </div>
<!--/noindex-->

hexo 将category作为目录归类博客

当文件数量已经比较多，单层级目录很难去管理文章分类。用hexo-directory-category 可以较好的管理post文档，便于源文件查找和更新。

hexo-next-pwa，支持页面离线访问

PWA应用的创建包含两部分，一个是manifest.json文件放在source目录下，用于提示浏览器安装PWA应用。一个是sw.js文件，用hexo workbox命令生成并注册到index.html文件，使应用支持离线访问，在线更新功能。

PWA应用的好处是运用sw.js文件，在浏览器启动一个类似原生应用的app，加载初始页面，在没有网的情况下访问离线页面，有网的情况下可以选择优先加载。对于静态页面的应用具有提升加载速度的好处。

hexo-highcharts, 支持绘制highchart原生图

这是一个轻量级的plugin，主要支持在markdown内嵌一段highcharts的配置文件，绘制出相应的图。

在加密文档里chart加载会出现竞争问题，需要用如下代码解决


let template = `
    <script defer src="https://code.highcharts.com/12.1.2/highcharts.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/sankey.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/treemap.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/treegraph.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/exporting.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/export-data.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/accessibility.js"></script>
    <button onclick="(function() {
        console.log('show highcharts')
        var event = new Event('hexo-blog-decrypt');
        window.dispatchEvent(event);
    })()">HighCharts</button>
    <div id="highcharts${id}" style="width:${args[0] || "85%"}" height:"${args[1] || 400} overflow: auto"></div>
    <script>
        var op = Object.assign(${defaultOpt},${options})
        var chart = !!window.Highcharts ? Highcharts.chart(highcharts${id},op) : console.log("Highcharts undefined");
        window.addEventListener('hexo-blog-decrypt', function() {
            console.log('decrypted')
            //if (sessionStorage.getItem("encryptState") != "1") {
            var op = Object.assign(${defaultOpt},${options})
              if(op.url){
                  $.ajax({
                      url: op.url,
                      type: "JSON",
                      method: op.method || "GET",
                      success: function(res){
                          if(op.seriesFormat){
                              op.series = op.seriesFormat(res)
                          } else {
                              op.series = res;
                          }
                          var chart = Highcharts.chart(highcharts${id},op);
                      }
                  })
              }else{
            var chart = !!window.Highcharts ? Highcharts.chart(highcharts${id},op) : console.log("Highcharts undefined");
            }
            //  sessionStorage.setItem("encryptState", "1");
            //}
        });
    </script>
    `;
    return template;

Authentication

发表于 1970-01-01 更新于 2024-06-03 分类于架构， Web

Authentication服务鉴权机制

用户在访问系统或者服务时，服务器端需要验证用户是否拥有访问的权力，这个过程称为鉴权。在服务器-客户端架构的软件系统中，当一个没有经过鉴权的用户登录时，服务器可能会返回鉴权请求。鉴权是一种客户端和服务器协同认证的方式，有多种方式可以实现：

HTTP Basic Authentication
session-cookie
Token 验证(JWT)
OAuth(开放授权)

HTTP Basic Authentication

HTTP认证时一种无状态的认证模式，因此用户在提供相关凭据的请求中能够得到认证用户的访问，而服务器本身在接下来的请求中并不能持续保持登录状态。

HTTP基本认证的具体流程如下:

在你访问一个需要HTTP Basic Authentication的URL的时候，如果你没有提供用户名和密码，服务器就会返回401，返回Header中会包含类似”WWW-Authenticate: Basic realm=”test””信息。如果你直接在浏览器中打开，浏览器会弹出对话框提示你输入用户名和密码。

要在发送请求的时候添加HTTP Basic Authentication认证信息到请求中，有两种方法:

在请求头中添加Authorization信息：Authorization: “Basic {用户名:密码}的base64加密字符串”。
在url中添加用户名和密码。

其中，鉴权机制中的身份验证并非一定要依赖Basic方式的用户名密码作为凭据，可以通过如下方式：

“WWW-Authenticate: Negotiate” SPNEGO协议,支持Kerberos, NTLM点对点认证方式完成。在协商过程中：
- 可以请求 Authorization: Negotiate {kerberos票据}进行Kerberos验证
- 或者也能读取返回头中的 Authorization: Negotiate NTLMSSP{八字节质询码} ，并在请求头部中加入 Authorization: Negotiate NTLM{加密的质询码和明码用户名}
“WWW-Authenticate: Digest realm=”test”,qop=”auth”,nonce=”{md5加密时间},opaque=”{不透明字符串}”摘要认证协议，能避免明文传输数据。
- 在请求中需要加入 Authoriztion: Digest username=”guest”,realm=”test”,nonce=”{同上},qop=”auth”,nc=”00000001”,response=”{通过md5加密的user paswd httpmethod uri等信息}”,cnonce=”{客户端提供的非明文字符串}”,uri=”{uri信息}”
- 服务器需要检查时间在允许范围内，而且response匹配本地生成值。使用MD5算法的优势在于可以很快正向哈希，而无法短时间内逆向哈希得出用户密码等信息。

session-cookie鉴权

Session是HTTP协议中为了支持有状态的通信而发明的会话机制，本质上是通过服务器为用户建立sessionid从而保证用户的状态信息能够在服务器端保存。用户不需要反复进行登录认证就能保持会话。

而Cookie则是一种特殊的HTTP头部，能够在HTTP通信中保存一定的用户信息，如sessionid从而达到认证用户的目的。由于Cookie本身是针对某一域名而产生的，所以在发送Cookie过程中必须提供正确域名的sessionid才行。

具体流程如下：

cookieAuth

Cookie鉴权常用Single Sign On场景，例如，于对于企业中的不同子域名的验证，可以通过结合SAML, CAS等协议完成。对于不同网络更加广泛的第三方验证则有OIDC协议支持。

Token 验证(JWT)

Token验证方式和Seesion验证方式很类似，不同的是Token本身包含一些有意义的信息：用户名、密码、过期时间等。Token本身由服务器签发，客户端请求的发送中需要包含 Authorization : JWT “{jwt token}”，服务器提取token信息通过相同的算法验证即可。相较于Session验证方式节约了分布式系统中服务器存储sessionid和用户信息的开销，只需要服务器拥有相同的密钥即可。

具体流程如下:

tokenAuth

JWT(json-web-token)算法细节：

JWT由三部分”{header}.{payload}.{signature}’,两种算法生成，公式如下：
signature = sha256(base64(header)+’.’+base64(payload),{服务器密钥})

header包含算法和类别信息,
payload为加密部分，包含公有声明和私有声明，公有声明为约定的key，私有为公司定制key，
signature，算法签名。
sha256为header中写的加密算法，基于服务器密钥生成不同的加密签名,具有不可逆性
base64为编码算法，可逆运算

OAuth2/OIDC认证

OIDC 即Open ID Connect, 是一种基于OAuth2授权流程，并且扩展了身份认证层的一种新的认证机制。

OIDC认证模型主要包含如下四个角色和一个令牌（完整术语参见http://openid.net/specs/openid-connect-core-1_0.html#Terminology）：

EU用户：End User：一个人类用户。
RP客户端：Relying Party ,用来代指OAuth2中的受信任的客户端，身份认证和授权信息的消费方；
OP认证服务器：OpenID Provider，有能力提供EU认证的服务（比如OAuth2中的授权服务），用来为RP提供EU的ID Token身份认证信息和Access Token访问令牌；
UE用户资源服务器：UserInfo Endpoint用户信息接口（受OAuth2保护），当RP使用Access Token访问时，返回授权用户的信息，此接口必须使用HTTPS。
ID Token认证令牌：JWT格式的数据，包含EU身份认证的信息。通过OP提供。

认证流程如下：

OIDCAuth

其中，UserIndo EndPoint是一个受OAuth2保护的资源。在RP得到Access Token后可以请求此资源，然后获得一组EU相关的Claims，这些信息可以说是ID Token的扩展，比如如果你觉得ID Token中只需包含EU的唯一标识sub即可（避免ID Token过于庞大），然后通过此接口获取完整的EU的信息。此资源必须部署在TLS之上。

OIDC的支持的授权流程如下：

Authorization Code(授权码模式)：使用OAuth2的授权码来换取Id Token和Access Token。
Implicit (简化模式)：使用OAuth2的Implicit流程获取Id Token和Access Token。
Hybrid(混合模式)：混合Authorization Code +Implicit。

OAuth2授权模型

OAuth2的授权模型时为了已登录用户通过第三方应用访问资源服务器进行授权的流程，授权模型和OIDC相似，包含如下四个角色:

资源拥有者（User） - 指应用的用户，比如github的一个账户拥有者
认证服务器（Authorization Server） - 提供登录认证接口的服务器，比如：github等
资源服务器（Resources Server） - 提供资源接口及服务的服务器，通常和认证服务器是同一个应用。
第三方客户端（Client） - 第三方应用，希望使用资源服务器提供的资源，比如你的一个支持通过github账户登录的应用
服务提供商(Provider): 认证服务和资源服务归属于一个机构，该机构就是服务提供商，比如github公司

OAuth2具有四种授权模式，下文将分述这四种模式具体流程：

授权码模式（authorization code）
简化模式（implicit）
密码模式（resource owner password credentials）
客户端模式（client credentials）

授权码模式(最为常见)

用户访问客户端应用
引导用户到认证服务器进行登录（此步骤需要携带客户端应用的clientId，可以是html直接转发认证服务器），用户输入用户名、密码
认证成功后，认证服务器向客户端应用发一个授权码code
客户端应用拿着授权码code，和clientId，clientSecret，去换取access_token
返回access_token给客户端应用

AuthorizationCodeOAuth

这种场景下，用户名、密码、客户端应用信息，都没有直接暴露在浏览器，是web下是最安全的。

简化模式

授权码模式的简化，用户认证成功后，直接将token返回给浏览器。因为某些应用没有前端服务器，只有一堆静态的html（很少见），这种模式，一般不用。

ImplicitOAuth

密码模式

适用场景：手机app ，这个客户端应用是你完全可以信任的，你的app就是自己公司开发的。但是这个模式并不适合在web场景下用，在web下，用户名密码并不是直接填给自己写的应用的，而是填在浏览器呈现的一个页面上的，这个浏览器是客户端应用的一个代理，浏览器是没法保证安全性的。

PasswordOAuth

客户端证书模式

客户端应用直接发 clientId、clientSecret给认证服务器，发的令牌是针对客户端应用的，不是针对用户的。跟没授权一样，令牌不能识别用户身份。

ClientOAuth

Authentication实战

本章将着重描述如何在java springboot应用中实现相应的认证流程。springboot提供了一站式应用的开发模式，但是认证流程是需要spring security，同时具体的认证核心模块需要spring securty keberos或者spring security oauth组件支持。下文将主要介绍如何利用这两个模块实现具体的基于siteminder/spnego/oauth协议的认证流程。

siteminder sso + preauth

Siteminder是企业级认证产品，它提供了一站式认证中间件，从应用开发者的角度来看，就是采用了外部认证系统，应用不需要重新进行认证而是可以直接从siteminder处理过的http request header中提取SM_USER中拿到userprincipal()。因此从spring securty框架的角度之需要直接读取认证后的信息，而不需要再对request进行认证验证。这通常是一种企业内网用户认证采用的sso机制，因为用户之需要进行简单认证后就能得到对多种内部webapp的访问toekn，而且不需要进行细粒度的鉴权的场景适合大部分内部应用，但是，因为外部网站可容易会被假的header所欺骗，安全性较差而不会采用这种方式进行验证。

spnego auth

SPNEGO是微软设计的一种企业级认证协议，底层支持多种token协议，因此是应用proid常用的一种方式，因为应用的id会常常跑在不同的window/linux环境，而spnego能够支持多种密钥认证从而对跨系统认证能有很好的支持，这种认证方式需要用户自己执行认证检查，所以需要spring-security-keberos模块的相关auth provider进行验证。

oidc oauth2 + ping federate

oauth标准的实现一般是用oidc协议，spring security oauth2拥有对oauth2标准的鉴权模型的实现，并且可以通过适当的配置完成oidc用户验证。oauth单独并不能完成验证鉴权功能，需要部署一个oauth provider例如云服务商azure AD等，企业级内部可以自己部署ping federate服务器完成auth信息提供功能，并且向下兼容sso（即open Id）功能。

Ping Identity是支持OIDC和OAuth2标准的企业化产品

以https://abc.com作为签发域名，PingIdentity具体支持方式如下：

openid配置查询Url：https://abc.com/.well-known/openid-configuration 返回json配置提供相关的认证终端信息，例如：

{
  "issuer": "https://abc.com", // 
  "authorization_endpoint": "https://abc.com/as/authorization.oauth2",
  "token_endpoint": "https://abc.com/as/token.oauth2",
  "revocation_endpoint": "https://abc.com/idp/userinfo.openid",
  "introspection_endpoint": "https://abc.com/as/inrospect.oauth2",
  "jwks_uri": "https://abc.com/pf/JWKS",
  "outh_jwks_uri": "https://abc.ocm/ext/oauth/JWKS",
  
  "scopes_supported" : [
    "address",
    "phone",
    "openid",
    "profile",
    "email"
  ],
  "claims_supported": [
    "email",
    "email_verified",
    "family_name",
    "given_name",
    "name",
    "preferred_username",
    "sub"
  ],
  "grant_types_supported": [
    "implicit",
    "authorization_code",
    "refresh_token",
    "password",
    "client_credentials"
  ]
}

authorization_code 授权码流程

用户发起请求到授权码endpoint：

打开chrome.exe，发起 GET https://abc.com/as/authorization.oauth2?client_id=foo&response_type=code&redirect=https%3A%2F%2Fabc.com%2Freal%2Fdocs%2F&scope=openid 请求

Chrome界面 redirect to url: https://abc.com/real/docs/?code=XXXXXXXXXXXXXXXXXX 获得授权码。

用户用返回授权码发起token请求：

1 2	curl -k --data "grant_type=authorization_code" --data "client_id=foo" --data "code=xxxxxxx" --data "redirect_uri=https://abc.com/real/docs/" https://abc.com/as/token.oauth2

返回token json:

{
  "id_token" : "xxxxxxxxxxxxxxxxx",
  "access_token" : "xxxxxxxxxxxxxx",
  "refresh_token": "xxxxxxxxxxxxxxxxxx",
  "token_type": "Bearer",
  "expires_in": 7200
}

用户刷新过期token请求：

1 2	curl -k --data "grant_type=refresh_token" --data "client_id=foo" --data "refresh_token=XXXXXXXXXX" --data "redirect_uri=https://abc.com/real/docs/" https://abc.com/as/token.oauth2

JWT 验证流程：

对于RSA加密算法加密的token，需要公私钥才能进行加解密。 “jwks_uri”: “https://abc.com/pf/JWKS“, 认证服务器会用私钥将内容加密并且作为jwt的签名部分签发给客户端，资源服务器拿到jwt token后，需要用公钥解密签名，并且和明文的payload的进行比较确认没有篡改则为有效。整个算法过程有已有的实现例如jose4j。
对于对称加密算法的token，假设资源服务器和认证服务器都已经知道密钥内容，客户端拿到jwt token后，资源服务器需要利用密钥进行解密，并且验证payload的合法性即可。

Problem

Solution

解题思路

程序设计

实现技巧

Ubuntu on Windows 10

Update package sources

Intall Nodejs and npm

Problem

Solution

解题思路

程序设计

实现技巧

Welcome to Sunny’s hexo post

Prepare Node.js

Use Hexo to manage blogs

Use SSH git management

Create {username}.github.io repo for statics hexo pages

Configure _config.yml file for hexo blogs and deployments

Deploy hexo static files to target repo

Quick Start

Create a new post

Run server

Generate static files

Deploy to remote sites

Nodejs and NPM requirement

Hexo Mermaid for graph

Hexo simple mindmap

Hexo search功能

hexo UML图绘制

顺序图(Sequence Diagram)

类图（Class Diagram）

Hexo post asset image 管理

Hexo blog encrypt 支持TOC

hexo 将category作为目录归类博客

hexo-next-pwa，支持页面离线访问

hexo-highcharts, 支持绘制highchart原生图

Authentication服务鉴权机制

HTTP Basic Authentication

session-cookie鉴权

Token 验证(JWT)

OAuth2/OIDC认证

OAuth2授权模型

授权码模式(最为常见)

简化模式

密码模式

客户端证书模式

Authentication实战

siteminder sso + preauth

spnego auth

oidc oauth2 + ping federate

Ping Identity是支持OIDC和OAuth2标准的企业化产品

Jetty Session Model