LuftBallon

Posted on Edited on

0 一些基础

判断整个图是否连通

使用dfs判断整个图是否连通：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// if not connected, return false
vecctor<int> stack = {0};
vector<bool> vis(graph.size(), false);
vis[0] = true;
int visCnt = 1;
// dfs to check if connected
while(!stack.empty()) {
    int top = stack.back();
    bool allVisited = true;
    for(int i = 0; i < graph[top].size(); ++i) {
        if(!vis[graph[top][i]]) {
            stack.emplace_back(graph[top][i]);
            vis[graph[top][i]] = true;
            allVisited = false;
            visCnt++;
            break;
        }
    }
    if(allVisited) {
        stack.pop_back();
    }
}

if(visCnt != n) return false;

使用bfs也是可以的，比如下面的0684-冗余链接

并查集的使用

主要是将有关联的边聚合到同一个root里去，可以压缩路径加速find过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(vector<int>& parent, int curNode) {
    while(parent[curNode] != curNode) {
        parent[curNode] = parent[parent[curNode]];
        curNode = parent[curNode];
    }
    return curNode;
}

void unionMerge(vector<int>& parent, int from, int to) {
    int x = find(parent, from);
    int y = find(parent, to);
    
    if(x != y) {
        parent[x] = y;
    }
}

二分图判断

  • 1 普通思路
    使用bfs遍历，考虑奇偶层级，奇层级为节点集合A，偶层级为节点集合B，最后扫描一遍所有的边，判断是否有边位于AB而不是横跨AB的，
    有的话返回false，不然则true

  • 2 并查集

  • 3 dfs

实例讲解

0785 是否二分图

1 题目

https://leetcode-cn.com/problems/is-graph-bipartite/

2 解题思路

  • 1 普通思路
    使用bfs遍历，考虑奇偶层级，奇层级为节点集合A，偶层级为节点集合B，最后扫描一遍所有的边，判断是否有边位于AB而不是横跨AB的，
    有的话返回false，不然则true；
    同时注意邻接表的判空，所有边个数为0为空的图，是可以二分的哦！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    class Solution {
    public:
        bool isBipartite(vector<vector<int>>& graph) {
            int n = graph.size();
            
            int edgeNum = 0;
            for(int u = 0; u < n; ++u) {
                for(int v = 0; v < graph[u].size(); ++v) {
                    ++edgeNum;
                }
            }
            if(edgeNum == 0) return true;

            // if not connected, return false
            vector<int> stack = {0};
            // vector<bool> vis(graph.size(), false);
            // vis[0] = true;
            // int visCnt = 1;
            // // dfs to check if connected
            // while(!stack.empty()) {
            //     int top = stack.back();
            //     bool allVisited = true;
            //     for(int i = 0; i < graph[top].size(); ++i) {
            //         if(!vis[graph[top][i]]) {
            //             stack.emplace_back(graph[top][i]);
            //             vis[graph[top][i]] = true;
            //             allVisited = false;
            //             visCnt++;
            //             break;
            //         }
            //     }
            //     if(allVisited) {
            //         stack.pop_back();
            //     }
            // }

            // if(visCnt != n) return false;

            // bfs to judge biPartitable
            deque<int> q = {};


            vector<bool> vis2(graph.size(), false);
                unordered_set<int> biPart1 = {};
                unordered_set<int> biPart2;
                deque<int> level = {};
            int bfsNum = 0;
            
            while(bfsNum != n) {        

                for(int i = 0; i < n; ++i) {
                    if(!vis2[i]) {
                        q.emplace_back(i);
                        level.emplace_back(0);
                        biPart1.insert(i);
                        ++bfsNum;
                        vis2[i] = true;
                        break;
                    }
                }
                while(!q.empty()) {
                    int front = q.front();
                    for(int i = 0; i < graph[front].size(); ++i) {
                        if(!vis2[graph[front][i]]) {
                            q.emplace_back(graph[front][i]);
                            ++bfsNum;
                            level.emplace_back(level.front() + 1);
                            if(level.front() % 2 == 0) {
                                biPart2.insert(graph[front][i]);
                            } else {
                                biPart1.insert(graph[front][i]);
                            }
                            vis2[graph[front][i]] = true;          
                        }
                    }
                    q.pop_front();
                    level.pop_front();
                }
                // for(auto& i : biPart1) {
                //     std::cout << i << " ";
                // }
                // cout << endl;
                // for(auto& i : biPart2) {
                //     std::cout << i << " ";
                // }
                // cout << endl;
                
                for(int u = 0; u < n; ++u) {
                    for(int v = 0; v < graph[u].size(); ++v) {
                        if((biPart2.count(u) == 1 && biPart2.count(graph[u][v]) == 1) || \
                        (biPart1.count(u) == 1 && biPart1.count(graph[u][v]) == 1)) {
                            return false;
                        }
                    }
                }
            }


            return true;
        }
    }

0765minSwapsCouple

1 题目

https://leetcode-cn.com/problems/couples-holding-hands/

2 解题思路

  • 0 一句话：找连通子图，每个连通子图节点数－1之和即为结果
  • 1 普通思路
    对于每一个2k - 2， 2k - 1的连续两个座位去找，2k - 2上的人的情侣，把它换到2k - 1位置上，遍历k即可 o(n**2)
  • 2 改进思路
    考虑到这样一个事实：
    如果有8个座位，然后所有情侣都没办法相邻而坐，则考虑：将在2k-2和2k-1座位上的相邻两人但不是情侣创建一条边，节点则是情侣的cp序号
    (比如4,5序号的情侣对应一个节点，为5/2 == 4/2 == 2)
    然后我们可以知道，这个图只有一个连通子图，然后其节点数量为4，那么需要交换的次数为4-1 = 3，

    容易被迷惑的地方： 一次交换至少能够完成一对情侣，只有最后的一次交换能够完成两队情侣，其余均只能完成一次
    所以说这个最小交换次数，其实别反复换，算出来的就是最小的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    class Solution {
    public:
        int minSwapsCouples(vector<int>& row) {
            // 容易被迷惑的地方： 一次交换至少能够完成一对情侣，只有最后的一次交换能够完成两队情侣，其余均只能完成一次
            // 所以说这个最小交换次数，其实别反复换，算出来的就是最小的
            
            // 首先注意到，将2个情侣看成一个节点，如果不属于一对的情侣坐在2k - 2, 2k - 1的两个位置上，则连一条线
            vector<int> parent(row.size() / 2);
            for(int i = 0; i < row.size() / 2; ++i) {
                parent[i] = i;
            }

            for(int i = 0; i < row.size(); i += 2) {
                int nodeIdx = i / 2;
                unionMerge(parent, row[i] / 2, row[i + 1] / 2);
                // std::cout << row[i] / 2<< " -> " << row[i + 1] / 2 << std::endl;
            }

            // 找出上图所有连通子图, 所有连通子图的边的节点个数减去1得到一个子图所有情侣相邻而坐需要的交换次数
            unordered_map<int, int> rootIdxToCnt;
            for(int i = 0; i < row.size() / 2; ++i) {
                rootIdxToCnt[find(parent, i)] ++;
                // std::cout << i << " -> " << find(parent, i) << std::endl;
            }

            int res = 0;
            for(auto& it : rootIdxToCnt) {
                res += it.second - 1;
            }
            return res;

        }

        int find(vector<int>& parent, int curNode) {
            while(parent[curNode] != curNode) {
                parent[curNode] = parent[parent[curNode]];
                curNode = parent[curNode];
            }
            return curNode;
        }

        void unionMerge(vector<int>& parent, int from, int to) {
            int x = find(parent, from);
            int y = find(parent, to);
            
            if(x != y) {
                parent[x] = y;
            }
        }
    }

0684 冗余链接

1 题目描述

https://leetcode-cn.com/problems/redundant-connection

2 解题思路

使用并查集，将每一条边都看做一个子树，然后一条边一条边加入这个树，当加入的边的两个顶点属于同一个子树时，就认为有回环，则返回这个冗余边。
见如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        tree.resize(edges.size() * 2 + 1, -1);
        subTreeSize.resize(edges.size() * 2 + 1, 1);
        
        vector<int> res;
        for(auto& c : edges) {
            if(!unionMerge(c[0], c[1], tree)) {
                res = c;
                break;
            }
        }
        return res;
    }
    
    int find(int tar, vector<int>& tree) {
        int curFather = tree[tar];
        if (curFather < 0) { // tar has no father, so he is the root
            tree[tar] = tar;
            return tar;
        }
        if(tar != curFather) {
            tree[tar] = find(curFather, tree); // compress the data path
        }
        return tree[tar];
    }
    
    
    bool unionMerge(int x, int y, vector<int>& tree) {
        int fx = find(x, tree);
        int fy = find(y, tree);
        if(fx == fy) {
            return false; // x, y are in the same tree, need no merge
        }
        if(subTreeSize[fx] >= subTreeSize[fy]){ // merge by rank of the sub Tree
            tree[fy] = fx;
            subTreeSize[fx] += subTreeSize[fy];
        } else {
            tree[fx] = fy;
            subTreeSize[fy] += subTreeSize[fx];
        }
        return true;
    }
    
    vector<int> subTreeSize;
    vector<int> tree;
};

