专栏首页机器学习入门LeetCode Weekly Contest 42解题思路

LeetCode Weekly Contest 42解题思路

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/75911369

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来表示,所以优化的思想在于,如何用出现次数来区分奇偶且能够保证nums[i]的值不变。

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

接着遍历下标,找寻nums[i] > 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所致。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode Weekly Contest 37解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 44解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(80):4.3 2-SAT(4)

    挑战程序竞赛系列(80):4.3 2-SAT(4) 传送门:POJ 2749: Building roads 题意: 阳关路与独木桥:有N个农场,其中A对相...

    用户1147447
  • 简单ac自动机学习

    简单的来讲解一下自动机,虽然都在说这是和的组合,但个人觉得不需要深入理解这两个仍然可以学会它。同时由于网上已经存在了很多教程,本文尽量避免采取和网上一样的说法,...

    ACM算法日常
  • 105. 从前序与中序遍历序列构造二叉树

    前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    祝你万事顺利
  • PAT 甲级 1021 Deepest Root (并查集,树的遍历)

    1021. Deepest Root (25) 时间限制 1500 ms 内存限制 65536 kB 代码长度限制 16000 B ...

    ShenduCC
  • 常见内存错误

    C语言强大的原因之一在于几乎能掌控所有的细节,包括对内存的处理,什么时候使用内存,使用了多少内存,什么时候该释放内存,这都在程序员的掌控之中。而不像Java中,...

    编程珠玑
  • C++ STL stack 用法

    Stack(栈)是一种后进先出的数据结构,也就是LIFO(last in first out) ,最后加入栈的元素将最先被取出来,在栈的同一端进行数据的插入与取...

    于小勇
  • 剑指offer刷题记(C++版本)

    也算是临时抱佛脚了吧,3月之前刷了lintcode100多道题吧,后来发文章什么的就放下了,最近秋招在即在牛客网上想着把剑指offer这本书刷完,尽量早刷完吧,...

    和蔼的zhxing
  • 线性同余同余方程组解法(excrt)

    【问题描述】 求关于 x 的同余方程组 x%a 1 =b 1  a1=b1 x%a 2 =b 2  a2=b2 x%a 3 =b 3  a3=b3 x%a...

    attack

扫码关注云+社区

领取腾讯云代金券