记录下我的Leetcode坑爹之路——Easy篇

这篇文章主要记录了我在刷 Leetcode 的过程中的思路以及对答案的理解；但由于我是拿 JS 刷的，所以绝大部分题目的答案对于我来说都会理解起来有困难，所以对答案的理解可能会有一些偏差，请谅解；
本文并不会列出题目的 JS 答案，JS 实现在我的另一篇文章：Leetcode 的 JS 实现——Easy 篇中；截止到 2017 年 3 月 31 日，我基本上刷完了 Leetcode 的 Easy 部分，如果有可能的话，我会继续将 Leetcode 上的剩余题目刷完，所以可能又会有 Medium 篇、Hard 篇……

2017-3-16

461-Hamming distance

我的想法：一开始还想怎么取余，后来才发现js里也有取余运算符，就是”^”，然后我就想是不是可以将取余之后的数遍历相加，其实结果是正确的，但是有点太死板了理想答案：将0用””replace，然后取新字符串的长度；同时学到的是，原来js的toString()方法中的参数是进制，之前一直都不知道我擦。。java解法：戳我一下

2017-3-17

476-Number Complement

我的想法：这道题看上去很简单，主要思路依然是取余操作，以数字5为例，二进制表示为“101”，其结果应该为“101”^“111”，也就是数字和相同位数的“全1”二进制数的取余，然后问题就是如何确定这个位数，我的想法是用Math.ceil(Math.log(num)/Math.log(2))，这样就可以取到位数了，但是取到位数之后还要取2得对数，这怎么求？理想答案：其实取位数不需要那么复杂，直接num.toString(2).length就可以了，然后查了一下，js中Math有pow(x,y)方法，可以计算x为底，y为幂的指数，这样就可以了。

339-Nested List Weight Sum

加锁了，没钱

500-Keyboard Row

我的想法：一开始打算设置三个数组，然后再写个方法，对数组中的每个元素遍历执行该方法，但是想想都麻烦啊靠理想答案：果不其然，正则表达式万能无敌出人意料和意料之中

2017-3-21

359-Logger Rate Limiter

加锁了

412-Fizz Buzz

其实这道题在日常写代码中经常碰到，就是整除的问题，然而如何更快更简单的得出答案却很难，如果用js的话，我确实没想到什么好的办法我的想法：先声明一个空数组，然后对空数组进行循环赋值，对i的值进行判断，当能整除15时就是”FizzBuzz”，以此类推，但是需要注意的是数组下标从零开始，某些值可能会需要-1或者+1 理想答案：没有找到关于js的理想答案，但是看排名第一的java答案，发现其实可以不用”%”也可以关于这一经典问题，还有一些扩展问题，可以点击这里查看）

344-Reverse String

字符串翻转问题我的想法：因为字符串在js中也有一些数组的属性，所以很容易进行遍历赋值理想答案：没找到关于js的

346-Moving Average from Data Stream

加锁了

496-Next Greater Element I

我的想法：就是按照题目所说的进行遍历判断，然而我看提示是stack，但是我仍然没有想到更好的用stack实现的方案，而看过网上的解法之后感觉js好像没有办法实现线性复杂度的解法理想答案：使用栈，从后往前遍历nums[i]，每当栈不为空的时候，一直出栈直到遇到比nums[i]大的数字停止。设立一个map<int, int> m，存储nums中每一个元素以及它对应的下一个最大元素构成的映射。如果停止后栈为空就将m[nums[i]]标记为-1，否则就写栈的栈顶元素；最后将findNums中出现的每一个元素对应的map的值放入result数组中返回

463-Island Perimeter

我的想法：直接遍历，然后考虑所有情况进行判断加几，应该可以求出来，只不过并没有发现其中的规律理想答案：其实规律很好发现，可以将“陆地”加入的过程分解开一步一步看，就会发现其中的规律，可以根据陆地的上面一格和左边一格有没有陆地来进行区分，如果有，就是在加了4条边的基础上再减去两条边，因为有两条边重合了，导致减少了两条边

266-Palindrome Permutation

为什么加锁的题这么多

292-Nim Game

我承认这是我第一次和理想答案一样，所以就不分开描述了，其实举几个例子就能发现其中的规律了，因为这道题的前提是你先走，而且你和对方都可以走1到3步，所以加入像他说的那样，最后剩4个了然后你先走的话，你肯定不会赢；而迭代之后就是，只要n不是4的倍数，你就可以在行动完之后让剩下的棋子是4的倍数然后让对方先走，这样你就可以保证最后剩下4个棋子的时候让对方先走。所以，只要一开始棋子的个数就是4的倍数的话，你就没有办法赢，因为对方也会采取最优策略。

485-Max Consecutive Ones

这个应该是简化版的最长子序列问题吧我的想法：有一个存储结果值的变量result（初始值为0），还有一个变量相当于计数器num（初始值为0），对数组进行遍历，遇到1就将计数器加1，遇到0的话先将结果值赋值为Math.max(result,num)；最后需要注意的是返回的仍然是Math.max(result,num)，因为需要考虑输入为单纯的1或0时；理想答案：果然java大神多啊，其实思路差不多，只不过可以将其简化一下而已

293-Flip Game

锁

136-Single Number

重点是线性复杂度，不能有额外内存占用我的想法：我的想法过于复杂（复杂度应该是指数级的），看提示是哈希表和二进制，但是二进制我想到的是异或，哈希表就不知道怎么用js实现了理想答案：知道答案的我泪流满面，因为异或运算是可交换的，而且A XOR A = 0，所以对于实例{2,1,4,5,2,4,1}就会有这样的结果：