Posted on Edited on

0 全排列算法

0.1 全排列实现

  • 1 一个排列，其优先交换靠右的位置的数字来获得下一个排列，比如1 2 3，他下一个必定是交换2 3,1不会参与其中，
  • 2 意识到一个排列，左侧属于高位，打个比方，若全排列对应的都有一个数字表示该排列的大小，那么左侧值越大，那么排列越大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# ref: https://blog.51cto.com/u_4925054/884291
全排列（非递归求顺序）算法  
1、建立位置数组，即对位置进行排列，排列成功后转换为元素的排列；  
2、按如下算法求全排列：  
    设P是1～n(位置编号)的一个全排列：p = p1,p2...pn = p1,p2...pj-1,pj,pj+1...pk-1,pk,pk+1...pn  
    (1)从排列的尾部开始，找出第一个比右边位置编号小的索引j（j从首部开始计算），即j = max{i | pi < pi+1}  
    (2)在pj的右边的位置编号中，找出最后一个比pj大的位置编号索引k，即 k = max{i | pi > pj} (k > j)
    (3)交换pj与pk  
    (4)再将pj+1...pk-1,pk,pk+1...pn翻转得到排列p' = p1,p2...pj-1,pj,pn...pk+1,pk,pk-1...pj+1  
    (5)p'便是排列p的下一个排列  

例如：  
24310是位置编号0～4的一个排列，求它下一个排列的步骤如下：  
(1)从右至左找出排列中第一个比右边数字小的数字2；  
(2)在该数字后的数字中找出比2大的数中编号最大的3；  
(3)将2与3交换得到34210；  
(4)将原来2（当前3）后面的所有数字翻转，即翻转4210，得30124；  
(5)求得24310的下一个排列为30124。  

这里给出官方的可能实现：
5 6 1 2 3 4的下一个排列是： 6 1 2 3 4 5

0.2 迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 比如求 6 5 4 2 3 1的下一个排列
template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (true) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) { // i = prev(i1), 找到了一个 i < i1的(2 < 3)相邻对子
            i2 = last;
            while (!(*i < *--i2)) // 从i的右边找最后一个比i大的数字
                ;
            std::iter_swap(i, i2); // 交换 i和i2 (2,3),变成6 5 4 3 2 1
            std::reverse(i1, last); // 从i1(原始数据中的3处)到最后，得到 6 5 4 3 1 2
            return true;
        }
        if (i == first) { // 若果找不到两个相邻的数，使得右边<左边,则认为是最大排列
            std::reverse(first, last);
            return false;
        }
    }
}
  • 2 回溯
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void chooseN3(vector<char>& dq, int n, priority_queue<string, vector<string>, std::function<bool(string, string)>>& res, string& tmpRes) {
        if(n == 0) {
            res.push(tmpRes);
            // std::cout << "-d2 " << tmpRes << " with n = " << tmpRes.size() <<std::endl;
            return;
        }
        for(int i = 0; i < dq.size(); ++i) {
            tmpRes.push_back(dq[i]);
            vector<char> tmpDq;
            tmpDq.insert(tmpDq.end(), dq.begin(), dq.begin() + i);
            tmpDq.insert(tmpDq.end(), dq.begin() + i + 1, dq.end());
            chooseN3(tmpDq, n - 1, res, tmpRes);
            tmpRes.pop_back();
        }
    }

2014 重复 K 次的最长子序列

1 题目

https://leetcode-cn.com/problems/largest-color-value-in-a-directed-graph/

2 解题思路

  • 1 自己的思路： 首先查出来哪些字符有k个，压入dq中，若一个字符有2k个，则压入两次(代表最终结果里可以有两个该字符)，而后将其逆序排序
  • 2 那么最后的结果一定是从dq中来，我们可以枚举dq的所有子序列即可(枚举子序列需要按照逆序字典序，这样找到的第一个子序列即为我们的目标)
  • 关键: 如何获得逆序子序列呢？
    • 1.1 最简单的想法，从dq(已经是最大的子序列了)中选择长度为n(7到1)的子序列，获取每个子序列(由于父序列为最大序列，那么子序列也一定是最大序列)所有的全排列
    • 1.2 但是这样做有问题，比如 有fd，fe两个子序列，那么优先对于fe去看其所有的排列是否满足要求，然而若是ef满足要求，那么其检测顺序在fd前面，
    • 这样就没有满足按照逆序字典序的方法去检测，于是对于长度为n的子序列，需要先生成所有的全排列，然后按照字典序排序，
      最后中实现总代码：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      class Solution {
      public:
          string longestSubsequenceRepeatedK(string s, int k) {
              // 找出大于等于k的字符记作kSet
              int n = s.size();

              vector<int> cnt(26, 0);
              vector<char> dq;
              for(int i = 0; i < n; ++i) {
                  int charNo = s[i]-'a';
                  ++cnt[charNo];
                  if(cnt[charNo] % k == 0) {
                      dq.push_back(s[i]);
                  }
              }

              // 将kSet按照逆序字典序排序
              auto cmp = [](char a, char b) {return a > b;};
              sort(dq.begin(), dq.end(), cmp);

                  // string tmp = "";
                  // for(char& c : dq) tmp += c;
                  // std::cout << "-d1 " << tmp << std::endl;


              // 找到第一个满足的最大长度为dq的字典序逆序的子序列的排列即为结果
              // 从子模式串的最大长度dq.size()一直遍历到1
              for(int len = dq.size(); len >= 1; --len) {
                  // vector<char> tmp;
                  // vector<vector<char>> res;
                  // chooseN(dq, len, 0, res, tmp);
                  // string tmp;
                  // vector<string> res;
                  // chooseN2(dq, len, 0, res, tmp);

                  // // 构建出同len的所有permutaion，然后sort然后再来以此比较
                  // vector<string> sameLenStr;
                  // for(int i = 0; i < res.size(); ++i) {
                  //     do {

                  //         // string tmp4 = "";
                  //         // for(char& c : res[i]) tmp4 += c;
                  //         // std::cout << "-d4 " << tmp4 << " with n = " << len <<std::endl;
                  //         sameLenStr.push_back(res[i]);
                  //     }while(prev_permutation(res[i].begin(), res[i].end()));
                  // }
                  // sort(sameLenStr.begin(), sameLenStr.end(), [](string a, string b){return a > b;});
                              // for(int subIdx = 0; subIdx < sameLenStr.size(); ++subIdx) {
                  //     // do {
                  //     // 构造seq*k
                  //     string tmpDq;
                  //     for(int i = 0; i < k; ++i) {
                  //         tmpDq += sameLenStr[subIdx];
                  //     }
      // 
                  //     // string tmp3 = "";
                  //     // for(char& c : tmpDq) tmp3 += c;
                  //     // std::cout << "-d3 " << tmp3 << " with n = " << tmpDq.size() <<std::endl;
      // 
                  //     // 判断构造的seq*k是否存在于s中
                  //     int tmpIdx = 0;
                  //     int realIdx = 0;
                  //     int cnt = 0;
                  //     for(; tmpIdx < tmpDq.size(); ++tmpIdx) {
                  //         for(; realIdx < n; ++realIdx) {
                  //             if(s[realIdx] == tmpDq[tmpIdx]) {
                  //                 ++cnt;
                  //                 ++realIdx;
                  //                 break;
                  //             }
                  //         }
                  //     }
      // 
                  //     
                  //     if(cnt == tmpDq.size()) {
                  //         return sameLenStr[subIdx];
                  //     }
                  //         
                  // }
                  string tmp;
                  std::function<bool(string, string)> cmp = [](string a, string b)->bool{return a < b;};
                  priority_queue<string, vector<string>, std::function<bool(string, string)>> sameLenStr(cmp);
                  chooseN3(dq, len, sameLenStr, tmp);
       
                  // 看该子序列是否可以
                  while(!sameLenStr.empty()) {
                      string curStr = sameLenStr.top();
                      sameLenStr.pop();
                      string tmpDq;
                      for(int i = 0; i < k; ++i) {
                          tmpDq += curStr;
                      }

                      // string tmp3 = "";
                      // for(char& c : tmpDq) tmp3 += c;
                      // if(curStr.size() <= 10)std::cout << "-d3 " << curStr << " with n = " << tmpDq.size() <<std::endl;

                      // 判断构造的seq*k是否存在于s中
                      int tmpIdx = 0;
                      int realIdx = 0;
                      int cnt = 0;
                      for(; tmpIdx < tmpDq.size(); ++tmpIdx) {
                          for(; realIdx < n; ++realIdx) {
                              if(s[realIdx] == tmpDq[tmpIdx]) {
                                  ++cnt;
                                  ++realIdx;
                                  break;
                              }
                          }
                      }

                      if(cnt == tmpDq.size()) {
                          return curStr;
                      }
                  }

              }
              return "";
          }

          void chooseN2(vector<char>& dq, int n, int st, vector<string>& res, string& tmpRes) {
              if(n == 0) {
                  res.push_back(tmpRes);
                  // std::cout << "-d2 " << tmpRes << " with n = " << tmpRes.size() <<std::endl;
                  return;
              }
              for(int i = st; i < dq.size() - n + 1; ++i) {
                  tmpRes.push_back(dq[i]);
                  chooseN2(dq, n - 1, i + 1, res, tmpRes);
                  tmpRes.pop_back();
              }
          }

          void chooseN3(vector<char>& dq, int n, priority_queue<string, vector<string>, std::function<bool(string, string)>>& res, string& tmpRes) {
              if(n == 0) {
                  res.push(tmpRes);
                  // std::cout << "-d2 " << tmpRes << " with n = " << tmpRes.size() <<std::endl;
                  return;
              }
              for(int i = 0; i < dq.size(); ++i) {
                  tmpRes.push_back(dq[i]);
                  vector<char> tmpDq;
                  tmpDq.insert(tmpDq.end(), dq.begin(), dq.begin() + i);
                  tmpDq.insert(tmpDq.end(), dq.begin() + i + 1, dq.end());
                  chooseN3(tmpDq, n - 1, res, tmpRes);
                  tmpRes.pop_back();
              }
          }
        
      };

      0047 全排列去重

