【算法攻坚】双指针技巧解题

发表于

这是我参与11月更文挑战的第12天，活动详情查看：2021最后一次更文挑战

前言

今天的题目按照顺序的话应该是第8题字符串转换整数 (atoi)，但是这道题完全是对字符串的边界转换考察，个人认为并没有什么算法思想，所以这次跳过第8题。

今日题目1

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：

输入：x = -101
输出：false

进阶：你能不将整数转为字符串来解决这个问题吗？

思路

前面刷到的第5题，最长回文子串中已经介绍了回文的意思

这里回文数，其实也是类似，回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数

这道题思路也是通过双指针方式，来判断前后是否相同

如果数字为负数，直接返回false，因为有‘-’所以一定不是回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码public boolean isPalindrome(int x) {
    if( x < 0){
        return false;
    }
    String s = String.valueOf(x);
    int left = 0, right = s.length()-1;

    while(left <= right){
        if(s.charAt(left) == s.charAt(right)){
            left++;
            right--;
        }else{
            return false;
        }
    }
    return true;
}

执行用时：6 ms, 在所有 Java 提交中击败了96.93%的用户

内存消耗：37.9 MB, 在所有 Java 提交中击败了46.32%的用户

解法二

再次看下回文数的定义 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数

也就说把数字翻转后与翻转前数值相当，这时就可以利用前文的整数翻转思路

1
2
3
4
5
6
7
8
9
10
11
12
13
java复制代码public boolean isPalindrome(int x) {
    if( x < 0){
        return false;
    }
    int temp = x;
    long result = 0;
    while(x != 0){
        int cuur = x %10;
        result = result * 10 + cuur;
        x = x /10;
    }
    return temp == result;
}

执行用时：5 ms, 在所有 Java 提交中击败了98.60%的用户

内存消耗：37.8 MB, 在所有 Java 提交中击败了54.14%的用户

今日题目2

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

说明：你不能倾斜容器。

示例 1：

img

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

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

思路

本题解法也是双指针，一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，

接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。

那该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。

这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。

把每次移动后的体积最大值保存，然后移动指针，为什么移动小的指针就可以呢？

这是因为高度由两边中矮的一边决定，

所以如果移动高的一边，即使遇到再高的，体积也不会变大

如果移动短的就可能变大，也可能变小

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java复制代码public int maxArea(int[] height) {
    int result = 0;
    int left = 0, right = height.length -1;
    while(left < right){
        //两边哪个短，移动哪个指针
        if(height[left] < height[right]){
            result = Math.max(result, height[left]*(right - left));
            left++;
        }else{
            result = Math.max(result, height[right]*(right - left));
            right--;
        }
    }
    return result;
}

执行用时：3 ms, 在所有 Java 提交中击败了92.67%的用户

内存消耗：51.8 MB, 在所有 Java 提交中击败了64.99%的用户

小结

从力扣第9/10题可以看出，双指针在解题中很常见，也很有用，通过几道题明显的感觉到比暴力破解快很多,类似的还有前文描述的三数之和等都是使用了双指针。

双指针，或者跟多的三指针问题都是有着一定的规律，这些题都有着不断压缩搜索距离的特征，以后再遇到类似的题目可以轻车熟路。

今天多学一点，明天就少说一句求人的话，加油！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%