最新消息:深度思考

两个指针

算法 liuxuecheng 2010浏览 0评论

总结一下有关两个指针的算法题。这里的指针起游标的作用,一般用在处理字符串或者数组的相关问题上。有两个指针从头尾向中间移动,也有从头到尾一前一后一起移动。

1.求一个字符串的最大不重复子串的长度

一种接近暴力求解的方法就是遍历所有可能的子串组合,然后找出其中最长的一个。每次拿到一个子串的时候使用HashSet去判断有没有重复字符,如果有则不参与最长的比对计算。但是这种方式的时间复杂度太高,为O(n^3)。
代码如下:

  public int lengthOfLongestSubstring(String s) {
        //全局最大数
        int max = 0;
        for(int i = 0;i<s.length();i++){
            // j比i先走一步,这里j如果小于s.length()的话,一个字符的时候不会进入循环
            for(int j = i+1;j<=s.length();j++){
                //判断子串没有重复字符的时候才进入
                if(!hasRepeated(s.substring(i,j))){
                    max = Math.max(max,j-i);
                }
            }
        }
        return max;
    }
    public boolean hasRepeated(String substr){
        HashSet<Character> set = new HashSet<Character>();
        boolean flag = true;
        for(Character c :substr.toCharArray()){
            if(set.contains(c)){
                flag = true;
                break;
            }else {
                set.add(c);
                flag = false;
            }
        }
        return flag;
    }

上述代码优化一下,还是使用两个游标。游标j先走,如果遇到的字符不重复则继续走,并求最大值;否则,后走的游标向前走一步。代码如下:

public int lengthOfLongestSubstring(String s) {
        int i = 0,j = 0,max = 0;
        ArrayList<Character> list = new ArrayList<Character>();
        while(i<s.length() && j<s.length()){
            if(list.contains(s.charAt(j))){
                //如果直接写list.remove(s.charAt(i++)) 会执行remove(int index)方法导致数组越界异常
                Character c = s.charAt(i++);
                list.remove(c);
            }else{
                list.add(s.charAt(j++));
                max = Math.max(j-i,max);
            }
        }
        return max;
    }

代码较为简洁,执行效率还不错,打败了85%的提交。

2.最大容器

给定一个整数数组array,再给定一个坐标轴,数组中第i个数对应坐标轴上的点为(i,array[i])。从坐标点a(i,array[i])向坐标点b(i,0)连一条垂直于x轴的竖线,另外从坐标点c(j,array[j])向坐标点d(j,0)连接另外一条垂直于x轴的竖线。两条连线组成一个桶,这个桶能装的水量取决于桶的短板。求所有坐标点可能形成的桶中能装最多水的桶面积。
坐标
对于两个坐标点a(i,array[i]),b(j,array[j])形成的面积为area = Math.min(array[i],array[j])*(j-i)。
和上题一样依然可以使用暴力求解的方式找出最大面积,但是时间复杂度太高。下面给出一种时间复杂度为O(N)的解法:

 public int maxArea(int[] height) {
        int l = 0,r = height.length-1,max=0;
        while(l<r){
            max = Math.max(max,Math.min(height[l],height[r])*(r-l));
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return max;
    }

转载请注明:大数据随笔 » 两个指针

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址