数组

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 题目：https://leetcode-cn.com/problems/container-with-most-water/
 * 题解：https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
 */
@Test
public void test() {
    int[] test = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
    System.out.println(maxArea2(test));
}

/**
 * 暴力解法
 * @param height
 * @return
 */
public int maxArea1(int[] height) {
    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i));
        }
    }
    return maxArea;
}

/**
 * 双指针法
 * @param height
 * @return
 */
public int maxArea2(int[] height) {
    int i = 0, j = height.length - 1, maxArea = 0;
    while (i < j) {
        maxArea = height[i] > height[j] ?
                Math.max(maxArea, (j - i) * height[j--]) :
                Math.max(maxArea, (j - i) * height[i++]);
    }
    return maxArea;
}

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 题目：https://leetcode-cn.com/problems/move-zeroes/
 * 题解：https://leetcode-cn.com/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/
 */
@Test
public void test() {
    int[] test = new int[]{0, 1, 0, 3, 12};
    moveZeroes1(test);
    moveZeroes2(test);
}

public void moveZeroes1(int[] nums) {
    // 纪录0出现的个数
    int count = 0;
    // 遍历数组将非0元素前提
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[count++] = nums[i];
        }
    }
    // 将 count-nums.length 全部置为0
    for (int i = count; i < nums.length; i++) {
        nums[i] = 0;
    }
    System.out.println(Arrays.toString(nums));
}

/**
 * 快慢指针
 *
 * @param nums
 */
public void moveZeroes2(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            if (i > j) {
                nums[j] = nums[i];
                nums[i] = 0;
            }
            j++;
        }
    }
    Syste.out.println(Arrays.toString(nums));
}

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
    * 题目：https://leetcode-cn.com/problems/climbing-stairs/
    * 题解：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
    */
   @Test
   public void test() {
       System.out.println(climbStairs(3));
   }

   public int climbStairs(int n) {
       int p = 0;
       int q = 0;
       int r = 1;
       for (int i = 1; i <= n; i++) {
           p = q;
           q = r;
           r = p + q;
       }
       return r;
   }

1. 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
    * 题目：https://leetcode-cn.com/problems/two-sum/
    * 解析：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
    */
   @Test
   public void test() {
       System.out.println(Arrays.toString(twoSum1(new int[]{1, 3, 4, 2}, 6)));
       System.out.println(Arrays.toString(twoSum2(new int[]{1, 3, 4, 2}, 6)));
       System.out.println(Arrays.toString(twoSum3(new int[]{1, 3, 4, 2}, 6)));
   }

   /**
    * 暴力求解
    *
    * @param nums
    * @param target
    * @return
    */
   public int[] twoSum1(int[] nums, int target) {
       // 双重for循环遍历，将所有的可能全部列举，一一与target比较
       for (int i = 0; i < nums.length; i++) {
           for (int j = i + 1; j < nums.length; j++) {
               if (nums[i] + nums[j] == target) {
                   return new int[]{i, j};
               }
           }
       }
       throw new IllegalArgumentException("No two sum solution");
   }

   /**
    * 两遍哈希表
    *
    * @param nums
    * @param target
    * @return
    */
   public int[] twoSum2(int[] nums, int target) {
       Map<Integer, Integer> hashMap = new HashMap<>();
       // 遍历数组将数组中的值-下标保存到hashMap中
       for (int i = 0; i < nums.length; i++) {
           hashMap.put(nums[i], i);
       }
       // 遍历数组，如果hashMap中存在target - nums[i] 这个值&&该值的下标不等于i（防止数组中正好target - nums[i]为其本身，例如6 - 3 = 3），
       // 那么就立即返回结果
       for (int i = 0; i < nums.length; i++) {
           if (hashMap.containsKey(target - nums[i]) && hashMap.get(target - nums[i]) != i) {
               return new int[]{i, hashMap.get(target - nums[i])};
           }
       }
       throw new IllegalArgumentException("No two sum solution");
   }

   /**
    * 一遍哈希表
    *
    * @param nums
    * @param target
    * @return
    */
   public int[] twoSum3(int[] nums, int target) {
       Map<Integer, Integer> hashMap = new HashMap<>();
       // 一边将元素保存到hashMap中，一边同时进行检查，如果找到符合的条件立即返回
       for (int i = 0; i < nums.length; i++) {
           if (hashMap.containsKey(target - nums[i]) && hashMap.get(target - nums[i]) != i) {
               // 之所以{hashMap.get(target - nums[i]), i}而不是{i, hashMap.get(target - nums[i])}
               // 是因为hashMap最后的那个元素，i永远比hashMap.get(target - nums[i])大
               return new int[]{hashMap.get(target - nums[i]), i};
           }
           hashMap.put(nums[i], i);
       }
       throw new IllegalArgumentException("No two sum solution");
   }

15. 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 题目：https://leetcode-cn.com/problems/3sum/
 * 题解：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
 */
@Test
public void test() {
    System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    System.out.println(threeSum(new int[]{0, 0, 0, 0, 0, 0}));
}

public List<List<Integer>> threeSum(int[] nums) {
    ArrayList<List<Integer>> list = new ArrayList<>();
    // 排序
    Arrays.sort(nums);
    int n = nums.length;
    // 数组长度小于三，无意义
    if (n < 3) {
        return list;
    }
    for (int i = 0; i < n; i++) {
        // 最小的都大于0，肯定不存在结果 a + b + c = 0;
        if (nums[i] > 0) {
            break;
        }
        // i>0 防止i=0的时候 i-1=-1；去重，前一个值等于后一个值已经计算过，不能重复计算
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // l 指向i的前一个位置
        int l = i + 1;
        // r 指向数组的最后一个位置
        int r = n - 1;
        // l 指针不能大于r
        while (l < r) {
            // 计算这三个数的值
            int result = nums[i] + nums[l] + nums[r];
            if (result == 0) {
                // 等于0添加到列表中
                list.add(Arrays.asList(nums[i], nums[l], nums[r]));
                // 去重，防止存在重复元素，导致结果重复
                while (l < r && nums[l] == nums[l + 1]) {
                    l++;
                }
                // 去重，同理上
                while (l < r && nums[r] == nums[r - 1]) {
                    r--;
                }
                // 左指针++
                l++;
                // 右指针--
                r--;
            } else if (result > 0) {
                // a + b + c > 0 说明这个 c太大 要减小 自然 r-- 指向c的前一个位置 （注意这是排过序的数组）
                r--;
            } else {
                // 同理上
                l++;
            }
        }
    }
    return list;
}

这个题目真的需要自己去思考，debug调试一下，我写的注释仅仅是我个人理解。

链表