09Leetcode周赛

0开发 > Z刷题 Java python

发布时间 : 2022-09-18 16:23

字数:3.2k 阅读 :

第X场周赛
第 311 场周赛(2道)
第334场周赛(20230227)(1道)
第336场周赛(20230312)(1道)

第X场周赛

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

第 311 场周赛(2道)

6180. 最小偶倍数

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

判断奇偶

思路

判断奇偶即可, 偶数答案为n, 奇数答案为2*n;

代码

class Solution {
    public int smallestEvenMultiple(int n) {
        if(n%2==0) return n;
        else return n*2;
    }
}

6181. 最长的字母序连续子字符串的长度

给你一个仅由小写英文字母组成的字符串 s ，返回其最长的字母序连续子字符串的长度。

示例 1：
输入：s = "abacaba"
输出：2
解释：共有 4 个不同的字母序连续子字符串 "a"、"b"、"c" 和 "ab" 。
"ab" 是最长的字母序连续子字符串。

模拟-遍历计数比大小😄

思路

遍历, 如果后一个字符比前一个字符字典序+1, 则length+1, 否则length = 0继续计数, 用max_length记录最大的length.

代码

class Solution {
    public int longestContinuousSubstring(String s) {
        
        int length = 1;
        int max_length = 1;
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i) - s.charAt(i-1) == 1) {
                length++;
                max_length = length > max_length? length:max_length;
            }
            else
            {
                length = 1;
            }
        }
        return max_length;

    }
}

复杂度

时间: $O(N)$
空间: $O(1)$

6182. 反转二叉树的奇数层

给你一棵完美二叉树的根节点 root ，请你反转这棵树中每个奇数层的节点值。

输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

层序遍历记录再建树💭

思路

层序遍历进数组, 然后利用数组完全二叉树性质进行交换, 然后再建树或者修改原树.

递归🙆♂

思路

函数作用: 满足一定条件时交换两颗树根结点的值, 并且交换左树左孩子与右树右孩子的值, 交换左树右孩子与右树左孩子的值(也同样满足一定条件).

返回值: 无.

传递参数: 左树, 右树, 层次数.

终止状态: 要交换的左树和右树为空.

非终止状态: 先判断条件交换左树和右树根节点的值. 然后递归交换左树左孩子与右树右孩子的值, 交换左树有孩子与右树左孩子的值

代码

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        swapLeftRight(root.left, root.right, 1);
        return root;
    }
    public void swapLeftRight(TreeNode left, TreeNode right, int level) {
        if (left == null && right == null) {
            return;
        }
        if (level % 2 == 1) {
            int t = left.val;
            left.val = right.val;
            right.val = t;
        }
        swapLeftRight(left.left, right.right, level+1);
        swapLeftRight(left.right, right.left, level+1);
    }
}

复杂度

时间: $O(2^n-1)$ 遍历节点的个数
空间: $O(h)$ 递归栈的深度, 完美二叉树的高

6183. 字符串的前缀分数和

给你一个长度为 n 的数组 words ，该数组由非空字符串组成。

定义字符串 word 的分数等于以 word 作为前缀的 words[i] 的数目。

例如，如果 words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2 ，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数总和。

注意：字符串视作它自身的一个前缀。

map+扫描😭

思路

用map存储某个前缀的分数, 然后对于每个单词从最长到最短的子串来查找map, map没找到的话就扫描words来计算分数.

错误: 时间复杂度太高了, 如果只有一个超长的字符串, 就会新建这个超长的的map.

代码

class Solution {
    public int[] sumPrefixScores(String[] words) {     
        int nums[] = new int[words.length];
        Map<String, Integer> m = new HashMap<>();
        
        for (int i = 0; i < words.length; i++) {
            int num = 0;
            for (int j = 0; j < words[i].length(); j++) {
                String sub_string = words[i].substring(0, words[i].length()-j);
                int grade = 0;
                if(m.containsKey(sub_string) == true) {
                    grade = m.get(sub_string);
                    num += grade;
                }else{
                    grade = getStringGrade(words, sub_string);
                    m.put(sub_string, grade);
                    num += grade;
                }
            }
            nums[i] = num;
        }
        return nums;

    }
    
    public int getStringGrade(String [] words, String str) {
        int num = 0;
        for (int i = 0; i < words.length; i++) {
            if (words[i].startsWith(str) == true) {
                num= num+1;
            }
        }
        return num;
    }
    
}

代码2

改进, 但还是超过复杂度了

class Solution {
    public int[] sumPrefixScores(String[] words) {     
        int nums[] = new int[words.length];
        Map<String, Integer> m = new HashMap<>();
        m.put("",0);
        for (int i = 0; i < words.length; i++) {
            int num = 0;
            for (int j = 1; j <= words[i].length(); j++) {
                String sub_string = words[i].substring(0, j);
                int grade = 0;
                if(m.containsKey(sub_string) == true) {
                    //如果有子串的话直接取
                    grade = m.get(sub_string);
                    num += grade;
                }else if(sub_string.length() == 1 || m.containsKey(sub_string.substring(0,sub_string.length()-1)) == true){
                    //如果没有字串并且字串=1 或者 没有子串但有前子串的话
                    grade = getStringGrade(words, sub_string);
                    m.put(sub_string, grade);
                    num +=grade;
                }
                else if(m.containsKey(sub_string.substring(0,sub_string.length()-1)) == true){
                    // 如果没有子串也没有前子串的话
                    grade = 1;                  //它本身
                    num += grade;
                    break;
                }
            }
            nums[i] = num;

        }
            
        return nums;

    }
    