1 题目

https://leetcode-cn.com/problems/permutations-ii/

2 解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Solution {
public:
    unordered_set<string> hash;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // vector<vector<int>> res;
        // vector<int> tmp;
        // string tmpStr = "";
        // chooseN(nums, nums.size(), res, tmp, tmpStr);
        // vector<vector<int>> res;
        // vector<int> tmp;
        // string tmpStr = "";
        // chooseN2(nums, 0, nums.size(), res, tmpStr);
        vector<vector<int>> res;
        vector<int> tmp;
        vector<bool> vis(nums.size(), false);
        sort(nums.begin(), nums.end());
        chooseN3(nums, 0, nums.size(), res, vis, tmp);
        return res;
    }

    // 160ms
    void chooseN(vector<int>& nums, int n, vector<vector<int>>& res, vector<int>& tmp, string tmpStr) {
        if(n == 0) {
            if(hash.count(tmpStr) == 0) {
                std::cout << tmpStr << std::endl;
                hash.insert(tmpStr);
                res.emplace_back(tmp);
            }
        }

        for(int i = 0; i < nums.size(); ++i) {
            
            vector<int> tmpNums;
            tmpNums.insert(tmpNums.end(), nums.begin(), nums.begin() + i);
            tmpNums.insert(tmpNums.end(), nums.begin() + i + 1, nums.end());
            tmp.emplace_back(nums[i]);
            tmpStr.push_back(static_cast<char>(nums[i] + 107));
            chooseN(tmpNums, n-1, res, tmp, tmpStr);
            tmpStr.pop_back();
            tmp.pop_back();
        }
    }


   
    // chooseN由于每次构造新的串子，这样降低了速度，只用swap到最左边就行了
    // 32ms
    void chooseN2(vector<int>& nums, int st, int n, vector<vector<int>>& res, string tmpStr) {
        if(st == nums.size()) {
            if(hash.count(tmpStr) == 0) {
                std::cout << tmpStr << std::endl;
                hash.insert(tmpStr);
                res.emplace_back(nums);
            }
        }

        for(int i = st; i < nums.size(); ++i) {
            
            vector<int> tmpNums;
            tmpStr.push_back(static_cast<char>(nums[i] + 107));
            swap(nums[st], nums[i]);
                      
            chooseN2(nums, st + 1, nums.size(),  res, tmpStr);

            swap(nums[st], nums[i]);
            tmpStr.pop_back();
        }
    }

    // 由于使用string来判断还是降低了速度，于是在搜索过程中判断是否能够压入
    void chooseN3(vector<int>& nums, int st, int n, vector<vector<int>>& res, vector<bool>& vis, vector<int>& tmp) {
        if(st == nums.size()) {
                res.emplace_back(tmp);
        }

        for(int i = 0; i < nums.size(); ++i) {
            // 如果当前数作为第st层的回溯已经用过了，则不再使用 || 若当前数字和st层上一次使用数字相同，则也不再使用
            if(vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            // if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
            //     continue;
            // }
            vector<int> tmpNums;
            tmp.emplace_back(nums[i]);
            vis[i] = 1;
                      
            chooseN3(nums, st + 1, nums.size(),  res, vis, tmp);

            vis[i] = 0;
            tmp.pop_back();
            // swap(nums[st], nums[i]);
        }
    }
};

Posted on Edited on

0 有向图的环路判断

  • 1 bfs访问节点的数目超过n本身才能说明有环
  • 2 或者dfs能够访问到之前访问过的节点，也说明有环
  • 3 不能仅仅通过是否有出度为0的节点来判断是否成环，eg:
    [[0,1],[1,1]]

1857largestPathValue 路径最大节点颜色数

1 题目

https://leetcode-cn.com/problems/largest-color-value-in-a-directed-graph/

2 解题思路

  • 1 自己的思路：自然能够想到的解题方法, 对于出度为0的点做dfs，然后统计每个颜色的值
  • 2 思路存在的问题：

    上述算法的遍历节点总是从出度为0的地方开始遍历所有可能的路径
    有重复计算的第方，想象一下，1, 2分别连着3,3后面跟了1000个节点
    那么会从1,2分别计算一遍，那3后面的1000个节点被重复计算了2次

  • 3 解决思路：

    很显然我们就会想到从小规模开始计算，那么1,2的计算结果就能利用
    小规模的值得到了,那么什么样的节点算是小规模子图的起始点？
    这隐藏了一个拓扑排序 + 动态规划的思路在其中：
    如果想要减少上述重复计算过程，可以考虑使用动态规划，但是
    需要直到1,2,3以及后面节点谁在前谁在后的问题，使用拓扑排序解决
    这里可以顺便说一下
    首先bfs获得拓扑排序，依此入栈s，(则s的栈顶得到的是没有后继节点的
    那些节点)，则依此从s中pop然后得到节点v，dp[v][c]代表从v出发的
    颜色为c的最大值    ，则对于每个有到达v的边的u，有：
    dp[u][c] = max(dp[u][c], dp[v][c]);
    但是这个需要知道，v的前级节点有哪些，则需要翻转一遍v，所以就
    bfs拓扑排序依此入队列，从队头出数据(这些数据都是没有入度的)，
    dp[v][c] 表示到达节点v的所有路径的颜色为c的最大值(并未统计v节点本身)
    对于u所有的 -> v:
    dp[v][c] = max(dp[u][c], dp[v][c]); // 广度优先遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    class Solution {
    public:
        int ans = -1;

        void dfs(int from, string& colors, vector<vector<int>>& g, map<char, int>& cntInPath) {
            cntInPath[colors[from]]++;
            ans = max(ans, cntInPath[colors[from]]);
            for(int to = 0; to < g.size(); ++to) {
                if(g[from][to] == 1) {
                    dfs(to, colors, g, cntInPath);
                }
            }
            cntInPath[colors[from]]--;
        }

        int largestPathValue(string colors, vector<vector<int>>& edges) {
            // // 自然能够想到的解题方法: 
            // // 基于出度为0的点做dfs，然后统计每个颜色的值
            // vector<int> noInNode;
            // map<int, int> inDegreeStatistic;
            // for(auto &e : edges) {
            //     inDegreeStatistic[e[1]]++;
            // }
            // int n = colors.size();
            // for(int i = 0; i < n; ++i) {
            //     auto it = inDegreeStatistic.find(i);
            //     if(it == inDegreeStatistic.end()) {
            //         noInNode.emplace_back(i);
            //     }
            // }

            // if(noInNode.size() == 0){
            //     return -1;
            // }

            // vector<vector<int>> g(n, vector<int>(n, -1));
            // for(int i = 0; i < edges.size(); ++i) {
            //     g[edges[i][0]][edges[i][1]] = 1;
            // }

            // // 对每一个节点出度为0的遍历
            // int maxApperanceNumInPath = -1;
            // map<char, int> cntInPath;
            // for(auto& c : colors) {
            //     cntInPath[c] = 0;
            // }
            // for(auto& n : noInNode) {
            //     dfs(n, colors, g, cntInPath);
            // }

            // 上述算法的遍历节点总是从出度为0的地方开始遍历所有可能的路径
            // 有重复计算的第方，想象一下，1, 2分别连着3,3后面跟了1000个节点
            // 那么会动1,2分别计算一遍，那3后面的1000个节点被重复计算了2次
            // 很显然我们就会想到从小规模开始计算，那么1,2的计算结果就能利用
            // 小规模的值得到了,那么什么样的节点算是小规模子图的起始点？
            // 这隐藏了一个拓扑排序 + 动态规划的思路在其中：
            // 如果想要减少上述重复计算过程，可以考虑使用动态规划，但是
            // 需要直到1,2,3以及后面节点谁在前谁在后的问题，使用拓扑排序解决
            // dp[v][c] 表示到达节点v的所有路径的颜色为c的最大值(并未统计v节点本身)
            // 对于u所有的 -> v: 
            // dp[v][c] = max(dp[u][c], dp[v][c]); // 广度优先遍历

            // 构建邻接表，统计入度情况
            vector<int> noInNode;
            int n = colors.size();
            vector<vector<int>> g(n);

            map<int, int> inDeg;
            for(auto &e : edges) {
                inDeg[e[1]]++;
                g[e[0]].emplace_back(e[1]);
            }
            
            // 做拓扑排序，首先找到那些个入度为0的点
            vector<array<int, 26>> dp(n);
            deque<int> q;
            for(int i = 0; i < n; ++i) {
                auto it = inDeg.find(i);
                if(it == inDeg.end()) {
                    q.push_back(i);
                }
            }
            
            // bfs访问节点的数目超过n本身才能说明有环
            // 或者dfs能够访问到之前访问过的节点，也说明有环
            // 不能仅仅通过是否有出度为0的节点来判断是否成环，eg:
            // [[0,1],[1,1]]
            int bfsTravelNum = 0;
            // 使用bfs遍历获取拓扑排序顺便动态规划
            while(!q.empty()) {
                ++bfsTravelNum;
                // 取出一个没有入度的节点
                int u = q.front();
                q.pop_front();
                // 访问到u节点
                dp[u][colors[u] - 'a']++;

                // 更新所有 以v为终点的路径(不包含v本身) 的颜色为c的最大节点数
                for(int v : g[u]) {
                    inDeg[v]--;
                    for(int c = 0; c < 26; ++c) {
                        dp[v][c] = max(dp[v][c], dp[u][c]);
                    }
                    // 位于u拓扑排序后面的v
                    if(0 == inDeg[v]) {
                        q.push_back(v);
                    }
                }
            }
            
            if(bfsTravelNum != n) return -1;

            for(int i = 0; i < n; ++i) {
                ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
            }

            return ans;
        }
    };

