作者：whisper

链接：http://proprogrammar.com:443/article/202

声明：请尊重原作者的劳动，如需转载请注明出处

    有一些 LeetCode 题目，我们可以采用对撞指针进行求解：指针 i 和 j 分别指向数组的第一个元素和最后一个元素，然后指针 i 不断向前， 指针 j 不断递减，知道 i = j（当然具体的逻辑操作根据题目的变化而变化）。

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

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

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

说明:

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

示例:

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

 

    想法：因为有序，所以从两端开始，如果两端和大于目标，大端减小，如果两端和小于目标，小端增加，直到找到结果

// 想法：因为有序，所以从两端开始，如果两端和大于目标，大端减小，如果两端和小于目标，小端增加，直到找到结果
    public int[] twoSum(int[] numbers, int target) {
        int little = 1;
        int large = numbers.length;
        
        while(numbers[little-1] + numbers[large-1] != target)
        {
            if(numbers[little-1] + numbers[large-1] > target)
            {
                large--;
            }
            else
            {
                little++;
            }
        }
        
        return new int[]{little, large};
    }

     很简洁的代码了，只用了一重循环

    解题思路

    暴力解法

    双层遍历，时间复杂度为 O(n^2)，暴力解法没有充分利用原数组的性质 —— 有序，本文不采用。

    当我们看到数列有序的时候，就应该想到可以用二分搜索法。

    二分搜索法

    遍历每个 nums[i]，在剩余数组中查找 target-nums[i] 的值，时间复杂度为 O(n log n)。

    有兴趣的读者可以用这种方法尝试一下，应该也是可以 AC 的， 本文采用对撞指针法。

    对撞指针法

    我们首先判断首尾两项的和是不是 target，如果比 target 小，那么我们左边 (i)+1 位置的数（比左边位置的数大）再和右相相加，继续判断。如果比 target 大，那么我们右边 (j)-1 位置的数（比右边位置的数小）再和左相相加，继续判断。我们通过这样不断放缩的过程，就可以在 O(n) 的时间复杂度内找到对应的坐标位置。

    验证回文串

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

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

示例 1:

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

示例 2:

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

 

    想法：提取原字符串中的数字和字母，对新串最后一个字符与第一个字符，倒数第二与第二个字符。。。。进行比较

// 想法：提取原字符串中的数字和字母，对新串最后一个字符与第一个字符，倒数第二与第二个字符。。。。进行比较
    public boolean isPalindrome(String s) {
        if(null == s || "".equals(s))
        {
            return true;
        }
        
        StringBuilder sb = new StringBuilder();
        char temp;
        for(int i = 0; i < s.length(); i++)
        {
            temp = s.charAt(i);
            if((temp >= '0' && temp <= '9') || (temp >= 'A' && temp <= 'Z') || (temp >= 'a' && temp <= 'z'))
            {
                sb.append(temp);
            }
        }
        
        String newStr = sb.toString().toLowerCase();
        
        if("".equals(newStr))
        {
            return true;
        }
        
        for(int i = 0; i < newStr.length()/2; i++)
        {
            if(newStr.charAt(i) != newStr.charAt(newStr.length() - 1 - i))
            {
                return false;
            }
        }
        
        return true;
    }

     我是正常思维，常规解法，下面来看一下更高效的解法

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

    上面显然更直接，用了一次循环，而我的做法更接近常规思维，用了两次循环

    解题思路

    采用对撞指针。

    反转字符串中的元音字母

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

示例 1:

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

示例 2:

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

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

    想法：两端寻找，小端要小于大端，两端都找到后交换，然后增大小端，减小大端，重复这个过程

// 两端寻找，小端要小于大端，两端都找到后交换，然后增大小端，减小大端，重复这个过程
    public String reverseVowels(String s) {
        if(null == s || s.length() == 0)
        {
        	return s;
        }
        
        char[] charArr = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        
        while(left < right)
        {
        	if(!isVowel(charArr[left]))
        	{
        		left++;
        	}
        	else if(!isVowel(charArr[right]))
        	{
        		right--;
        	}
        	else 
        	{
				char temp = charArr[left];
				charArr[left] = charArr[right];
				charArr[right] = temp;
                left++;
				right--;
			}
        }
        
        return Arrays.asList(charArr).stream().map(c -> String.valueOf(c)).reduce((a, b) -> a + b).get();
    }
    
    private boolean isVowel(char c)
    {
        String vowels = "aeiouAEIOU";
        
        return vowels.contains(c + "");
    }

     最后return用了lambda的语法，感觉有点低效，有点只为了做出结果不顾效率，看一下更好的解法

