删除链表的倒数第N个节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = head;
        ListNode cur = head;
        ListNode fast = head;

        int count = 0;
        while (fast != null) {
            fast = fast.next;
            if (count >= n) {
                pre = cur;
                cur = cur.next;
            }
            count++;
        }

        if (pre != null && cur != null) {
            if (pre == cur) {               //如果要删除的是头节点
                head = cur.next;
            } else {                        //要删除的不是头节点
                pre.next = cur.next;
            }
        }

        return head;
    }
}

展开全文 >>

交换字符串中的元素

并查集+PriorityQueue排序根相同的字符

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
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        if (s.length() == 0) return s;
        int n = s.length();
        father = new int[n];

        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        for (List<Integer> list : pairs) {
            union(list.get(0), list.get(1));
        }

        char[] arr = s.toCharArray();

        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int root = find(i);
            PriorityQueue<Character> pq = map.getOrDefault(root, new PriorityQueue<Character>());
            pq.offer(arr[i]);
            map.put(root, pq);
        }

        StringBuilder bd = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int root = find(i);
            PriorityQueue<Character> pq = map.get(root);
            bd.append(pq.poll());
        }

        return bd.toString();
    }


    int[] father = null;

    public int find(int x) {
        int a = x;
        while (x != father[x]) x = father[x];
        while (a != father[a]) {
            int z = a;
            a = father[a];
            father[z] = x;
        }
        return x;
    }

    public void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) father[fa] = fb;
    }

    public boolean connected(int a, int b) {
        return find(a) == find(b);
    }
}
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
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        if (pairs.size() == 0) {
            return s;
        }

        // 第 1 步：将任意交换的结点对输入并查集
        int len = s.length();
        UnionFind unionFind = new UnionFind(len);
        for (List<Integer> pair : pairs) {
            int index1 = pair.get(0);
            int index2 = pair.get(1);
            unionFind.union(index1, index2);
        }

        // 第 2 步：构建映射关系
        char[] charArray = s.toCharArray();
        // key：连通分量的代表元，value：同一个连通分量的字符集合（保存在一个优先队列中）
        Map<Integer, PriorityQueue<Character>> hashMap = new HashMap<>(len);
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            if (hashMap.containsKey(root)) {
                hashMap.get(root).offer(charArray[i]);
            } else {
                // PriorityQueue<Character> minHeap = new PriorityQueue<>();
                // minHeap.offer(charArray[i]);
                // hashMap.put(root, minHeap);
                // 上面三行代码等价于下面一行代码，JDK 1.8 以及以后支持下面的写法
                hashMap.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);
            }
        }

        // 第 3 步：重组字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            stringBuilder.append(hashMap.get(root).poll());
        }
        return stringBuilder.toString();
    }

    private class UnionFind {

        private int[] parent;
        /**
         * 以 i 为根结点的子树的高度（引入了路径压缩以后该定义并不准确）
         */
        private int[] rank;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            if (rank[rootX] == rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度仅加了 1
                rank[rootY]++;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度不变
            } else {
                // 同理，此时以 rootX 为根结点的树的高度不变
                parent[rootY] = rootX;
            }
        }

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

作者：LeetCode
链接：https://leetcode-cn.com/problems/smallest-string-with-swaps/solution/1202-jiao-huan-zi-fu-chuan-zhong-de-yuan-wgab/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

第k个排列

要想解决本题，首先需要了解一个简单的结论：

对于 $n$ 个不同的元素（例如数 $1, 2, \cdots, n$），它们可以组成的排列总数目为 $n!$。

对于给定的 $n$ 和 $k$，我们不妨从左往右确定第 $k$ 个排列中的每一个位置上的元素到底是什么。

我们首先确定排列中的首个元素 $a_1$。根据上述的结论，我们可以知道：

  • 以 $1$ 为 $a_1$的排列一共有 $(n-1)!$ 个；
  • 以 $2$ 为 $a_1$的排列一共有 $(n-1)!$个；
  • $\cdots⋯$
  • 以 $n$ 为 $a_1$的排列一共有 $(n-1)!$ 个。

由于我们需要求出从小到大的第 $k$ 个排列，因此：

  • 如果 $k \leq (n-1)!$，我们就可以确定排列的首个元素为 $1$；
  • 如果$(n-1)! < k \leq 2 \cdot (n-1)!$ ，我们就可以确定排列的首个元素为 2；
  • $\cdots⋯$
  • 如果 $(n-1) \cdot (n-1)! < k \leq n \cdot (n-1)!$，我们就可以确定排列的首个元素为 $n$。
    因此，第 $k$ 个排列的首个元素就是：