3 环路判断

  • 1 bfs访问节点的数目超过n本身才能说明有环
  • 2 或者dfs能够访问到之前访问过的节点，也说明有环
  • 3 不能仅仅通过是否有出度为0的节点来判断是否成环，eg:
    [[0,1],[1,1]]

Posted on Edited on

1 docker-compose安装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
version: "3.4"

# https://docs.influxdata.com/influxdb/v1.7/administration/config
services:
  influxdb:
    image: influxdb:1.7-alpine
    environment:
      - INFLUXDB_ADMIN_ENABLED=true 
      - INFLUXDB_ADMIN_USER=${INFLUXDB_ADMIN_USER:-root}
      - INFLUXDB_ADMIN_PASSWORD=${INFLUXDB_ADMIN_PASSWORD:-root}
      - INFLUXDB_DB=test
      - INFLUXDB_HTTP_LOG_ENABLED=false
      - INFLUXDB_REPORTING_DISABLED=true
      - INFLUXDB_USER=${INFLUXDB_USER:-test}
      - INFLUXDB_USER_PASSWORD=${INFLUXDB_USER_PASSWORD:-test}
    ports:
      - "8083:8083"
      - "8086:8086"
    deploy:
      mode: replicated
      replicas: 1
      resources:
        limits:
          memory: 2048M
        reservations:
          memory: 1024M
    volumes:
      - ./local_bind_volume_dir:/var/lib/influxdb

1.5 基本概念理解

https://www.cnblogs.com/yihuihui/p/11386679.html

2 基本操作

https://jasper-zhang1.gitbooks.io/influxdb/content/Guide/writing_data.html
插入一个值：

1
2
3
curl -i -X POST "http://localhost:8086/write?db=test" -u root:root --data-binary "cpu_load_short,host=server01,region=us-west value=0.64,value2=0.86 1434055562000000000"

> insert cpu_load_short,host=server02,region=de value=0.1,value2=0.2

从上面的输出，简单小结一下插入的语句写法:
insert + measurement + “,” + tag=value,tag=value + + field=value,field=value

  • tag与tag之间用逗号分隔；field与field之间用逗号分隔
  • tag与field之间用空格分隔
  • tag都是string类型，不需要引号将value包裹
  • field如果是string类型，需要加引号

查询该值：

1
2
3
4
5
6
> select * from cpu_load_short;
name: cpu_load_short
time                host     region  value value2
----                ----     ------  ----- ------
1434055562000000000 server01 us-west 0.64  0.86
1637648158355267700 server02 de      0.1   0.2

4 代码操作:

注意写入的过程需要保证有field，不能全为tag，将很多raw插入：(以下划线开始的为filed，filed字段不会建立索引，故查询慢)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
    public void insert(String table, List<Map<String, Object>> rows) {
        if (CollectionUtils.isEmpty(rows)) {
            return;
        }
        List<Point> points = rows.stream()
                .filter(e -> !CollectionUtils.isEmpty(e))
                .map(e -> {
                        return to(table, e);

                })
                .collect(Collectors.toList());
        if (CollectionUtils.isEmpty(points)) {
            return;
        }
        BatchPoints batchPoints = BatchPoints.builder()
                .points(points)
                .build();
        influxDB.write(batchPoints);
        influxDB.flush();
    }

/** to函数 **/ 
    private Point to(String table, Map<String, Object> row)  {
        Point.Builder builder = Point.measurement(table).time(getTime(row), TimeUnit.MILLISECONDS);
        row.remove("time");
        row.forEach((k, v) -> {
            if (v == null) {
                return;
            }
            if (StringUtils.startsWith(k, "_")) {
                String key = StringUtils.removeStart(k, "_");
                if (v.getClass().getName().equals(boolean.class.getName())) {
                    builder.addField(key, (boolean) v);
                } else if (v.getClass().getName().equals(short.class.getName())) {
                    builder.addField(key, (short) v);
                } else if (v.getClass().getName().equals(int.class.getName())) {
                    builder.addField(key, (int) v);
                } else if (v.getClass().getName().equals(long.class.getName())) {
                    builder.addField(key, (long) v);
                } else if (v.getClass().getName().equals(float.class.getName())) {
                    builder.addField(key, (float) v);
                } else if (v.getClass().getName().equals(double.class.getName())) {
                    builder.addField(key, (double) v);
                } else if (v instanceof Boolean) {
                    builder.addField(key, (Boolean) v);
                } else if (v instanceof Number) {
                    builder.addField(key, (Number) v);
                } else if (v instanceof String) {
                    builder.addField(key, (String) v);
                } else {
                    builder.addField(key, v.toString());
                }
            } else {
                builder.tag(k, v.toString());
            }
        });
        return builder.build();
    }
    
/** build函数(influxdb官方维护) 将会检测是否含有field字段 **/ 
        public Point build() {
            Preconditions.checkNonEmptyString(this.measurement, "measurement");
            Preconditions.checkPositiveNumber(this.fields.size(), "fields size"); // 此处需保证fields size 大于等于1
            Point point = new Point();
            point.setFields(this.fields);
            point.setMeasurement(this.measurement);
            if (this.time != null) {
                point.setTime(this.time);
                point.setPrecision(this.precision);
            }

            point.setTags(this.tags);
            return point;
        }

Posted on Edited on

1 滑动窗口

priority_queue经常用

0480 滑动窗口中位数

1 题目

https://leetcode-cn.com/problems/sliding-window-median/

