这道题的题意是:给出一个数组和一个数字k,返回一个由输入数组中出现次数排在前K位的元素组成的数组。 继续阅读“LeetCode-347-Top K Frequent Elements”
LeetCode-113-Path Sum Ⅱ
这道题与上一篇博客的那道题非常类似,比那个题更近一步,要求找出节点之和等于给定数值的所有路径。 继续阅读“LeetCode-113-Path Sum Ⅱ”
LeetCode-112-Path Sum
题意描述:给出一棵二叉树和一个数值sum,判断这棵树从树根到某个叶子的路径上的数值之和是否等于sum。 继续阅读“LeetCode-112-Path Sum”
LeetCode-198-House Robber
LeetCode上有一些题目,初看描述时会让人觉得丈二和尚摸不着头脑,绞尽脑汁也想不出解决方法,但看了题解之后会大呼过瘾和巧妙,让人感受到算法的神奇和魅力。今天要说的这个题目就具有以上这些特点。 继续阅读“LeetCode-198-House Robber”
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”
WWDC2013 Hidden Gems in Cocoa and Cocoa Touch
这个Seesion介绍了Cocoa和Cocoa Touch框架中一些鲜为人知的特性,总共有29个tips,从中我挑一些比较常用的介绍一下。视频地址。 继续阅读“WWDC2013 Hidden Gems in Cocoa and Cocoa Touch”
WWDC2015 Networking with NSURLSession学习笔记
这个 Session 是我观看的第一个 WWDC Seesion,在线地址在这里。 继续阅读“WWDC2015 Networking with NSURLSession学习笔记”
LeetCode上的power (x,n)类型的题目
下面几道题都是和求 x的 n 次方形式类似的,在这里一起总结一下。 继续阅读“LeetCode上的power (x,n)类型的题目”
LeetCode-101-Symmetric Tree
这道题的题意是判断一棵二叉树是不是对称的,如下图,当一棵树呈现这样的结构时,就可以称作是对称二叉树。
我采用的是递归的方法,根据题意,如果输入的根节点为空的话,那么直接返回 true;否则调用一个辅助函数来处理根节点的左右子树。在这个辅助函数里面,我们将左右子树作为参数传入,先判断左右子树的结构是否相同,相同的前提下判断这两个镜像位置的节点的数值是否相同,然后递归调用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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遍历和它的正常前序遍历结果是一样的。根据这种思路,可以写出如下的算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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); } }; |