public String reverseVowels(String s) {
       if (s == null || s.trim().equals("")) return s;
        char[] cs = s.toCharArray();
        int low = 0,high = cs.length-1;
        while (low < high) {
            if (isVowelChar(cs[low])) {
                if (isVowelChar(cs[high])) {
                    char temp = cs[low];
                    cs[low] = cs[high];
                    cs[high] = temp;
                    low++;
                    high--;
                } else {
                    high--;
                }
            } else {
                low++;
            }
        }
        return String.valueOf(cs);
    }

    private boolean isVowelChar(char ch){
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U' ;
    }

    基本上就是return的地方不同，不知道可以用String.valueOf这个方法

    解题思路

    同样，也是采用对撞指针。

    盛最多水的容器

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

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

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

 

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

 

    想法：双端逼近，从一端找到更大值后再从另一端找，保证每次找到的值更大 

// 想法：双端逼近，从一端找到更大值后再从另一端找，保证每次找到的值更大
    public int maxArea(int[] height) {
        
        int left = 0;
        int right = height.length - 1;
        int actLeft = left;
        int actRight = right;
        int max = (right - left) * min(height[right], height[left]);
        boolean leftHit = true;
        boolean rightHit = true;
        boolean leftSeq = true;
        
        while(actLeft < actRight)
        {
            if(!leftHit && !rightHit)
            {
                actLeft = actLeft(actLeft, height);
                left = actLeft;
                leftHit = true;
                rightHit = true;
                continue;
            }
            
            if(leftSeq)
            {
                leftHit = false;
                while(right > left)
                {
                    left++;
                    if(max < (right - left) * (min(height[right], height[left])))
                    {
                        max = (right - left) * (min(height[right], height[left]));
                        actLeft = left;
                        actRight = right;
                        leftHit = true;
                    }

                }
                leftSeq = false;
            }
            else
            {
                rightHit = false;
                while(right > left)
                {
                    right--;
                    if(max < (right - left) * (min(height[right], height[left])))
                    {
                        max = (right - left) * (min(height[right], height[left]));
                        actLeft = left;
                        actRight = right;
                        rightHit = true;
                    }

                }
                leftSeq = true;
            }
            
            left = actLeft;
            right = actRight;
        }
        
        return max;
    }
    
    public int min(int a, int b)
    {
        return a < b ? a : b;
    }
              
    public int actLeft(int curLeft, int[] nums)
    {
        int result = nums.length;
        for(int i = curLeft + 1; i < nums.length; i++)
        {
            if(nums[curLeft] < nums[i])
            {
                result = i;
                break;
            }
        }
        
        return result;
    }

    从两端向中间找，两端时宽最大，向中间会找更高的，左右逼近找面积更大的，可以证明找到更大面积时不会出现左右中间的一个高度与左右之外的一个高度的高度更高，当前找到的高度是当前最优的，然后再向中间找更优的面积，算法是一点点抠出来的，用了两重循环，第二重中还套了两个循环，效率不行，而且还不容易看懂，看一下更好的算法

public int maxArea(int[] height) {
        int maxCap = 0;
        int tmp;
        for(int i = 0, j = height.length - 1; i < j;){
            if(height[i] < height[j]){
                tmp = (j - i) * height[i];
                if(tmp > maxCap){
                    maxCap = tmp;
                }
                i++;
            }
            else{
                tmp = (j - i) * height[j];
                if(tmp > maxCap){
                    maxCap = tmp;
                }
                j--;
                
            }   
        }
        return maxCap;
    }

    代码相当简洁，可以理解向中间的话只有更高的高度才可能产生更大的面积，所以要保留大的高度，舍弃小的高度

    解题思路

    我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxarea，并将指向较短线段的指针向较长线段那端移动一步。

    总结

    练习了双索引技巧中的对撞指针

亲爱的读者：有时间可以点赞评论一下