    public int getStringGrade(String [] words, String str) {
        int num = 0;
        for (int i = 0; i < words.length; i++) {
            if (words[i].startsWith(str) == true) {
                num= num+1;
            }
        }
        return num;
    }
    
    
}

用map还是太浪费空间了, 必须用字典树.

第334场周赛(20230227)(1道)

6369. 左右元素和的差值

给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：

answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|

其中：

leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。

返回数组 answer 。

示例 1：

输入：nums = [10,4,8,3]
输出：[15,1,11,22]
解释：数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。

模拟

思路

就按题目中的模拟就行了

代码

class Solution {
    public int[] leftRigthDifference(int[] nums) {
        int[] ans = new int[nums.length];
        int[] leftSumArr = new int[nums.length];
        int[] rightSumArr = new int[nums.length];
        
        for(int i = 1; i < nums.length; i++) {
            leftSumArr[i] = leftSumArr[i-1] + nums[i-1];
        }
        for(int i = nums.length-2; i >= 0; i--) {
            rightSumArr[i] = rightSumArr[i+1] + nums[i+1];
        }
        
        for(int i = 0; i < nums.length; i++) {
            ans[i] = Math.abs(leftSumArr[i]-rightSumArr[i]);
        }
        return ans;
        
    }
}

复杂度

时间: $$
空间: $$

6368. 找出字符串的可整除数组

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

如果 word[0,...,i] 所表示的数值能被 m 整除，div[i] = 1
否则，div[i] = 0

返回 word 的可整除数组。

示例 1：

输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

数学推导

思路

记N[i]为word[0 ~ i]表示的值。

记n[i]为word[i]表示的数。

不难得出 : N[i] = N[i - 1] * 10 + n[i]

在此假设 : N[i - 1] = p * m + q(即余数是q)

那么 : N[i] % m = (p * m * 10) % m + (q * 10 + n[i ] ) % m

其中 : (p * m * 10) % m必能整除, 因此只要看后半部分。

结论 : 每次向后增加一位时, 我们只考虑前面的余数部分, 这样是不会影响结果的。

==用迭代取大数的余数的方法==

代码

class Solution {
    public int[] divisibilityArray(String word, int m) {
        long remainder = 0;          //N[i-1]的余数, 初始为0
        int[] ans = new int[word.length()];
        for(int i = 0; i < word.length(); i++) {
            remainder = (remainder * 10 + (word.charAt(i)-'0'))%m;              //思想, 大数取余的思想
            
            if(remainder == 0) ans[i] = 1;
            else ans[i] = 0;                        //思想, 其实默认为0, 可以不写
        }
        return ans;
    }
}

复杂度

时间: $O(n)$
空间: $O(1), 不考虑结果数组$

大数(超出时间限制)

思路

用BigInteger, 需要自己导包, 会超出时间限制

代码

import java.math.BigInteger;

class Solution {
    public int[] divisibilityArray(String word, int m) {
        int[] ans = new int[word.length()];
        for(int i = 1; i <= word.length(); i++) {
            BigInteger num = new BigInteger(word.substring(0,i));
            BigInteger remainder = num.remainder(new BigInteger(String.valueOf(m)));
            if(remainder.equals(BigInteger.ZERO)) {
                ans[i-1] = 1;
            }else {
                ans[i-1] = 0;
            }
        }
        return ans;
    }
}

复杂度

时间: $$
空间: $$

6367. 求出最多标记下标

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

暴力检验

思路

如果有k次匹配, 那一定是前k个最小的和后k的最大的数字, 但是如果遍历检验就超出时间限制了

代码

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        int k = 1;
        for(k = 1; k <= nums.length/2; k++) {
            if(checkAns(nums, k) == true) continue;
            else break;
        }
        return 2*(k-1);
    }

    private boolean checkAns(int[] nums, int k) {
        int len = nums.length;

        for(int i = 1; i <= k; i++) {
            if(2 * nums[0+i-1] <= nums[(len-1) -(k) + 1 + (i-1)]) continue;
            else return false;
        }
        return true;
    }
}

复杂度

时间: $$
空间: $$

2576. 求出最多标记下标

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

前后指针+贪心

思路

我们需要用左半部分的数，去匹配右半部分的数。

从右半部分中，找到第一个满足 2⋅nums[0]≤nums[j] 的 j，那么 nums[1]只能匹配右半部分中的下标大于 j 的数，依此类推。

先排序
让j=(n+1)/2, 也就是让j从数组长度的一半往后找, 那么找到第一个的j一定是nums[0]对应的最好的j, 因为k最大为数组的一半, 所以j再小就算能匹配但是也无法增大答案
前后指针, 从j=(len+1)/2中点的下一位开始找起, 然后符合条件就同时增加front和back, 不符合条件就移动back直到找到当前front符合条件对应的back.

代码

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        //前后指针, 排序后从j=(len+1)/2中点的下一位开始找起, 然后符合条件就同时增加front和back, 不符合条件就移动back直到找到当前front符合条件对应的back.
        int back = (nums.length+1)/2;
        int front = 0;
        Arrays.sort(nums);
        while(back < nums.length) {
            if(2*nums[front] > nums[back]){
                back++;
            }
            else {
                front++;
                back++;
            }
        }
        return 2*front;
    }
}

复杂度

时间: $$
空间: $$

第336场周赛(20230312)(1道)

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

题号.题目

描述

样例

思想1名称

思路

描述

代码

\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想

复杂度

时间: $$
空间: $$

欢迎在评论区中进行批评指正，转载请注明来源，如涉及侵权，请联系作者删除。