2 解题思路

  • 1 使用一个multiset维护当前窗口，
    • 1.1 不使用priority_queue的原因，无法删除元素
    • 1.2 不使用map/set的原因，不能含有重复元素
  • 2 对于窗口，维护一个中位数指针，注意到中位数指针在每一次窗口移动只会发生几种情况
    • 2.1 向左，向右，不动
    • 2.2 分类讨论清除即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        long long n = nums.size();
        std::multiset<long long, std::less<long long>> mySet(nums.begin(), nums.begin() + k);

        vector<double> res;
        multiset<long long>::iterator mid = mySet.begin();
        std::advance(mid, (k-1)/2);

        for(long long i = k; i <= n; ++i) {
            res.emplace_back((*mid + *next(mid, 1 - k%2))*1.0L/2);
            if(i == n) break;

            mySet.insert(nums[i]);
            if (nums[i] > *mid && nums[i - k] < *mid) {
                mid++;
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
                // std::advance(mid, 1);
            }

            if (nums[i] < *mid && nums[i - k] > *mid) {
                mid--;
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
                // std::advance(mid, -1);
            }
            // 7 3 7 7 4, k = 4
            // 7 8 7 7 4, k = 4
            if(nums[i-k] == *mid) {
                if(nums[i] >= *mid)  ++mid;
                else {
                    if(*prev(mid) != *mid) {
                        --mid;
                    }
                }
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
            } 

            if(nums[i] == *mid) {// 相当于一个比mid大的数字插入到了mid的前面
                if(nums[i-k] <= *mid)  ++mid;
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
            }
        }
        return res;
    }
};

0992 k个不同元素的子数组个数

1 题目

https://leetcode-cn.com/problems/subarrays-with-k-different-integers/submissions/

2 解题思路

  • 1 正常思路：
    • 1.1 首先窗口是必须的，即为[st, ed]，那么保证这个窗口时刻含有k个不同变量，然后求出来每个以ed为结尾的子数组的个数求和即可
    • 1.2 那么以ed为结尾的窗口[st, ed]的子数组个数求法，假设k=2，窗口为1,2，1,2,那么以ed为结尾，st就向前移动，直到窗口内的不同元素个数减少到了k-1，此时st移动到第二个2的位置，一共移动了3次，也就是说以ed为结尾的含有k个不同变量的子数组个数为3。
    • 1.3 其中的复杂之地在于：如何判断窗口内不同元素的个数，我们采用经典的空间换时间的方法(因为所有元素的值不会大于数组本身长度),用freq[val]记录val出现的次数， 倘若长度不限呢？那就需要使用unordered_map来记录当前窗口所有元素的出现次数，然后每移动一次st需要遍历一遍这个map来判断当前窗口内不同元素的个数，那么整体复杂度为： o(n * k * k)
  • 2 官方题解：
    • 2.1 不同元素为k的子数组的个数为： 不同元素最多为k的子数组个数 - 不同元素最多为k-1的子数组个数，那么问题转为求不同元素最多为k的一个数组它子数组的个数
    • 2.2 求法： 还是滑动窗口的思想，始终保持窗口中最多元素的个数不超过k（方式为每次移动ed，直到第一次超过k，然后移动st直到小于k），然后对于每个ed，ed - st就是以ed为窗口结尾对应的不同元素不超过k的子数组的个数，举个例子：(官方例子)：

      用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return maxSubArrayNumForKDiff(nums, k) - maxSubArrayNumForKDiff(nums, k - 1);

    }

    int maxSubArrayNumForKDiff(vector<int>& nums, int k) {
        vector<int> freq(nums.size() + 1);
        long long res = 0;
        int st = 0;
        int ed = 0;
        int curCnt = 0;
        while(ed < nums.size()) {
            // 求每个ed对应得到的最多k个不同元素的子数组个数
            if(freq[nums[ed]] == 0) {
                curCnt ++;
            }
            freq[nums[ed]]++;
            ++ed;

            // 减小窗口到窗口内元素种类第一次为k-1个
            while(curCnt > k) {
                freq[nums[st]]--;
                if(freq[nums[st]] == 0) {
                    curCnt--;
                }
                ++st;
            }
            res += ed - st;
        }
        return res;
    }
};

0904 完全水果个数

1 题目

https://leetcode-cn.com/problems/fruit-into-baskets/

2 解题思路

  • 1 正常思路：(于0904https://leetcode-cn.com/problems/fruit-into-baskets/实现)
    • 1.1 首先窗口是必须的，即为[st, ed]，那么保证这个窗口时刻含有k个不同变量，然后求出来每个以ed为结尾的子数组的个数求和即可
    • 1.2 那么以ed为结尾的窗口[st, ed]的子数组个数求法，假设k=2，窗口为1,2，1,2,那么以ed为结尾，st就向前移动，直到窗口内的不同元素个数减少到了k-1，此时st移动到第二个2的位置，一共移动了3次，也就是说以ed为结尾的含有k个不同变量的子数组个数为3。
    • 1.3 其中的复杂之地在于：如何判断窗口内不同元素的个数，我们采用经典的空间换时间的方法(因为所有元素的值不会大于数组本身长度),用freq[val]记录val出现的次数， 倘若长度不限呢？那就需要使用unordered_map来记录当前窗口所有元素的出现次数，然后每移动一次st需要遍历一遍这个map来判断当前窗口内不同元素的个数，那么整体复杂度为： o(n * k * (log k)) = o(n)
  • 2 官方题解：
    • 2.1 不同元素为k的子数组的个数为： 不同元素最多为k的子数组个数 - 不同元素最多为k-1的子数组个数，那么问题转为求不同元素最多为k的一个数组它子数组的个数
    • 2.2 求法： 还是滑动窗口的思想，始终保持窗口中最多元素的个数不超过k（方式为每次移动ed，直到第一次超过k，然后移动st直到小于k），然后对于每个ed，ed - st就是以ed为窗口结尾对应的不同元素不超过k的子数组的个数，举个例子：(官方例子)：

      用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size() <= 1) {
            return 1;
        }

        // 不同元素最多为2的数组长度
        int res = 0;
        int st = 0;
        int ed = 0;
        int curCnt = 0;
        map<int, int> freq;
        bool stNotMov = true;
        while(ed < fruits.size()) {
            while(freq.size() <= 2 && ed < fruits.size()) {
                if(freq.find(fruits[ed]) == freq.end()) {
                    curCnt++;
                }
                freq[fruits[ed]]++;
                ed++;
            }
            
            if(!stNotMov && ed != fruits.size()) {
                res = std::max(res, ed - st - 1);
            } else  {
                if(freq.size() == 3) {
                    res = std::max(res, ed - st - 1);
                } else {
                    res = std::max(res, ed - st);
                }
                
            }
            
            while(freq.size() > 2) {
                freq[fruits[st]]--;
                if(freq[fruits[st]] == 0) {
                    freq.erase(freq.find(fruits[st]));
                }
                ++st;
                stNotMov = false;
            }
        }
        return res;
    }
};

0995 执行次数最小: 每次翻转k个让数组全为1

1 题目

https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/

2 解题思路

  • 1 正常思路：窗口始终保持k个，去模拟翻转过程，由于需要在窗口内找到翻转后第一个为0的数字，这个复杂度为O（k），所以总复杂度为： O(n*k)
  • 2 官方题解：使用差分数组diff,diff[i]表示nums[i]比nums[i-1]多了多少次翻转，那么当前总的翻转次数就为： sum(diff[i])，对于nums[i]而言， sum(diff[i])%2为0则表示nums[i]需要翻转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        vector<long long> preSum = {0};
        for(long long num : nums) {
            preSum.emplace_back(preSum.back() + num);
        }

        long long st = 0;
        long long ed = st + k - 1;
        long long n = nums.size();
        long long res = 0;

        vector<long long> diff(n+1);
        long long flipCnt = 0;
        // while(st < n - k + 1) {
            // 模拟思路会超时
            // if(nums[st] == 1) {
            //     ++st;
            //     continue;
            // }
            // int newSt = flipKBit(nums, k, st, preSum);
            // if(newSt == -1) {
            //     st = st + k;
            // } else {
            //     st = newSt;
            //     res += 1;
            // }
        // }
        // if(find(nums.end() - k, nums.end(), 0) == (nums.end())) {
        //     return res;
        // } 

        while(st < n) {
            // 采用查分数组记录每个元素应该翻转的次数
            // 这启发我们用差分数组的思想来计算当前数字需要翻转的次数。我们可以维护一个差分数组 \textit{diff}diff，其中 \textit{diff}[i]diff[i] 表示两个相邻元素 
            // \textit{nums}[i-1]nums[i−1] 和 \textit{nums}[i]nums[i] 的翻转次数的差，对于区间 [l,r][l,r]，将其元素全部加 11，只会影响到 ll 和 r+1r+1 处的差分值，
            // 故 \textit{diff}[l]diff[l] 增加 11，\textit{diff}[r+1]diff[r+1] 减少 11。
            flipCnt += diff[st];
            if((flipCnt + nums[st]) % 2 == 0) {
                if(st + k > n) {
                    return -1;
                }
                diff[st] ++;
                diff[st + k] --;
                res++;
                flipCnt ++;
            }
            ++st;
        }
        return res;
    }

    // 翻转kbit，返回第一个翻转窗口中反转后值不等于1的下标，否则返回-1
    int flipKBit(vector<int>& nums, int k, int st, vector<int>& preSum) {
        int firstNot1 = INT_MAX;
        // 需要O(k)时间的复杂度
        bool needFlip = find(nums.begin() + st, nums.begin() + st + k, 0) != (nums.begin() + st + k);
        // 使用前缀和优化，由于实地翻转了数组，于是会改变对应的前缀和，所以此方法行不通
        // bool needFlip = ((preSum[st + k] - preSum[st]) != k);

        // for(int i = st; i < k; ++i) {
        //     if(nums[st + i] != 1) {
        //         needFlip = true;
        //     }
        // }
        if(needFlip) {
            for(int i = 0; i < k; ++i) {
                nums[st + i] = abs(nums[st + i] - 1);
                if(nums[st + i] != 1) {
                    firstNot1 = min(firstNot1, st + i);
                }
            }
            return firstNot1 > nums.size() ? st + k : firstNot1 ;
        }
        

        return -1;
    }
};

