Leetcode周赛367补题（3 / 3）

目录

1、找出满足差值条件的下标 I - 暴力

2、最短且字典序最小的美丽字符串 - 滑动窗口

（1）枚举

（2）滑动窗口 

3、找出满足差值条件的下标 II - 双指针 + 思维

---

1、找出满足差值条件的下标 I - 暴力

2903. 找出满足差值条件的下标 I

class Solution {
    public int[] findIndices(int[] nums, int ind, int val) {
    int[] res={-1,-1};
    int n=nums.length;
    for(int i=0;i
    {
        
        for(int j=i;j
        {
            if(Math.abs(nums[i]-nums[j])>=val&&Math.abs(i-j)>=ind)
            {
                res[0]=i;
                res[1]=j;
                return res;
            }
        }
    }
    return res;
    }
}

2、最短且字典序最小的美丽字符串 - 滑动窗口

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

（1）枚举

思路：

要求满足k个1的最小串，因此最短长度必为k

我们可以从k开始枚举子串长度，然后截取看其中1的个数，若满足k则更新最小串

class Solution {
    public String shortestBeautifulSubstring(String S, int k) {
        if(S.replace("0","").length()return ""; //如果全部1都比k少则直接返回空句
 
        int n=S.length();
        int cur=0;
        char[] s=S.toCharArray();
        String res=S;
 
        for(int len=k;len<=n;len++)
        {
            for(int i=0;i1;i++)
            {
                String t=S.substring(i,i+len);
                if(t.replace("0","").length()==k)
                    if(t.length()0) res=t;
            }
        }
        return res;
    }
}

 

（2）滑动窗口 

思路：

顺序移动右边界，如果窗口内1的个数大于k，则缩小左边界直至窗口内1个数小于等于k

当1的个数=k时，更新字典序最小的最短串

class Solution {
    public String shortestBeautifulSubstring(String S, int k) {
        if(S.replace("0","").length()return ""; //如果全部1都比k少则直接返回空句
 
        int n=S.length();
        int l=0,cur=0;
        char[] s=S.toCharArray();
        String res=S;
 
        for(int r=0;r
        {
            cur+=s[r]-'0';
            while(cur>k || s[l]=='0')
            {
                cur-=s[l]-'0';
                l++;
            }
            if(cur==k)
            {
                String t=S.substring(l,r+1);
                if(t.length()0) res=t;
            }
        }
        return res;
    }
}

 

3、找出满足差值条件的下标 II - 双指针 + 思维

2905. 找出满足差值条件的下标 II

 

思路：

题意和第一题一样，但数据范围限定不能用双for循环

我们可以直接枚举满足 |i - j| ≥ index 的区间，也就是直接限定差值j从index开始枚举

这样i = j - index才永远满足 i>0 在合法区间内

然后找出合法区间的最大最小值，在

• nums[j] - nums[minid] >= value
• nums[maxid] - nums[j] >= value

最有可能满足第二个条件

class Solution {
    public int[] findIndices(int[] nums, int index, int value) {
        int maxid=0,minid=0;
 
        for(int j=index;j
        {
            int i=j-index; //这里的i肯定符合|i-j|>=index
 
            //找出最大值和最小值的下标
            if(nums[i]>nums[maxid]) maxid=i;
            else if(nums[i]
 
            if(nums[maxid]-nums[j]>=value) return new int[]{maxid,j};
            
            if(nums[j]-nums[minid]>=value) return new int[]{minid,j};
 
        }
        return new int[]{-1,-1};
    }
}