专栏首页光城(guangcity)数组刷题<下>套路分析

数组刷题<下>套路分析

数组刷题<下>套路分析

一、双索引技术-对撞指针1.167. 两数之和 II - 输入有序数组2. 345. 反转字符串中的元音字母3.344. 反转字符串4.125. 验证回文串5.11. 盛最多水的容器二、双索引技术-滑动窗口1.209. 长度最小的子数组2.438. 找到字符串中所有字母异位词3.76. 最小覆盖子串

一、双索引技术-对撞指针

类似题目:

  • 167. 两数之和 II - 输入有序数组
  • 345. 反转字符串中的元音字母
  • 344. 反转字符串
  • 125. 验证回文串
  • 11. 盛最多水的容器

注意的问题:

  • 定义前后指针
  • 向中间靠拢

1.167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

实现思路:

使用双索引技术-对撞指针:

  • 一般会是大于或者小于。
  • 如果大i++ 小 j--
  • 两个索引在往中间走。对撞指针。

实现:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res=new int[2];
        int i=0,j=numbers.length-1;
        while(i<j){
            if(numbers[i]+numbers[j]==target){
                res[0]=i+1;
                res[1]=j+1;
                break;
            }else if(numbers[i]+numbers[j]>target){
                j--;
            }else{
                i++;
            }
        }
        return res;
    }
}

2. 345. 反转字符串中的元音字母

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "leetcode"
输出: "leotcede"

说明: 元音字母不包含字母"y"。

实现思路:

使用双索引技术-对撞指针:

  • 两个索引在往中间走。对撞指针。

实现:

这道题难点在于语言的熟悉度。比如在下面java中可以用匿名函数来创建HashMap并初始化。中间使用s.charAt(i)函数获取每个字符,最后将char数组转为String。

class Solution {
   public String reverseVowels(String s) {
        int i=0,j=s.length()-1;
        HashMap<Character,Integer> hashMap = new HashMap<Character, Integer>(){
            {
                put('a',0);put('A',0);put('e',0);put('E',0);put('i',0);
                put('I',0);put('o',0);put('O',0);put('u',0);put('U',0);
            }
        };

        char[] str = new char[s.length()];

        while(i<=j){
            if(hashMap.getOrDefault(s.charAt(i),-1)==-1){
                str[i]=s.charAt(i);
                i+=1;
                continue;
            }
            if(hashMap.getOrDefault(s.charAt(j),-1)==-1){
                str[j]=s.charAt(j);
                j-=1;
                continue;
            }
            str[i]=s.charAt(j);
            str[j]=s.charAt(i);
            i+=1;
            j-=1;
        }
        return String.valueOf(str);
    }
}

3.344. 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:

输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

实现思路:

使用双索引技术-对撞指针:

  • 两个索引在往中间走。对撞指针。

实现:

两边交换即可。

class Solution {
    public void reverseString(char[] s) {
        int i=0,j=s.length-1;
        char temp;
        while(i<j){
            temp=s[i];
            s[i]=s[j];
            s[j]=temp;
            i++;
            j--;
        }
    }
}

4.125. 验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

实现思路:

使用双索引技术-对撞指针:

  • 两个索引在往中间走。对撞指针。

实现:

两边往中间走即可。