1	(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

就把只出现了一次的元素给找出来了，算法复杂度为 O(n)，且不需要额外空间

448-Find All Numbers Disappeared in an Array

依然是线性复杂度，不能有额外内存占用我的想法：用一个全部数字都有的数组进行匹配，如果在完整数组里面有这个数字，就把它移除，最后剩下的就是丢失的数字；然而复杂度太高，而且占用了额外内存理想答案：利用nums[nums[i] -1] = -nums[nums[i]-1]，这样可以将出现过的数字所在位置的数字变为负数，最后判断哪个位置是正的，就是从来没出现过的数字，对于实例[2,3,1,3]来说，出现过的数字为1，2，3；所以就需要将数组中索引值为0，1，2的数字变成负的，所以处理后的结果是[-2,-3,-1,3]，再对这个数组进行遍历判断，如果大于零就说明没出现过，所以第四个数字是3（正数），所以就是4没出现过

520-Detect Capital

我的想法：一开始觉得正则表达式肯定可以做，但是不会写；看完python的答案后，感觉js的indexOf和toUpperCase()、toLowerCase()应该可以做理想答案：java基本上使用正则表达式，python有现成的方法，而js按照我那个思路应该是最佳答案

104-Maximum Depth of Binary Tree

我的想法：首先，我都不知道js如何实现一个二叉树，然后感觉这应该是深度优先遍历能解决的问题，所以就去看了答案理想答案：用栈缓存最大高度，希望有人能够用js实现以下深度优先遍历

243-Shortest Word Distance

锁

389-Find the Difference

看到有些答案是用异或做的，而我的想法是遍历短字符串，然后将新字符串中的对应字母替换成空字符，最后返回替换完毕之后的字符串，这个想法是由几天前那个妙用replace()方法的js答案想到的

371-Sum of Two Integers

题目最容易读懂，但是基本上一点思路都没有，想到用计算机理解的那样去做，也就是位操作，但是具体怎么做就不知道了；应该是计算机基础没学好，否则应该很容易想出来吧（关于位操作的更多总结，可以查看我的另一篇文章：一些位操作的技巧）

2017-3-22

226-Invert Binary Tree

看见这种二叉树的算法题就头疼，做了几道关于二叉树的题后发现，掌握二叉树的遍历方法之后解类似的问题会变得很简单，而且要逐渐培养自己的递归思维和动态规划思维（从leetcode的tags可以看到，动态规划思维可以解答很多问题）我的想法：没找到什么规律，然后看提示是Math，还是没有什么想法理想答案：主要思路是对9取余，因为用到了一个很重要的定理，九余数定理：一个数N 各位数字的和对9 取余等于这个数对 9取余

492-Construct the Rectangle

我的想法：一开始打算求根值，然后在根值附近找整数，但是好像对于质数来说根本行不通理想答案：我的想法太狭隘了，应该再多想一步，就是从根值开始向下找，直到找到能整除的那个数字

283-Move Zeroes

我的想法：遍历数组，如果碰到0，就把这个0从数组中删除，然后再push一个0到尾部，需要注意的是需要有一个变量用来存储有几个不是0的元素被遍历到了，因为这会影响到下一次循环的判断理想答案：看了java的1ms答案，他的思路是遍历数组，然后当遍历到一个不是0的值得时候就进行交换，而交换的位置需要进行存储，并且每次碰到不是0的值就将该值加1，因为交换会使0的位置加1

530-Minimum Absolute Difference in BST

求最小临近距离，看java的答案是先赋一个int型最大值，然后再用Math.min方法，然而js怎么做就不知道了；关于二叉树算法题的js实现有点麻烦，而且网上的代码有点繁杂并且思路很乱，有时间的话我会总结一篇关于二叉树的各种算法题的js实现和解释的。

506-Relative Ranks

我的想法：我最先想到的就是先把整个数组排序，然后进行替换取值，但是难点是如何记住一开始每个数值的位置，可能还需要开辟额外的空间来存储index 理想答案：看java的答案，好像java有现成的数组排序方法， js可以用array的sort方法，然后用二维数组分别存储数值和index（python更简单，内置方法很适合算法实现），在写js答案的过程中发现js初始化一个二维数组真的好麻烦。

function arraySort(nums){
    var nums_new = \[\],
        n = nums.length;

    for(var a=0;a<n;a++){
        nums_new\[a\]=\[\[\],\[\]\];
    }

    for(var i=0;i<n;i++){
        nums_new\[i\]\[0\] = nums\[i\];
        nums_new\[i\]\[1\] = i;

        for(var j=0;j<n-1-i;j++){
            if(nums\_new\[j\]\[0\]>nums\_new\[j+1\]\[0\]){
                var temp = nums_new\[j+1\];
                nums\_new\[j+1\] = nums\_new\[j\];
                nums_new\[j\] = temp;
            }
        }
    }
    return nums_new;
}

var findRelativeRanks = function(nums) {

    var nums_new = arraySort(nums),
        result = new Array(nums.length);

    for(var k=0,n=nums_new.length;k<n;k++){
        if(k===0){
            result\[nums_new\[0\]\[1\]\] = "Gold Medal";
        }else if(k==1){
            result\[nums_new\[1\]\[1\]\] = "Silver Medal";
        }else if(k==2){
            result\[nums_new\[2\]\[1\]\] = "Bronze Medal";
        }else{
            result\[nums_new\[k\]\[1\]\] = k+1 + "";
        }
    }
    return result;
};

167-Two Sum II - Input array is sorted

我的想法：从最右边找到比target得数，然后从这个数的index值开始向左进行数组遍历，看两个数的和与target相比如何，如果相加大于target，就将index值，再进行遍历理想答案：利用二分查找，left=0，right=numbers.length-1；然后分别进行向左和向右的遍历

455-Assign Cookies

我的想法：一开始打算遍历小孩数组，然后再判断cookie的size能不能满足小孩的需要；后来感觉还是应该以cookie为第一层遍历，然后满足了某个小孩之后再将小孩的指针+1（这都是在两个数组排好序的前提下，js需要用sort方法）理想答案：和我的想法差不多（不知道为什么总是提示Time Limit Exceeded，js代码如下）

var findContentChildren = function(g, s) {
    var i=0,m=g.length,n=s.length;

    for(var j=0;j<n,i<m;j++){
        if(g\[i\]<=s\[j\]){
            i++;
        }
    }
    return i;
};

453-Minimum Moves to Equal Array Elements

我的想法：我承认一开始被这道题骗了，我还在傻呵呵的列式子，后来才感觉不对劲，因为其实可以将这个过程逆过来，因为每次都将n-1项加1，其实就相当于从最终结果开始每次都将1项-1，直到所有项都等于数组中的最小值理想答案：好像和我的思路一样，只不过js中求数组中的最小值需要用到一些技巧（Math.min.apply(null,arr)）

383-Ransom Note

我的想法：我又想到了replace方法，首先对ransomNote进行遍历，如果ransomNote中的字母在magazine中不存在的话，就直接返回false；如果找到了，就将找到的那个字母替换为””，并赋给magazine（因为replace不会改变原数组），这样的话，如果遍历完毕之后magazine的长度大于等于0（等于0也可以满足，此时ransomNote和magazine长度相同并且所含字母的种类和个数相同），此时就应该返回true 理想答案：依然没有js实现方案，看其他语言好像和我的思路大同小异

404-Sum of Left Leaves

这不知道是我第几道不会做的二叉树题了，思路是有，就是递归嘛，但是就是不会写。看完java的答案后写了一下js的版本（主要是要找到叶子节点）：

var sumOfLeftLeaves = function(root) {
    if(root === null) {return 0;}
    var ans = 0;
    if(root.left !== null) {
        if(root.left.left === null && root.left.right === null) {
            ans += root.left.val;
        }else {
            ans += sumOfLeftLeaves(root.left);
        }
    }
    ans += sumOfLeftLeaves(root.right);
    return ans;
};

349-Intersection of Two Arrays

我的想法：既然找相同的数字，我觉得应该先把两个数组排序吧，然后再双层遍历？感觉用二分查找应该能简化，但是两个数组如何进行二分查找呢？理想答案：看别人的答案的话我只看懂了用两个指针的方法，复杂度为O(nlogn)，用哈希表那个方法没看懂什么意思，所以就用js实现一下两个指针的方法吧（果然需要先将两个数组排序，而且重点是删除重复元素）；而且这个题还有个bug就是题目明明说result可以以任何顺序，但是不是升序的答案根本提交不了……

var intersection = function(nums1, nums2) {
        var nums1_n = nums1.sort(),
            nums2_n = nums2.sort(),
            i = 0,
            j = 0,
            result = \[\];
        while (i < nums1.length && j < nums2.length) {
            if (nums1\_n\[i\] < nums2\_n\[j\]) {
                i++;
            } else if (nums1\_n\[i\] > nums2\_n\[j\]) {
                j++;
            } else {
                if(result.indexOf(nums1_n\[i\]) == -1){
                    result.push(nums1_n\[i\]);
                }
                i++;
                j++;
            }
        }
        return result.sort();
};

252-Meeting Rooms

锁

122-Best Time to Buy and Sell Stock II

知道了原理之后就很好做了，假如价格数组为[3,1,4,6,2,5,8]，从中可以发现，如果今天的价格比明天的价格便宜，我就今天买然后明天卖掉就可以了，只需要这一个判断就可以，因为不需要在手中呆多过1天1，拿数组中的[2,5,8]举例，你就会发现这个规律

387-First Unique Character in a String

我的想法：遍历两次，实在想不出好方法了理想答案：看有一个人用java可以实现18ms的速度，用两个指针->slow来只想当前字符，fast来浏览整个字符串，但是最后还是没看懂；后来看到了用ASCII码记录下出现的字母，然后在进行比较的方法，用js实现如下：

/\*\*
 \* @param {string} s
 \* @return {number}
 */
var firstUniqChar = function(s) {
    var freq = new Array(26),
        a = 'a'.charCodeAt();
    for(var i = 0; i < s.length; i ++) {
        if (freq \[s\[i\].charCodeAt() - a\] === undefined) {
            freq \[s\[i\].charCodeAt() - a\] = 1;
        } else {
            freq \[s\[i\].charCodeAt() - a\]++;
        }
    }
    for(var k = 0; k < s.length; k ++){
        if(freq \[s\[k\].charCodeAt() - a\] == 1){
            return k;
        }
    }
    return -1;
};

2017-3-23

171-Excel Sheet Column Number

我的想法：这道题其实蛮简单的，学过多进制的人很容易就想到了，很类似于多进制转换（比如十六进制转换成十进制），同时结合ASCII码就可以很快得出答案：

/\*\*
 \* @param {string} s
 \* @return {number}
 */
var titleToNumber = function(s) {
    var result = 0;
    for(var i=0,n=s.length;i<n;i++){
        result += Math.pow(26,n-i-1)*(s\[i\].charCodeAt() - 64);
    }
    return result;
};

256-Paint House

锁

504-Base 7

我的想法：这种多进制的转换道理我都懂，可是如何用式子表达出来就不会了，包括循环的结束条件以及正负号的处理理想答案：看完答案的我哭晕在厕所，因为其实js中的toString()方法已经解决了所有关于进制转换的问题；当然，也可以用递归去解，用js实现如下（需要注意在某些地方需要将数字转换成字符串，否则就会是两个数字相加，结果肯定不对，在js里数字转换成字符串最简单的方法就是将数字和””相加）：

/\*\*
 \* @param {number} num
 \* @return {string}
 */
var convertToBase7 = function(num) {
    return num>=0 ? "" + (num>=7 ? convertToBase7(Math.floor(num/7)) + "" + num%7 : num) : '-'+convertToBase7(-num);
};

237-Delete Node in a Linked List

我的想法：这应该是是我碰到的第一道链表算法题，但是我竟然连题都没弄懂，因为参数只给了一个node，这个node到底是链表本体呢还是要删的那个元素的value呢，反正也是第一道题，我就直接看答案了理想答案：因为题目已假设删除的不是尾部的元素，所以只需要将值和next与下一个节点相等就可以了（由于这道题过于简单，就不贴代码了，简单到有人说这道题实在太蠢了）

100-Same Tree

我的想法：题目很简短，应该可以递归做，就是假如根节点值相同，就看root.left和root.right是否都相同理想答案：需要先判断两个数都为null时应该返回true

169-Maiority Element

我的想法：这道题有种似曾相识的感觉，好像曾经做过一道类似的题，应该还是用二维数组来做，一维用来存储数字，另一维用来计数，然后进行按计数值得排序就可以得到”多单元”了（看答案还有另一种思路，就是因为该元素出现次数不少于n/2次，所以如果将数组排序，第n/2个元素肯定是该元素了）理想答案：有一个人的想法很巧妙，因为题目中规定”多单元”是出现不少于n/2次的元素，所以可以先将指针设为num[0]，同时有一个计数变量，然后对数组中剩下的n-1个元素进行遍历，如果该元素和”多单元”相同，就将计数器++，否则；当计数器为0时，证明之前的那些元素都不是”多单元”，就将指针指向当前元素，同时将count++，相当于开始新一轮检测=>穆尔投票算法（有一个网友总结了6种c++方法，并进行了解释，有兴趣的同学可以点击题目去瞅瞅）

242-Valid Anagram

我的想法：一开始打算将字符串进行排序之后比较，然而不知道怎么更快速的对字符串进行排序理想答案：其中一个思路是将字母转换成数字（ASCII码），然后用一个新的数组进行存储s数组的数字，然后在相同的位置减去t数组的数字；当这些都完成后，再对新数组进行遍历，当遇到一个不是0的数字时就说明有一处不同，就直接返回false；最后假如没有不是0的数字就返回true

409-Longest Palindrome

我的想法：应该可以先统计某一字母个数为偶数和某一字母个数为奇数的数量，然后偶数字母个数加上是否有奇数字母个数（没有就加0，有就加1）理想答案：由于没有js的标准答案，所以只能看其他语言的大概思路，基本上思路和我的想法相同，只不过是简化代码的问题。

541-Reverse String II

我的想法：既然交换元素是和k有关，而且移动的步数也和k有关，所以可以进行循环交换，每次移动2k步，然后判断条件就是不能移动出数组理想答案：有的思路是再写一个交换元素的函数，其实交换可以在遍历过程中进行，主要是循环结束的判断可能需要画个草图进行确定。

2017-3-24

401-Binary Watch

我的想法：可以把十个灯看做一个数组的十个元素，然后有几盏灯亮，就是数组相应位置上的元素值为1，其余元素为0，再然后对此二进制数组遍历取值，需要排除掉一些元素，因为时间不可能超过11:59；关键是如何实现将指定数目的1分配给数组中的随机元素。理想答案：有的答案是从结果出发，对h从0-11和m从0-59这些所有的情况进行遍历，然后如果满足给定参数，就添加进数组；还有就是写出来所有的可能情况，然后就行匹配（这种答案简直无耻，而且速度还非常酷啊）；还有一种思路和我的比较像，就是从1的分配出发，先将数值求出来，然后假如h<12并且m<60，就将其加入数组中；

217-Contains Duplicate

我的想法：这个可以用哈希表这种数据结构来做（之前做过类似的题太多了），然后对数组遍历的过程中就将哈希表更新一次，同时进行判断，如果哈希表以该数组元素为键值的地方有value，证明之前出现过改元素，就返回true；最后返回false，因为数组遍历结束还没有发现有元素出现过两次理想答案：我的想法也可以是一种思路，还有一种思路就是先将数组排序，然后只需要比较相邻元素就可以了

13-Roman to Integer

我的想法：看完题之后的第一感觉是：什么是罗马数字？然后我上网搜了一下，发现了罗马数字为什么没有广泛应用的原因，真的是太麻烦了！所以，最后我选择直接看答案理想答案：原来罗马数字的构成还是满足一定规则的，但是这倒算法题未免过于局限了，可以去我的另一篇文章-罗马数字转换成整数去看构成规则和代码实现

2017-3-25

206-Reverse Linked List

我的想法：题目只有短短的一行，就是翻转一个单链表，而学过其他语言比如C、java、C++的人应该对链表这种数据结构很熟悉，但是在js里很难用到（反正我基本上没碰见过必须用链表这种数据结构才能解决的问题），所以虽然题目很简单，但是需要首先知道在js里，链表是如何构建的理想答案：其实画一张草图就可以很清楚的知道这道题的答案了，就是head.next.next = head,head=null；然后对整个链表进行遍历

350-Intersection of Two Arrays II

我的想法：之前有过一道类似的题，只不过那道题只需要找出相同的元素；这道题需要找出所有重复的元素，所以需要用哈希表来对重复的元素进行计数理想答案：我的想法在两个数组未排序时是可以的；而如果先对两个数组进行排序或已经排好序的情况下，可以采用两个指针的方案，然后对两个数组中的元素进行比较，如果相等就push进新数组，不相等就移动指针

268-Missing Number

我的想法：早在刷Leetcode之前就听说过这道题，我觉得应该先将数组排序，然后对数组进行遍历，对数组的值和索引值进行比较，不相等时就说明找到了，直接返回（需要注意的是js中的sort方法会默认按照字符串进行排序所以10会比2小，具体写法可以看下面代码；最后需要return n；因为循环索引值只会到n-1；如果遍历结束都没找到，证明是最大的那个数）理想答案：除了我的想法（可以用二分查找进行优化），还可以用位运算中的异或，因为只有一个数丢失了，所以根据异或操作的性质，可以很容易找出来那个数字；还有一种方法是用求和的方式，先求出应该的和，然后减去数组中的所有数字，差就是那个丢失的数字

var missingNumber = function(nums) {
    var sort = nums.sort(function(a,b){
        return a-b;
    }),n=nums.length;
    for(var i=0;i<n;i++){
        if(sort\[i\] != i){
            return i;
        }
    }
    return n;
};

447-Number of Boomerangs

我的想法：一开始没什么想法，就看了提示（Hash Table），如果要用哈希表的话，那应该把每个元素的大小记录下来吧，然后对其进行排序，对排好序的哈希表进行二分查找？理想答案：我是真的蠢，两个点之间的距离并不等于两个点距离原点距离大小之和，所以我那个想法是行不通的，看答案感觉这道题只能按照很普通的方法来解：首先将所有点到其他所有点的距离的平方作为key保存到map容器中，key相同就累加value，然后计算每个元素的value*(value-1)，并累加到返回结果中，最终就得到符合条件的点序列数，时间复杂度为O(n^2)

543-Diameter of Binary Tree

我的想法：这种求最大值的应该用栈可以解决，但是如何递归我没有想清楚理想答案：对于每个节点来说，传过它的最长的路径是它的左子树的最大深度和它的右子树的最大深度；而一个节点的最大深度是它的左子树的深度和右子树的深度中的较大值加一

415-Add Strings

我的想法：根据我之前的经验，在字符串前加一个”+”号是可以直接将字符串转换成数字的，但是在提交之后会发现，当字符串中的数字过大时，转换将出现误差。理想答案：最关键的一点是将字符串减去”0”或数字0，是可以将字符串转换成数字的；但是还是不明白我的想法为什么会出现误差，而且提示是Math，看答案基本上都是用字符串减去”0”，好像并没有用到Math的哪些方法

108-Convert Sorted Array to Binary Search Tree

我的想法：首先得知道什么是平衡二叉树，然后需要了解如何用js构造一棵二叉树，才会有这道题的思路；因为根节点肯定是中值，所以可以先将根节点确定，然后左子树和右子树的根节点可以递归求得理想答案：和我的思路一样，但是我用js实现之后提交总是出错，跪求有大神用js解出这道题

405-Convert a Number to Hexadecimal

我的想法：我能想到两种思路，一种是先将整数转换成二进制，然后再对二进制的字符串进行遍历；还有一种是取余理想答案：基本上就是这两种思路，但是将二进制数转换成16进制数不需要进行遍历，可以利用位运算”&15”，同时”>>4”可以将二进制数字向右移4位，可以很方便的进行计算赋值

2017-3-26

121-Best Time to Buy and Sell Stock

我的想法：既然是求最大值，那可以先将数组排序，然后双指针进行判断，如果right的索引值小于left的索引值，就直接返回差值；循环结束仍没有返回就返回0，此时不存在最优化策略理想答案：可以将数组元素中的最小值缓存下来，然后最大利润就是使得当前元素减去最小值之后差最大的值（动态规划的思想）

202-Happy Number

我的想法：如果最后以和为1结束，那应该只有几种情况：1，10，100，1000……而某两个整数加起来的平方是这些数就是倒数第二步中的那个数，但是如何求出这两个数是个问题，也许会有某些定理？理想答案：一种思路是按照题目中所说的求平方，然后假如陷入了死循环（之前出现过该值）就直接返回false；还有一种思路就利用弗洛伊德循环检测算法（Floyd Cycle detection algorithm）=>将求平方的过程分为快和慢两个过程，慢过程一次只求一次平方和，快过程一次求两次平方和，如果快过程所得结果和慢过程所得结果相等，就证明进入了死循环，就返回false

326-Power of Three

我的想法：既然不让用循环，那我觉得可能需要用位运算，但是写了几个数字之后没有发现规律理想答案：果然这道题是到智力题，虽然不让循环，但是可以用某些很简单的方法，比如让这个数字一直除以3（并没有进行循环，而是不断调用方法），或者用js的toString()方法，然后进行正则匹配……

327-Power of Two

我的想法：吸取了上一题的教训，我打算直接看答案了理想答案：可以通过位运算，也可以通过上一题那些方法

246-Strobogrammatic Number

锁

83-Remove Duplicates from Sorted List

我的想法：其实是一道很简单的题，但是由于js和链表这种数据结构打交道很少，所以在看答案之前并不知道用js如何实现理想答案：直接比较就可以了，相等就删除

70-Climbing Stairs

我的想法：如果有n步，可以把这n步分成n个1步，然后对相邻的1进行随机组合（可以组合成需要1个两步、2个两步、3个两步……），然后将所有的可能性相加理想答案：有网友指出这是个斐波那契数列；还有种方法就是从终点往前用两个指针进行循环

53-Maximum Subarray

我的想法：这道题确实一点想法都没有（感觉后面的题会越来越难）理想答案：用动态规划的思想去解，maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];意思是从0开始到i的数组中的最大子数组和从0开始到i-1的数组中的最大子数组有关；一直相加知道和比0小，如果和是负的，就将序列重置