$a_1 = \lfloor \frac{k-1}{(n-1)!} \rfloor + 1$

其中 $\lfloor x \rfloor$ 表示将 $x$ 向下取整。

当我们确定了 $a_1$后，如何使用相似的思路，确定下一个元素 $a_2$呢？实际上，我们考虑以 $a_1$为首个元素的所有排列：

  • 以 $[1,n] \backslash a_1$最小的元素为 $a_2$的排列一共有 $(n-2)!$个；
  • 以 $[1,n] \backslash a_1$次小的元素为 $a_2$的排列一共有 $(n-2)!$个；
  • $\cdots⋯$
  • 以 $[1,n] \backslash a_1$最大的元素为 $a_2$的排列一共有 $(n-2)!$个；

其中 $[1,n] \backslash a_1[1,n]$表示包含 $1, 2, \cdots n$ 中除去 $a_1$ 以外元素的集合。

这些排列从编号 $(a_1-1) \cdot (n-1)!$开始，到 $a_1 \cdot (n-1)!$结束，总计 $(n-1)!$个，因此第 $k$ 个排列实际上就对应着这其中的第$k’ = (k-1) \bmod (n-1)! + 1$个排列。这样一来，我们就把原问题转化成了一个完全相同但规模减少 1 的子问题：

求 $[1, n] \backslash a_1$这 $n-1$ 个元素组成的排列中，第 $k’$小的排列。
avatar

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
import java.util.Arrays;

public class Solution {

    /**
     * 记录数字是否使用过
     */
    private boolean[] used;

    /**
     * 阶乘数组
     */
    private int[] factorial;

    private int n;
    private int k;

    public String getPermutation(int n, int k) {
        this.n = n;
        this.k = k;
        calculateFactorial(n);

        // 查找全排列需要的布尔数组
        used = new boolean[n + 1];
        Arrays.fill(used, false);

        StringBuilder path = new StringBuilder();
        dfs(0, path);
        return path.toString();
    }


    /**
     * @param index 在这一步之前已经选择了几个数字，其值恰好等于这一步需要确定的下标位置
     * @param path
     */
    private void dfs(int index, StringBuilder path) {
        if (index == n) {
            return;
        }

        // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        int cnt = factorial[n - 1 - index];
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (cnt < k) {
                k -= cnt;
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(index + 1, path);
            // 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
            // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
            return;
        }
    }

    /**
     * 计算阶乘数组
     *
     * @param n
     */
    private void calculateFactorial(int n) {
        factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }
}

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/di-kge-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

从前序遍历与中序遍历构造二叉树

105. 从前序与中序遍历序列构造二叉树

难度: 中等

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

根据前序遍历找根，（使用哈希表记录中序遍历每个元素的index）根据根找左子树的元素和右子树的元素

难度在于处理边界条件

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        TreeNode node = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);

        return node;
    }

    public TreeNode buildTree(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd, Map<Integer, Integer> val2Index) {

        if (pStart > pEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[pStart]);
        if (pStart == pEnd) {
            return root;
        }

        int rootIndex = val2Index.get(root.val);
        int leftNum = rootIndex - iStart;
        int rightNum = iEnd - rootIndex;

        TreeNode left = buildTree(preorder, pStart + 1, pStart + leftNum, inorder, iStart, rootIndex - 1, val2Index);
        TreeNode right = buildTree(preorder, pEnd - rightNum + 1, pEnd, inorder, rootIndex + 1, iEnd, val2Index);

        root.left = left;
        root.right = right;
        return root;
    }
}

展开全文 >>

二叉树展开为链表 

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
给定一个二叉树，原地将它展开为一个单链表。

 

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
通过次数103,182提交次数144,008

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        deep(root);
    }

    TreeNode pre = null;

    public void deep(TreeNode root) {
        if (root == null) return;
        deep(root.right);
        deep(root.left);

        //root
        root.right = pre;
        pre = root;
        root.left = null;
    }
}

展开全文 >>

按摩师

面试题 17.16. 按摩师

难度简单

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

1
2
3
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

1
2
3
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

1
2
3
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

动态规划

对于每个客人有两种选择：
选择和不选择