class Solution {
    public boolean isPalindrome(String s) {
        int i=0,j=s.length()-1;
        s = s.toLowerCase();
        while(i<j){
            if(!((s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z'))){
                i++;
                continue;
            }
            if(!((s.charAt(j) >= '0' && s.charAt(j) <= '9') || (s.charAt(j) >= 'a' && s.charAt(j) <= 'z'))){
                j--;
                continue;
            }
            if(s.charAt(i)!=s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

上述是吧字符串全部转小写了,当然也可以在比较中转:

class Solution {
    public static boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (!((s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'))) {
                i++;
                continue;
            }
            if (!((s.charAt(j) >= '0' && s.charAt(j) <= '9') || (s.charAt(j) >= 'a' && s.charAt(j) <= 'z') || (s.charAt(j) >= 'A' && s.charAt(j) <= 'Z'))) {
                j--;
                continue;
            }
            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

5.11. 盛最多水的容器

给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

实现思路:

使用双索引技术-对撞指针:

  • 两个索引在往中间走。对撞指针。

实现:

使用双指针,选择最小高度乘以间距即可。

class Solution {
    public int maxArea(int[] height) {
        int left=0,right=height.length-1;


        int area=0;
        while(left<right){
            if(height[left]<height[right]){
                area=Math.max((right-left)*height[left],area);
                left++;
            }else{
                area=Math.max((right-left)*height[right],area);
                right--;
            }
        }
        return area;
    }
}

上述简化版:

class Solution {
   public int maxArea(int[] height) {
        int left=0,right=height.length-1;

        int area=0;
        while(left<right){
            area=Math.max(area,(right-left)*Math.min(height[left],height[right]));
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
        }
        return area;
    }
}

二、双索引技术-滑动窗口

类似题目:

  • 209. 长度最小的子数组
  • 438. 找到字符串中所有字母异位词
  • 76. 最小覆盖子串

注意的问题:

  • 如何维护窗口?

1.209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和≥ s 的长度最小的连续子数组如果不存在符合条件的连续子数组,返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

实现思路:

当窗口内的值大于等于目标值,则压缩窗口,左边界向右压缩,否则的话右边界扩容。

注意边界点:右边界的index不能超过数组的最大值,另外右边界与做左边界都要指向计算和的当前元素,所以右窗口j从-1开始,先j++,这样可以保证每次窗口的总和的右边界是与j一致!

实现:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i=0,j=-1;
        int n=nums.length;
        int number=n+1;
        int total=0;
        while(i<n){
            if(j+1<n && total<s){
                j++;
                total+=nums[j];
            }else {
                total-=nums[i];
                i++;
            }
            //获取每次结果的窗口长度
            if(total>=s){
                if(number>j-i+1){
                    number=j-i+1;
                }
            }
        }
        //若不变,则没有找到
        if (number==n+1){
            return 0;
        }
        return number;
    }
}

滑动窗口升级版1:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i=0,j=-1;
        int n=nums.length;
        int number=0;
        int total=0;
        while(i<n){
            if(j+1<n && total<s){
                j++;
                total+=nums[j];
            }else {
                total-=nums[i];
                i++;
            }
            //获取每次结果的窗口长度
            if(total>=s){
                number=number==0?j-i+1:Math.min(j-i+1,number);
            }
        }
        return number;
    }
}

滑动窗口升级版2:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i=0;
        int sum=0;
        int number=0;
        for (int j=0;j<nums.length;j++){
            sum+=nums[j];
            while(sum>=s){
                number=number==0?j-i+1:Math.min(j-i+1,number);
                sum-=nums[i++];
            }
        }
        return number;
    }
}

除了上述O(n)时间复杂度,题目中说了O(nlogn)呢?

实现思路:

二分法:

时间复杂度:O(nlogn),空间复杂度O(n)。

思路:

将原先数组所有数字累加求和得到一个新数组,例如:

nums=[2,3,1,2,4,3]
parNums=[0,2,5,6,8,12,15]

然后循环parNums,对每一个数组中的index对应的值,利用二分法找到最小的窗口。

举个例子:

nums=[2,3,1,2,4,3]
parNums=[0,2,5,6,8,12,15]
--------------
i=0时
--------------
第一轮
left=0,right=6
left<right,计算出mid=3,此时对应的值为6,mid距离i的和也就是6<7,
调整left=mid+1=4。
第二轮
left=4,right=6
left<right,计算出mid=5,此时对应的值为12,mid距离i的和也就是12>7,
调整right=mid-1。
是不是上述可以看作是查找7的二分法,那么后面依次类推即可。
当然left调整也可以是left++,right调整也可以是right--,也可以AC,但是效率会低一些!
--------------
......

实现:

循环+二分

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int[] parNums = new int[nums.length+1];
        //构造nums元素依次累加数组
        for(int i=1;i<parNums.length;i++){
            parNums[i]=parNums[i-1]+nums[i-1];
        }

        int min=0;
        for(int i=0;i<parNums.length;i++){
            int left=i;
            int right=parNums.length-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                int subSum=parNums[mid]-parNums[i];
                if(subSum>=s){
                    right=mid-1; //可以换成right--;
                    min=min==0?mid-i:Math.min(min,mid-i);
                }else{
                    left=mid+1; //可以换成left++;
                }
            }
        }
        return min;
    }
}

2.438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

字符串只包含小写英文字母,并且字符串 sp 的长度都不超过 20100。

说明:

  • 字母异位词指字母相同,但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

实现思路:

字母异位数指的是:字母异位词指字母相同,但排列不同的字符串。所以只要满足字母异位数,那么p字符串的每个字符肯定会在字符串中出现!

实现:

题目中提到只考虑小写字母,那么创建一个数组长度包含所有小写字母大小,这里创建26个长度数组。使用ch-'a'来存储每个字符与a字符的距离也就是一个int值。