437-Path Sum III

我的想法：本来打算从根节点开始向下相加，如果大于sum，就不去右子树，同时另一路重置节点，但是这种二叉树的遍历我是真的一点都不会；或者从树的结构发现，对于某个节点来说，这个路径的数量等于左子树符合的路径和右子树符合的路径个数之和再加上当前节点的值是否正好等于目标数字理想答案：可以用哈希表来建立所有的前缀路径之和和其个数之间的映射，然后看子路径之和有没有等于给定值的；或者利用前序遍历，维护一个变量pre来记录之前路径之和，然后cur为pre加上当前节点值，如果cur等于sum，那返回结果时要加1（有点类似于我的想法）

501-Find Mode in Binary Search Tree

我的想法：这道题比较简单，用一个哈希表用来存储数字和其出现的个数就可以，然后遍历比较的同时更新哈希表理想答案：为了保证O(1)的空间复杂度，可以先得到modes的个数，然后再申请空间，但是可能leetcode对js的编译存在bug，run code时是正确的答案在提交时就无法通过

191-Number of 1 Bits

我的想法：在js中，可以用toString(2)将数字转换成二进制字符串，然后利用replace将字符串中的0替换为空字符串，最后求替换后的字符串长度就可以了理想答案：除了我的想法，还可以用位运算

