[LeetCode周赛]第 62 场双周赛

一.介绍

  周赛链接: LeetCode第62场双周赛
  结果这样,还行吧

  为什么现在才写这个博客呢,因为我懒,下次争取参加完就把总结写了
  A了三题,还算OK吧,但是三次罚时……,无话可说,没罚时的话就能前500了,可惜.

二.分析

2.1 将一维数组转变为二维数组(Easy)

  题目链接: LeetCode-2022

题目内容:
	给你一个下标从 0 开始的一维整数数组 original 和两个整数 m 和  n 。
	你需要使用 original 中 所有 元素创建一个 m 行 n 列的二维数组。
	original 中下标从 0 到 n - 1 (都 包含 )的元素构成二维数组的第一行
	下标从 n 到 2 * n - 1 (都 包含 )的元素构成二维数组的第二行,依此类推。
	请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组,请你返回一个空的二维数组。

示例:
	输入:original = [1,2,3,4], m = 2, n = 2
	输出:[[1,2],[3,4]]
	解释:
	构造出的二维数组应该包含 2 行 2 列。
	original 中第一个 n=2 的部分为 [1,2] ,构成二维数组的第一行。
	original 中第二个 n=2 的部分为 [3,4] ,构成二维数组的第二行。

提示:
	1 <= original.length <= 5 * 10^4
	1 <= original[i] <= 10^5
	1 <= m, n <= 4 * 10^4

  我的解答如下:

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        int len=original.length;
        if(m*n!=len) return new int[][]{};
        int[][]res=new int[m][n];
        for(int i=0;i<len;i++)
        {
            res[i/n][i%n]=original[i];
        }
        return res;
    }
}

  简单题没啥好说的,注意先判断能否构成,再按序往结果数组中填数就可以了,罚时就是因为填数时行列条件切换错了,小心一些就可以了
  时间复杂度为O(mn),空间复杂度为O(1)(不计算答案所用空间)

2.2 连接后等于目标字符串的字符串对(Medium)

  题目链接: LeetCode-2023

题目内容:
	给你一个 数字 字符串数组 nums 和一个 数字 字符串 target ,
	请你返回 nums[i] + nums[j] (两个字符串连接)结果等于 target 的下标 (i, j)
	需满足 i != j 的数目。

示例:
	输入:nums = ["777","7","77","77"], target = "7777"
	输出:4
	解释:符合要求的下标对包括:
	- (0, 1):"777" + "7"
	- (1, 0):"7" + "777"
	- (2, 3):"77" + "77"
	- (3, 2):"77" + "77"

提示:
	2 <= nums.length <= 100
	1 <= nums[i].length <= 100
	2 <= target.length <= 100
	nums[i] 和 target 只包含数字。
	nums[i] 和 target 不含有任何前导 0 。

  我的解答如下:

class Solution {
    public int numOfPairs(String[] nums, String target) {
        int n=nums.length,res=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(j==i) continue;
                if(target.equals(nums[i]+nums[j]) ) res+=1;
            }
        }
        return res;
    }
}

  这个题难度也不高,数据范围都只有100,所以O(n2)时间复杂度的算法也可以,罚时的原因是完全没考虑到int的范围,直接把字符串转为int比较了,实际上应该直接用字符串比较
  时间复杂度为O(n2),空间复杂度为O(1)
  当然这题应该用哈希表做更好一些:

class Solution {
    public int numOfPairs(String[] nums, String target) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> map1 = new HashMap<>();
        int res = 0;
        int count = 0;
        // 正序,num当右半部分
        for (String num : nums) {
            res += getNumOfPairs(map, target, num);
        }
        System.out.println(res);
        // 倒序,num还为右半部分
        for (int i = nums.length - 1; i >= 0; i--) {
            res += getNumOfPairs(map1, target, nums[i]);
        }
        return res;
    }

    /**
     * 获取与当前匹配的组合数
     * @param map 哈希表
     * @param target 目标target
     * @param num 当前String
     * @return
     */
    private int getNumOfPairs(Map<String, Integer> map, String target, String num) {
        int count = 0;
        if (num.length() < target.length()) {
            // 判断是否符合target的右部分
            if (num.equals(target.substring(target.length() - num.length()))) {
                String s = target.substring(0, target.length() - num.length());
                count += map.getOrDefault(s, 0);
            }
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return count;
    }
}

  时间复杂度为O(n),空间复杂度为O(n)

