2017年11月 – Tamarous

2017-11-292018-05-22

LeetCode-347-Top K Frequent Elements

这道题的题意是：给出一个数组和一个数字k，返回一个由输入数组中出现次数排在前K位的元素组成的数组。继续阅读“LeetCode-347-Top K Frequent Elements”

2017-11-262018-05-22

LeetCode-113-Path Sum Ⅱ

这道题与上一篇博客的那道题非常类似，比那个题更近一步，要求找出节点之和等于给定数值的所有路径。继续阅读“LeetCode-113-Path Sum Ⅱ”

2017-11-262017-12-24

LeetCode-112-Path Sum

题意描述：给出一棵二叉树和一个数值sum，判断这棵树从树根到某个叶子的路径上的数值之和是否等于sum。继续阅读“LeetCode-112-Path Sum”

2017-11-252017-12-24

LeetCode-198-House Robber

LeetCode上有一些题目，初看描述时会让人觉得丈二和尚摸不着头脑，绞尽脑汁也想不出解决方法，但看了题解之后会大呼过瘾和巧妙，让人感受到算法的神奇和魅力。今天要说的这个题目就具有以上这些特点。继续阅读“LeetCode-198-House Robber”

2017-11-242017-12-24

LeetCode-70-Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer. 继续阅读“LeetCode-70-Climbing Stairs”

2017-11-222017-12-24

WWDC2013 Hidden Gems in Cocoa and Cocoa Touch

这个Seesion介绍了Cocoa和Cocoa Touch框架中一些鲜为人知的特性，总共有29个tips，从中我挑一些比较常用的介绍一下。视频地址。继续阅读“WWDC2013 Hidden Gems in Cocoa and Cocoa Touch”

2017-11-182017-11-18

WWDC2015 Networking with NSURLSession学习笔记

这个 Session 是我观看的第一个 WWDC Seesion，在线地址在这里。继续阅读“WWDC2015 Networking with NSURLSession学习笔记”

2017-11-122017-12-24

LeetCode上的power (x,n)类型的题目

下面几道题都是和求 x的 n 次方形式类似的，在这里一起总结一下。继续阅读“LeetCode上的power (x,n)类型的题目”

2017-11-052018-01-05

LeetCode-101-Symmetric Tree

这道题的题意是判断一棵二叉树是不是对称的，如下图，当一棵树呈现这样的结构时，就可以称作是对称二叉树。

Symetric Tree

我采用的是递归的方法，根据题意，如果输入的根节点为空的话，那么直接返回 true；否则调用一个辅助函数来处理根节点的左右子树。在这个辅助函数里面，我们将左右子树作为参数传入，先判断左右子树的结构是否相同，相同的前提下判断这两个镜像位置的节点的数值是否相同，然后递归调用。

class Solution {
    public:
        bool isSymmetric(TreeNode *root) {
            if (root == NULL) {
                return true;
            }
            return isSymmetricHelper(root->left, root->right);
        }
    private:
        bool isSymmetricHelper(TreeNode *p,  TreeNode *q) {
            if (!p && !q) {
                return true;
            }
            if (p == NULL || q == NULL) {
                return false;
            }
            return (p->val == q->val) && isSymmetricHelper(p->left, q->right) && isSymmetricHelper(p->right, q->left);
        }
    };

class Solution {

public:

bool isSymmetric(TreeNode *root) {

if (root == NULL) {

return true;

}

return isSymmetricHelper(root->left, root->right);

}

private:

bool isSymmetricHelper(TreeNode *p, TreeNode *q) {

if (!p && !q) {

return true;

}

if (p == NULL || q == NULL) {

return false;

}

return (p->val == q->val) && isSymmetricHelper(p->left, q->right) && isSymmetricHelper(p->right, q->left);

}

};

今天刷剑指 offer，发现这道题还有另一种解法：首先定义另一种前序遍历A，也就是访问过父节点后，先遍历右子节点再遍历左子节点。那么一棵对称二叉树的A遍历和它的正常前序遍历结果是一样的。根据这种思路，可以写出如下的算法：

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        return isSymmetrical(root,root);
    }    
    bool isSymmetrical(TreeNode *root1, TreeNode *root2) {
        if (root1 == NULL && root2 == NULL) {
            return true;
        }
        if (root1 == NULL || root2 == NULL) {
            return false;
        }
        if (root1->val != root2->val) {
            return false;
        }
        return isSymmetrical(root1->left, root2->right) && isSymmetrical(root1->right, root2->left);
    }
};

class Solution {

public:

bool isSymmetric(TreeNode *root) {

return isSymmetrical(root,root);

}

bool isSymmetrical(TreeNode *root1, TreeNode *root2) {

if (root1 == NULL && root2 == NULL) {

return true;

}

if (root1 == NULL || root2 == NULL) {

return false;

}

if (root1->val != root2->val) {

return false;

}

return isSymmetrical(root1->left, root2->right) && isSymmetrical(root1->right, root2->left);

}

};