1696 最大结果

1 题目

https://leetcode-cn.com/problems/jump-game-vi/submissions/

2 解题思路

  • 1 采用动态规划：dp[i]表示跳到i处的最大收益,如下：搜索i的前k个下标即可
    1
    2
    3
    4
    5
    6
    7
    8
    // o(n * k)解法
    dp[0] = 0;
    dp[1] = nums[0];
    for(int i = 1; i < nums.size() + 1; ++i) {
        for(int m = 1; m < k + 1 && i - m > 0; ++m) {
            dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
        }
    }
  • 2 优化上述搜索前k个下标的方案，我们采用优先队列来维护前k个中最大的上一跳：
    • 将上述O(n*k)变为O(n*logk)，原因是maxHeap的push操作是logN的复杂度
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      class Solution {
      public:
          struct number {
              long long idx = 0;
              long long val = 0;
              number(long long idx, long long val): idx(idx), val(val) {};

              // sort descending
              bool  operator<(const number& b) const {return this->val < b.val;}
          };
          int maxResult(vector<int>& nums, int k) {
              vector<long long> dp(nums.size() + 1, INT_MIN);
              // o(n * k)解法
              dp[0] = 0;
              dp[1] = nums[0];
              // for(int i = 1; i < nums.size() + 1; ++i) {
              //     for(int m = 1; m < k + 1 && i - m > 0; ++m) {
              //         dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
              //     }
              // }

              std::priority_queue<number, std::vector<number>, std::less<number>> maxHeap;
              maxHeap.push({1, nums[0]});
              // 使用堆优化：
              for(int i = 2; i < nums.size() + 1; ++i) {
                  while(maxHeap.top().idx < i - k) {
                      maxHeap.pop();
                  }

                  dp[i] =  maxHeap.top().val + nums[i - 1];
                  maxHeap.push({i, dp[i]});
                  
                  // for(int m = 1; m < k + 1 && i - m > 0; ++m) {
                  //     dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
                  // }
              }
              
              return dp[nums.size()];

          }
      };

总结

滑动窗口的最大值：可以使用maxHeap来维护，复杂度logk

Posted on Edited on

1 前缀和

1
2
3
4
vector<int> prefSum {nums[0]};
for(int i = 1; i < nums.size(); ++i) {
    prefSum[i] += (nums[i] + prefSum.back()); 
}

1546最大非重叠数组

1 题目

https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/submissions/

2 解题思路

最为关键的一句话：
每次找结束序号最小的和为target的子数组，然后从这个子数组的后面开始搜寻下一个子数组，经典贪心。

前缀和，普通为o(n^2)，使用hash优化：
subSum[j:i]，本来需要遍历所有的j找出为k的subarray，
但是换个思路： 其实就是找i之前，有多少个前缀和为 preSum[j] - k，
那么我们把前缀和用hash存一下，那不就能够很快找到了？

但是有一个问题，在下一次搜寻开始的时候，需要将上一次搜寻过程的hash清零，
否则上一次的hash的结果会影响当前子序和。
而且假设上一次搜寻到j了，那么这次从j+1开始搜寻，必须保证前缀和也是从j+1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int ans = 0;
        // vector<int> preSum(nums.size());

        // preSum[0] = nums[0];
        // for(int i = 1; i < nums.size(); ++i ){
        //     preSum[i] = preSum[i-1] + nums[i];
        // }
        // while(ed < nums.size()) {
        //     for(int st = lastFoundEd; st <= ed; ++st) {
        //         if(preSum[ed] - preSum[st] + nums[st] == target) {
        //             ++ans;
        //             lastFoundEd = ed+1;
        //             break;
        //         }
        //     }
        //     ++ed;
        // }

        int st = 0;
        int ed = 0;
        int lastFoundEd = ed;

        // map<int, int> hash;

        
        while(st < nums.size()) {
            ed = st;
            // hash.clear();   // clear history to avoid repeat count
            unordered_set<int> hash = {0};
            int curSumFromLastFoundEd = 0;
            while(ed < nums.size()) {
                curSumFromLastFoundEd += nums[ed];
                if(hash.count(curSumFromLastFoundEd - target)) {
                    ++ans;
                    st = ed;        // new search start
                    break;
                } else {
                    hash.insert(curSumFromLastFoundEd);
                }
                ++ed;
            }
            ++st;
        }

        return ans;
    }
};

0560subArraySum 子数组和为k

1 题目

https://leetcode-cn.com/problems/subarray-sum-equals-k/

2 解题思路

前缀和，普通为o(n^2)，使用hash优化：
subSum[j:i]，本来需要遍历所有的j找出为k的subarray，
但是换个思路： 其实就是找i之前，有多少个前缀和为 preSum[j] - k，
那么我们把前缀和用hash存一下，那不就能够很快找到了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> prefSum(nums.size());
        prefSum[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            prefSum[i] += (nums[i] + prefSum[i-1]); 
        }

        int st = 0;
        int ed = 0;
        int ans = 0;
        int curSum = 0;
        std::unordered_map<int, int> hash;
        hash[0] = 1;
        while(ed < nums.size()) {
            if(hash.find(prefSum[ed] - k) != hash.end()) {
                ans += hash[prefSum[ed] - k];
            } 
            hash[prefSum[ed]]++;

            
            // for(int st = ed; st >= 0; --st) {
            //     curSum = prefSum[ed] - prefSum[st] + nums[st];
            //     if(curSum == k){
            //         ++ans;
            //     }
            // }
            ++ed;
        }
        
        return ans;
    }
};

1171移除和为0的子链表

1 题目：

https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

2 解题思路：

个人暴力思路：

  • 1 每次移除一个和为0的子数组，返回一个新的链表
  • 2 重复上述过程直到没有和为0的子数组

前缀和思路参考：
采用前缀和判断和为0方法：
我们可以考虑如果给的入参不是链表是数组的话，只需要求出前缀和，对于前缀和相同的项，那他们中间的部分即是可以消除掉的，比如以 [1, 2, 3, -3, 4] 为例，其前缀和数组为 [1, 3, 6, 3, 7] ，我们发现有两项均为 3，则 6 和 第二个 3 所对应的原数组中的数字是可以消掉的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    ListNode* newHead;

    ListNode* removeZeroSumSublists(ListNode* head) {
        newHead = head;
        while(removeOneZeroSubList(newHead)){ }
        return newHead;
    }

    bool removeOneZeroSubList(ListNode* newHead) {
        vector<int> valVec;
        ListNode* head = newHead;
        ListNode* p = head;
        while(p != nullptr) {
            valVec.emplace_back(p->val);
            p = p->next;
        }
        size_t len = valVec.size();
        vector<vector<int>> sumMat(len, vector<int>(len));

        // cal all the sub len
        // sumMat[a, b] = sumMat[a, b-1] + a
        ListNode* stPtr = head;
        ListNode* lastStPtr = nullptr;
        for(int st = 0; st < len; ++st) {
            sumMat[st][st] = valVec[st];
            if(sumMat[st][st] == 0) {
                if(nullptr == lastStPtr) {
                    this->newHead = head->next;
                    return true;
                }
                lastStPtr->next = stPtr->next;
                return true;
            }
            ListNode* edPtr = stPtr->next;
            for(int ed = st + 1; ed < len; ++ed) {
                sumMat[st][ed] = sumMat[st][ed-1] + valVec[ed];
                if(sumMat[st][ed] == 0) {
                    if(nullptr == lastStPtr) {
                        this->newHead = edPtr->next;
                        return true;
                    }
                    lastStPtr->next = edPtr->next;
                    return true;
                }
                edPtr = edPtr->next;
            }
            lastStPtr = stPtr;
            stPtr = stPtr->next;
        }
        return false;
    }
};

1292最大方块长度

1 题目

https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/

