周赛367

周赛367

好久没看周赛了，今天来试试做题。

​

T1-2. 100096. 找出满足差值条件的下标 I

• 100101. 找出满足差值条件的下标 II ：和这道题思路一样，只是数据量规模不一样而已。

1. 题目说明

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

• abs(i - j) >= indexDifference 且
• abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

提示：

• 1 <= n == nums.length <= 100

• 0 <= nums[i] <= 50

• 0 <= indexDifference <= 100

• 0 <= valueDifference <= 50

  ​

---

2. 解答分析

• 无脑暴力解答，这里用到的是嵌套两个循环进行判断。（当然这里需要考虑到n的长度和nums[i]的大小关系）

• 当然如果考虑到nums[i]的长度关系，我们还可以利用双指针进行判断。

• 还有一种方法是红黑树，但是这种方法之前没试过，后续准备一份HashMap和TreeMap的区别文章总结一下，这里就直接贴代码解释

  ​

---

3. 具体代码

（1）暴力解法

• 适用于数组的长度较小的情况，而且对于当前的两层循环注意前后顺序

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int[] ans=new int[2];
        int n=nums.length;
        for(int i=0;i<n-indexDifference;i++){
            for(int j=i+indexDifference;j<n;j++){
                if(Math.abs(nums[i]-nums[j])>=valueDifference){
                    ans[0]=i;
                    ans[1]=j;
                    return ans;
                }
            }
        }
        ans[0]=-1;
        ans[1]=-1;
        return ans;
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n^2)$，两层嵌套循环

  • 空间复杂度：$O(1)$，只用到了数组的数据结构

    ​

（2）双指针优化

• 不用全部元素都循环遍历，而是考虑两个指针之间的差值关系就行。
• 枚举indexDifference的同时，开始进行nums[i]的最大值和最小值的维护判断。

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int maxIdx = 0, minIdx = 0;
        for (int j = indexDifference; j < nums.length; j++) {
            int i = j - indexDifference;
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            } else if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
            if (nums[maxIdx] - nums[j] >= valueDifference) {
                return new int[]{maxIdx, j};
            }
            if (nums[j] - nums[minIdx] >= valueDifference) {
                return new int[]{minIdx, j};
            }
        }
        return new int[]{-1, -1};
    }
}

• 复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为$nums$ 的长度。

  • 空间复杂度：$O(1)$。

    ​

（3）红黑树TreeMap

class Solution{
	//使用TreeMap将数组中的元素与下标映射关联起来，然后依次遍历数组中的元素，判断是否存在满足条件的两个元素。
    
	public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
   	 // 创建一个TreeMap对象
    	TreeMap<Integer,Integer> map = new TreeMap<>();
    	int n = nums.length;
    	// 遍历数组
    	for(int i = indexDifference; i < n; i++) {
        	// 将元素作为key，下标作为value，添加到map中去
        	map.put(nums[i - indexDifference], i - indexDifference);
        	// 判断当前元素与最小的元素的差的绝对值是否大于等于valueDifference
        	if(Math.abs(map.firstKey() - nums[i]) >= valueDifference) {
           	 	return new int[] {map.get(map.firstKey()), i};
        	}
        	// 判断当前元素与最大的元素的差的绝对值是否大于等于valueDifference
        	if(Math.abs(map.lastKey() - nums[i]) >= valueDifference) {
            	return new int[] {map.get(map.lastKey()), i};
        	}
    	}
    	// 如果找不到满足条件的两个元素，则返回[-1, -1]
    	return new int[] {-1, -1};      
	}
}

• 复杂度分析：

  • 时间复杂度：$O(nlogn)$，在for循环中需要遍历全部数组元素，复杂度为$O(n)$；在寻找最大/最小值的时候查找的复杂度为$O(logn)$。综上所述：时间复杂度为$O(nlogn)$

  • 空间复杂度：$O(n)$，因为需要使用大小为n-indexDifference+1的TreeMap来存储数据。

    ​

    ​

T3. 100084. 最短且字典序最小的美丽子字符串

1. 题目说明

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

• 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

示例 1：

输入：s = "100011001", k = 3
输出："11001"
解释：示例中共有 7 个美丽子字符串：
1. 子字符串 "/100011/001" 。
2. 子字符串 "/1000110/01" 。
3. 子字符串 "/100011001/" 。
4. 子字符串 "1/00011001/" 。
5. 子字符串 "10/0011001/" 。
6. 子字符串 "100/011001/" 。
7. 子字符串 "1000/11001/" 。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。

提示：

• 1 <= s.length <= 100

• 1 <= k <= s.length

  ​

2. 解答分析

• 可以看出当前的字符串的长度较短，可以直接利用暴力解答。利用双指针就行,确定好具体的范围关系。

  ​

3. 具体代码

class Solution{
    public String shortestBeautifulSubstring(String s,int k){
        String result="";//返回字符串
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                String sub=s.substring(i,j+1);//返回前后指针构造成的字符串
                if(isValid(sub,k)){
                    if(result.length()==0){
                        result=sub;
                    }else if(result.length()>sub.length()){
                        result=sub;
                    }else if(result.length()==sub.length() && result.compareTo(sub) > 0){  //如果"result"的字典序大于"sub"的字典序，那么返回值就会大于0；否则返回-1或0
                        result=sub;
                    }
                }
            }
        }
        return result;
    }
    
    private boolean isValid(String sub,int k){
        int count=0;
        for(int i=0;i<sub.length();i++){
            if(sub.charAt(i)=='1'){
                count++;
            }
        }
        return count==k;
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n^2)$

  • 空间复杂度：$O(1)$

    ​

---

END~