樊轶群的个人网站

import java.util.HashMap;
import java.util.Map;

// 1814. Count Nice Pairs in an Array
class Solution {
    public int countNicePairs(int[] nums) {
        Map<Integer, Integer> selfMinusReverse = new HashMap<>();
        for (int num : nums) {
            int diff = num - reverse(num);
            selfMinusReverse.put(diff, selfMinusReverse.getOrDefault(diff, 0) + 1);
        }
        long ans = 0L;
        for (Map.Entry<Integer, Integer> entry : selfMinusReverse.entrySet()) {
            ans += (long) entry.getValue() * (entry.getValue() - 1) / 2;
        }
        return (int) (ans % 1000000007L);
    }

    private int reverse(int num) {
        int res = 0;
        while (num > 0) {
            res = res * 10 + num % 10;
            num /= 10;
        }
        return res;
    }
}

学习笔记：
这其实也算是一道写着中等题的困难题了。
看到1 <= nums.length <= 10^5就知道n^2的时间复杂度会过不去了。
那么就不能使用暴力解法。

巧妙的地方就是在于
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
这个公式让你会觉得需要i和j两个都一起算才能知道是否相等。
移项整理后会发现
其实上只需要自己算一下差就可以了。
nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
所以就要统计一下，每个数字减自身反转后的差有多少相同，然后统计即可。

然后要注意最后是value * (value - 1) / 2这样的形式。
为什么是这样呢，因为题目规定i < j。
也就是说i不能和j一样，所以要-1。然后i和j不能调换再算一次，所以要/2。

// 1813. Sentence Similarity III
class Solution {
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        String[] words1 = sentence1.split(" ");
        String[] words2 = sentence2.split(" ");
        int left;
        int right;
        int shortLength = Math.min(words1.length, words2.length);
        for (left = 0; left < shortLength; ++left) {
            if (!words1[left].equals(words2[left])) {
                break;
            }
        }
        if (left == shortLength) {
            return true;
        }
        for (right = 0; right < shortLength - left; ++right) {
            if (!words1[words1.length - 1 - right].equals(words2[words2.length - 1 - right])) {
                break;
            }
        }
        return shortLength == left + right;
    }
}

学习笔记：
这是一道字符串的题目。
先一波切割，然后比较左边，比较右边。
左右相同的加起来应该会等于短的那一串。

这里有两个细节我踩过坑，一个是
"Ogn WtWj HneS"
"Ogn WtWj HneS"
一模一样，我两边都是3。变成6了，我就加了一个判断，左边如果完事儿了就直接返回。

另一个是
"A A AAa"
"A AAa"
左边1，右边2，加起来是3了。我就把right < shortLength改成了right < shortLength - left避免了重复。

// 2293. Min Max Game
class Solution {
    public int minMaxGame(int[] nums) {
        int newLength = nums.length >> 1;
        while (newLength > 0) {
            for (int i = 0; i < newLength; ++i) {
                if ((i & 1) == 0) {
                    nums[i] = Math.min(nums[i << 1], nums[(i << 1) + 1]);
                } else {
                    nums[i] = Math.max(nums[i << 1], nums[(i << 1) + 1]);
                }
            }
            newLength >>= 1;
        }
        return nums[0];
    }
}

学习笔记：
一道简单的模拟题，但是其实上这道题是有递归写法的，而且递归写法竟然是最快的。
我这边全部都使用了位运算代替/2 *2 %2但是还是不给力，哈哈哈。