35-Search Insert Position

我的想法：对数组进行遍历，如果发现当前元素大于等于目标数字，就返回index；最后返回数组长度，因为此时证明目标数字比数组中的所有元素都大理想答案：其实可以用二分查找简化遍历

107-Binary Tree Level Order Traversal II

我的想法：关键是如何知道当前元素属于哪一层，应该用一个变量对当前遍历到的层数进行存储理想答案：可以用链表或栈，但是用js如何实现还不知道

263-Ugly Number

我的想法：既然2，3，5是互质的，就直接用3个while分别除以2，3，5；直到无法整除时再判断余数是否为0就可以了理想答案：大体上就是我的思路，只不过可以更加简化

270-Closest Binary Search Tree Value

锁

459-Repeated Substring Pattern

我的想法：总感觉这道题会有很简单的解法，但是肯定要遍历到所有的元素，而如何确定循环字母的个数以及如何进行遍历是个难题理想答案：方法有很多，主要区别在于对子序列的确定和判断上

21-Merge Two Sorted Lists

我的想法：就是从前往后对两个链表遍历，需要注意的是对于头和尾的处理理想答案：如果l1为null，就返回l2；如果l2为null，就返回l1；之后就是递归的过程

235-Lowest Common Ancestor of a Binary Search Tree

