分割回文串(简单题) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public List<List<String>> partition(String s) {
        if (s.length() == 0) return new ArrayList<>();
        List<List<String>> resList = new ArrayList<>();

        deep(s, s.toCharArray(), 0, new ArrayList<>(), resList);
        return resList;
    }

    public void deep(String s, char[] arr, int cur, List<String> tempList, List<List<String>> resList) {
        if (cur >= arr.length) {
            resList.add(new ArrayList<>(tempList));
            return;
        }

        for (int i = cur; i < arr.length; i++) {
            if (isReword(arr, cur, i)) {
                tempList.add(s.substring(cur, i + 1));
                deep(s, arr, i + 1, tempList, resList);
                tempList.remove(tempList.size() - 1);
            }
        }


    }

    public boolean isReword(char[] arr, int begin, int end) {
        if (begin == end) return true;
        int l = begin, r = end;
        while (l <= r) {
            if (arr[l] == arr[r]) {
                l++;
                r--;
            } else {
                return false;
            }
        }
        return true;
    }
}

展开全文 >>

可被5整除的二进制前缀 

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
给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。

返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

 

示例 1：

输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
示例 2：

输入：[1,1,1]
输出：[false,false,false]
示例 3：

输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]
示例 4：

输入：[1,1,1,0,1]
输出：[false,false,false,false,false]
 

提示：

1 <= A.length <= 30000
A[i] 为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-prefix-divisible-by-5
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        if (A == null || A.length == 0) return new ArrayList<>();
        List<Boolean> resList = new ArrayList<>();

        int sum = 0;
        resList.add(A[0] % 5 == 0);
        sum = A[0];
        for (int i = 1; i < A.length; i++) {
            sum = (sum << 1) + A[i];          // 每增加一位时，前面的和左移一位加上现在的值
            boolean res = sum % 5 == 0;       // 如果满足条件，就加入列表
            resList.add(res);                 
            sum=sum%10;                       // 因为是否模5只和最后一位有关，因此如果大于10，将sum变成原来的数的最后一位，防止溢出
        }
        return resList;
    }
}

展开全文 >>

连接连续二进制数字 

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
给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 109 + 7 取余的结果。

 

示例 1：

输入：n = 1
输出：1
解释：二进制的 "1" 对应着十进制的 1 。
示例 2：

输入：n = 3
输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。
示例 3：

输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 109 + 7 取余后，结果为 505379714 。
 

提示：

1 <= n <= 105

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

位运算

数字每次被左移了i的二进位数字的长度，因此数字每次左移i的二进制长度的位数再加上i即可求出结果，为了防止溢出，需要对结果求模

求模的性质

$(a + b) % p = (a % p + b % p) % p$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
      public int concatenatedBinary(int n) {
        long res = 0;
        int mod = 1000000007;
        int shift = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                shift++;
            }
            res = ((res << shift) % mod + i) % mod;
        }
        return (int)res;
    }
}

展开全文 >>

余数运算

运算规则

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

$(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）

展开全文 >>

一和零

474. 一和零

难度中等473收藏分享切换为英文接收动态反馈

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

1
2
3
4
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

1
2
3
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0' 和 '1' 组成
  • 1 <= m, n <= 100

动态规划

多维0-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
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        Node [] counter = new Node[len];

        for(int i=0;i<len;i++){
            String s = strs[i];
            int zeroCnt = 0, oneCnt = 0;
            for(int j=0;j<s.length();j++){
                if(s.charAt(j)=='0'){
                    zeroCnt++;
                }else{
                    oneCnt++;
                }
            }
            counter[i] = new Node(zeroCnt,oneCnt);
        }
        
        int [][]dp = new int[m+1][n+1];
        for(int k=0;k<len;k++){
            // 注意这里需要从后往前遍历，否则就有重复
            for(int i=m;i>=counter[k].zeroCnt;i--){
                // 注意这里需要从后往前遍历，否则就有重复
                for(int j=n;j>=counter[k].oneCnt;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-counter[k].zeroCnt][j-counter[k].oneCnt]+1);
                }
            }
        }
        return dp[m][n];
    }
    class Node {
        int zeroCnt = 0;
        int oneCnt = 0;
        public Node(int zeroCnt,int oneCnt){
            this.zeroCnt = zeroCnt;
            this.oneCnt = oneCnt;
        }
    }
}

