编写目的

准备循序渐进地刷算法题和数据结构，每天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. 数字 1-9 在每一行只能出现一次。

2. 数字 1-9 在每一列只能出现一次。

3. 数字 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;
};