我的想法：两个节点的祖先肯定也是其各自左子树与右子树的祖先，而最小祖先的话应该是从根节点出发，然后看两个节点在什么时候在某个节点的两侧或其中一个节点是另一个节点的祖先节点理想答案：根据我所说的那两种情况，又因为这是一棵二叉搜索数，所以两个节点分别与共同的祖先节点相减所得的差应该是异号或等于0的，否则就根据节点与当前根节点的大小比较对其左子树或右子树进行递归

198-House Robber

我的想法：看这种题目就应该是动态规划，但是想了半天还是想不到子问题是什么，因为这种相邻的元素会传染啊理想答案：其实应该从房间数为1时开始找规律，当房间数为2时，需要比较的是a[0]和a[1]，而当房间数为3时，需要比较的是a[1]和a[0]+a[2]……这样就能够发现需要把房间数的奇偶作为判断标准，同时对最大值进行存储

342-Power of Four

我的想法：首先可以判断二进制数字中1的个数，当有且只有1个1且位于偶数位上时，就是可以整除4；或者可以利用位运算理想答案：除了上面说的两种思路，还有一种是利用2的倍数减1无法整除3而4的倍数减1可以整除3的特性

2017-3-27

345-Reverse Vowels of a String

我的想法：既然是交换字母，那应该用二分查找是没问题的，而需要注意的是在js中是无法对字符串重新赋值的，因为字符串是类数组并不是真正的数组，所以需要先用一个array将字符串存储进来并在数组中完成交换；最后再通过join方法将数组转换成字符串理想答案：其他语言是可以对字符串重新赋值的，而js的话应该只能按照我那种方式

