快排、归并、二分

数组

原地转置

不过这个是对一维数组的操作，暂时没想到对二维非方阵数组，除了不停的resize以外的方法。 

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
int getNext(int i, int m, int n)
{
    return (i%n)*m + i/n;
}
 
/* 前驱 */
int getPre(int i, int m, int n)
{
    return (i%m)*n + i/m;
}
 
/* 处理以下标i为起点的环 */
void movedata(int *mtx, int i, int m, int n)
{
    int temp = mtx[i];  // 暂存
    int cur = i;       // 当前下标
    int pre = getPre(cur, m, n);
    while(pre != i)
    {
        mtx[cur] = mtx[pre];
        cur = pre;
        pre = getPre(cur, m, n);
    }
    mtx[cur] = temp;
}
 
/* 转置，即循环处理所有环 */
void transpose(int *mtx, int m, int n)
{
    for(int i=0; i<m*n; ++i)
    {
        int next = getNext(i, m, n);
        while(next > i) // 若存在后继小于i说明重复
            next = getNext(next, m, n);
        if(next == i)   // 处理当前环 
            movedata(mtx, i, m, n);
    }
}
 
/* 输出矩阵 */
void print(int *mtx, int m, int n)
{
    for(int i=0; i<m*n; ++i)
    {
        if((i+1)%n == 0)
            cout << mtx[i] << "\n";
        else
            cout << mtx[i] << " ";
    }
}

双指针法

http://chocoluffy.com/2016/12/04/%E6%B5%85%E6%9E%90%E7%BB%8F%E5%85%B8%E9%9D%A2%E8%AF%95%E7%AE%97%E6%B3%95%E9%A2%98-two-pointer%E7%9A%84%E8%BF%90%E7%94%A8/

表:

双重链接表

正交表

树:

二叉树

遍历
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//filename: BinTreeNode.h
template <typename T>
void travPre_R(BinTreeNode<T> * root) {//二叉树先序遍历算法（递归版）
    if (!root) return;
    cout << root->data;
    travPre_R(root->LeftChild);
    travPre_R(root->RightChild);
}


// 非递归先序遍历
public static void preorderTraversal(TreeNode root) {
    // 用来暂存节点的栈
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    // 新建一个游标节点为根节点
    TreeNode node = root;
    // 当遍历到最后一个节点的时候，无论它的左右子树都为空，并且栈也为空
    // 所以，只要不同时满足这两点，都需要进入循环
    while (node != null || !treeNodeStack.isEmpty()) {
        // 若当前考查节点非空，则输出该节点的值
        // 由考查顺序得知，需要一直往左走
        while (node != null) {
            System.out.print(node.val + " ");
            // 为了之后能找到该节点的右子树，暂存该节点
            treeNodeStack.push(node);
            node = node.left;
        }
        // 一直到左子树为空，则开始考虑右子树
        // 如果栈已空，就不需要再考虑
        // 弹出栈顶元素，将游标等于该节点的右子树
        if (!treeNodeStack.isEmpty()) {
            node = treeNodeStack.pop();
            node = node.right;
        }
    }
}



// 递归中序遍历
public static void recursionMiddleorderTraversal(TreeNode root) {
    if (root != null) {
        recursionMiddleorderTraversal(root.left);
        System.out.print(root.val + " ");
        recursionMiddleorderTraversal(root.right);
    }
}



// 非递归中序遍历
public static void middleorderTraversal(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    while (node != null || !treeNodeStack.isEmpty()) {
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }
        if (!treeNodeStack.isEmpty()) {
            node = treeNodeStack.pop();
            System.out.print(node.val + " ");
            node = node.right;
        }
    }
}


// 递归后序遍历
public static void recursionPostorderTraversal(TreeNode root) {
    if (root != null) {
        recursionPostorderTraversal(root.left);
        recursionPostorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}


// 非递归后序遍历
public static void postorderTraversal(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    TreeNode lastVisit = root;
    while (node != null || !treeNodeStack.isEmpty()) {
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }
        //查看当前栈顶元素
        node = treeNodeStack.peek();
        //如果其右子树也为空，或者右子树已经访问
        //则可以直接输出当前节点的值
        if (node.right == null || node.right == lastVisit) {
            System.out.print(node.val + " ");
            treeNodeStack.pop();
            lastVisit = node;
            node = null;
        } else {
            //否则，继续遍历右子树
            node = node.right;
        }
    }
}


方法三：Morris 遍历
思路与算法

有一种巧妙的方法可以在线性时间内，只占用常数空间来实现后序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其后序遍历规则总结如下：

新建临时节点，令该节点为 root；

如果当前节点的左子节点为空，则遍历当前节点的右子节点；

如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点；

如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点，当前节点更新为当前节点的左子节点。

如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右子节点。

重复步骤 2 和步骤 3，直到遍历结束。

