首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode Weekly Contest 42解题思路

LeetCode Weekly Contest 42解题思路

作者头像
用户1147447
发布2019-05-26 09:28:08
4020
发布2019-05-26 09:28:08
举报
文章被收录于专栏:机器学习入门机器学习入门

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434657

LeetCode Weekly Contest 42解题思路

详细代码可以fork下Github上leetcode项目,不定期更新。

赛题

本次周赛主要分为以下4道题:

Leetcode 645. Set Mismatch

Problem:

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number. Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = 1,2,2,4 Output: 2,3

Note:

  • The given array size will in the range 2, 10000.
  • The given array’s numbers won’t have any order.

水题,提供两种做法,采用map:

    public int[] findErrorNums(int[] nums) {
        int[] map = new int[nums.length + 1];

        for (int i = 0; i < nums.length; ++i){
            map[nums[i]]++;
        }

        int a1 = 0;
        int a2 = 0;
        for (int i = 1; i <= nums.length; ++i){
            if (map[i] == 2){
                a1 = i;
            }
            if (map[i] == 0){
                a2 = i;
            }
        }

        return new int[]{a1, a2};
    }

上述空间复杂度为O(n)。

优化思路:在一个数组中,出现奇数次和偶数次可以用(−1)n(-1)^n来表示,所以优化的思想在于,如何用出现次数来区分奇偶且能够保证numsi的值不变。

很easy,遍历所有的num,由它定位到某个位置,此时如果num只出现一次,这些位置的值都变成了负,但当num第二次出现时,此时定位相同的位置已经被访问过了(<0的一个数),只能说明num的次数为2次,也就是要找的错误num。

接着遍历下标,找寻numsi > 0的index,它是没有被搜索到的。

代码如下:

    public int[] findErrorNums(int[] nums) {
         int[] res = new int[2];
         for (int i : nums){
             if (nums[Math.abs(i) - 1] < 0) res[0] = Math.abs(i);
             else nums[Math.abs(i) - 1] *= -1;
         }
         for (int i = 0; i < nums.length; ++i){
             if (nums[i] > 0) res[1] = i + 1;
         }
         return res;
    }

Leetcode 646. Maximum Length of Pair Chain

Problem:

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [1,2, 2,3, 3,4] Output: 2 Explanation: The longest chain is 1,2 -> 3,4

Note:

  • The number of given pairs will be in the range 1, 1000.

此次周赛的题都是一些原题,此题的思路为排序+动规,排序为了分阶段选择,动规为了记录所有子序列的值,毕竟它在选择上只需要当某个阶段的最大即可,代码如下:

    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; ++i){
            for (int j = 0; j < i; ++j){
                if (pairs[i][0] > pairs[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                else{
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
        }
        return dp[n - 1];
    }

DP方法时间复杂度为O(n2)O(n^2),此题还可以更优,时间复杂度为O(nlogn)O(n\log n),先对start排序,直接按照贪心法会出错,如:[1,20],[2,3],[4,5],所以可以对end进行排序,于是有了[2,3],[4,5],[1,20],此时再根据贪心选择start > end的区间,再更新end,即能得到答案。

代码如下:

    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        int ans = 0;
        int end = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i){
            while (i < n && pairs[i][0] <= end){
                i ++;
            }
            if (i < n){
                end = pairs[i][1];
                ans ++;
            }
        }
        return ans;
    }

Leetcode 647. Palindromic Substrings

Problem:

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: “abc” Output: 3 Explanation: Three palindromic strings: “a”, “b”, “c”.

Example 2:

Input: “aaa” Output: 6 Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Note:

  • The input string length won’t exceed 1000.

还是原题,暴力过了,代码如下:

    public int countSubstrings(String s) {
        char[] cs = s.toCharArray();
        int n = s.length();
        int start = 0;
        int cnt = 0;
        while (start < n){
            for (int i = start; i < n; ++i){
                if (isPalidrome(cs, start, i)){
                    cnt++;
                }
            }
            start++;
        }
        return cnt;
    }

    public boolean isPalidrome(char[] cs, int i, int j){
        while (i < j){
            if (cs[i] != cs[j]) return false;
            i++;
            j--;
        }
        return true;
    }

之所以暴力,是因为即使在某种状态下的substring已经不是palindrome,在它基础上还会分别向外扩展去判断其它的substring是否为palindrome,这一部分可以省去,比如:

abacba

判断 ac是否为palindrome,如果ac不是palindrome,那么由此衍生出来的substring
a. bacb
b. abacba
这两种情况是可以避免的,也是接下来算法优化的核心思路。

方法一:(采用区间DP记录被访问过的index)

    public int countSubstrings(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int ans = 0;
        for (int i = 0; i < n; ++i){
            for (int j = i; j >= 0; --j){
                if (i == j || (dp[i - 1][j + 1] && cs[i] == cs[j]) || (cs[i] == cs[j] && i - j == 1)){
                    dp[i][j] = true;
                    ans ++;
                }   
            }
        }
        return ans;
    }

方法二:(扩展回文法)

    public int countSubstrings(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; ++i){
            ans += extendPalindrom(s.toCharArray(), i, i, 0);
            ans += extendPalindrom(s.toCharArray(), i, i + 1, 0);
        }
        return ans;
    }

    public int extendPalindrom(char[] cs, int i, int j, int count){
        while (i >= 0 && j < cs.length && cs[i] == cs[j]){
            count ++;
            i --;
            j ++;
        }
        return count;
    }