2 解题思路

  • 1 建立二维前缀和： 
    1
    2
    3
    4
    5
    6
      vector<vector<int>> preSum(m+1, vector<int>(n+1, 0));
    for(int i = 1; i < m+1; ++i) {
        for(int j = 1; j < n+1; ++j) {
            preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + mat[i-1][j-1];
        }
    }
  • 2 遍历所有边长的正方形即可(每个正放形为起点加上边长)，遍历长度的过程可以通过二分搜索加速

值得思考的点：
如何快速得知当前位置是不是被阻挡了？
使用unordered_set作为hash快速查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        // mat.row >= m > i >= 0, mat.col >= n > j >= 0
        // preSum[m][n] -> preSum[i][j] = preSum[m][n] - preSum[m][j] - preSum[i][n] + preSum[i][j];
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> preSum(m+1, vector<int>(n+1, 0));
        for(int i = 1; i < m+1; ++i) {
            for(int j = 1; j < n+1; ++j) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + mat[i-1][j-1];
            }
        }

        // traverse all square
        int maxSquareLen = std::min(m, n);
    //    for(int len = maxSquareLen; len >= 1; --len) { // len could be binary search
    //         for(int i = 0; i <= m - len; ++i) {
    //             for(int j = 0; j <= n - len; ++j) {
    //                 if(getRec(preSum, i+1, j+1, i + len, j + len) <= threshold) {
    //                     return len;
    //                 };
    //             }
    //         }
    //    }
        int stLen = 1;
        int edLen = maxSquareLen;
        int ans = 0;
        while(stLen <= edLen) {
            int len = (stLen + edLen) / 2;
            bool found = false;
            for(int i = 0; i <= m - len; ++i) {
                for(int j = 0; j <= n - len; ++j) {
                    if(getRec(preSum, i+1, j+1, i + len, j + len) <= threshold) {
                        found = true;
                    };
                }
            }
          
            if(found) { // len too small
                stLen = len+1;
                ans = len;
            } else { // len too big
                edLen = len-1;
            }
          
        }

        return ans;
    }

    int getRec(vector<vector<int>>& preSum, int i, int j, int m, int n) {
        return preSum[m][n] - preSum[m][j-1] - preSum[i-1][n] + preSum[i-1][j-1];
    }
};

1124 良好表现的最长时间段

1 题目

https://leetcode-cn.com/problems/longest-well-performing-interval/

2 解题思路

较为容易想到前缀和思路：
不好想的地方在于第1和3条，思路如下：

  • 1 对于这种良好费良好的判断，我们需要把数组转换成 -1, 1的数组
  • 2 对上述数组作前缀和
  • 3 那么对于每个到来的j，只需要找到最小的i，满足 preSum[j] - preSum[i] == 1即可
    • 3.1 如何理解最小的i，也就是说，对于同一个preSum值的下标，我们总是去最小的i即可
    • 3.2 对于 9 9 9 9 9这种全正常的思路，如何判断？ 前缀和的值本身就可以判断，大于零的下标都可以是良好工作区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        vector<int> preSum = {0};
        for(int i = 0; i < hours.size(); ++i) {
            preSum.emplace_back((hours[i] > 8 ? 1 : -1) + preSum.back());
        }
          
        int st = 0;
        int ed = 0;
        int res = INT_MIN;
        // key: presum's value, value: presum's index
        map<int, int> m;
        m[0] = 0;
        int lastPop = 0;
        vector<int> mono = {0};
        for(; ed < hours.size(); ++ed) {
            if (preSum[ed + 1] > 0) {
                res = std::max(res, ed + 1);
                continue;
            }
            map<int, int>::iterator it = m.find(preSum[ed + 1] - 1);
            if(it != m.end()) {
                res = std::max(ed - it->second, res);
            } 
            if (m.find(preSum[ed + 1]) == m.end()) {
                m[preSum[ed + 1]] = ed; 
            }
            
        }
        return res < 0 ? 0 : res;

    }
};

Posted on Edited on

1 强联通分量解释

SCC(stronglyConnectedComponents) 对于G(v, e)的一个子图中，其任何两个顶点都存在一个path相互到达;

2 图的拓扑排序

拓扑排序的核心思路还是利用深度优先搜索，排序的基本思想为深度优先搜索正好只会访问每个顶点一次，如果将dfs的参数顶点保存在一个数据结构中，遍历这个数据结构就能访问图中的所有顶点，而遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是递归调用之后保存。

  • 1 前序：　在递归调用之前将顶点加入队列　—- pre()方法
  • 2 后序：　在递归调用之后将顶点加入队列　—- post()方法
  • 3 逆后序： 在递归调用之后将顶点压入栈 —- reversePost()方法
    这里给出一个逆后序的例子：
    强连通分量
    其逆后序得到的一个栈为：(右侧为栈顶，代表最晚完成访问的节点) 6 4 2 5 3 1

逆后序获得代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class DepthFirstOrder {
	private boolean[] marked;
	private Queue<Integer> pre;			//所有顶点的前序排列
	private Queue<Integer> post;		//所有顶点的后序排列
	private Stack<Integer> reversePost;	//所有顶点的逆后序排列
	
	public DepthFirstOrder(Digraph G){
		pre = new Queue<Integer>();
		post = new Queue<Integer>();
		reversePost = new Stack<Integer>();
		marked = new boolean[G.V()];

		for(int v =0;v<G.V();v++)
			if(!marked[v]) dfs(G,v);
	}
	private void dfs(Digraph G,int v){
		pre.enqueue(v);

		marked[v] = true;
		for(int w:G.adj(v))
			if(!marked[w])
				dfs(G,w);

		post.enqueue(v);
		reversePost.push(v);
	}
	
	public Iterable<Integer> pre(){
		return pre;
	}
	
	public Iterable<Integer> post(){
		return post;
	}
	
	public Iterable<Integer> reversePost(){
		return reversePost;
	}

}

3 求解算法

3.1 kosaraju算法

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm 伪代码:

  1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
  2. For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine:
    If u is unvisited then:
    1. Mark u as visited.
    2. For each out-neighbour v of u, do Visit(v).
    3. Prepend u to L.
    Otherwise do nothing.
  3. For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine:
    If u has not been assigned to a component then:
    1. Assign u as belonging to the component whose root is root.
    2. For each in-neighbour v of u, do Assign(v,root).
    Otherwise do nothing.

换句话说：
主要就是2次dfs：

  • 1 获得G的逆图G’，对G做一遍dfs获得其逆后序的顶点访问序列
  • 2 对于逆后序顶点访问序列，重复2.1即可
    • 2.1 将最晚完成访问的顶点，在G’中访问，能够一遍到达的那些顶点，就是目标的连通分量，将相关顶点在逆后序访问序列中移除即可

3.2 Tarjan算法（待续）

参考： https://www.cnblogs.com/wuchanming/p/4138705.html

3.3 Gabow算法(待续)

参考： https://www.cnblogs.com/wuchanming/p/4138705.html

具体的例子：

4 实际题解

4.1 针对无向图连通分量求解

该解题方案实际上为有向图强联通分量求解的一个子集，无向图即为顶点和顶点之间的边均为双向边。
这里以kosaraju算法为例:

  • 1 对于有向图，一开始我们需要获取dfs的逆序遍历栈，原因是，在第二次dfs也就是逆图中的遍历我们可以总是用最晚完成遍历的点去遍历，如此依赖，这样的一个遍历就能得到一个连通分量。
  • 2 但是针对无向图，不需要这样，因为遍历到不能拓展新的节点，我们就获取到了一个连通分量。

https://leetcode-cn.com/problems/number-of-provinces/
其解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public:
    void dfs(vector<vector<int>>& g, vector<int>& reversePost, vector<bool>& vis, int tarV) {
        vis[tarV] = true;
        for(int j = 0; j < g.size(); ++j) {
            if(g[tarV][j] != 0) {
                if(!vis[j]) {
                    dfs(g, reversePost, vis, j);
                }
            }    
        }
        reversePost.emplace_back(tarV);
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        // 获取逆图
        int n = isConnected.size();
        vector<vector<int>> revIsConnected(isConnected);

        // 由于不是针对有向图，故不需要这一步
        // 获取逆序
        vector<bool> vis(n, false);
        vector<int> reversePost;
        // dfs(isConnected, reversePost, vis, 0);

        // 直接任选一点遍历，看有几个连通分量即可
        int ans = 0;       
        for(int j = 0; j < isConnected.size(); ++j) {
            if(!vis[j]) {
                dfs(isConnected, reversePost, vis, j);
                ans ++;
            }          
        }
        return ans;
    }
};

// 顺便给一个并查集解法：
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] parent = new int[provinces];
        for (int i = 0; i < provinces; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < provinces; i++) {
            for (int j = i + 1; j < provinces; j++) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (parent[i] == i) {
                circles++;
            }
        }
        return circles;
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}

4.2 针对有向图连通分量的求解

参考例子

Posted on Edited on

1 购买云主机

