leecode-js

100-same-tree

// 这里用递归的方法来匹配两个二叉树，需要注意的是，要在判断之前，先判断这个值是否存在

/**
 * Definition for binary tree
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @returns {boolean}
 */
var isSameTree = function(p, q) {
    if (p && q){
        if (p.val == q.val)
            return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
        else
            return false;
    }
    else if (!p && !q)
        return true;
    else
        return false;
};

104-Maximum-Depth-of-Binary-Tree

// 用递归的方法来求二叉树的深度，此外还可以用深度遍历的方式来做，时间复杂度会少很多。

/**
 * Definition for binary tree
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @returns {number}
 */
var maxDepth = function(root) {
    if (!root){return 0;}
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;  
};

122-best-time-to-buy-and-sell-stock-ii

// 由于每天的袜子只有1只，因此只需要考虑能把握整个上升趋势即可。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
        if(!prices.length)
            {return 0;}
            
        var ret = 0;//收益
        var buy = prices[0];
        var last = prices[0];
        for(var i = 1; i < prices.length; i ++)
        {
            // 如果价格低于昨天的价格，买入，并计算收益
            if(prices[i] < last)
            {
                ret += (last - buy);
                buy = prices[i];
            }
            // 更新价格
            last = prices[i];
        }
        // 计算最后一天的收益
        ret += (last - buy);
        return ret;
};

136-single-number

// 这里需要利用异或的原理来解决这个问题，其中一个整数和它本身异或之后得到值是0，0与其他整数异或得到的是这个整数本身

/**
 * @param {number[]} A
 * @return {number}
 */
var singleNumber = function(A) {
    if(A.length == 0){return -1}
    var result = 0;
    for (int i = 0; i < A.length; i++) {
        result = result ^ A[i];
    }
    return result
};

144-binary-tree-preorder-traversal

//这个问题是需要按照前序输出一个二叉树，也就是根，左节点，右节点，利用递归来解决比较简单，这里需要注意的是需要拆分成两个函数，或许使用闭包也可以解决这个问题
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
 
var helper = function(node,arrays){
    if(node === []||node === null){return [];} 
    arrays.push(node.val);
    helper(node.left,arrays);
    helper(node.right,arrays);
    return arrays
}

var preorderTraversal = function(root) {
    var arrays = [];
    helper(root,arrays);   
    return arrays
};

171-excel-sheet-column-number

// 本质上，这是一个26进制的问题，所以只需要按位获取，并乘26就可以了。
/**
 * @param {string} s
 * @return {number} Return column number
 */
var titleToNumber = function(s) {
    if(!s){return 0;}
    var answer = 0;
    for(var i = 0; i < s.length; i++){
	    answer = answer * 26 + (s[i].charCodeAt() - 64);}
	return answer;
};

191-number-of-1-bits

// 这里比较快的方案是向右位移，当然转成字符串判断属于js的福利了……
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    if(!n){return 0;}
    var string = n.toString(2);
    var temp = 0;
    for(var i=0;i<string.length;i++){
        if(string[i]=='1'){temp++}
    }
    return temp
};

96-unique-binary-search-trees

// 首先要明白二叉搜索树的规则（左子树比右子树小），其次要分析，当节点增加时，其实仅仅是在n-1的数量上增加了一层（这一层需要重新进行分配一次，即[0,n-1]~ [n-1,0]），因此用两层搜索来逐个计算出最终的结果。
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    var count = [];
    count[0] =1;  
    count[1] =1;  
    for(var i = 2; i<=n; i++)  
    {  
        count[i] = 0;
        for(var j =0; j<i; j++)  
        {  
            count[i] += count[j]*count[i-j-1];   
        }  
    }  
    return count[n];  
};