0-1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int [][]dp=new int[m+1][n+1];
        for(String s:strs){
            int[]count=countZeroAndOne(s);
            for(int zero=m;zero>=count[0];zero--){
                for(int one=n;one>=count[1];one--){
                    // 前面是不选当前字符串，后面是选当前字符串
                    dp[zero][one]=Math.max(dp[zero][one],dp[zero-count[0]][one-count[1]]+1);
                }
            }
        }
        return dp[m][n];
    }

    public int[] countZeroAndOne(String str) {
        int []count=new int[2];
        for (int i = 0; i < str.length(); i++) {
            count[str.charAt(i)-'0']++;
        }
        return count;
    }
}

展开全文 >>

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.$

算法：

avatar

参考文献

0-1背包问题的动态规划算法 - Bat特白的文章 - 知乎

展开全文 >>

区域和检索数组可修改 

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
给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1], ..., nums[right]）

示例：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5]) = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 9

提示：
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
最多调用 3 * 104 次 update 和 sumRange 方法

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

树状数组

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
class NumArray {
    FenwickTree fenwickTree;

    int[] nums = null;

    public NumArray(int[] nums) {
        fenwickTree = new FenwickTree(nums.length);
        int count = 1;
        this.nums = nums;
        for (int num : nums) {
            fenwickTree.update(count, num);
            count++;
        }
    }

    public void update(int index, int val) {

        fenwickTree.update(index + 1, -nums[index]);
        nums[index] = val;
        fenwickTree.update(index + 1, val);
    }

    public int sumRange(int left, int right) {
        return fenwickTree.query(right + 1) - fenwickTree.query(left);
    }

    private class FenwickTree {

        int len = 0;
        int[] tree;

        public FenwickTree(int n) {
            this.len = n;
            tree = new int[n + 1];
        }


        public void update(int i, int num) {
            while (i <= len) {
                tree[i] += num;
                i += lowbit(i);
            }
        }

        public int query(int i) {
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= lowbit(i);
            }
            return sum;
        }


