Ukulele谱《Ob-La-Di, Ob-La-Da》the Beatles

发表在 樊轶群Ukulele谱 | 留下评论

Daily LeetCode – day0172 1814. Count Nice Pairs in an Array

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。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0171 1813. Sentence Similarity III

// 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避免了重复。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0170 2293. Min Max Game

// 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但是还是不给力,哈哈哈。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0169 1819. Number of Different Subsequences GCDs

// 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也是一样的道理。
用上变量可以更快,不用反复去除以。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0168 2287. Rearrange Characters to Make Target String

// 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;
    }
}
学习笔记:
这是一道计数的题目,可以用哈希表但是没有必要,直接拿数组来解决就最快了。
把需要的和拥有的材料数量统计一遍,然后除一下取最小值即可。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0167 1807. Evaluate the Bracket Pairs of a String

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();
    }
}
学习笔记:
这是一道哈希表的题,难度是中等,但是和一般中等题比简单不少。
可以切割字符串也可以一个个字符来处理添加。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0166 2283. Check if Number Has Equal Digit Count and Digit Value

// 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;
    }
}
学习笔记:
这是一道简单题,看一下每一位的出现次数对不对,不对就提前返回。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0165 0753. Cracking the Safe

import java.util.HashSet;
import java.util.Set;

// 0753. Cracking the Safe
class Solution {
    public String crackSafe(int n, int k) {
        if (n == 1 && k == 1) {
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n - 1; ++i) {
            sb.append("0");
        }
        String start = sb.toString();
        Set<String> visited = new HashSet<>();
        dfs(start, k, visited, ans);
        ans.append(start);
        return ans.toString();
    }

    public void dfs(String start, int k, Set<String> visited, StringBuilder ans) {
        for (int i = 0; i < k; ++i) {
            String nbr = start + i;
            if (!visited.contains(nbr)) {
                visited.add(nbr);
                dfs(nbr.substring(1), k, visited, ans);
                ans.append(i);
            }
        }
    }
}
学习笔记:
这又是一道超级困难题,普通深搜似乎是难以通过的,得剪枝。
这其实是求一个de Bruijn序列,和汉密尔顿圈、欧拉回路都有关系。
这个需要等以后有空了才能去研究了。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0164 1806. Minimum Number of Operations to Reinitialize a Permutation

// 1806. Minimum Number of Operations to Reinitialize a Permutation
class Solution {
    public int reinitializePermutation(int n) {
        int[] perm = new int[n];
        for (int i = 0; i < n; ++i) {
            perm[i] = i;
        }
        int ans = 0;
        while (true) {
            ++ans;
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                if ((i & 1) == 0) {
                    arr[i] = perm[i >> 1];
                } else {
                    arr[i] = perm[(n >> 1) + (i - 1 >> 1)];
                }
            }
            if (isReinitialized(n, arr)) {
                break;
            }
            perm = arr;
        }
        return ans;
    }

    private boolean isReinitialized(int n, int[] arr) {
        for (int i = 0; i < n; ++i) {
            if (arr[i] != i) {
                return false;
            }
        }
        return true;
    }
}
学习笔记:
这道题是一道中等题,如果是数学算法,我觉得算是困难题了可以。
主要这道题用n^2的模拟算法也给过,我时间紧迫就先写了一个模拟算法的了。
这个其实就是一个循环次数的问题,还有寻找面向答案的编程、还有数学算法可以使用。
发表在 每日LeetCode | 留下评论