编写目的
准备循序渐进地刷算法题和数据结构，每天2到3条算法题，几天时间将初始算法的数组篇搞定，这里将算法题总结一遍还有把自己的一些知识盲区挑出来，加深印象。
1.从排序数组中删除重复元素
这里题干里面也有说，不需要考虑超出范围的数组后的项。而且遍历的数组是已经排好序的数组，所以解题思路为：
从前往后遍历数组，遇到重复的忽略，遇到不同的将值放在已经遍历的前项上，重复此操作，直到遍历完毕。
我的解法：我最开始解题的时候没有懂题意，用了 splice 进行重复元素的切割
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/** * @param {number[]} nums * @return {number} */ // my algorithm var removeDuplicates = function (nums) { var flag = true; while (flag) { flag = false; for (var i = 0; i < nums.length - 1; i++) { for (var j = i + 1; j < nums.length; j++) { if (nums[i] === nums[j]) { nums.splice(j, 1); flag = true; } } } } return nums.length; };
答案解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// awnser algorithm var removeDuplicates_answer = function (nums) { if (nums.length === 0) { return 0; } var number = 0; for (var i = 0; i < nums.length; i++) { if (nums[i] !== nums[number]) { number++; nums[number] = nums[i]; } } number++; return number; };
巧用api解法：若允许使用filter，则可以用filter解决：
1
2
3
4
5
6// filter api var removeDuplicates_filter = function (nums) { return nums.filter((item, index, self) => { return self.indexOf(item) === index; }); }
2.购买股票的最佳时机
遍历数组，遇到低价买入，遇到高价卖出，从中赚取差价。此题没有什么特别值得注意的地方
答案解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14/** * @param {number[]} prices * @return {number} */ // answer algorithm var maxProfit_answer = function (prices) { var max = 0; for (var i = 0; i < prices.length; i++) { if (prices[i] < prices[i + 1]) { max += prices[i + 1] - prices[i]; } } return max; }
3.旋转数组
类似于数位的循环右移n位，位对应数字的元素。
我的解法：右移n步相当于执行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/** * @param {number[]} nums * @param {number} k * @return {void} Do not return anything, modify nums in-place instead. */ // my algorithm var rotate = function (nums, k) { // ------容错------ if (k < 1) { return; } if (nums.length < 2) { return; } // ------容错------ var init = nums[0]; var temp; var index; while (k > 0) { for (var i = 0; i < nums.length; i++) { index = (i + 1) % nums.length; temp = nums[index]; nums[index] = init; init = temp; } k--; init = nums[0]; } };
api解法：旋转数组其实换个角度想就是切割数组的一部分并且换个顺序拼接，于是有了如下的大神解法：
1
2
3
4
5
6// unshift splice ... var rotate_answer = function (nums, k) { let l = nums.length; k %= l; nums.unshift(...nums.splice(l - k, k)); }
4.存在重复元素
判断数组内部是否存在重复元素
答案解法：充分利用数据结构的知识，集合Set就是一个没有重复元素的数据结构：
1
2
3
4
5
6
7
8/** * @param {number[]} nums * @return {boolean} */ // answer algorithm var containsDuplicate_answer = function(nums) { return new Set(nums).size !== nums.length; }
5.只出现一次的数字
数组中有且仅有一个唯一数字，其余均是出现两次，找出那个唯一数字
我的解法：O(n^2)找出那个唯一数字，不太可行但可以解决
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/** * @param {number[]} nums * @return {number} */ // my algorithm var singleNumber = function(nums) { var len = nums.length; var result,flag = false; for(var i = 0;i < len;i++) { for(var j = 0;j < len;j++) { if(nums[i] === nums[j] && i !== j) { flag = true; break; } } if(!flag) { result = nums[i]; break; } flag = false; } return result; };
答案解法：O(n)使用 ^ 位异或运算符，重复数字异或会复位为零，留下唯一数字
1
2
3
4
5
6
7
8// answer algorithm var singleNumber_answer = function(nums) { var result = 0; for (var i = 0; i < nums.length; i++) { result = result ^ nums[i]; } return result; }
6.两个数组的交集②
给定两个数组，编写一个函数来计算它们的交集。
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
我的解法：使用Map数据结构进行重复数组的映射，但是代码冗长：
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
34
35
36
37
38
39
40
41
42// my algorithm /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} * */ var intersect = function (nums1, nums2) { var result = []; var map1 = setMap(nums1); var map2 = setMap(nums2); for (var [key, value] of map1) { var final = map2.get(key); if (typeof final !== "undefined") { var maxCount = getMin(map1.get(key), map2.get(key)); for (var j = 0; j < maxCount; j++) { result.push(key); } } } return result; }; var setMap = function (nums) { var map = new Map(); for (var num of nums) { if (typeof map.get(num) !== "undefined") { var count = map.get(num); map.set(num, ++count); } else { map.set(num, 1); } } console.log(map); return map; }; var getMin = function (num1, num2) { return (num1 < num2) ? num1 : num2; }
答案解法：自定义map对象，缩减代码量：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// answer algorithm let intersect_answer = function (nums1, nums2) { let res = []; let map = {}; for (let e of nums1) { map[e] = map[e] + 1 || 1; } for (let e of nums2) { if (map[e]) { res.push(e); map[e]--; } } return res; };
7.加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
答案解法：适当采用标志位可以缩减运行时间：
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/** * @param {number[]} digits * @return {number[]} */ // answer algorithm var plusOne_answer = function (digits) { let addFlag = true; for (let i = digits.length - 1; i >= 0; i--) { if (addFlag) { digits[i]++; if (digits[i] === 10) { digits[i] = 0; addFlag = true; } else { addFlag = false; } } } if (addFlag) { digits.unshift(1); } return digits; };
8.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
我的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ // my algorithm /** * 我觉得这条题因为有 js 原生的数组 api 所以不难， * 可是如果不准使用api的情况下又该怎么实现 * */ var moveZeroes = function(nums) { var zeroCount = 0; var len = nums.length; for(var i = len;i >= 0;i--) { if(nums[i] === 0) { nums.splice(i,1); nums.push(0); } } };
答案解法：解法思路和 1.从排序数组中删除重复元素 相似，利用遍历后的前项为空余空间的思想进行移项：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution { public void moveZeroes(int[] nums) { int j = 0; for(int i = 0;i < nums.length;i++) { if(nums[i] != 0) { nums[j++] = nums[i]; } } while(j < nums.length) { nums[j++] = 0; } } }
9.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
答案解法：使用一个对象进行映射类似于map：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// answer algorithm /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum_answer = function (nums, target) { var dict = {}, i, len; for (i = 0, len = nums.length; i < len; i++) { var item = nums[i]; if (dict[target - item] !== undefined) { return [dict[target - item], i]; } dict[item] = i; } };
最后两题开始有难度了，都是求解二维数组的问题，之前的题目都是求解一维数组，不存在解不解得出来，基本都是寻求最优或最简解的过程。
10.有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
-
数字
1-9在每一行只能出现一次。 -
数字
1-9在每一列只能出现一次。 -
数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
说明:
-
一个有效的数独（部分已被填充）不一定是可解的。
-
只需要根据以上规则，验证已经填入的数字是否有效即可。
-
给定数独序列只包含数字
1-9和字符'.'。
我的解法：
思路：1.使用 map={} 判断每行（列）中是否有重复的数字（1~9）
2.用降维的思想看待每个小九宫格，判断是否有重复数字（1~9）
虽然执行时间长，但是思路清晰可行
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function(board) { var flag = true; var len = board.length; // 检测行和列 for(var n = 0;n < len;n++) { flag = checkBoard(board,len,n); if(!flag) { return false; } } // 检测三宫格斜线 for(var i = 0;i < len/3;i++) { for(var j = 0;j < len/3;j++) { flag = checkSmallBoard(board,len/3,i,j); if(!flag) { return false; } } } return flag; }; // 检测行和列 var checkBoard = function(board,len,n) { var rowMap = {}; var ColumnMap = {}; for(var j = 0;j < len;j++) { if(rowMap[board[n][j]] && board[n][j] !== '.'){ return false; } if(ColumnMap[board[j][n]] && board[j][n] !== '.') { return false; } rowMap[board[n][j]] = true; ColumnMap[board[j][n]] = true; } return true; } // 检测每个小九宫格 var checkSmallBoard = function(board,len,n,m) { var map = {}; for(var i = 0;i < len;i++) { for(var j = 0;j < len;j++) { if(map[board[i + n * 3][j + m * 3]] && board[i + n * 3][j + m * 3] !== ".") { return false; } map[board[i + n * 3][j + m * 3]] = true; } } return true; }
答案解法：在遍历整个大九宫格的过程中，就将行列和小九宫格的三种判断放在一起执行，提高效率
特别注意：~~ 运算符相当于高效率的 Math.floor() 。~相当于按位取反，~~两次取反复位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22// answer algorithm var isValidSudoku_answer = function (board) { let row = {} let col = {} let box = {} for (let i = 0; i < 9; ++i) { for (let j = 0; j < 9; ++j) { if (board[i][j] !== '.') { let c = board[i][j] + ''; let key = (~~(i / 3) * 3 + ~~(j / 3)) + '' + c if (row[i + c] || col[c + j] || box[key]) { return false; } row[i + c] = true; col[c + j] = true; box[key] = true; } } } return true; }
11.旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
原地算法（in-place algorithm）是一种使用小的，固定数量的额外之空间来转换资料的算法。并非任何额外空间都不允许使用
答案解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ // answer algorithm //这里只用到了一个 额外空间变量 temp var rotate = function (matrix) { var len = matrix.length - 1; for (var i = 0; i < len / 2; i++) { for (var j = i; j < len - i; j++) { var temp = matrix[i][j]; matrix[i][j] = matrix[len - j][i]; matrix[len - j][i] = matrix[len - i][len - j]; matrix[len - i][len - j] = matrix[j][len - i]; matrix[j][len - i] = temp; } } return matrix; };
最后
以上就是年轻果汁最近收集整理的关于LeetCode_初始算法_javascript_数组_总结的全部内容，更多相关LeetCode_初始算法_javascript_数组_总结内容请搜索靠谱客的其他文章。
发表评论 取消回复