        public int lowbit(int x) {

            return x & (-x);
        }

    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */

线段树（待填坑）

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
// 构建线段树
int[] tree;
int n;
public NumArray(int[] nums) {
    if (nums.length > 0) {
        n = nums.length;
        tree = new int[n * 2];
        buildTree(nums);
    }
}
private void buildTree(int[] nums) {
    for (int i = n, j = 0;  i < 2 * n; i++,  j++)
        tree[i] = nums[j];
    for (int i = n - 1; i > 0; --i)
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
// 更新线段树
void update(int pos, int val) {
    pos += n;
    tree[pos] = val;
    while (pos > 0) {
        int left = pos;
        int right = pos;
        if (pos % 2 == 0) {
            right = pos + 1;
        } else {
            left = pos - 1;
        }
        // parent is updated after child is updated
        tree[pos / 2] = tree[left] + tree[right];
        pos /= 2;
    }
}

// 线段树求和
public int sumRange(int l, int r) {
    // get leaf with value 'l'
    l += n;
    // get leaf with value 'r'
    r += n;
    int sum = 0;
    while (l <= r) {
        if ((l % 2) == 1) {
           sum += tree[l];
           l++;
        }
        if ((r % 2) == 0) {
           sum += tree[r];
           r--;
        }
        l /= 2;
        r /= 2;
    }
    return sum;
}


作者：LeetCode
链接：https://leetcode-cn.com/problems/range-sum-query-mutable/solution/qu-yu-he-jian-suo-shu-zu-ke-xiu-gai-by-leetcode/
来源：力扣（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
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：
输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：
输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：
输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

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

  • 将每个格子抽象成图中的一个点；

  • 将每两个相邻的格子之间连接一条边，长度为这两个格子本身权值的差的绝对值；

  • 需要找到一条从左上角到右下角的「最短路径」，其中路径的长度定义为路径上所有边的权值的最大值。

  • 「并查集」：我们可以将所有边按照长度进行排序并依次添加进并查集，直到左上角和右下角连通为止。

并查集

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
class Solution {

    public int minimumEffortPath(int[][] heights) {

        int row = heights.length;
        int col = heights[0].length;
        father = new int[row * col];

        for (int i = 0; i < row * col; i++) {
            father[i] = i;
        }

        // id,id,dis
        int[][] dis = new int[row * col * 2][3];
        int count = 0;

        // 每个点只需要计算上边和左边与其相邻的边的长度，
        // 即可计算所有的相邻节点的边的长度
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int id = i * col + j;
                if (i > 0) {
                    // 计算与其上边相邻的
                    // 上边相邻的id是id-col
                    dis[count][0] = id - col;
                    dis[count][1] = id;
                    dis[count++][2] = Math.abs(heights[i][j] - heights[i - 1][j]);
                }
                if (j > 0) {
                    //计算与其左边相邻的
                    // 左边相邻的id是id-1
                    dis[count][0] = id - 1;
                    dis[count][1] = id;
                    dis[count++][2] = Math.abs(heights[i][j] - heights[i][j - 1]);
                }
            }
        }

        Arrays.sort(dis, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        int res = 0;
        for (int i = 0; i < row * col * 2; i++) {
            union(dis[i][0], dis[i][1]);
            int fa = find(0);                     // 开始节点
            int fb = find(row * col - 1);         // 结束节点
            if (fa == fb) {                       // 开始节点和结束节点连通
                return dis[i][2];                 // 那么路径上的最大值就是当前的距离
            }
        }

        return 0;
    }

    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;
    }
}

参考文献

1
2
3
4
作者：zerotrac2
链接：https://leetcode-cn.com/problems/path-with-minimum-effort/solution/zui-xiao-ti-li-xiao-hao-lu-jing-by-zerotrac2/
来源：力扣（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
33
34
35
36
37
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 
示例 1：
输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

示例 2：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。

示例 4：
输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

提示：

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

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

并查集

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 makeConnected(int n, int[][] connections) {
        father = new int[n];

        int len = connections.length;
        if (n - 1 > len) return -1;

        for (int i = 0; i < n; i++) {
            father[i] = i;
        }

        int connected = 0;
        for (int i = 0; i < connections.length; i++) {
            int fa = find(connections[i][0]);
            int fb = find(connections[i][1]);
            if (fa != fb) {
                union(connections[i][0], connections[i][1]);
                // 连线的数量加1
                connected++;
            }
        }
        // 主机的数量等于连线的数量加1
        return n - connected - 1;
    }

    int[] father = null;

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

    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;
    }
}

展开全文 >>

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

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
给你两个整数数组 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

来源：力扣（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
class Solution{
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        father = new int[source.length + 1];
        Map<Integer, List<Integer>> tMap = new HashMap<>();
        for (int i = 0; i < source.length; i++) {
            father[i] = i;

            List<Integer> list = tMap.getOrDefault(target[i], new ArrayList<>());
            list.add(i);
            tMap.put(target[i], list);
        }

        for (int i = 0; i < allowedSwaps.length; i++) {
            union(allowedSwaps[i][0], allowedSwaps[i][1]);
        }

        int ans = 0;
        for (int i = 0; i < source.length; i++) {
            if (tMap.containsKey(source[i])) {
                List<Integer> indexList = tMap.get(source[i]);
                int fa = find(i);
                boolean flag = false;
                for (Integer idx : indexList) {
                    int fb = find(idx);
                    if (fa == fb) {
                        indexList.remove(idx);
                        tMap.put(source[i], indexList);
                        flag = true;
                        break;
                    }
                }
                if (!flag) ans++;
            } else {
                ans++;
            }
        }

        return ans;
    }

    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;
    }
}

展开全文 >>

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>希望有一天被领走