367-Valid Perfect Square

我的想法：既然不让用sqrt，那应该是模拟计算机在求根值的时候是如何处理的，所以可能是位运算吧，但是到底如何运用没有思路理想答案：有一个定理就是完全平方数一定等于1+3+5+7……所以可以通过迭代判断；其实可以通过二分查找；最后可以通过牛顿迭代法判断

27-Remove Element

我的想法：本来还打算继续用replace的，但是正则表达式不能带引号，而将变量和字符串相加之后会出现引号，我目前还不知道怎么去掉；还可以先将数组排序，然后用二分查找理想答案：大体上思路都差不多，不过我很诧异为什么没有用二分查找的，难道先排序会让时间复杂度变高吗？

101-Symmetric Tree

我的想法：对于这种数的遍历我是真不会写，思路应该是对于某个节点来说，它是否是个”镜像树”取决于它的左子树和右子树是否都是个”镜像树” 理想答案：可以再写一个方法，然后判断其左右子树是否都是”镜像树”

66-Plus One

我的想法：本来想通过一些简单的方式将它变成数字再变成数字组成的数组的，但是最后的结果数组是一个字符串数组，所以就放弃了，老老实实遍历原数组了理想答案：答案都是从n-1开始遍历，难点只有对于进位的处理了

2017-3-28

118-Pascal’s Triangle

我的想法：鉴于是一个数组组成的数组，而且数组中的每个元素只与前一个元素有关，所以可以先用一个方法生成某一行的数组元素，然后再通过循环将这些数组push进数组中返回理想答案：除了单独写一个方法之外，其实完全可以用一个函数就解决了，只不过这时候的赋值是对二维数组赋值

434. Number of Segments in a String

我的想法：首先需要去掉首尾空格，因为会影响判断长度的判断，然后再将连续的空格替换成一个空格，再然后将非空字符替换成””，最后返回空格的长度+1 理想答案：除了我的想法之外，可以先在首尾分别加一个空格，然后再将多个空格替换成1个空格，最后返回空格数量-1

110. Balanced Binary Tree

我的想法：又是一道二叉树的题，这种根据高度判断的题用深度优先遍历就可以了吧，但是我用js依然不会（感觉我的下一篇文章就会是js实现二叉树的各种遍历）理想答案：某节点的高度等于该节点的左子树和右子树的高度中的较大值再加一，所以知道这个公式之后就可以递归求解了，其实是一道很简单的题

257-Binary Tree Paths

我的想法：首先需要明确的是路径的数量是叶子节点的数量，所以对于某个节点来说，如果其左右子节点不为null的话，就需要有两条路径理想答案：我没有想到的是，其实最终返回的是一个链表群组，而对于本身就有链表这种数据结构的语言来说是很简单的，而对于js来说，需要用数组模拟链表

422-Valid Word Square

锁

441-Arranging Coins

我的想法：因为求和的公式是能算出来的，所以本来打算先求根值确定大致范围，结果试了几次之后发现总是有一些时候是不对的，所以就看答案了理想答案：因为公式是可以算出来的，所以直接根据公式求出解就行了，然后用Math.floor就可以了；

119-Pascal’s Triangle II

我的想法：规律我找到了，就是各种和n(n+1)有关，但是如何用代码表现出来还是不太知道；如果用之前的方案解的话就是再单独写一个方法理想答案：递归，相当于第一层循环是生成之前一层的元素，第二层是生成当前层的元素；根据公式a(k+1) = a(k) (n-k)/(k+1)

232-Implement Queue using Stacks

我的想法：其实在js中实现队列也没办法用栈，因为js中就没有栈嘛，所以还是用数组就可以了，然后具体如何实现大家可以参考的我的另外一篇文章：JS实现复杂数据结构，这篇文章里面有一些复杂数据结构（比如栈、队列、单链表等）的实现以及方法的定义理想答案：基本上都是自带方法，没什么好说的

141-Linked List Cycle

