Leetcode-数组刷题记录

数组的遍历

485. 最大连续1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findMaxConsecutiveOnes(int[] nums) {
//res存储最长的子数组
int res = 0;
//count记录的是每个被0隔断的子数组
int count = 0;
for(int i = 0; i < nums.length; i++){
//如果当前元素是1,更新当前子数组的长度
if(nums[i] == 1){
count++;
}else {
//遇到0,比较res, count的大小,并将count重置为0
res = Math.max(res, count);
count = 0;
}
}
//避免最后一个子数组是最大的情况,例如:1,0,1,1,0,1,1,1,1
return Math.max(res, count);
}

495. 提莫攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findPoisonedDuration(int[] timeSeries, int duration) {
int res = 0;
for(int i = 0; i < timeSeries.length; i ++){
//当前能持续的时间
int time = timeSeries[i] + duration -1;
//超过下一次攻击的时间
if(i != timeSeries.length -1 && time >= timeSeries[i + 1]){
res += (timeSeries[i + 1] - timeSeries[i]);
}else{
res += duration;
}
}
return res;
}

第三大的数

时间复杂度要求\(O(n)\),也就是只能通过一趟遍历完成。

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
public int thirdMax(int[] nums) {
if(nums.length == 1){
return nums[0];
}
if(nums.length == 2){
return nums[0] >= nums[1] ? nums[0] : nums[1];
}
long firstMax = Long.MIN_VALUE;
long secondMax = Long.MIN_VALUE;
long thirdMax = Long.MIN_VALUE;
//判断相等情况是避免相同数字,例如:[2, 2, 3, 1]
for(int num : nums){
if(num > firstMax) {
thirdMax = secondMax;
secondMax = firstMax;
firstMax = num;
}else if(num == firstMax) {
continue;
}else if(num > secondMax){
thirdMax = secondMax;
secondMax = num;
}else if(num == secondMax) {
continue;
}else if(num > thirdMax){
thirdMax = num;
}
}
if(thirdMax == Long.MIN_VALUE){
return (int)firstMax;
}else{
return (int) thirdMax;
}
}

628. 三个数的最大乘积

偷🐔解法,需要注意考虑负数的情况。

时间复杂度为\(O(nlogN)\)

1
2
3
4
5
6
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
return Math.max(nums[0] * nums[1] * nums[nums.length - 1],
nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]);
}

如果使用一趟遍历的方法,那么需要使用五个变量,分别保存最大的三个数,和最小的两个数。

统计数组中的元素

645. 错误的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
int[] count = new int[nums.length];
for(int num : nums){
count[num - 1]++;
}
for(int i = 0; i< count.length;i++){
if(count[i] == 2){
res[0] = i + 1;
}else if(count[i] == 0){
res[1] = i + 1;
}
}
return res;
}

697. 数组的度

三个HashMap的作用分别如下:

  • left:数字第一次出现的索引
  • right:数字最后一次出现的索引
  • count:数字出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> left = new HashMap(),
right = new HashMap(), count = new HashMap();

for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (left.get(x) == null) left.put(x, i);
right.put(x, i);
count.put(x, count.getOrDefault(x, 0) + 1);
}

int ans = nums.length;
int degree = Collections.max(count.values());
for (int x: count.keySet()) {
if (count.get(x) == degree) {
ans = Math.min(ans, right.get(x) - left.get(x) + 1);
}
}
return ans;
}

448. 找到所有数组中消失的数字

HashMap做记录,再通过一轮遍历找到不存在的数字。

时间复杂度\(O(n)\),空间复杂度\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> findDisappearedNumbers(int[] nums) {
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], true);
}
List<Integer> res = new LinkedList<Integer>();
for (int i = 1; i <= nums.length; i++) {
if (!map.containsKey(i)) {
res.add(i);
}
}
return res;
}

如果使用时间复杂度\(O(n)\),并不用额外的空间,可以通过添加标记来解决。

一轮遍历添加标记:能标识该数字出现过。

第二轮遍历查找没有做标记的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int index = (nums[i] - 1) % nums.length;
nums[index] += nums.length;
}
List<Integer> res = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
if(nums[i] <= nums.length){
res.add(i + 1);
}
}
return res;
}

442. 数组中重复的数据

与上面一题异曲同工。使用标记法。

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> findDuplicates(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int index = (nums[i] - 1) % nums.length;
nums[index] += nums.length;
}
List<Integer> res = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
if(nums[i] > nums.length * 2){
res.add(i + 1);
}
}
return res;
}

41. 缺失的第一个正数

通过索引交换元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while((nums[i] >= 1 && nums[i] <= nums.length) && (nums[i] != nums[nums[i] - 1])){
int temp = nums[i];
nums[i] = nums[temp -1];
nums[temp -1] = temp;
}
}
int res = nums.length + 1;
for(int i = 0; i < nums.length; i++){
if (nums[i] != (i + 1)) {
res = i + 1;
break;
}
}
return res;
}

274. H指数

偷🐔了一下,直接sort解决。

1
2
3
4
5
6
7
8
9
10
11
public int hIndex(int[] citations) {
int len = citations.length;
Arrays.sort(citations);
for(int i = 0; i < len; i++){
int count = len - i;
if(citations[i] >= count){
return count;
}
}
return 0;
}

数组的改变、移动

453. 最小操作次数使数组元素相等

每次操作会使\(n-1\)个元素增加1 == > 每次操作让一个元素减去1