没选择时：上一次可以选了，也可以没选，求两种情况的最大值
选择时：上一次没选+本次选的，上上次选了，求两种情况的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int massage(int[] nums) {

        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);

        int[][] dp = new int[nums.length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];

        dp[1][0] = nums[0];
        dp[1][1] = nums[1];

        for (int i = 2; i < nums.length; i++) {

            dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);                //上一次选了，上一次没选
            dp[i][1] = Math.max(dp[i - 1][0] + nums[i], dp[i - 2][1]);      //上一次没选，上上次选了

        }

        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][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

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int dp0 = 0, dp1 = nums[0];

        for (int i = 1; i < n; ++i){
            int tdp0 = Math.max(dp0, dp1); // 计算 dp[i][0]
            int tdp1 = dp0 + nums[i]; // 计算 dp[i][1]

            dp0 = tdp0; // 用 dp[i][0] 更新 dp_0
            dp1 = tdp1; // 用 dp[i][1] 更新 dp_1
        }
        return Math.max(dp0, dp1);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/the-masseuse-lcci/solution/an-mo-shi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

新知识列表

新知识列表

树状数组（与前缀和、逆序对有关）

相关知识

树状数组学习笔记

树状数组(推荐)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lowbit(int x) {
    return x & (-x);
}

public void update(int i, int delta) {
    // len 为数组长度
    while (i <= len) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

public int query(int i) {
    // 从右到左查询
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

应用

并查集（与深度优先搜索，集合合并有关）

相关知识

通俗易懂地讲解《并查集》

并查集

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
public void init(int n){
    int[]father=new int[n];
    // 初始化，每个人的父节点都是自己
    for(int i = 1; i <= n; i++)
        father[i] = i;
}


public void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA != faB) father[faA] = faB;
}

public int find(int x) {
    int a = x;
    // 寻找当前节点的根节点
    // x 就是要找的根节点
    while(x != father[x])
        x = father[x];
    // 找到根节点后，把当前集合点的根节点都改为 x  
    while(a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
1
2
3
4
// 查找根节点这句的理解
while(x != father[x])
        x = father[x];
//因为我们在初始化的时候，每个节点的根节点初始化为它自己，即我爸爸是我自己，这就是根节点和其他节点的不同之处！！！当 x == parent[x] 的时候，不就说明x是根节点了吗.

应用

并查集应用列表

字典树(前缀树)（与字符串前后缀和字符串匹配有关）

相关知识

字典树

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
public class Trie {
    private boolean isEnd = false;
    private Trie next[] = new Trie[26];

    public Trie() {
    }

    public void insert(String word) {               // 插入单词
        Trie root = this;
        char w[] = word.toCharArray();
        for (int i = 0; i < w.length; ++i) {
            int index = w[i] - 'a';
            if (root.next[index] == null)root.next[index] = new Trie();
            root = root.next[index];
        }
        root.isEnd = true;
    }

    public boolean search(String word) {            // 查找单词
        Trie root = this;
        char w[] = word.toCharArray();
        for (int i = 0; i < w.length; ++i) {
            int index = w[i] - 'a';
            if (root.next[index] == null)return false;
            root = root.next[index];
        }
        return root.isEnd;
    }

    public boolean startsWith(String prefix){       //查找前缀
        Trie root=this;
        char p[]=prefix.toCharArray();
        for(int i=0; i < p.length; ++i){
            int index = p[i]-'a';
            if(root.next[index] == null)return false;
            root = root.next[index];
        }
        return true;
    }
}

Trie (发音为 “try”) 或前缀树是一种树数据结构，用于检索字符串数据集中的键。这一高效的数据结构有多种应用：

  1. 自动补全
  2. 拼写检查
  3. IP 路由 (最长前缀匹配)
  4. T9 (九宫格) 打字预测
  5. 单词游戏

还有其他的数据结构，如平衡树和哈希表，使我们能够在字符串数据集中搜索单词。为什么我们还需要 Trie 树呢？尽管哈希表可以在 O(1) 时间内寻找键值，却无法高效的完成以下操作：

  • 找到具有同一前缀的全部键值。
  • 按词典序枚举字符串的数据集。

应用

摩尔投票

核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

作者：胡新辰来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

应用

滑动窗口

先向右扩展窗口，当窗口的值满足条件时，收缩左边界，并记录所要求的最优质，直至窗口内的值刚好满足条件。 然后继续向右移动右边界，收缩左边界，$…$

应用

5.数组中数字出现的次数

6.拼车问题

思路：不管上车人是谁，也不管下车人是谁，上车的时候加人，下车的时候减人。然后遍历行程序列，对路途中的在行程中的人数计数，如果大于capacity就不能顺利接收

应用

拓扑排序

思路：对于每个节点维护一个入度数组，如果入度数组的值为0，将其加入队列。从队列取出元素，将依赖该节点的所有节点的入度减一，如果某个节点的入度为0，那么将该节点加入到队列中去。
在这个过程中记录每次出队的元素即为拓扑排序的顺序，如果最后排序完的数量小于原始节点的数量，那么无法完成拓扑排序

应用

判断链表是否存在环路

思路：一个快指针 $f$ 每次走两步，一个慢指针 $s$ 每次走一步，如果快指针和慢指针相遇了 $（f==s）$ ，那么说明链表存在环路

如何寻找进入环的第一个节点？

思路：快指针 $f$ 每次走两步，慢指针 $s$ 每次走一步，快慢指针相遇的时候 $(f==s)$ ，一个每次走一步的慢指针 $ps$ 从头节点出发，当慢指针 $s$ 与 $ps$ 相遇的时候，就是第一个进入环路的节点

两个链表的第一个公共节点

思路：两个节点同时走，即指针 $P_A$ 走 $A$ 链表，指针 $P_B$ 走 $B$ 链表，$P_A$ 走到末尾时，切换到B链表上，$P_B$ 走到末尾时切换到 $A$ 链表上，这时如果链表有交点，两个指针将会在交点相遇。

你变成我，走过我走过的路。

我变成你，走过你走过的路。

然后我们便相遇了..

或许这就是程序员的浪漫吧

应用

链表的转置（reverse）

汉诺塔

八皇后

对角线的计算方式是：

主对角线的计算方式是：$row-cloumn$ 在主对角线上的点的坐标的$row-column$的差值相同

副对角线的计算方式是：$row+column$在副对角线上的点的坐标的$row+column$的差值相同

应用

求模运算的性质

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

$(a + b) % p = (a % p + b % p) % p （1）$

(重要，求模时每一步求模，最后对结果求模所得的结果和最后一次求模的计算结果相同)

$(a - b) % p = (a % p - b % p) % p （2）$

$(a b) % p = (a % p b % p) % p （3）$

$a ^ b % p = ((a % p)^b) % p （4）$

结合律：

$((a+b) % p + c) % p = (a + (b+c) % p) % p （5）$

$((ab) % p c)% p = (a (bc) % p) % p （6）$

交换律：

$(a + b) % p = (b+a) % p （7）$

$(a b) % p = (b a) % p （8）$

分配律：

$((a +b)% p c) % p = ((a c) % p + (b * c) % p) % p （9）$

重要定理

若$a≡b (% p)$，则对于任意的$c$，都有$(a + c) ≡ (b + c) (%p)；（10）$

若$a≡b (% p)$，则对于任意的$c$，都有$(a c) ≡ (b c) (%p)；（11）$

若$a≡b (% p)$，$c≡d (% p)$，则

$(a + c) ≡ (b + d) (%p)$，

$(a - c) ≡ (b - d) (%p)$，

$(a c) ≡ (b d) (%p)$，

$(a / c) ≡ (b / d) (%p)； （12）$

0-1背包问题的递推关系

0-1背包问题的递推关系

定义子问题$P(i,W)$为：在前$i$个物品中挑选总重量不超过$w$的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作$dp(i,W)$，其中$1<=i<=n$ , $1<=w<=c$

考虑第$i$件物品，无外乎两种可能：选，或者不选。

  • 不选的话，背包的容量不变，改变为问题$P(i-1,W)$
  • 选的话，背包的容量变小，改变为问题$P(i-1,W-w_i)$

最优方案就是比较这两种方案，哪个会更好些：

$dp(i,W)=max{dp(i-1,W),dp(i-1,W-w_i)+v_i}$

得到

$dp(i, W)=\left{\begin{array}{ll}
0 & \text { if } i=0 \
0 & \text { if } W=0 \
dp(i-1, W) & \text { if } w_{i}>W \
\max \left{dp(i-1, W), v_{i}+dp\left(i-1, W-w_{i}\right)\right} & \text { otherwise }
\end{array}\right.$

应用

二分查找

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch(int[] arr, int start, int end, int target) {
    int result = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;    //防止溢位
        if (arr[mid] > target)
            end = mid - 1;
        else if (arr[mid] < target)
            start = mid + 1;
        else {
            result = mid;
            break;
        }
    }
    return result;
}

变种以及应用

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

这里就需要差分数组的技巧，类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：

定义

差分数组
差分数组

对于已知有n个元素的数列d，建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。

1
2
3
4
5
6
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}
1
2
3
构造差分数组：
nums:   8   2   6   3   1
diff:   8   -6  4   -3  -2

通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：

1
2
3
4
5
6
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3

1
2
3
nums:   8   5   9   6   1
diff:   8   -3  4   -3  -5
            i        j

展开全文 >>

执行交换操作后的最小汉明距离 

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
给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

 

示例 1：

输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
示例 2：

输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
示例 3：

输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0
 

提示：

n == source.length == target.length
1 <= n <= 105
1 <= source[i], target[i] <= 105
0 <= allowedSwaps.length <= 105
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
通过次数1,058提交次数3,345

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int ans = 0, n = source.length;
        UnionFind unionFind = new UnionFind(n);
        for (int[] swap : allowedSwaps) {
            unionFind.union(swap[0], swap[1]);
        }

        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(target[i], new LinkedList<>());
            map.get(target[i]).add(i);
        }

        for (int i = 0; i < n; i++) {
            if (!map.containsKey(source[i])) {
                ans++;
                continue;
            }

            List<Integer> list = map.get(source[i]);
            Iterator<Integer> iterator = list.iterator();
            boolean flag = false;
            while (iterator.hasNext()) {
                Integer index = iterator.next();
                if (unionFind.connected(i, index)) {
                    iterator.remove();
                    flag = true;
                    break;
                }
            }
            if (!flag)
                ans++;
        }
        return ans;
    }

    private static class UnionFind {
        private int[] parent;
        private int[] rank;
        private int count;

        public UnionFind(int n) {
            count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            rank = new int[n];
        }

        // 路径压缩
        public int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            return parent[x] = find(parent[x]);
        }

        // 按秩合并
        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);

            if (fx == fy) {
                return;
            }

            if (rank[fx] > rank[fy]) {
                parent[fy] = fx;
            } else {
                parent[fx] = fy;
            }

            if (rank[fx] == rank[fy]) {
                rank[fy]++;
            }
            count--;
        }

        public int count() {
            return count;
        }

        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }
}