我的想法：如果判断是否有环，那应该是遍历时出现了同一元素，所以用哈希表应该可以做理想答案：之前有道题用到了两个指针，一个移动的快，一个移动的慢，而这道题也可以用那种解法，当快指针和慢指针遇到一起时，证明存在环，否则就不存在

26-Remove Duplicates from Sorted Array

我的想法：既然只需要返回长度，那就遍历时如果碰到前后元素相等就原长度-1，最后返回剩余长度理想答案：同样是对数组进行遍历，设置一个变量用来记录当前没有重复数字的数组长度，当遇到不相等元素时就将变量加一，同时进行赋值；或者用一个变量记录当前数组中重复元素的数量，最后用总长度减去重复元素数量

172-Factorial Trailing Zeroes

我的想法：某个数的阶乘是有现成的公式的，如果直接套用公式的话就会很好求，但是如果不套用公式又要保证复杂度是对数级的话可能要用二分查找？（事实证明，我题都没读懂）理想答案：和我理解的题意不同，题目所要求的是n的阶乘小数点前面有几个0，而0产生的情况只可能是5*2，所以就可以简化为n！里有几个5，因为2是有足够多的

9-Palindrome Number

我的想法：看到回文数字，我的第一反应就是二分查找，用left和right指针进行判断理想答案：应为js可以很轻松的将数字转换成字符串，所以用二分查找比较方便；还可以用前一半数字是否等于后一半数字来判断

374-Guess Number Higher or Lower

我的想法：这个游戏在某些购物类电视节目里经常遇到，因为数字的挑选是随机的，所以可以看做等概率的，所以一直取中间数是个正确的策略理想答案：竟然只能用java、python、c++，所以只能看答案了

276-Paint Fence

锁

438-Find All Anagrams in a String

我的想法：和著名的KMP算法一样，可以用一个指针来记录可能存在的index索引值，然后对当前字符和之前的字符进行判断理想答案：这道题可以用著名的滑动窗口算法来解，这样可以将复杂度控制在O(N)

112-Path Sum

我的想法：对于一个节点来说，其到叶子节点的路径之和等于左子树的所有可能路径加上右子树所有可能路径的和再加上当前节点的val，所以重点是如何确定左子树和右子树有多少条路径理想答案：二叉树真的是太强大了，既然我们不好确定多少条路径，不如将其简化为如果知道目标值sum和当前节点的val，就看左子树和右子树能否满足sum-root.val就可以了

2017-3-29

38-Count and Say

我的想法：首先需要读懂题目，这道题的题目我认为是很难理解的，所以我就搜了一下，规则如下：n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211，所以这是个典型的递归问题理想答案：大家对这道题的抱怨很多，原因是题意很难读懂，而且我一开始没有注意到需要返回字符串，还以为是数字；但是题目很简单，典型的递归问题

250-Isomorphic Strings

我的想法：我觉得题目说的有歧义，因为其实并不是单向的替换，而是说s和t是可以交换的，所以需要同时判断两个字符串，我采取了最笨的一种方法，就是用另外一种方法来判断能否替换，然后将s和t交换之后再判断一遍理想答案：可以通过另外一个数组来保存s和t中的元素分别在其字符串中的位置，如果不相等，就证明其中一个字符串中出现了重复字符串，而另外一个没有出现，此时就返回false

20-Valid Parentheses

我的想法：首先需要分清楚哪些情况是无效的，哪些情况是有效的，首先是符号必须闭合，其次是符号之间必须是包含关系，所以直观上来看应该可以用栈来解决理想答案：栈是公用的思路，区别在于如何确定哪两个标签是一对儿，indexOf或许是个不错的选择

111-Minimum Depth of Binary Tree

我的想法：这道题是比较简单的二叉树递归题，主要是注意当root的左子树或右子树为null时，并不能单纯的用Math.min，因为最小高度是不会把null算在内的理想答案：只要分辨出来叶子节点和非叶子节点就可以确定递归方程，详情可见我的另一篇文章：Leetcode的JS实现（有个大神总结了各种语言的各种实现方案，可以点击题目链接查看solutions）

290-Word Pattern

我的想法：之前有一道类似的题，这道题将其扩展了一下，从字母组合变成了字符串组合，所以增加了一些难度（也有可能是减少了？），还是觉得用哈希表会好一些理想答案：其他语言的复杂数据结构都有好多自带的方法，而JS连哈希表都没有，所以只能先定义一下会用到的方法，再通过哈希表进行判断，只要把可能情况考虑全这道题就没有什么问题

234-Palindrome Linked List

我的想法：因为题目中的链表是单向的，所以我感觉可以先将链表遍历一遍，然后将值推进栈中在进行二分查找，不过这样复杂度可能会有点高理想答案：果然不能按照我的思路，可以通过两个指针（slow和fast）对链表进行遍历，fast跑到链表结尾时slow正好走到中间，然后开始反转，比较前一半和后一半是否形成回文，可见下图

1.Two Sum

我的想法：我一开始以为这是一道非常简单的题，就直接排序之后二分查找就可以了，但是这样返回的索引值不一定是未排序之前的数组的索引值，所以可能又需要哈希表？理想答案：确实需要用到哈希表，但是由于是两个数相加的和，所以可以遍历时将差值推进哈希表，当循环到下一元素时，只需要看哈希表中有没有这个数字就可以了（但是js没有哈希表啊，所以需要自己提前写好方法）

219-Contains Duplicate II

我的想法：这道题和上面那道题有点相似，同样是只包含数字的数组，同样是求满足条件的两个数字的索引值，所以应该可以用哈希表理想答案：我竟然题目都没弄清楚，原来题目的真正要求是查看数组内是否有重复元素且相邻重复元素索引间隔不大于K，虽然题目理解错了，但是用哈希表依然能够解决

225-Implement Stack using Queues

我的想法：看到这个题目我就笑了，用队列实现栈，在js里这两个都不存在，所以只能先定义好队列，再通过数组的一些方法实现栈（想想就好蠢）理想答案：参考我的另一篇文章JS实现复杂数据结构

88.Merge Sorted Array