2.3 考试的最大困扰度(Medium)

  题目链接: LeetCode-2023

题目内容:
	一位老师正在出一场由 n 道判断题构成的考试,每道题的答案为 true (用 'T' 表示)或者 false (用 'F' 表示)。
	老师想增加学生对自己做出答案的不确定性,方法是 最大化 有 连续相同 结果的题数。(也就是连续出现 true 或者连续出现 false)。
	给你一个字符串 answerKey ,其中 answerKey[i] 是第 i 个问题的正确结果。
	除此以外,还给你一个整数 k ,表示你能进行以下操作的最多次数:
	每次操作中,将问题的正确答案改为 'T' 或者 'F' (也就是将 answerKey[i] 改为 'T' 或者 'F' )。
	请你返回在不超过 k 次操作的情况下,最大 连续 'T' 或者 'F' 的数目。

示例:
	输入:answerKey = "TTFTTFTT", k = 1
	输出:5
	解释:我们可以将第一个 'F' 换成 'T' ,得到 answerKey = "TTTTTFTT" 。
	或者我们可以将第二个 'F' 换成 'T' ,得到 answerKey = "TTFTTTTT" 。
	两种情况下,都有五个连续的 'T' 。

提示:
	n == answerKey.length
	1 <= n <= 5 * 10^4
	answerKey[i] 要么是 'T' ,要么是 'F'
	1 <= k <= n

  我的解答如下:

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        Queue<Character> queuet=new LinkedList<>(); //T的队列
        Queue<Character> queuef=new LinkedList<>(); //F的队列
        int res=1;
        char[] cs=answerKey.toCharArray();
        int kt=k,kf=k;   //分别代表可以改变的T和F的个数
        for(int i=0;i<cs.length;i++)
        {
            if(cs[i]=='F')
            {
                queuef.add('f');
                res=Math.max(res,queuef.size());
                if(kf>0)
                {
                    kf--;
                    queuet.add('f');
                    res=Math.max(res,queuet.size());
                }
                else
                {
                    while(queuet.peek()!='f') queuet.poll();
                    queuet.add('f');
                    queuet.poll();
                }
            }
            else
            {
                queuet.add('t');
                res=Math.max(res,queuet.size());
                if(kt>0)
                {
                    kt--;
                    queuef.add('t');
                    res=Math.max(res,queuef.size());
                }
                else
                {
                    while(queuef.peek()!='t') queuef.poll();
                    queuef.add('t');
                    queuef.poll();
                }
            }
        }
        return res;
    }
}

  这个题难度不算特别高,我的做法是维护两个队列,根据answerKey值为T还是F以及K的值判断该两个队列的情况,如果k==0了,相反的那个队列就要出队,直到把第一个相反的元素排除出去,罚时的原因是,错误的第一个元素出队后,实际上对应的K应该还是0,因为当前还需要入队一个相反元素,但我把k设成了1,我也不知道我当时咋想的……
  这个时间复杂度算的我头晕,应该是O(n)吧,因为所有元素入队一次,出队一次,空间复杂度为O(n)
  显然这题维护两个队列是没有必要的,直接利用滑窗的思想,维护两个下标就可以了:

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int n = answerKey.length();
        char[] c = answerKey.toCharArray();
        int left = 0, right = 0;
        int numT = 0, numF = 0;
        int ans = 0;
        while(right < n){
            if(c[right] == 'T')
                numT++;
            else
                numF++;
			//任意一个值小于k都代表可以通过该值大小变成一个统一字符串,至于是T还是F,我们并不需要关心
            while(numT > k && numF > k){
                if(c[left] == 'T')
                    numT--;
                else
                    numF--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}

  时间复杂度为O(n),空间复杂度为O(1)

2.4 分割数组的最多方案数(Hard)

  题目链接: LeetCode-2025

题目内容:
	给你一个下标从 0 开始且长度为 n 的整数数组 nums。分割数组 nums 的方案数定义为符合以下两个条件的 pivot 数目:

	1 <= pivot < n
	nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
	
	同时给你一个整数 k 。你可以将 nums 中 一个 元素变为 k 或 不改变 数组。
	请你返回在 至多 改变一个元素的前提下,最多 有多少种方法 分割 nums 使得上述两个条件都满足。
示例:
	输入:nums = [0,0,0], k = 1
	输出:2
	解释:一个最优的方案是不改动数组。
	有两种方法分割数组:
	- pivot = 1 ,我们有分割 [0 | 0,0]:0 == 0 + 0 。
	- pivot = 2 ,我们有分割 [0,0 | 0]: 0 + 0 == 0 。

提示:
	n == nums.length
	2 <= n <= 10^5
	10^5 <= k, nums[i] <= 10^5

  我当时的解答如下:

class Solution {
    public int waysToPartition(int[] nums, int k) {
        int sum=0,n=nums.length,res=0;
        int[]leftsum=new int[n];
        int[]rightsum=new int[n];
        for(int num:nums) sum+=num;
        rightsum[0]=sum;
        for(int i=1;i<n;i++)
        {
            leftsum[i]=leftsum[i-1]+nums[i-1];
            rightsum[i]=sum-nums[i-1]-leftsum[i-1];
        }

        for(int i=1;i<n;i++)
            if(leftsum[i]==rightsum[i]) res++;
        for(int i=0;i<n;i++)
        {
            int temp=0;
            for(int j=1;j<n;j++)
            {
               if(j>i)
                {
                     if(leftsum[j]+k-nums[i]==rightsum[j])
                        temp++;
                }
                else
                {
                     if(leftsum[j]==rightsum[j]+k-nums[i])
                         temp++;
                }
                res=Math.max(res,temp);
            }
        }
        return res;
    }
}

  其实这是一个正确的解,但注意到2 <= n <= 105,该解的时间复杂度为O(n2),所以无法通过全部案例
  显然本题降时间复杂度的方法是前缀和+哈希,竞赛的时候想起来了,但可惜没时间了,该方法实现如下:

class Solution {
    public int waysToPartition(int[] nums, int k) {
        int n = nums.length;
        int[] preSum = new int[n + 1];
        Map<Integer, Integer> m1 = new HashMap<>();
        Map<Integer, Integer> m2 = new HashMap<>();
        for (int i = 1; i < n; i++) {
            preSum[i] = nums[i - 1] + preSum[i - 1];
            // 一开始除了最后一个前缀和,其余均在m2中
           m2.put(preSum[i], m2.getOrDefault(preSum[i], 0) + 1);
        }
        preSum[n] = nums[n - 1] + preSum[n - 1];
        int ans = 0;
        if (preSum[n] % 2 == 0) {
            // 只有总和为偶数时,才可以一个值都不修改
            ans = m2.getOrDefault(preSum[n] / 2, 0);
        }
        for (int i = 0; i < n; i++) {
            // 修改下标为i的元素变成k
            int change = k - nums[i];
            // 所有元素总和的变化量也是change
            int pn = preSum[n] + change;
            if (pn % 2 == 0) {
                // 在m1中我们要找的目标是 target1 = 总和/2 的数量
                int t1 = pn / 2;
                // 在m2中我们要找的目标是 target2 = target1 - change 的数量
                int t2 = t1 - change;
                //分别统计变化点在左边和右边的个数,相加
                int found = m1.getOrDefault(t1, 0) + m2.getOrDefault(t2, 0);
                ans = Math.max(ans, found);
            }
            // 不断减少m2中的计数,增加m1对应的计数
            if (i != n - 1) {
                m1.put(preSum[i + 1], m1.getOrDefault(preSum[i + 1], 0) + 1);
                int tmp = m2.get(preSum[i + 1]);
                if (tmp == 1)  m2.remove(preSum[i + 1]);
                else m2.put(preSum[i + 1], tmp - 1);
            }
        }
        return ans;
    }
}
end
  • 作者:Yuan(联系作者)
  • 发表时间:2021-12-04 22:54
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载博主转载的文章,请附上原文链接
  • 公众号转载:请联系作者
  • 评论