283.移动 0 （easy） 2021-01-18
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
两个月前做过，居然一点印象也没。
class Solution { public void moveZeroes(int[] nums) { int n = nums.length, i = 0; for (int j = 0; j < n; j++){ if (nums[j] != 0) { nums[i++] = nums[j]; } } while (i < n) { nums[i++] = 0; } } }
566.重塑矩阵 （easy） 2021-01-18
在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
class Solution { public int[][] matrixReshape(int[][] nums, int r, int c) { if(r * c != nums.length * nums[0].length){ return nums; } int[][] ans = new int[r][c]; int a = 0, b = 0; for(int i = 0; i < r; i ++){ for(int j = 0; j < c; j ++){ ans[i][j] = nums[a][b]; b++; if(b == nums[0].length){ a++; b = 0; } } } return ans; } }
485.最长连续的 1 （easy） 2021-01-18
给定一个二进制数组， 计算其中最大连续1的个数。
class Solution { public int findMaxConsecutiveOnes(int[] nums) { int len = 0; int max = 0; for(int i = 0; i < nums.length; i++){ if(nums[i] == 1){ len++; } if(nums[i] != 1){ max = Math.max(max, len); len = 0; } } return Math.max(max, len); } }
240.搜索二维矩阵Ⅱ （medium） 2021-01-19
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
两个月前在剑指刷的题，居然忘得一干二净。
此题的关键在于找到矩阵的规律，从左下角开始检索，上面的比它小，右边的比它大。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int i = matrix.length - 1, j =0; while(i >= 0 && j < matrix[0].length){ if(matrix[i][j] == target){ return true; }else if(matrix[i][j] > target){ i--; }else{ j++; } } return false; } }
378.有序矩阵的第K个最小的元素 （medium） 2021-01-19
给定一个
n x n矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个不同的元素。
没有思路了，我要休息了。
这个题需要尤其注意，完全没有思路。
二分法( 比较通用的解法，事实上并没有用到矩阵中元素升序的信息 )：
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; } }
645.错误的集合 （easy） 2021-01-20
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
我的方法，排序暴力解法。
class Solution { public int[] findErrorNums(int[] nums) { int[] ans = new int[2]; Arrays.sort(nums); for(int i = 0 ; i < nums.length - 1; i++){ if(nums[i] == nums[i + 1]){ ans[0] = nums[i]; } if(nums[i + 1] - nums[i] == 2){ ans[1] = nums[i] + 1; } } if(nums[0] != 1){ ans[1] = 1; } if(nums[nums.length - 1] != nums.length){ ans[1] = nums.length; } return ans; } }
大佬的方法，时间复杂度为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; }
287.寻找重复数 （medium） 2021-01-21
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以在不修改数组 nums 的情况下解决这个问题吗？
你可以只用常量级 O(1) 的额外空间解决这个问题吗？
你可以设计一个时间复杂度小于 O(n2) 的解决方案吗？
哈哈哈哈，我用的双重循环方法，时间和空间完全都不满足进阶的要求，就不贴出来了。
重点看看二分法，比暴力双重循环复杂度小。
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; }
快慢指针，特别妙的算法，时间复杂度为O(n)。
这个算法太妙了，发明人简直天才。可用于判断单向链表是否有环，在此题中，可以将此数组抽象为链表进行操作。
举个例子，nums = [2,5,9,6,9,3,8,9,7,1]，构造成链表就是：2->[9]->1->5->3->6->8->7->[9]，也就是在[9]处循环。他们不一定在[9 ]处相遇，事实上它们在7 处相遇。
理论分析： 这里涉及到很严谨的数学分析。首先设数组长度为n, 环的长度为c ，那么数组外不属于环的部分长度为m = n - c。
快指针的速度是慢指针速度的2 倍， 同时出发，相遇时快指针比慢指针多走了整数倍 c 的长度。不妨看成c ,那么慢指针走的长度也为 c。所以，慢指针在环中的位置为 c - m。
第二次循环将快指针从头开始，并且速度和慢指针相同。那么当快指针行走m 步进环时， 慢指针也正好行走 m 步走到环的开始位置。两指针相遇，返回环口值。=
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.优美的排列Ⅱ （medium）2021-01-22
给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
② 如果存在多种答案，你只需实现并返回其中任意一种.
示例 1:
输入: n = 3, k = 1
输出: [1, 2, 3]
解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1
这个题又是完全没有思路，诶。
这种数学找规律的题真的是伤脑筋。需要k 个间隔，那么就让k 递减，然后正负交替放进数组。
697. 数组的度 （easy） 2021-01-23
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.
我的方法是，将数组存放进哈希表，然后找出最大的出现频次。遍历数组找出最大出现频次的几个数，每个数再遍历数组找出最先出现和最后出现的位置。算法可行，但是时间超出限制。
总所周知，以空间换时间。建立三个哈希表，分别存放频次，首次位置，末次位置。
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; }
766. 托普利茨矩阵 （easy） 2021-01-23
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
示例 1:
输入:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
输出: True
解释:
在上述矩阵中, 其对角线为:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是True。
class Solution { public boolean isToeplitzMatrix(int[][] matrix) { for(int i = 0; i < matrix.length; i++){ //行 if(!isToeplitzCatercorner(matrix, i, 0)){ return false; } } for(int i = 1; i < matrix[0].length; i++){ //列 if(!isToeplitzCatercorner(matrix, 0, i)){ return false; } } return true; } //判断（i，j）为起点的对角线的元素是否均相同 public boolean isToeplitzCatercorner(int[][] matrix, int a, int b){ int m = matrix.length; int n = matrix[0].length; int num = matrix[a][b]; int i = a, j = b; while(i < m && j < n){ if(matrix[i][j] != num){ return false; } i++; j++; } return true; } }
565. 嵌套数组 （medium） 2021-01-23
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
刚学了个快慢指针，迅速地用上了，但是漏洞不止一个。首先快指针比慢指针是快n圈而不是一圈，其次，我想用第二次快慢指针相遇的步长但是这种做法显然只针对nums[0]开始的循环链表，而不能搜索 整个链表。
整个算法逻辑还是挺清晰的，就是遍历然后将遍历到的元素标记为-1，若是遍历到-1则结束当前遍历，进入下一轮。
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. 最多能完成排序的块 （medium） 2021-01-23
数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例 1:
输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
数组的题目确实好多需要找数学规律，一开始看到这个题都毫无思路。
这个题有个规律就是，如果数组的前i 个数的最大值就是i ，那么这前 n 个数就可以分块。找个这个规律，medium题瞬间变easy。
class Solution { public int maxChunksToSorted(int[] arr) { int count = 0, max = 0; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); if(max == i) count++; } return count ; } }
原文：https://www.cnblogs.com/nobita/p/14295463.html