循环s-p次,也就是让p当作窗口扫描s字符串,然后在s中截取子串,并查看这个字串中的每个字符是否在p中存在(或者说p中的字符是否在子串),这个判断是通过对字串的每个字符累加,然后在p中去减,如果是>=0,那么肯定是字母异位词,<0肯定不是字母异位词。最后把子串开始索引加入list中即可。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s==null || p==null||s.length()<p.length()) return res;
        for(int i=0;i<s.length()-p.length()+1;i++){
            if(isAn(s.substring(i,i+p.length()),p)){
                res.add(i);
            }
        }
        return res;
    }

    public boolean isAn(String s,String p){
        int[] arr= new int[26];
        for(char ch:s.toCharArray()){
            arr[ch-'a']++;
        }
        for(char ch:p.toCharArray()){
            arr[ch-'a']--;
            if(arr[ch-'a']<0) {
                return false;
            }
        }
        return true;
    }

}

对上述优化,上述代码在取子串后调用isAn函数的时候每次都会做循环,也就是连续几个递进会有重复的循环操作,所以效率非常低。

实现思路:

第一个循环让arr数组统计字符串p的每个字符个数,第二个循环,让滑动窗口达到p的长度,并计算第一个窗口是否满足字母异位词。第三个循环是根据s中的字符来调整窗口的左右边界。

实现:

class Solution {
    public List<Integer>  findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s==null || p==null || s.length()<p.length()) return list;

        int[] arr =  new int[26];
        for(int i=0;i<p.length();i++){
            arr[p.charAt(i)-'a']++;
        }

        int p_len=p.length();
        int left=0,right=p.length();

        for(int i=0;i<p.length();i++){
            arr[s.charAt(i)-'a']--;
            if (arr[s.charAt(i)-'a']>=0) p_len--;
        }
        if(p_len==0) list.add(0);

        while(right<s.length()){

            if(arr[s.charAt(left)-'a']>=0) 
                p_len++;
            arr[s.charAt(left)-'a']++;
            left++;

            arr[s.charAt(right)-'a']--;
            if (arr[s.charAt(right)-'a']>=0) 
                p_len--;
            right++;
            if(p_len==0) list.add(left);
        }
        return list;
    }

}

实现思路:

使用一个数组arr存储p字符串的每个字符出现的个数。循环字符串s,right表示窗口的右边界,left表示窗口的左边界,根据s中每个窗口内的字符是否存在在arr中来调整左右边界。

实现:

class Solution {
    public List<Integer>  findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s==null || p==null || s.length()<p.length()) return list;

        int[] arr =  new int[26];
        for(int i=0;i<p.length();i++){
            arr[p.charAt(i)-'a']++;
        }

        int p_len=p.length();
        int left=0,right=0;
        while(right<s.length()){
            arr[s.charAt(right)-'a']--;
            if (arr[s.charAt(right)-'a']>=0) p_len--;
            if(p_len==0) list.add(left);

            //维护窗口大小
            if(right-left==p.length()-1){
                if(arr[s.charAt(left)-'a']>=0) 
                    p_len++;
                //恢复
                arr[s.charAt(left)-'a']++;
                left++;
            }
             right++;
        }
        return list;
    }

}

3.76. 最小覆盖子串

给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。

示例:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明:

  • 如果 S 中不存这样的子串,则返回空字符串 ""
  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。

实现思路:

首先让右指针不断往前走,左指针不动,直到将窗口拉到最大,同时包含t中所有字符串。

定义一个HashMap,keycharacter,valueInteger。先循环t字符串长度,这个HashMap中保存了t中所有字符。key为t中字符,value为t中字符出现的次数。

然后定义左右指针,leftright,当s中的right对应的元素在HashMap中,就让对应的value减1,每减1,也就是与t中匹配的字符串就得减去1,也就是t_len减去1。当t_len为0,表示right已经拉到最大,此时窗口包含所有t中元素,就要移动left,进而压缩窗口大小,使得找出最小覆盖子串。

实现:

class Solution {
    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        if (s == null || t == null || s.length() < t.length()) return "";

        for (int i = 0; i < t.length(); i++) {
            if(hashMap.get(t.charAt(i))!=null){
                hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1);
            }else{
                hashMap.put(t.charAt(i), 1);
            }
        }

        int t_len = t.length();
        int left = 0, right = 0;
        int minlen = s.length() + 1;
        int minleft=0;
        while (right < s.length()) {

            if (hashMap.containsKey(s.charAt(right))) {

                Integer in = hashMap.get(s.charAt(right));
                in--;
                hashMap.remove(s.charAt(right));
                hashMap.put(s.charAt(right),in);
                if (in >= 0)
                    t_len--; //表示t中此时被访问过的元素-1
            }
            //窗口拉到了最大,寻找匹配,看是否是最小长度子串。
            while(t_len == 0){
                if(right - left + 1 < minlen){
                    minlen = right - left + 1;
                    minleft = left;
                }
                //左边的元素如果在hashMap中,那么就要恢复原来的值,因为左边的值必定被右边right访问过,而right访问的时候只要在hashMap中,就会减去1,所以这里要恢复,也就是+1,同是如果此时恢复过后的值>0就需要,让t_len+1。表示t中此时没被访问过的元素+1。
                if (hashMap.containsKey(s.charAt(left))) {
                    Integer lt = hashMap.get(s.charAt(left));
                    lt++;
                    if(lt>0){
                        t_len++;
                    }
                    hashMap.remove(s.charAt(left));
                    hashMap.put(s.charAt(left),lt);
                }
                left++;
            }
            right++;
        }
        if(minlen==s.length()+1){
            return "";
        }

        return s.substring(minleft, minleft + minlen);
    }
}

