首页目录 点击查看

第一题

• 难度：中等
• 题目：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