这样我们利用 Morris 遍历的方法，后序遍历该二叉搜索树，即可实现线性时间与常数空间的遍历。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def addPath(node: TreeNode):
            count = 0
            while node:
                count += 1
                res.append(node.val)
                node = node.right
            i, j = len(res) - count, len(res) - 1
            while i < j:
                res[i], res[j] = res[j], res[i]
                i += 1
                j -= 1
        
        if not root:
            return list()
        
        res = list()
        p1 = root

        while p1:
            p2 = p1.left
            if p2:
                while p2.right and p2.right != p1:
                    p2 = p2.right
                if not p2.right:
                    p2.right = p1
                    p1 = p1.left
                    continue
                else:
                    p2.right = None
                    addPath(p1.left)
            p1 = p1.right
        
        addPath(root)
        return res

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

平衡二叉树

AVL树

自由树

有向树

无穷性引理

树的枚举

通路长度

图

有向图

有向无环图

拓扑排序

我们都知道对于有向图进行拓扑排序可以判断是否存在环。

对于有向图的拓扑排序，大家都知道的kahn算法：

计算图中所有点的入度，把入度为0的点加入栈 如果栈非空： 取出栈顶顶点a，输出该顶点值，删除该顶点

从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈

如果图中还存在顶点，则表示图中存在环；否则输出的顶点就是一个拓扑排序序列

dfs
bfs

邻接矩阵

邻接表

十字链表

舞蹈链算法

BFS

BFS（显式用队列） DFS（隐式用栈）（即递归） 当然，对于DFS，用递归可能会造成栈溢出，所以也可以更改为显示栈。

1
2
3
4
5
6
7
8
9
10
11
12
将（起始）首节点加入队列：
q.push(head);
   标记首节点已经被访问：
isvisited[head]=true;
   以下自动反应：
while(!q.empty()){
   	int temp=q.front();
   	q.pop();
	访问temp，并标记temp已被访问过，将temp的子相关节点加入队列
	q.push(temp相关节点);
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int 当前状态)
	{
	      if(当前状态为边界状态)
	      {
	        记录或输出
	        return;
	      }
	      for(i=0;i<n;i++)		//横向遍历解答树所有子节点
	     {
	           //扩展出一个子状态。
	           修改了全局变量
	           if(子状态满足约束条件)
	            {
	              dfs(子状态)
	           }
	            恢复全局变量//回溯部分
	        }
	}

转换 为 迭代时

尾递归

非尾递归:下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值。

尾递归的精髓在于往内进行下一层解析的时候，这一层函数执行完了没卵用了，编译器一想，你都没卵用了我把你参数改改也没事啊，改了之后发现，哟呵这不是你儿子吗，那你爷俩就用这一块地儿好了。所以空间复杂度是O(1)。

尾递归优化主要看语言编译器的支持吧？python，因此鼓励用迭代的方式来实现。「似乎说是为了抛出异常时有完整的Stack trace」

好像C中并没有规定需要尾递归优化，默认并不开启，也不推荐写尾递归，如果代码需要跨平台（那就不要写了）

似乎Erlang更推荐。Erlang的虚拟机会进行优化。

是不是应该写个例子出来？

尾递归优化主要解决内存占用问题，从O(n)转为O(1)

dijkstra单源最短路径算法

Prim最小生成树算法

每个阶段只有一个状态->递推； 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心； 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索； 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到这个性质叫做最优子结构； 而不管之前这个状态是如何得到的这个性质叫做无后效性。

动态规划

数字三角形问题，

由底向上，才算是每个阶段的最优状态

最长上升子序列(LIS)

究竟怎么由状态转移方程写成代码？

水库抽样算法

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
  S has items to sample, R will contain the result
*/
ReservoirSample(S[1..n], R[1..k])
  // fill the reservoir array
  for i = 1 to k
      R[i] := S[i]

  // replace elements with gradually decreasing probability
  for i = k+1 to n
    j := random(1, i)   // important: inclusive range
    if j <= k
        R[j] := S[i]

滑动窗口问题，substring

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> pv(26, 0), sv(26, 0), ans;
        if (s.size() < p.size())
            return ans;

        for (int i = 0;i < p.size(); i++)
        {
            ++pv[p[i] - 'a'];
            ++sv[s[i] - 'a'];
        }

        if (pv == sv)
            ans.push_back(0);

        for (int i = p.size(); i < s.size(); i++)
        {
            ++ sv[s[i] - 'a'];
            -- sv[s[i - p.size()] - 'a'];
            if (sv == pv)
                ans.push_back(i - p.size() + 1);
        }
        return ans;


    }
};

leetcode 样题:

  • 1562

动态规划 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int LongCommonSubsequence(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));

        for (int i = 0;i <= word1.size(); i++)
            dp[i][0] = 0;

        for (int j = 0;j <= word2.size(); j++)
            dp[0][j] = 0;

        for (int i = 1;i <= word1.size(); i++)
            for (int j = 1;j <= word2.size(); j++)
            {
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
		return dp[word1.size()][word2.size()];
    }
};

二分

子序列?