645. Set Mismatch
- 这道题只需确保 i 位置上的数满足 nums[i]==i+1，通过不断换位置即可。
- time complexity: O(n), space complexity: O(1)
- 代码如下：
public class SetMismatch {
public int[] findErrorNums(int[] nums) {
// swap and find trick
int[] res = new int[2];
// find duplicates
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1) {
int left = nums[i];
int right = nums[nums[i] - 1];
swap(nums, i, nums[i] - 1);
if (left == right) {
res[0] = left;
break;
}
}
}
// find missing
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
res[1] = i + 1;
break;
}
}
return res;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
646. Maximum Length of Pair Chain
这道题跟 meeting room 的解法类似，使用 greedy 算法。首先根据每个pair的第二个数的大小对所有pair进行排序。然后依次取第二个数最小的pair，如何当前的pair的第一个数比前一个pair的第二个数小则跳过。
647. Palindromic Substrings
这道题与在字符串中找最长的回文字符串解法相同，使用 dynamic programming 不断判断对应字符串是否是回文，同时进行统计即可。
648. Replace Words
这道题首先根据dict建立一个 multiway trie，然后依次对 sentence 中的 word 在 trie 中查找，取最先达到的字符串作为替换。