购买地址：(选择centos即可)
https://www.vultr.com/register/
建议： 选择硅谷服务器，ip比较好用
购买后deploy完成（大胆deploy，一次0.01$，它收费是按照使用时长收费的）

2 ssh登入主机然后安装ss服务端

2.0 安装ss-server， 以及obfs或者v2ray作为混淆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 关闭防火墙
systemctl status firewalld.service
systemctl stop firewalld.service
systemctl disable firewalld.service

# 安装ss-server
## mac: brew install shadowsocks-libevs

cd /etc/yum.repos.d/
yum install -y https://dl.fedoraproject.org/pub/epel/epel-release-latest-7.noarch.rpm
curl -O https://copr.fedorainfracloud.org/coprs/librehat/shadowsocks/repo/epel-7/librehat-shadowsocks-epel-7.repo
yum install -y shadowsocks-libev 
ss-server -h # 之后应该能看到提示信息

# 安装simple-obfs(已经不再维护)
yum install zlib-devel openssl-devel git autoconf automake asciidoc libtool xmlto libev-devel -y
git clone https://github.com/shadowsocks/simple-obfs.git
cd simple-obfs
git submodule update --init --recursive
./autogen.sh
./configure && make
make install
cd .. && obfs-server # 应该能看到提示信息

# 安装v2ray-plugin
# v2ray需要域名支持，所以重新考虑吧




### 2.1 配置ss-server的配置文件：
```sh
[root@vultrguest simple-obfs]# cat /etc/shadowsocks-libev/config.json
{
    "server":["[::0]","0.0.0.0"],
    "server_port": 8388,
    "password":"0000",
    "timeout":300,
    "plugin": "obfs-server",
    "plugin_opts": "obfs=tls;obfs-host=iosapps.itunes.apple.com",
    "method":"aes-256-gcm",
    "fast_open":false
}

2.2 将ss-server启动配置成服务

1
2
3
4
5
6
7
8
9
10
11
# 创建文件： /etc/systemd/system/shadowsocks.service，其内容如下
[Unit]
Description=Shadowsocks Server
After=network.target

[Service]
ExecStart=/usr/bin/ss-server -c /etc/shadowsocks-libev/config.json -u
Restart=on-abort

[Install]
WantedBy=multi-user.target

之后启动服务：

1
2
3
systemctl enable shadowsocks.service
systemctl start shadowsocks.service
systemctl status shadowsocks.service

应该能看到如下结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[root@nash5 ~]# systemctl status shadowsocks.service
● shadowsocks.service - LSB: Fast tunnel proxy that helps you bypass firewalls
   Loaded: loaded (/etc/rc.d/init.d/shadowsocks; generated)
   Active: active (running) since Mon 2021-09-27 01:53:36 UTC; 1 weeks 4 days ago
     Docs: man:systemd-sysv-generator(8)
  Process: 61718 ExecStop=/etc/rc.d/init.d/shadowsocks stop (code=exited, status=0/SUCCESS)
  Process: 61720 ExecStart=/etc/rc.d/init.d/shadowsocks start (code=exited, status=0/SUCCESS)
    Tasks: 2 (limit: 5048)
   Memory: 19.0M
   CGroup: /system.slice/shadowsocks.service
           ├─61722 /usr/local/bin/ss-server -v -c /etc/shadowsocks-libev/config.json -f /var/run/shadowsocks-libev.pid
           └─61723 obfs-server

Oct 08 05:43:26 nash5 /usr/local/bin/ss-server[61722]: close a connection to remote, 4 opened remote connections
Oct 08 05:43:26 nash5 /usr/local/bin/ss-server[61722]: close a connection from client, 4 opened client connections

3 win 客户端方面

3.1 修改主机host

3.3 - end -

连接成功

4 linux&mac客户端

4.0.0 linux 安装simple-obfs(已经不再维护)

yum install zlib-devel openssl-devel git autoconf automake asciidoc libtool xmlto libev-devel -y
git clone https://github.com/shadowsocks/simple-obfs.git
cd simple-obfs
git submodule update –init –recursive
./autogen.sh
./configure && make
make install
cd .. && obfs-server # 应该能看到提示信息

linux将ss-local做成服务：

1
2
3
4
5
6
7
8
9
10
11
12
13
~ >>> cat /usr/lib/systemd/system/ss-local.service                                                                                              [130]
[Unit]
Description=Shadowsocks-Libev Client Service
After=network.target

[Service]
Type=simple
User=nobody
CapabilityBoundingSet=CAP_NET_BIND_SERVICE
ExecStart=/usr/local/bin/ss-local -c /etc/shadowsocks/ld.json --plugin obfs-local --plugin-opts "obfs=tls;obfs-host=cn.bing.com;fast-open=true;" 

[Install]
WantedBy=multi-user.target

编译过程不需要了，直接

1
2
3
4
5
6
brew install simple-obfs
brew install shadowsocks-libev

# 参照linux的写法：
/opt/homebrew/opt/shadowsocks-libev里的将plist文件改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
	<key>KeepAlive</key>
	<true/>
	<key>Label</key>
	<string>homebrew.mxcl.shadowsocks-libev</string>
	<key>ProgramArguments</key>
	<array>
		<string>/opt/homebrew/opt/shadowsocks-libev/bin/ss-local</string>
		<string>-c</string>
		<string>/opt/homebrew/etc/shadowsocks-libev.json</string>
		<string>plugin</string>
		<string>obfs-local</string>
		<string>plugin-opts</string>
		<string>obfs=tls;obfs-host=cn.bing.com;fast-open=true;</string>
	</array>
	<key>RunAtLoad</key>
	<true/>
</dict>
</plist>

可以看出对应的config文件，修改为如下：
其中的method一定要和server的方法对齐

1
2
3
4
5
6
7
8
9
10
ldxy@ldxydeMacBook-Pro softwares % cat /opt/homebrew/etc/shadowsocks-libev.json
{
    "server":"你的ip",
    "server_port":8388,
    "local_port":1080,
    "password":"你的秘密",
    "timeout":600,
    "method":"aes-256-gcm" 
}

修改完成以后启动运行调试即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
brew services list
cat ~/Library/LaunchAgents/homebrew.mxcl.shadowsocks-libev.plist 
brew services start shadowsocks-libev
ps -ef | grep ss-local
````

# V2ray配置安装
## 1 购买域名
参考：
[https://www.clloz.com/programming/assorted/2021/11/15/vps-2021/](https://www.clloz.com/programming/assorted/2021/11/15/vps-2021/)

## 2 配置v2ray
参考: [https://iyideng.vip/black-technology/cgfw/vmess-v2ray-server-building-and-using-tutorial.html](https://iyideng.vip/black-technology/cgfw/vmess-v2ray-server-building-and-using-tutorial.html)

值得注意的一点是，当你本地ping不通你的域名，你需要修改dns服务器，使得你能够获得你的域名：
```sh
sudo vim /etc/resolv.conf
# 添加以下内容
nameserver 202.114.0.131
nameserver 202.114.0.242
nameserver 114.114.114.114

nslookup 你的域名

Posted on Edited on

1 最大流-最小割本身含义

首先 起始点 s, 终止点 t, 从s->t的所有通路中，能够流过来的最大流量就是最大流，这里举个例子：
比如有如下的图：
1 -> 2 管道是5的容量，
2 -> 4 管道是4的容量，
1 -> 3 管道是3的容量，
3 -> 4 管道是6的容量，
那么从1->4的最大流，就是4 + 3 = 7

最小割：
最小割是指，从图中移除一些边的集合以达到隔断从s到t的目的，成为一个图割，然后最小割，就是所有图割中，边权(管道的流量)之和最小的一个图割，最小割的值和最大流的值是相等的

2 最大流最小割算法

最小割最大流算法

其过程就是：

  • 1 对于G中的每一个顶点，先将f(u, v)和f(v, u)都置为0
  • 2 当存在从s->t的一条路径(这样的一条路径称之为增广路径):
    • 2.1 找出这个路径上的最小边权，称为tmpC
    • 2.2 对增广路径上的每一条边，都做: f(u, v) += tmpC, f(v, u) = -f(u, v)
  • 3 G中的更改过后的图，称之为残余图(residual graph)
    上面过程的tmpC之和就是最大流的值

3 例子

引用自: https://www.baeldung.com/cs/minimum-cut-graphs
最小割示例

在上述例子里的残余图中：
可以看出： 最大流为: 4 + 4 + 3 + 2 = 13

4 最小割

在上述例子里的残余图中：
首先按照从s能够到达的点和不能到达的点分成2个集合set1(reaching by s)和set2(not reaching by s)，这两个set在残余图中的连线构成的那些边成为最小割

那么set1是： (a, b, c, e)
set2是：(d, f)]
残余图中，set1和set2相关连的边为： b->d, c->f, e->f,最小割值为： 4 + 3 + 6 = 13