6-图文打造LeeCode算法宝典-数组与排序算法题解

数组与排序

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
1
2
3
4
5
6
7

思路

双指针法

首先对数组进行排序，排序后固定一个数nums[i]nums[i]，再使用左右指针指向nums[i]后面的两端，数字分别为nums[L]nums[L]和nums[R]，计算三个数的和sum判断是否满足为 0，满足则添加进结果集

如果nums[i]大于 0，则三数之和必然无法等于 0，结束循环

如果nums[i] = nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过

当sum = 0时，nums[L] = nums[L+1]则会导致结果重复，应该跳过，L++

当sum =0 时，nums[R]= nums[R-1]则会导致结果重复，应该跳过，R–

时间复杂度：O(n^2)，n为数组长度

代码实现

public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //数组大小小于3
        if (nums == null || nums.length < 3){
            return res;
        }
        //排序
        Arrays.sort(nums);

        int len = nums.length;

        for (int i = 0 ; i < len; i++){
            if (nums[i] > 0)
                break;

            //去重
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            int l = i + 1;
            int r = len - 1;
            while (l < r && r > 0){
                int sum = nums[i] + nums[l] + nums[r];

                if(sum == 0){
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(nums[i]);
                    temp.add(nums[l]);
                    temp.add(nums[r]);
                    res.add(temp);

                    //去重
                    while (l < len-1 && nums[l] == nums[l+1]) l++;
                    while (r > 0 && nums[r] == nums[r-1]) r--;

                    r--;
                    l++;
                }else if (sum < 0){
                    l++;
                }else {
                    r--;
                }
            }
        }
        return res;
    }
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

岛屿的最大面积

岛屿的最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
1
2
3
4
5
6
7
8

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]
1

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

代码实现

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    int num = depthSearch(grid,i,j);
                    max = Math.max(num, max);
                }
            }
        }
        return max;
    }

    public int depthSearch(int[][] grid, int i, int j) {
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[i].length && grid[i][j] == 1) {
            grid[i][j] = 0;
            int num = 1 + depthSearch(grid, i + 1, j) + depthSearch(grid, i - 1, j) + depthSearch(grid, i, j + 1) + depthSearch(grid, i, j - 1);
             return num;
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
1
2

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
1
2

解法一

先二分查找数组中最大值的位置，将数组分成两个升序子数组，再在目标值所在的子数组内二分查找目标值。

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if(len == 0) return -1;
        int low = 0, high = len-1, mid = 0;
        while(low < high) {
            mid = (low+high) >>> 1;
            if(mid+1 <= high && nums[mid] > nums[mid+1]) break;
            if(nums[mid] > nums[high]) low = mid+1;
            else high = mid;
        }
        // 未旋转的情况
        if(low == high) return binarySearch(nums, 0, len-1, target);
        if(nums[len-1] < target) return binarySearch(nums, 0, mid, target);
        else return binarySearch(nums, mid+1, len-1, target);
    }
    private int binarySearch(int[] nums, int low, int high, int target) {
        int mid;
        while(low <= high) {
            mid = (low+high) >>> 1;
            if(nums[mid] < target) low = mid+1;
            else if(nums[mid] > target) high = mid-1;
            else return mid;
        }
        return -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

解法二

直接改造二分查找。

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length-1, mid;
        while(low <= high){
            mid = (low+high) >>> 1;
            if(nums[mid] < target){
                // 中值在右区间，目标值在左区间，需左移
                if(nums[low]>nums[mid] && nums[low]<=target) high = mid-1;
                // 正常情况，右移
                else low = mid+1;
            }else if(nums[mid] > target){
                // 中值在左区间，目标值在右区间，需右移
                if(nums[low]<=nums[mid] && nums[low]>target) low = mid+1;
                // 正常情况，左移
                else high = mid-1;
            }else return mid;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对比来看的话，解法二应该更优一点。

朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
1
2
3
4
5
6
7

示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
1
2
3
4
5
6

注意：

1. N 在[1,200]的范围内。
2. 对于所有学生，有M[i][i] = 1。
3. 如果有M[i][j] = 1，则有M[j][i] = 1。

解题思路：

在这一道题的二维数组，并且由题意可以看出i和j的对应关系可以将他们看成图中的一个节点，他们之间的关系可以看成一条线这样我们就可以将他们之间的一个朋友圈我们可以看成一个无向图（关于图可以参考这篇博客就不详细解释了），然后我们就可以通过图的DFS遍历和BFS遍历(可以参考这一篇博客)这一个图的所有节点即朋友圈的所有的同学。我是实现代码使用的是BFS，然后通过一个辅助数组来标识那个同学已经被遍历过了吧所有同学都遍历。

代码实现

class Solution {
    public int findCircleNum(int[][] M) {
        int len=M.length;
        if(len<2){
            return len;
        }
        int []help=new int[len];
        int cnt=0;
        for(int i=0;i<len;++i){
            if(help[i]==0){
                bfs(M,i,help);
                cnt++;
            }
        }
        return cnt;
    }
    private void bfs(int[][] graph,int node,int[] help){
        int[] queue=new int[graph.length];
        int cnt=1;
        queue[0]=node;
        help[node]=1;
        for (int i=0;i<cnt;++i){
            for (int j=0;j<graph[queue[i]].length;++j){
                if (queue[i]!=j&&graph[queue[i]][j]==1&&help[j]==0){
                        help[j]=1;
                        queue[cnt++]=j;
                }
            }
        }
    }
}
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

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
1
2

思路

双指针夹逼寻找雨水数的另一种简化形式

在思路二的实现中，对于左边界索引left是从数组头到数组尾方向看，第一次出现下降趋势的那个索引的位置。对于右边界索引right是从数组尾到数组头方向看，第一次出现下降趋势的那个索引的位置。

事实上， 上述步骤完全可以省略不写。因为在循环的判断里已经规定了只有满足height[left] < leftHeight或者height[right] < rightHeight时，才会对结果雨水数result进行更新。这两种情况对于从数组头到数组尾方向或者从数组尾到数组头方向看呈上升趋势或者的索引位置都是不满足要求的。

在循环过程中，如果出现了height[left] >= leftHeight的情况，直接进入下一轮循环更新leftHeight的值，这不是可以简化为直接取height[left]和leftHeight中的较大者作为leftHeight的值吗？对于height[right] >= rightHeight的情况也是同理。本思路就是这样产生的，时间复杂度和空间复杂度均与思路二相同。

代码实现

public class Solution {
	
	public int trap(int[] height) {
		int n = height.length;
		int result = 0;
		if(n == 0 || n == 1) {
			return result;
		}
		int left = 0;
		int right = n - 1;
		int leftHeight = 0;
		int rightHeight = 0;
		while(left < right) {
			if(height[left] <= height[right]) {
				leftHeight = Math.max(leftHeight, height[left]);
				result += leftHeight - height[left];
				left++;
			}else {
				rightHeight = Math.max(rightHeight, height[right]);
				result += rightHeight - height[right];
				right--;
			}
		}
		return result;
	}
}
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