// 1819. Number of Different Subsequences GCDs
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int[] GCDs = new int[200001];
        for (int num : nums) {
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    if (GCDs[i] == 0) {
                        GCDs[i] = num;
                    } else {
                        GCDs[i] = gcd(GCDs[i], num);
                    }
                    if (GCDs[num / i] == 0) {
                        GCDs[num / i] = num;
                    } else {
                        GCDs[num / i] = gcd(GCDs[num / i], num);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 200001; ++i) {
            if (GCDs[i] == i) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

学习笔记：
强迫自己进步的一天，这是一道困难题。
思路用得很巧妙，本来是先归类再计算，然后转化成了一边分类分类进去就顺便计算。
题目说题目数字在20万以内，那么最大的最大公约数也就是20万了。

然后我们可以逐一去考虑，每一个最大公约数怎么检验是否符合呢？
比如要校验4，那么得把所有4的正整数倍数找出来：
情况1：4,8,12,16,20这样的，那么有4在，肯定最大公约数肯定是4了。
情况2：8,16,64这样的，那么最大公约数其实是8，那么就不存在最大公约数为4的情况。
情况3：8,12,16,20这样的，没有4在，但是他们的最大公约数也是4。
总结就是把倍数找出来，然后连续求最大公约数。

接着就遇到了死胡同，这样一个个校验，从1到200000，挑出来要遍历一整遍，然后连续求最大公约数也要时间。总共加起来要做200000个一整遍。

巧妙的来了，其实只要遍历一整遍，每次找到是某个数的倍数，那么就分类顺便把连续求最大公约数的步骤也做了。这样只需要弄个200001的空间存当前的最大公约数们就可以啦。

最后统计有多少个数字的最大公约数是自己那也就是存在。

// 1819. Number of Different Subsequences GCDs
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int[] GCDs = new int[200001];
        for (int num : nums) {
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    if (GCDs[i] == 0) {
                        GCDs[i] = num;
                    } else if (GCDs[i] != i) {
                        GCDs[i] = gcd(GCDs[i], num);
                    }
                    int numOverI = num / i;
                    if (GCDs[numOverI] == 0) {
                        GCDs[numOverI] = num;
                    } else if (GCDs[numOverI] != numOverI) {
                        GCDs[numOverI] = gcd(GCDs[numOverI], num);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 200001; ++i) {
            if (GCDs[i] == i) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

接下来又优化了代码，从572ms变到了446ms。
就是说一旦中途发现gcds[i]已经等于i了，那就没有下探空间了。
所以不需要再调用gcd函数递归去求了。
gcd[num / i]已经等于num / i也是一样的道理。
用上变量可以更快，不用反复去除以。

// 2287. Rearrange Characters to Make Target String
class Solution {
    public int rearrangeCharacters(String s, String target) {
        char[] charsTarget = target.toCharArray();
        int[] needs = new int[123];
        for (char c : charsTarget) {
            ++needs[c];
        }
        char[] charsS = s.toCharArray();
        int[] material = new int[123];
        for (char c : charsS) {
            ++material[c];
        }
        int ans = Integer.MAX_VALUE;
        for (char i = 'a'; i <= 'z'; ++i) {
            if (needs[i] != 0) {
                ans = Math.min(ans, material[i] / needs[i]);
            }
        }
        return ans;
    }
}

学习笔记：
这是一道计数的题目，可以用哈希表但是没有必要，直接拿数组来解决就最快了。
把需要的和拥有的材料数量统计一遍，然后除一下取最小值即可。

import java.util.HashMap;
import java.util.List;

// 1807. Evaluate the Bracket Pairs of a String
class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        HashMap<String, String> hashMap = new HashMap<>();
        for (List<String> know : knowledge) {
            hashMap.put(know.get(0), know.get(1));
        }
        StringBuilder sb = new StringBuilder();
        char[] ca = s.toCharArray();
        int len = ca.length;
        int i = 0;
        while (i < len) {
            if (ca[i] == '(') {
                ++i;
                StringBuilder temp = new StringBuilder();
                while (ca[i] != ')') {
                    temp.append(ca[i]);
                    ++i;
                }
                if (hashMap.containsKey(temp.toString())) {
                    sb.append(hashMap.get(temp.toString()));
                } else {
                    sb.append('?');
                }
            } else {
                sb.append(ca[i]);
            }
            ++i;
        }
        return sb.toString();
    }
}

学习笔记：
这是一道哈希表的题，难度是中等，但是和一般中等题比简单不少。
可以切割字符串也可以一个个字符来处理添加。

// 2283. Check if Number Has Equal Digit Count and Digit Value
class Solution {
    public boolean digitCount(String num) {
        for (int i = 0; i < num.length(); ++i) {
            int count = 0;
            for (int j = 0; j < num.length(); ++j) {
                if (num.charAt(j) - 48 == i) ++count;
            }
            if (num.charAt(i) - 48 != count) return false;
        }
        return true;
    }
}

学习笔记：
这是一道简单题，看一下每一位的出现次数对不对，不对就提前返回。