作者：mufanlee
链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/solution/5650-zhi-xing-jiao-huan-cao-zuo-hou-de-z-rk3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

解码异或后的数组 

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
未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

 

示例 1：

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
示例 2：

输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]
 

提示：

2 <= n <= 104
encoded.length == n - 1
0 <= encoded[i] <= 105
0 <= first <= 105
通过次数2,857提交次数3,383

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-xored-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

如果将一个数a和另一个数b做xor 得到结果c， 再 c xor b 就可以得到a

加法的逆运算是减法,异或的逆运算还是异或

$u=(x+y)⊕z$

$(u⊕z)-y=x$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] decode(int[] encoded, int first) {
        if (encoded.length == 0) return new int[]{};
        int[] res = new int[encoded.length + 1];

        res[0] = first;
        for (int i = 1; i <= encoded.length; i++) {
            res[i] = res[i - 1] ^ encoded[i - 1];
        }
        return res;
    }
}

展开全文 >>

交换链表中的节点 

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
给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

 

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[1,4,3,2,5]

示例 2：
输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]

示例 3：
输入：head = [1], k = 1
输出：[1]

示例 4：
输入：head = [1,2], k = 1
输出：[2,1]

示例 5：
输入：head = [1,2,3], k = 2
输出：[1,2,3]
 

提示：

链表中节点的数目是 n
1 <= k <= n <= 105
0 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        if(head==null)return head;
        ListNode h1 = head;

        ListNode fast = head;
        ListNode slow = head;

        ListNode fk = null;
        ListNode sk = null;
        ListNode slowPre = null;
        int count = 0;
        boolean flag = false;
        while (fast != null) {
            count++;
            if (count >= k) {
                slowPre = slow;
                slow = slow.next;
                if (flag == false) {
                    fk = fast;
                    flag = true;
                }
            }
            fast = fast.next;

        }
        sk = slowPre;

        if (fk.val != sk.val) {
            fk.val = fk.val ^ sk.val;
            sk.val = fk.val ^ sk.val;
            fk.val = fk.val ^ sk.val;
        }
        return h1;
    }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走