leetCode之数组操作
2020-09-28 本文已影响0人
Benzic
首页目录 点击查看
第一题
- 难度：中等
- 题目：54. 螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
解题思路
- 这道题我得想法是，通过方向判断，在边界内找到，下一个数排入数组的数是什么，用
turn分别表示上下左右四个放下，每改变一次方向，代表着它刚所处的行或者列不可再被选中，就要缩小边界。
我的答案
var spiralOrder = function (matrix) {
let array = []
if (!matrix.length) return array
let row = 0;
let len = matrix.length;
let rowLen = matrix[0].length
let col = 0;
let turn = rowLen - 1 === 0 ? "b" : "r"
let boxL = 0;
let boxR = rowLen - 1;
let boxU = 0;
let boxD = len - 1;
while (array.length < (len * rowLen)) {
!array.includes(matrix[row][col]) && array.push(matrix[row][col])
if (turn === 'b') {
row++
if (row == boxD) {
boxR--
turn = 'l'
}
} else if (turn === 'l') {
col--
if (col == boxL) {
boxD--
turn = 't'
}
} else if (turn === 't') {
row--
if (row == boxU) {
boxL++
turn = 'r'
}
} else if (turn === 'r') {
col++
if (col == boxR) {
boxU++
turn = 'b'
}
}
}
return array
};
image.png
第二题
- 难度：简单
- 题目： 59. 螺旋矩阵 II
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
解题思路
- 这道题和第一题基本思路是一样的，只是说根据，顺序填入数字就可以了，所以这里只需要创建一个变量
num用于保存递增的数字。
我的答案
var generateMatrix = function (n) {
let array = [];
let row = 0;
let col = 0;
let num = 0;
let turn = "r"
let boxL = 0;
let boxR = n - 1;
let boxU = 0;
let boxD = n - 1;
if (n === 0) return array;
while (num < (n * n)) {
num += 1;
if (!array[row]) {
array[row] = []
};
array[row][col] = num;
if (turn === 'b') {
row++
if (row == boxD) {
boxR--
turn = 'l'
}
} else if (turn === 'l') {
col--
if (col == boxL) {
boxD--
turn = 't'
}
} else if (turn === 't') {
row--
if (row == boxU) {
boxL++
turn = 'r'
}
} else if (turn === 'r') {
col++
if (col == boxR) {
boxU++
turn = 'b'
}
}
}
return array
};
image.png
第三题
- 难度：中等
- 题目：73. 一维数组的动态和
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
解题思路
- 这道题首先遍历一次，取出需要清空的行和列角标，然后分别取出角标清空原有数据
我的答案
var setZeroes = function (matrix) {
let len = matrix.length
let rowLen = matrix[0].length
let row = 0;
let col = 0
let num = 0;
let changeRow = []
let changeCol = []
while (num < (len * rowLen)) {
num++;
if (matrix[row][col] === 0) {
!changeRow.includes(row) && changeRow.push(row);
!changeCol.includes(col) && changeCol.push(col)
}
if (col < rowLen - 1) {
col++
} else {
col = 0
row++
}
}
while (changeRow.length || changeCol.length) {
while (changeCol.length) {
let sRow = 0;
let tcol = changeCol.pop()
while (sRow <= len - 1) {
matrix[sRow][tcol] = 0
sRow++
}
}
while (changeRow.length) {
let sCol = 0;
let trow = changeRow.pop()
while (sCol <= rowLen - 1) {
matrix[trow][sCol] = 0
sCol++
}
}
}
return matrix
};
image.png
第四题
- 难度：中等
- 题目：1395. 统计作战单位数
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
每 3 个士兵可以组成一个作战单位，分组规则如下：
从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
示例
输入：rating = [2,5,3,4,1]
输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
输入：rating = [2,1,3]
输出：0
解释：根据题目条件，我们无法组建作战单位。
解题思路
- 这道题首先想到的是非常暴力的三循环遍历，然后看了题解的答案发现了枚举中间点的方法处理，性能更佳。我们也可以枚举三元组 (i, j, k)(i,j,k) 中的 j，它是三元组的中间点。在这之后，我们统计：
出现在位置 j 左侧且比 j 评分低的士兵数量 leftLess；
出现在位置 j 左侧且比 j 评分高的士兵数量 leftMore；
出现在位置 j 右侧且比 j 评分低的士兵数量 rightless；
出现在位置 j 右侧且比 j 评分高的士兵数量 rightMore。
这样以来，任何一个出现在 leftLess中的士兵 j，以及出现在rightMore中的士兵 z，都可以和 i组成一个严格单调递增的三元组；同理，任何一个出现在 leftMore中的士兵 j，以及出现在rightless中的士兵 k，都可以和 i 组成一个严格单调递减的三元组。因此，以 jj 为中间点的三元组的数量为：
num += leftLess * rightMore + leftMore * rightLess
我们将所有的值进行累加即可得到答案。
我的答案
- 暴力三循环
var numTeams = function (rating) {
let num = 0;
for (let i = 0; i <= rating.length - 1; i++) {
for (let j = i + 1; j <= rating.length - 1; j++) {
for (let z = j + 1; z <= rating.length - 1; z++) {
if (rating[i] < rating[j] && rating[j] < rating[z]) {
num += 1
} else if (rating[i] > rating[j] && rating[j] > rating[z]) {
num += 1
}
}
}
}
return num
};
-
时间复杂度：O(N3)
-
空间复杂度： O(1)
image.png
-
枚举中间点
var numTeams = function (rating) {
let num = 0;
for (let i = 0; i <= rating.length - 1; i++) {
let leftLess = 0,
leftMore = 0;
let rightLess = 0,
rightMore = 0;
for (let j = 0; j <= i; j++) {
if (rating[j] > rating[i]) {
leftMore += 1
}
if (rating[j] < rating[i]) {
leftLess += 1
}
}
for (let z = i + 1; z <= rating.length - 1; z++) {
if (rating[z] > rating[i]) {
rightMore += 1
}
if (rating[z] < rating[i]) {
rightLess += 1
}
}
num += leftLess * rightMore + leftMore * rightLess
}
return num
};
- 时间复杂度：O(N2)
-
空间复杂度： O(1)
image.png
