Posted Updated LeetCode / Hard / 复习3 minutes read (About 449 words)

2318. Number of Distinct Roll Sequences

Question

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

  1. The greatest common divisor of any adjacent values in the sequence is equal to 1.
  2. There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the i<sup>th</sup> roll is equal to the value of the j<sup>th</sup> roll, then abs(i - j) > 2.

Return the* total number** of distinct sequences possible*. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Two sequences are considered distinct if at least one element is different.

Solution

DFS+记忆化搜索剪枝。
辅助方法getValidNext计算前两个位置为last1和last2时的所有的下一个有效值，将返回值储存在next[][]数组中。

DFS搜索

DFS搜索，传入剩余骰子数量n，前两个骰子的值x和y。
从next[x][y]中得到所有有效值。并进行递归。
将返回结果加和并返回。
当n等于0时，只有一个组合，因此返回1。

记忆化搜索

在搜索时会重复计算很多相同的x，y与n的组合，因此可以采用记忆化搜索进行剪枝。
用memo[][][]数组记录x，y与n的状态。如果此前已经计算过其结果，则直接返回memo[x][y][n]。

Code

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 {
    List<Integer>[][] next;
    int[][][] memo;
    public int distinctSequences(int n) {
        next = new ArrayList[7][7];
        for(int i = 0; i <= 6; i++){
            for(int j = 0; j <= 6; j++){
                next[i][j] = getValidNext(i, j);
            }
        }
        memo = new int[7][7][10001];
        return count(n, 0, 0);
    }
    
    private int count(int n, int x, int y){
        if(n == 0) return 1;
        if(memo[x][y][n] != 0) return memo[x][y][n];
        List<Integer> validNext = next[x][y];
        int sum = 0;
        for(int z : validNext){
            sum += count(n-1, y, z);
            sum %= 1000000007;
        }
        memo[x][y][n] = sum;
        return sum;
    }
    
    private List<Integer> getValidNext(int last1, int last2){
        List<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= 6; i++){
            if(last1 == 0 && last2 == 0) arr.add(i);
            else if(i == last1 || i == last2) continue;
            else if((last2 & 1) == 0 && (i & 1) == 0) continue;
            else if((last2 == 3 || last2 == 6) && (i == 3 || i == 6)) continue;
            else arr.add(i);
        }
        return arr;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 400 words)

2317. Maximum XOR After Operations

Question

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

Solution

异或运算相当于不进位的加和。
和运算相当于掩码操作。
或运算相当于保留该位上的1。

由于我们要对所有数字进行异或运算，因此只要能改变某一位对应的数字，我们就可以确保这一位在进行异或运算时结果可以为1。（当不改变时改为的异或运算结果为0，则我们只需要改变改为即可得到1）

将所有我们可以操作的位置变为1，就可以得到最大值。

因此，我们只需要确定哪些位是我们可以操作的即可：

  • nums[i]与任意正整数进行异或运算可以得到任意整数。在这个条件下我们可以得到任意的32位整数。
  • 然而和运算相当于掩码操作，如果nums[i]对应二进制的某一位上位0，则我们无法通过和运算将这一位改变为1。

只要该位出现过1，则我们可以控制这个位。因此我们可以通过或运算所有数字，保留所有可控制的位。

Code

1
2
3
4
5
6
7
8
9
class Solution {
    public int maximumXOR(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum |= num;
        }
        return sum;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 419 words)

2316. Count Unreachable Pairs of Nodes

Question

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a<sub>i</sub>, b<sub>i</sub>] denotes that there exists an undirected edge connecting nodes a<sub>i</sub> and b<sub>i</sub>.

Return the number of pairs of different nodes that are unreachable from each other.

Solution

并查集，将所有元素union，然后计算每个元素所在集之外的元素和相加即可。
注意由于是无向图，因此计算加和时每两个点之间都计算了两次，因此需要将结果除以2。

路径压缩

在进行find()查找时，将经过的每一个节点设置为根节点。
这样做可以有效的降低树高，减少操作次数。
采用递归的形式实现。

按秩合并

用size[]数组记录当前位置的节点数量。
在合并两个数字时，将秩较小的数字指向秩较大的数字。
并更新根节点的size[]值。

Code

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 long countPairs(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        long res = 0;
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        
        for(int i = 0; i < n; i++){
            res +=  ( n - uf.getSize(i) );
        }
        return res/2;   //无向图，因此每两个节点计算了两次
    }
    
    class UnionFind {
        int[] parent;
        int[] size;

        public UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        } 
           
        private int find(int id){
            return parent[id] == id ? id : find(parent[id]);   //路径压缩，将路径上的所有节点归结到根节点上
        }
           
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(size[p1] > size[p2]){    //按秩进行压缩
                parent[p2] = p1;
                size[p1] += size[p2];
            }
            else{
                parent[p1] = p2;
                size[p2] += size[p1];
            }
            return true;
        }

        public int getSize(int num){
            return size[find(num)];
        }
    }
}****
Posted Updated LeetCode / Easya minute read (About 119 words)

2315. Count Asterisks

Question

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.

Return *the number of '*' in s, excluding the '*' between each pair of *'|'.

Note that each '|' will belong to exactly one pair.

Solution

统计“|”字符出现的数量，如果数量为偶数时，则计算出现的“*”符号。

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int countAsterisks(String s) {
        int num = 0, count = 0;
        for(char c : s.toCharArray()){
            if(c == '|') num++;
            else if((num & 1) == 0 && c == '*') count++;
        }
        return count;
    }
}
665. Non-decreasing Array
Posted Updated LeetCode / Medium2 minutes read (About 356 words)

665. Non-decreasing Array

Question

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Solution 1

记录两个最大值last1和last2，初始化为整数最小值。真值flag初始化为true用来记录是否已经有非单调递增的值出现。
遍历数组，如果当前数字num大于等于last2，则符合单调递增，更新last1和last2。

如果num小于last2，则不符合单调递增，此时将flag置为false。

  • 如果num大于等于last1，则跳过现有的last2，将num保存在last2上。
  • 如果num小于，则保留当前的last2

如果flag已经为false，则非单调递增的数字超过1个，返回false。
遍历完毕则返回true。

Code

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 boolean checkPossibility(int[] nums) {
        boolean flag = true;
        int last1 = Integer.MIN_VALUE, last2 = Integer.MIN_VALUE;
        
        for(int num : nums){
            if(num >= last2){
                last1 = last2;
                last2 = num;
            }
            else if(flag){
                flag = false;
                if(num >= last1) last2 = num;
                else continue;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Solution 2

原理和Solution 1相同，只不过采用单调栈的形式保存单调递增数字。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean checkPossibility(int[] nums) {
        Stack<Integer> s = new Stack<>();
        boolean flag = true;
        
        for(int num : nums){
            if(s.isEmpty() || num >= s.peek()) s.push(num);
            else if(flag){
                flag = false;
                int temp = s.pop();
                if(s.isEmpty() || num >= s.peek()) s.push(num);
                else s.push(temp);
            }
            else{
                return false;
            }
        }
        return true;
    }
}
Follow

Recents

Archives

Links

×