吉林网站备案/辽源seo

1.旋转图像

题目：

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

思路：首先思考，旋转图像90度的效果。其实可以先按照对角线镜像翻转，然后按水平/竖直的中心线镜像翻转得到。

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var rotate = function(matrix) {const l = matrix.length;for (let i = 0; i < l - 1; i++) {for (let j = 0; j + i < l - 1; j++) {[matrix[i][j], matrix[l - 1 - j][l - 1 - i]] = [matrix[l - 1 - j][l - 1 - i],matrix[i][j],];}}for (let i = 0; i < l / 2; i++) {for (let j = 0; j < l; j++) {[matrix[i][j], matrix[l - 1 - i][j]] = [matrix[l - 1 - i][j],matrix[i][j],];}}
};

2.字母异位词分组

题目：给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

思路：用map记录异位词，然后分组，分组的方法很简单，对字符串排序即可

/*** @param {string[]} strs* @return {string[][]}*/
var getS = (s) => {return [...s].sort().join("");
};
var groupAnagrams = function (strs) {const map = new Map();for (const i of strs) {const as = getS(i);const a = map.get(as);if (!a) {map.set(as, [i]);} else {a.push(i);}}return [...map.values()];
};

3.pow(x,n)

题目：实现 pow(x, n) ，即计算 x 的 n 次幂函数。

思路：迭代可以，不过比较耗时。我们可以用递归，以空间换时间

注意到，对于n小于0，则计算pow(x,-n)的倒数。

如果n为偶数，则pow(x,n)=pow(x*x,n/2)，

如果n为奇数，则pow(x,n)=x*pow(x*x,n/2)，

最终实现递归

/*** @param {number} x* @param {number} n* @return {number}*/
var myPow = function(x, n) {if (n == 0) return 1;if (n < 0) return 1 / myPow(x, -n);if (n % 2) return x * myPow(x, n - 1);return myPow(x * x, n / 2);
};

4.螺旋矩阵

题目：

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

思路：可以发现，螺旋矩阵的终止条件是遍历次数超过平m*n，然后，我们需要一个值记录方向，另一个值记录到第几圈

  const res = [];const m = matrix.length;if(!m)return resconst n = matrix[0].length;if (!m) return res;let horiFlag = true;let verFlag = true;let count = 0;let i = 0;let j = 0;let a = 0;while (count < m * n) {count++;res.push(matrix[i][j]);if (verFlag && horiFlag) {if (j == n - 1 - i) {verFlag = false;i++;} else {j++;}} else if (horiFlag && !verFlag) {if (i == m - 1 - a) {horiFlag = false;j--;} else {i++;}} else if (!verFlag && !horiFlag) {if (j == a) {verFlag = true;i--;} else {j--;}} else {if (i == a+1) {horiFlag = true;a++;j++;} else {i--;}}}return res;

5.跳跃游戏

题目：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

思路：遍历数组，当前位置能够跳跃的最大值是当前下标+当前的值。用一个变量记录累计的最大值，如果到某个位置，最大值小于等于当前的下标，说明不能跳跃到终点。遍历完之后，判断最大位置和数组最大下标即可

/*** @param {number[]} nums* @return {boolean}*/var canJump = function (nums) {
const l=nums.length-1;
let dis=0;
for(let i=0;i<l;i++){dis=Math.max(i+nums[i],dis)if(dis<=i)return falseif(dis>=l)return true
}
return dis>=l
};

换个思路，有相加就有相减。可以从后往前遍历，某个点能到达终点，那么到达这个点就能到终点，。以此类推，直到起点也满足

/*** @param {number[]} nums* @return {boolean}*/var canJump = function (nums) {var lastPos = nums.length - 1;for (var i = lastPos - 1; i >= 0; i--) {if (i + nums[i] >= lastPos) {lastPos = i;}}return lastPos == 0;
};