我的想法：其实合并两个数组并没有什么难度，但是题目要求是in-place，也就是不占用额外空间，所以需要在其中一个数组上完成合并，而不能新声明一个数组理想答案：其实之前意识到这道题和归并排序有点像，但是我当时想的是从前往后比较，看了答案之后才发现应该从后往前比较，这样就可以提前把nums1扩展到m+n长度，然后从索引值为m+n-1的地方开始赋值

203-Remove Linked List Elements

我的想法：这道题其实很简单，因为对于单链表来说，只有next这样一个指针，所以只能单向进行遍历，而因为不能直接比较next的val，所以需要递归；其次就是需要当第一个元素就是val时注意返回值的改变理想答案：基本上就是我的思路

58.Length of Last Word

我的想法：又到了replace大显身手的时候了，在js中，字符串变成数组是非常简单的（split），所以只需要将其转换成数组之后返回数组最后一个元素的长度就可以了，需要注意的是需要用正则表达式去掉原字符串中的前后空格理想答案：这次js只用一行就解决了，而别的语言是肯定不行的

507-Perfect Number

我的想法：既然是它的因子相加，那就需要确定其根值，然后从根值开始进行遍历，如果能够整除，就将该数字和其商都加进结果中，需要注意的是0和1都需要返回false 理想答案：除了我的思路还可以把所有的“完美数字”列出来，然后看num是不是在其中（这个肯定复杂度最低吧，因为在int范围内的“完美数字”只有5个）

2017-3-30

67-Add Binary

我的想法：虽然题目很简短，但是解决起来却不是那么简单，其实实现的就是二进制的加法，应该是用位运算吧，因为模拟的是计算机内部的处理（或者当做数字字符串来循环处理）理想答案：答案里面没有用位运算的，都是对a和b进行循环处理，难点在于对进位的处理，需要用一个变量保存进位情况

14-Longest Common Prefix

我的想法：既然是求最长公共前缀，所以需要对数组中的字符串进行遍历，同时需要有一个指针来进行前缀字符串的选取理想答案：我没有写出来的原因是被判断字符串的前缀是否为某一字符串困住了，看完答案之后发现其实用indexOf就可以解决了

160-Intersection of Two Linked Lists

我的想法：如果在某个点合并为一个链表，特点就是a.next==b.next，难点在于对于循环的控制，因为对于单链表来说你只知道next和当前的val 理想答案：用两个指针进行遍历，遍历结束条件是两个指针相等，而如果遍历A的指针到达了A的终点，就将指针重新只想B的起点，这样就可以保证两个指针最终会指向同一点（如果两个链表有交集的话），因为相当于两个指针同时走了A+B的长度

400-Nth Digit

我的想法：我觉得应该先确定大致范围，就是在哪个数字中，然后再判断具体是这个数字的第几位；难点在于确定其大致范围理想答案：比我的思路更进一步，其实可以分成三步：首先确定这个数字有几位，然后确定这个数字是多少，最后确定需要返回这个数字的第几位

475. Heaters**

我的想法：既然是求最小角度，就应该同时考虑房子和加热器的位置，所以可以将其分成几种情况单独讨论，房子在加热器的左边或右边和房子在两个加热器的中间理想答案：在对房子进行遍历的基础上移动加热器的指针，当房子的位置的2倍大于左右热水器的位置和的时候，说明此时的房子应该被右边的加热器加热，此时就应该移动加热器的指针，同时有一个变量保存热水器的加热范围，其应该是加热器和房子距离的最大值

190-Reverse Bits

我的想法：其实在js中这类处理是很简单的，就是对一些自带的方法进行组合调用，不过需要注意的是题目要求在32位的前提下，所以需要进行“补0”，（toString(2)的结果是不够32位的）理想答案：js的答案没有看到，看其他语言的答案，基本上都是用位运算来解决，但是我试了一下，在js里有符号不对的问题，到现在也没有解决

303-Range Sum Query - Immutable

我的想法：这道题其实本身并没有什么难度，但是看完input之后就不知道题目到底想干什么？可能是想让你实现NumArray的原型，然后在原型上扩展sumRange方法吧理想答案：最后将别人写的java答案改写成了js的，但是总感觉这道题的意义不大

408-Valid Word Abbreviation

锁

28-Implement strStr()

我的想法：看完对strStr()的描述之后，我首先想到的是js中的indexOf()方法，然后试了一下成功Accepted…… 理想答案：好多提交的答案是老老实实进行遍历，还有的是利用KMP算法（复杂度会大大降低）

69-Sqrt(x)

我的想法：既然是求根值，那可以从二分之一处开始循环判断，但是总感觉会有更简便的方法（比如位运算？）理想答案：果然我的思路是属于最慢最容易想到的，比较好的方法是二分查找和牛顿迭代法

155-Min Stack

我的想法：这种题对于js来说意义不大，因为只会考察到数组的相关方法，不过我在多次sumbit的失败中知道了array.sort()方法是会改变原数组的，具体如何用js解这道题参考我的另一篇文章：JS实现复杂数据结构

414-Third Maximum Number

我的想法：复杂度要求是O(n)，所以肯定需要对之前的值进行保存，所以可以用三个变量分别保存目前为止最大、第二大和第三大的数是多少，然后进行比较替换（但是这样感觉复杂度会比O(n)大）理想答案：大部分答案我都没看懂，所以只能按照自己理解的去写；一种方法是逐个比较，另一种方法是先将数组排序，然后再进行遍历

532-K-diff Pairs in an Array

我的想法：本来打算先将数组排序后进行遍历，但是考虑到复杂度太高，所以就打算用哈希表了，不过由于js中没有哈希表，所以可能复杂度也不会低多少理想答案：通过两个指针进行判断，其中一个指针进行遍历，另外一个指针用来寻找和当前遍历到的元素配对的数字，需要注意的是相同的数字只能算一次

204-Count Primes

我的想法：既然是求素数的个数，那肯定得知道如何求素数，但是我并不知道如何判断一个数是不是素数，所以我就打算看答案了理想答案：质数（素数）判断思路->对正整数n，如果用2到根号n之间的所有整数去除，均无法整除，则n为质数