上述精简版:

class Solution {
    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        if (s == null || t == null || s.length() < t.length()) return "";

        for (int i = 0; i < t.length(); i++) {
            if(hashMap.get(t.charAt(i))!=null){
                hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1);
            }else{
                hashMap.put(t.charAt(i), 1);
            }
        }

        int t_len = t.length();
        int left = 0, right = 0;
        int minlen = s.length()+1,minleft=0;

        while (right < s.length()) {

            if (hashMap.containsKey(s.charAt(right))) {

                int rt = hashMap.getOrDefault(s.charAt(right), 0);
                rt--;
                hashMap.put(s.charAt(right), rt);
                if (rt >= 0)
                    t_len--;
            }
            while(t_len == 0){
                if(right - left + 1 < minlen){
                    minlen = right - left + 1;
                    minleft = left;
                }

                if (hashMap.containsKey(s.charAt(left))) {
                    int lt = hashMap.getOrDefault(s.charAt(left), 0);
                    lt++;
                    if(lt>0){
                        t_len++;
                    }
                    hashMap.put(s.charAt(left), lt);
                }
                left++;
            }
            right++;
        }

        return (minlen == s.length() + 1) ? "" : s.substring(minleft, minleft + minlen);
    }
}

总结:第3题与第2题特别相似,都是先确定一个窗口,然后不断调整左右窗口范围,需要注意不同点:第2道题是让t串的字符串出现在s中并且连续,所以滑动窗口的长度在第一次确定后就可以不变了。而第3道题则是先确定一个包含所有字符串t的窗口,不断压缩这个最大窗口,然后再继续移动左右指针。

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-22

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 螺旋矩阵你听过?

    昨天满课,我还是坚持来刷题了,写文时间是晚上10点45,刷题时间是10点,今日题目leetcode上的螺旋矩阵,这道题思路简单,实现困难,,对于考研的同学建议仔...

    公众号guangcity
  • LeetCode动态规划上之递归+记忆化搜索+DP逐步进阶(上)

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    公众号guangcity
  • 基于二分搜索法的floor与ceil

    此时使用上述二分查找算法,搜索出来的index为3。那如果我想要获取最左侧等于target的index或最右侧等于target的index呢?此时上述算法失效!

    公众号guangcity
  • 译文 | 怎样确保关键商业数据的安全性?

    本文由CDA数据分析研究院翻译,译者:王晨光,转载必须获得本站、原作者、译者的同意,拒绝任何不表明译者及来源的转载! 自互联网诞生之日起,黑客就诞生了,他们靠偷...

    CDA数据分析师
  • 数据库MySQL-实体之间的关系

    答:在字段数量很多情况下,数据量也就很大,每次查询都需要检索大量数据,这样效率低下。我们可以将所有字段分成两个部分,“常用字段”和“不常用字段”,这样对大部分查...

    cwl_java
  • CodeForces 663A Rebus

    A. Rebus time limit per test 1 second memory limit per test 256 megabytes ...

    ShenduCC
  • 【LTE系列课程】EMM和ECM

    在用户和网络之间的移动性和会话管理是由UE和MME的控制面的NAS层的NAS协议来控制的。UE和MME使用NAS消息相互通信。

    鲜枣课堂
  • tk.mybatis通用工具采坑记

    虽然不影响使用,但还是看着烦~,他的意思就是这个类被扫了两遍~~我就说哪里MyMapper类继承的类都被莫名其妙扫了一遍。。自己再配置扫一遍就重复了~

    老梁
  • [答疑]测试是不是不属于建模

    “测试”可以看作建模的验证过程,思考的还是那些内容,类似下面这张流行很广的图。当然,图上所用的术语统一为书中的术语就更好。

    用户6288414
  • 1722 最优乘车 1997年NOI全国竞赛

    1722 最优乘车 1997年NOI全国竞赛  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解 题目描述 Des...

    attack

扫码关注云+社区

领取腾讯云代金券