概述
编写目的
准备循序渐进地刷算法题和数据结构，每天2到3条算法题，几天时间将初始算法的数组篇搞定，这里将算法题总结一遍还有把自己的一些知识盲区挑出来，加深印象。
1.从排序数组中删除重复元素
这里题干里面也有说，不需要考虑超出范围的数组后的项。而且遍历的数组是已经排好序的数组，所以解题思路为：
从前往后遍历数组，遇到重复的忽略，遇到不同的将值放在已经遍历的前项上，重复此操作，直到遍历完毕。
我的解法：我最开始解题的时候没有懂题意，用了 splice 进行重复元素的切割
/**
* @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;
};答案解法：
// 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解决：
// filter api
var removeDuplicates_filter = function (nums) {
return nums.filter((item, index, self) => {
return self.indexOf(item) === index;
});
}
2.购买股票的最佳时机
遍历数组，遇到低价买入，遇到高价卖出，从中赚取差价。此题没有什么特别值得注意的地方
答案解法：
/**
* @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次右移一步，虽然这样蛮蠢并且执行时间长，但是还是可以实现。
/**
* @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解法：旋转数组其实换个角度想就是切割数组的一部分并且换个顺序拼接，于是有了如下的大神解法：
// unshift splice ...
var rotate_answer = function (nums, k) {
let l = nums.length;
k %= l;
nums.unshift(...nums.splice(l - k, k));
}
4.存在重复元素
判断数组内部是否存在重复元素
答案解法：充分利用数据结构的知识，集合Set就是一个没有重复元素的数据结构：
/**
* @param {number[]} nums
* @return {boolean}
*/
// answer algorithm
var containsDuplicate_answer = function(nums) {
return new Set(nums).size !== nums.length;
}
5.只出现一次的数字
数组中有且仅有一个唯一数字，其余均是出现两次，找出那个唯一数字
我的解法：O(n^2)找出那个唯一数字，不太可行但可以解决
/**
* @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)使用 ^ 位异或运算符，重复数字异或会复位为零，留下唯一数字
// 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数据结构进行重复数组的映射，但是代码冗长：
// 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对象，缩减代码量：
// 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 之外，这个整数不会以零开头。
答案解法：适当采用标志位可以缩减运行时间：
/**
* @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 移动到数组的末尾，同时保持非零元素的相对顺序。
我的解法：
/**
* @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.从排序数组中删除重复元素 相似，利用遍历后的前项为空余空间的思想进行移项：
class 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：
// 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）
虽然执行时间长，但是思路清晰可行
/**
* @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() 。~相当于按位取反，~~两次取反复位。
// 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:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]原地算法（in-place algorithm）是一种使用小的，固定数量的额外之空间来转换资料的算法。并非任何额外空间都不允许使用
答案解法：
/**
* @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_数组_总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复