11. 盛最多水的容器 - 力扣(LeetCode) (leetcode-cn.com)

  • 思路:
  1. 设双指针i、j分别位于容器的两端,移动的时候同时更新面积的最大值res,直到i==j
  2. 为什么要这样移动?
    1. 因为面积值之和两个因素有关:
      1. 长度:两个垂直线的距离
      2. 宽度:两个垂直线其中较短的一条长度
    2. 那么要满足最大化,两个垂直线的距离越远越好,两个垂直线的最短的长度也要越长越好
  • 代码

    class Solution {
        public int maxArea(int[] height) {
            int i = 0, j = height.length - 1, res = 0;
            while(i != j){
                res = height[i] < height[j] ? 
                    Math.max(res, (j - i) * height[i++]): 
                	Math.max(res, (j - i) * height[j--]);
            }
            return res;
        }
    }
    

31. 下一个排列 - 力扣(LeetCode) (leetcode-cn.com)

  • 题目举例理解:

    123456
    123465
    123546
    ...
    654321
    即:123456<123465<123546<...<654321
    
  • 思路:

  1. 12587为例,那么答案就是12758,过程就是:12785->12758
  2. 就是先从右向左定位一个前面的数比后面的数小的数,那么此时可以定位到5。
  3. 然后再从右往左找第一个比这个锁定大的数,交换两个数,然后再reverse后面的。
  • 代码

    class Solution {
        public void nextPermutation(int[] nums) {
            // 1 2 5 8 7
            //ans
            // 1 2 7 5 8
            //process
            // 1 2 7 8 5
            // 1 2 7 5 8
            int n = nums.length;
            int i = n - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]){
                i--;
            }
            if(i >= 0){
                int j = n - 1;
                while(j > i && nums[j] <= nums[i]){
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1, n - 1);
        }
        private void swap(int[] nums, int low, int height){
            int temp = nums[low];
            nums[low] = nums[height];
            nums[height] = temp;
        }
        private void reverse(int[] nums, int low, int height){
            while(low < height){
                swap(nums, low++, height--);
            }
        }
    }
    

75. 颜色分类 - 力扣(LeetCode) (leetcode-cn.com)

  • 思路:(当然,本题的意思就是一个排序,自然可以使用自己知道的排序算法做,这里只是提供双指针的解法)
  1. 本题的意思就是Arrays.sort(nums),但是不能使用这个,如何实现一个排序,并且只有一次扫描?
  2. 判断长度,小于2,直接返回就好。
  3. 实现一个三段式,[0,zero)这部分全为0,[zero,i)全为1,[two,len-1]全为2
  4. 设置zero为0,为了保证初始化[0,zero)为空。这样遍历到0的时候,先交换再加。
  5. 设置two=len,为了保证初始化[two,len-1]为空,遍历到2的时候,先减再交换。
  6. 当i==two的时候,上面的三个子区间正好覆盖了全部数组,所以循环的条件是i < two,i初始值设置为0。
  7. 总结就是:只要扫描到了是0,就和zero交换,因为zero是用来控制[0,zero)范围的元素全部为0,同时让zero和i下标前移;扫描到了是1,i下标前移;扫描到了2,two后移,就和i交换,因为[two,len-1)范围内要满足为2。
  • 代码

    class Solution {
        public void sortColors(int[] nums) {
            int len = nums.length;
            if(len < 2){
                return;
            }
            //zero目的就是找到所有的0,zero向前走
            int zero = 0;
            //two目的是从后向前找所有的2,two向后走
            int two = len;
            //i是用来控制下标的,只要找到0或者1,都向前。
            int i = 0;
            //循环的条件就是i<
            while (i < two) {
                //找到一个0,就交换当前下标和zero下标的元素,同时zero向前,i也向前
                if (nums[i] == 0) {
                    swap(nums, i, zero);
                    zero++;
                    i++;
                } else if (nums[i] == 1) { //找到的是1,下标向前
                    i++;
                } else {	//找到的是2,two向后走,同时交换当前下标和two下标的元素。
                    two--;
                    swap(nums, i, two);
                }
            }
        }
    
        private void swap(int[] nums, int idx1, int idx2){
            int temp = nums[idx1];
            nums[idx1] = nums[idx2];
            nums[idx2] = temp;
        }
    }
    

415. 字符串相加 - 力扣(LeetCode) (leetcode-cn.com)

  • 思路:
  1. 思路和链表的两数相加是一样的,只不过的是这个是从后向前的。
  2. 所以使用到stringbuffer,因为可以翻转,初始化一个sb,i,j分别指向两个字符串的尾部,以及初始化一个进位数carry。
  3. 只要i或者j大于等于0就循环,如果某一个指针小于0,那么就设置那个数为0,进入求和,求和要带上进位数。
  4. 如果大于9,那么carry = sum /10,sum=sum-10,否则carry设置为0;
  5. 每次将sum添加到sb中,并且向左移动两个指针。
  6. 如果还有carry,那么添加一个进位数。
  7. 最后将sb翻转在toString。
  • 代码:

    class Solution {
        public String addStrings(String num1, String num2) {
            StringBuffer sb = new StringBuffer();
            int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
            while(i >= 0 || j >= 0){
                int n1 = i >= 0? num1.charAt(i) - '0' : 0;
                int n2 = j >= 0? num2.charAt(j) - '0' : 0;
                int temp = n1 + n2 + carry;
                if(temp > 9){
                    carry = temp / 10;
                    temp -= 10; 
                }else {
                    carry = 0;
                }
                sb.append(temp);
                i--;
                j--;
            }
            if(carry > 0){
                sb.append(carry);
            }
            return sb.reverse().toString();
        }
    }
    
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