7.22-Contest 42-小结

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 中查找，取最先达到的字符串作为替换。