注意:此算法保证了在扩展时,没有重复的i和j,需要证明下。

Leetcode 648. Replace Words

Problem:

In English, we have a concept called root, which can be followed by some other words to form another longer word - let’s call this word successor. For example, the root an, followed by other, which can form another word another. Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length. You need to output the sentence after the replacement.

Example 1:

Input: dict = “cat”, “bat”, “rat” sentence = “the cattle was rattled by the battery” Output: “the cat was rat by the bat”

Note:

  • The input will only have lower-case letters.
  • 1 <= dict words number <= 1000
  • 1 <= sentence words number <= 1000
  • 1 <= root length <= 100
  • 1 <= sentence words length <= 1000

方法一:(Trie树,前缀搜索,在搜索过程中,遇到字典,放入list)

    class TrieNode{
        TrieNode[] children;
        String str;
        public TrieNode(){
            children = new TrieNode[26];
        }
    }

    public TrieNode add(TrieNode root, String str){
        if (root == null) root = new TrieNode();
        TrieNode cur = root;
        for (char c : str.toCharArray()){
            int pos = c - 'a';
            if (cur.children[pos] == null) cur.children[pos] = new TrieNode();
            cur = cur.children[pos];
        }
        cur.str = str;
        return root;
    }

    public List<String> search(TrieNode root, String prefix){
        List<String> ans = new ArrayList<>();
        if (root == null) return ans;
        TrieNode cur = root;
        for (char c : prefix.toCharArray()){
            int pos = c -'a';
            if (cur.children[pos] == null){
                break;
            }
            if (cur.children[pos] != null){
                cur = cur.children[pos];
                if (cur.str != null) ans.add(cur.str);
            }
        }
        return ans;
    }

    TrieNode root;
    public String replaceWords(List<String> dict, String sentence) {
        root = new TrieNode();
        for (String word : dict){
            root = add(root, word);
        }
        String[] replace = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < replace.length; ++i){
            List<String> lists = search(root, replace[i]);
            if (lists.isEmpty()){
                sb.append(replace[i] + " ");
            }
            else{
                int minLen = 1 << 30;
                String ans = "";
                for (String c : lists){
                    if (c.length() < minLen){
                        ans = c;
                        minLen = c.length();
                    }
                }
                sb.append(ans + " ");
            }
        }
        return sb.toString().substring(0, sb.length() - 1);
    }

稍微优化下,返回第一个前缀字典即可,代码如下:

    class TrieNode{
        TrieNode[] children;
        String str;
        public TrieNode(){
            children = new TrieNode[26];
        }
    }

    public TrieNode add(TrieNode root, String str){
        if (root == null) root = new TrieNode();
        TrieNode cur = root;
        for (char c : str.toCharArray()){
            int pos = c - 'a';
            if (cur.children[pos] == null) cur.children[pos] = new TrieNode();
            cur = cur.children[pos];
        }
        cur.str = str;
        return root;
    }

    public String search(TrieNode root, String prefix){
        if (root == null) return null;
        TrieNode cur = root;
        for (char c : prefix.toCharArray()){
            int pos = c -'a';
            if (cur.children[pos] == null){
                break;
            }
            if (cur.children[pos] != null){
                cur = cur.children[pos];
                if (cur.str != null){
                    return cur.str;
                }
            }
        }
        return null;
    }

    TrieNode root;
    public String replaceWords(List<String> dict, String sentence) {
        root = new TrieNode();
        for (String word : dict){
            root = add(root, word);
        }
        String[] replace = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < replace.length; ++i){
            String key = search(root, replace[i]);
            if (key == null){
                sb.append(replace[i] + " ");
            }
            else{
                sb.append(key + " ");
            }
        }
        return sb.toString().substring(0, sb.length() - 1);
    }

写个精短的,不需要Trie树,每次从字典集中找前缀,找到则替换。

代码如下:

public String replaceWords(List<String> dict, String sentence) {
        if (dict == null || dict.size() == 0) return sentence;

        Set<String> dictSet = new HashSet<>();
        for (String key : dict){
            dictSet.add(key);
        }

        StringBuilder sb = new StringBuilder();
        String[] replace = sentence.split(" ");
        for (int i = 0; i < replace.length; ++i){
            String prefix = "";
            for (int j = 0; j < replace[i].length(); ++j){
                prefix = replace[i].substring(0, j + 1);
                if (dictSet.contains(prefix)){
                    break;
                }
            }
            sb.append(" " + prefix);
        }
        return sb.deleteCharAt(0).toString();
    }

速度会慢点,但此次OJ对于暴力做法都过了,感觉是系统bug所致。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年07月23日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LeetCode Weekly Contest 42解题思路
    • 赛题
      • Leetcode 645. Set Mismatch
        • Leetcode 646. Maximum Length of Pair Chain
          • Leetcode 647. Palindromic Substrings
            • Leetcode 648. Replace Words
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档