数组和矩阵
数组与矩阵相关题目
把数组中的 0 移到末尾
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
public void moveZeroes(int[] nums) { int idx = 0; for (int num : nums) { if (num != 0) { nums[idx++] = num; } } while (idx < nums.length) { nums[idx++] = 0; } }
改变矩阵维度
566. Reshape the Matrix (Easy)
Input: nums = [[1,2], [3,4]] r = 1, c = 4 Output: [[1,2,3,4]] Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
public int[][] matrixReshape(int[][] nums, int r, int c) { int m = nums.length, n = nums[0].length; if (m * n != r * c) { return nums; } int[][] reshapedNums = new int[r][c]; int index = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { reshapedNums[i][j] = nums[index / n][index % n]; index++; } } return reshapedNums; }
找出数组中最长的连续 1
485. Max Consecutive Ones (Easy)
public int findMaxConsecutiveOnes(int[] nums) { int max = 0, cur = 0; for (int x : nums) { cur = x == 0 ? 0 : cur + 1; max = Math.max(max, cur); } return max; }
有序矩阵查找
240. Search a 2D Matrix II (Medium)
[ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]
public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int m = matrix.length, n = matrix[0].length; int row = 0, col = n - 1; while (row < m && col >= 0) { if (target == matrix[row][col]) return true; else if (target < matrix[row][col]) col--; else row++; } return false; }
有序矩阵的 Kth Element
378. Kth Smallest Element in a Sorted Matrix ((Medium))
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13.
解题参考：Share my thoughts and Clean Java Code
二分查找解法：
public int kthSmallest(int[][] matrix, int k) { int m = matrix.length, n = matrix[0].length; int lo = matrix[0][0], hi = matrix[m - 1][n - 1]; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int cnt = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n && matrix[i][j] <= mid; j++) { cnt++; } } if (cnt < k) lo = mid + 1; else hi = mid - 1; } return lo; }
堆解法：
public int kthSmallest(int[][] matrix, int k) { int m = matrix.length, n = matrix[0].length; PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(); for(int j = 0; j < n; j++) pq.offer(new Tuple(0, j, matrix[0][j])); for(int i = 0; i < k - 1; i++) { // 小根堆，去掉 k - 1 个堆顶元素，此时堆顶元素就是第 k 的数 Tuple t = pq.poll(); if(t.x == m - 1) continue; pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y])); } return pq.poll().val; } class Tuple implements Comparable<Tuple> { int x, y, val; public Tuple(int x, int y, int val) { this.x = x; this.y = y; this.val = val; } @Override public int compareTo(Tuple that) { return this.val - that.val; } }
一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数
Input: nums = [1,2,2,4] Output: [2,3]
Input: nums = [1,2,2,4] Output: [2,3]
最直接的方法是先对数组进行排序，这种方法时间复杂度为 O(NlogN)。本题可以以 O(N) 的时间复杂度、O(1) 空间复杂度来求解。
主要思想是通过交换数组元素，使得数组上的元素在正确的位置上。
public int[] findErrorNums(int[] nums) { for (int i = 0; i < nums.length; i++) { while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) { swap(nums, i, nums[i] - 1); } } for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { return new int[]{nums[i], i + 1}; } } return null; } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
类似题目：
- 448. Find All Numbers Disappeared in an Array (Easy)，寻找所有丢失的元素
- 442. Find All Duplicates in an Array (Medium)，寻找所有重复的元素。
找出数组中重复的数，数组值在 [1, n] 之间
287. Find the Duplicate Number (Medium)
要求不能修改数组，也不能使用额外的空间。
二分查找解法：
public int findDuplicate(int[] nums) { int l = 1, h = nums.length - 1; while (l <= h) { int mid = l + (h - l) / 2; int cnt = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] <= mid) cnt++; } if (cnt > mid) h = mid - 1; else l = mid + 1; } return l; }
双指针解法，类似于有环链表中找出环的入口：
public int findDuplicate(int[] nums) { int slow = nums[0], fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } fast = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }
数组相邻差值的个数
667. Beautiful Arrangement II (Medium)
Input: n = 3, k = 2 Output: [1, 3, 2] Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
题目描述：数组元素为 1~n 的整数，要求构建数组，使得相邻元素的差值不相同的个数为 k。
让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 ... k/2 k/2+1.
public int[] constructArray(int n, int k) { int[] ret = new int[n]; ret[0] = 1; for (int i = 1, interval = k; i <= k; i++, interval--) { ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval; } for (int i = k + 1; i < n; i++) { ret[i] = i + 1; } return ret; }
数组的度
697. Degree of an Array (Easy)
Input: [1,2,2,3,1,4,2] Output: 6
题目描述：数组的度定义为元素出现的最高频率，例如上面的数组度为 3。要求找到一个最小的子数组，这个子数组的度和原数组一样。
public int findShortestSubArray(int[] nums) { Map<Integer, Integer> numsCnt = new HashMap<>(); Map<Integer, Integer> numsLastIndex = new HashMap<>(); Map<Integer, Integer> numsFirstIndex = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1); numsLastIndex.put(num, i); if (!numsFirstIndex.containsKey(num)) { numsFirstIndex.put(num, i); } } int maxCnt = 0; for (int num : nums) { maxCnt = Math.max(maxCnt, numsCnt.get(num)); } int ret = nums.length; for (int i = 0; i < nums.length; i++) { int num = nums[i]; int cnt = numsCnt.get(num); if (cnt != maxCnt) continue; ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1); } return ret; }
对角元素相等的矩阵
1234 5123 9512 In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
public boolean isToeplitzMatrix(int[][] matrix) { for (int i = 0; i < matrix[0].length; i++) { if (!check(matrix, matrix[0][i], 0, i)) { return false; } } for (int i = 0; i < matrix.length; i++) { if (!check(matrix, matrix[i][0], i, 0)) { return false; } } return true; } private boolean check(int[][] matrix, int expectValue, int row, int col) { if (row >= matrix.length || col >= matrix[0].length) { return true; } if (matrix[row][col] != expectValue) { return false; } return check(matrix, expectValue, row + 1, col + 1); }
嵌套数组
Input: A = [5,4,0,3,1,6,2] Output: 4 Explanation: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2. One of the longest S[K]: S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
题目描述：S[i] 表示一个集合，集合的第一个元素是 A[i]，第二个元素是 A[A[i]]，如此嵌套下去。求最大的 S[i]。
public int arrayNesting(int[] nums) { int max = 0; for (int i = 0; i < nums.length; i++) { int cnt = 0; for (int j = i; nums[j] != -1; ) { cnt++; int t = nums[j]; nums[j] = -1; // 标记该位置已经被访问 j = t; } max = Math.max(max, cnt); } return max; }
分隔数组
769. Max Chunks To Make Sorted (Medium)
Input: arr = [1,0,2,3,4] Output: 4 Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
题目描述：分隔数组，使得对每部分排序后数组就为有序。
public int maxChunksToSorted(int[] arr) { if (arr == null) return 0; int ret = 0; int right = arr[0]; for (int i = 0; i < arr.length; i++) { right = Math.max(right, arr[i]); if (right == i) ret++; } return ret; }
图
图相关题目
二分图
如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么这个图就是二分图。
判断是否为二分图
785. Is Graph Bipartite? (Medium)
Input: [[1,3], [0,2], [1,3], [0,2]] Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2: Input: [[1,2,3], [0,2], [0,1,3], [0,2]] Output: false Explanation: The graph looks like this: 0----1 | \ | | \ | 3----2 We cannot find a way to divide the set of nodes into two independent subsets.
public boolean isBipartite(int[][] graph) { int[] colors = new int[graph.length]; Arrays.fill(colors, -1); for (int i = 0; i < graph.length; i++) { // 处理图不是连通的情况 if (colors[i] == -1 && !isBipartite(i, 0, colors, graph)) { return false; } } return true; } private boolean isBipartite(int curNode, int curColor, int[] colors, int[][] graph) { if (colors[curNode] != -1) { return colors[curNode] == curColor; } colors[curNode] = curColor; for (int nextNode : graph[curNode]) { if (!isBipartite(nextNode, 1 - curColor, colors, graph)) { return false; } } return true; }
拓扑排序
常用于在具有先序关系的任务规划中。
课程安排的合法性
2, [[1,0]] return true
2, [[1,0],[0,1]] return false
题目描述：一个课程可能会先修课程，判断给定的先修课程规定是否合法。
本题不需要使用拓扑排序，只需要检测有向图是否存在环即可。
public boolean canFinish(int numCourses, int[][] prerequisites) { List<Integer>[] graphic = new List[numCourses]; for (int i = 0; i < numCourses; i++) { graphic[i] = new ArrayList<>(); } for (int[] pre : prerequisites) { graphic[pre[0]].add(pre[1]); } boolean[] globalMarked = new boolean[numCourses]; boolean[] localMarked = new boolean[numCourses]; for (int i = 0; i < numCourses; i++) { if (hasCycle(globalMarked, localMarked, graphic, i)) { return false; } } return true; } private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked, List<Integer>[] graphic, int curNode) { if (localMarked[curNode]) { return true; } if (globalMarked[curNode]) { return false; } globalMarked[curNode] = true; localMarked[curNode] = true; for (int nextNode : graphic[curNode]) { if (hasCycle(globalMarked, localMarked, graphic, nextNode)) { return true; } } localMarked[curNode] = false; return false; }
课程安排的顺序
210. Course Schedule II (Medium)
4, [[1,0],[2,0],[3,1],[3,2]] There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
使用 DFS 来实现拓扑排序，使用一个栈存储后序遍历结果，这个栈的逆序结果就是拓扑排序结果。
证明：对于任何先序关系：v->w，后序遍历结果可以保证 w 先进入栈中，因此栈的逆序结果中 v 会在 w 之前。
public int[] findOrder(int numCourses, int[][] prerequisites) { List<Integer>[] graphic = new List[numCourses]; for (int i = 0; i < numCourses; i++) { graphic[i] = new ArrayList<>(); } for (int[] pre : prerequisites) { graphic[pre[0]].add(pre[1]); } Stack<Integer> postOrder = new Stack<>(); boolean[] globalMarked = new boolean[numCourses]; boolean[] localMarked = new boolean[numCourses]; for (int i = 0; i < numCourses; i++) { if (hasCycle(globalMarked, localMarked, graphic, i, postOrder)) { return new int[0]; } } int[] orders = new int[numCourses]; for (int i = numCourses - 1; i >= 0; i--) { orders[i] = postOrder.pop(); } return orders; } private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked, List<Integer>[] graphic, int curNode, Stack<Integer> postOrder) { if (localMarked[curNode]) { return true; } if (globalMarked[curNode]) { return false; } globalMarked[curNode] = true; localMarked[curNode] = true; for (int nextNode : graphic[curNode]) { if (hasCycle(globalMarked, localMarked, graphic, nextNode, postOrder)) { return true; } } localMarked[curNode] = false; postOrder.push(curNode); return false; }
并查集
并查集可以动态地连通两个点，并且可以非常快速地判断两个点是否连通。
冗余连接
684. Redundant Connection (Medium)
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3
题目描述：有一系列的边连成的图，找出一条边，移除它之后该图能够成为一棵树。
public int[] findRedundantConnection(int[][] edges) { int N = edges.length; UF uf = new UF(N); for (int[] e : edges) { int u = e[0], v = e[1]; if (uf.connect(u, v)) { return e; } uf.union(u, v); } return new int[]{-1, -1}; } private class UF { private int[] id; UF(int N) { id = new int[N + 1]; for (int i = 0; i < id.length; i++) { id[i] = i; } } void union(int u, int v) { int uID = find(u); int vID = find(v); if (uID == vID) { return; } for (int i = 0; i < id.length; i++) { if (id[i] == uID) { id[i] = vID; } } } int find(int p) { return id[p]; } boolean connect(int u, int v) { return find(u) == find(v); } }