因此需要计算的次数就是:数组中所有元素(除去最小值)与最小值之间的差值。

(Python的API用的舒服)

1
2
3
4
5
6
def minMoves(self, nums):
sum = 0
minnum = min(nums)
for i in nums:
sum += i - minnum
return sum

665. 非递减数列

拐点不能出现两次,修复会有两种情况:

  • nums[i - 2] > nums[i]:将nums[i]改为nums[i - 1]
  • nums[i - 2] <= nums[i]:将nums[i - 1]改为nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean checkPossibility(int[] nums) {
int count = 0;
for(int i = 1 ; i< nums.length; i++){
if(nums[i - 1] > nums[i]){
count++;
if(count >= 2) return false;
if(i - 2 >= 0 && nums[i - 2] > nums[i]){
nums[i] = nums[i - 1];
}else{
nums[i - 1] = nums[i];
}
}
}
return true;
}

283. 移动零

通过index存储有效位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
while (index < nums.length) {
nums[index++] = 0;
}
}

二维数组及滚动数组

118. 杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for(int i = 0; i < numRows; i++){
List<Integer> list = new ArrayList<>();
list.add(1);
for(int j = 1; j < i; j++){
List<Integer> front = ans.get(i - 1);
list.add(front.get(j) + front.get(j -1));
}
if(i > 0){
list.add(1);
}
ans.add(list);
}
return ans;
}

119. 杨辉三角Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for(int i = 0; i <= rowIndex; i++){
List<Integer> list = new ArrayList<>();
list.add(1);
for(int j = 1; j < i; j++){
List<Integer> front = ans.get(i - 1);
list.add(front.get(j) + front.get(j -1));
}
if(i > 0){
list.add(1);
}
ans.add(list);
}
return ans.get(rowIndex);
}

598. 范围求和Ⅱ

1
2
3
4
5
6
7
8
public int maxCount(int m, int n, int[][] ops) {
int minX = m , minY = n;
for(int i = 0; i < ops.length; i++){
minX = Math.min(minX, ops[i][0]);
minY = Math.min(minY, ops[i][1]);
}
return minX * minY;
}

419. 甲板上的战舰

暴力判断:如果当前点是X,判断其左边和上边是否有X,没有则不连通,增加计数。

1
2
3
4
5
6
7
8
9
10
11
12
public int countBattleships(char[][] board) {
int count = 0;
for(int i = 0; i <board.length; i++){
for(int j = 0; j < board[i].length; j++){
if(board[i][j] == 'X'){
if(i > 0 && board[i - 1][j] == 'X' || j > 0 && board[i][j - 1] == 'X') continue;
count++;
}
}
}
return count;
}

189. 数组的旋转

三轮reverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void rotate(int[] nums, int k) {
//如果数组长度小于旋转次数,那么执行k次和执行k % length次结果一样
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}

private void reverse(int[] nums, int start, int end) {
while (start < end) {
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
start++;
end--;
}
}

396. 旋转函数

可通过数学归纳法得到\(F[k]= F[k-1] + sum - n*A[n-k]\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxRotateFunction(int[] A) {
int n = A.length;
int max = 0;
int count = 0;
// 统计数组所有数的和
int sum = 0;
// 计算 F(1) 的值
for (int i : A) {
max += count++ * i;
sum += i;
}
int tmp = max;
for (int i = 1; i < n; i++) {
tmp = tmp + sum - n * A[n - i];
max = Math.max(tmp, max);
}
return max;
}

特定顺序遍历二维数组

54. 螺旋矩阵

抓住两个index的变化趋势,按照规律变化就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
int up = 0, down = m - 1, left = 0, right = n -1;
while(true){
for(int i = left; i <= right; i++) res.add(matrix[up][i]);
if(++up > down) break;
for(int i = up; i <= down; i++) res.add(matrix[i][right]);
if (--right < left) break;
for(int i = right; i >= left; i--) res.add(matrix[down][i]);
if (--down < up) break;
for(int i = down; i >= up; i--) res.add(matrix[i][left]);
if(++left > right) break;
}
return res;
}

59. 螺旋矩阵Ⅱ

和上题一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int up = 0, down = n - 1, left = 0, right = n -1;
int num = 1;
while(true){
for(int i = left; i <= right; i++) matrix[up][i] = num++;
if(++up > down) break;
for(int i = up; i <= down; i++) matrix[i][right] = num++;
if (--right < left) break;
for(int i = right; i >= left; i--) matrix[down][i] = num++;
if (--down < up) break;
for(int i = down; i >= up; i--) matrix[i][left] = num++;
if(++left > right) break;
}
return matrix;
}

498. 对角线遍历

二维数组变换

566. 重塑矩阵

笨方法,放入队列中,然后逐个按序取出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] res = new int[r][c];
if (nums.length == 0 || r * c != nums.length * nums[0].length)
return nums;
int count = 0;
Queue <Integer> queue = new LinkedList < > ();
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
queue.add(nums[i][j]);
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
res[i][j] = queue.remove();
}
}
return res;
}

原地算法:

  • \(count\)用于保存当前到第几个元素
  • \(count / c\)用于计算当前是第几行,\(count % c\)用于计算当前是第几个。
1
2
3
4
5
6
7
8
9
10
11
12
13
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] res = new int[r][c];
if (nums.length == 0 || r * c != nums.length * nums[0].length)
return nums;
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
res[count / c][count % c] = nums[i][j];
count++;
}
}
return res;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!