- 博客(268)
- 资源 (6)
- 收藏
- 关注
原创 Sum Root to Leaf Numbers
题目大意:求根到叶子节点的所有路径得到的所有整数和解题思路:递归/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x
2015-05-09 11:16:04
757
原创 Palindrome Partitioning
题目大意:给定一个字符串,要求你对其进行切割,保证切割后每个子字符串都是回文串,要你求所有满足条件的集合解题思路:递归,为了避免重复计算,用isPalindrome[i][j]表示str[i][j]是否是回文串,为0表示不是,1表示是,-1表示还没有遍历进行判断class Solution {public: vector> partition(string s) {
2015-04-13 11:05:31
576
原创 Sort List
题目大意: 给定一个链表,要求你对其进行排序,时间复杂度要求O(nlogn),空间复杂度为常量解题思路:用归并排序,每次递归用快慢指针确定链表的中点。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * List
2015-04-12 22:39:28
619
原创 Insertion Sort List
题目大意:对一个链表进行插入排序每次从头开始寻找小于等于当前数的节点,将这个数插入到节点前面。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(N
2015-04-12 18:10:56
511
原创 Triangle
题目大意: 求一个三角形二维数组从顶到低端的最小路径和解题思路:动态规划class Solution {public: int minimumTotal(vector > &triangle) { if(triangle.empty()) { return 0; } int m = trian
2015-04-11 23:56:00
614
原创 Flatten Binary Tree to Linked List
题目大意:将一个二叉树改成一个前序遍历的链表之前前序遍历递归/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NU
2015-04-11 23:20:32
538
原创 Path Sum II
题目大意:跟这题一样Path Sum, 只不过要求保存路径/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), ri
2015-04-11 20:25:27
539
原创 Path Sum
题目大意:给定一个二叉树,和一个数,要你求二叉树中是否存在一个从根节点到叶子节点的路径,这个路径中所有数的和等于给定的数解题思路:前序递归遍历二叉树,注意结束节点是叶子节点/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeN
2015-04-11 20:17:57
518
原创 Convert Sorted List to Binary Search Tree
题目大意:给定一个排序的链表,要你通过这个链表建立平衡排序二叉树解题思路:递归,每次用快慢指针确定链表的中点来作为根节点/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : v
2015-04-08 20:33:19
481
原创 Convert Sorted Array to Binary Search Tree
题目大意:给定一个排序好的数组,要你将这个数组转化成一个平衡的排序二叉树解题思路:递归,每次取当前数组的中间值作为根节点。#include #include #include using namespace std;struct TreeNode { int val; TreeNode *left; TreeNode *right;
2015-04-08 20:04:42
760
原创 Partition List
题目大意:给定一个链表和一个数值,要使得链表中小于给定数值的节点排在前面,并且保持原来的前后顺序。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL)
2015-04-07 22:25:45
1384
原创 Construct Binary Tree from Inorder and Postorder Traversal
题目大意:给定中序遍历和后序遍历的两组序列,根据这两组序列,还原出二叉树解题思路:递归确定每个子树的根/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int
2015-04-07 12:29:27
361
原创 Construct Binary Tree from Preorder and Inorder Traversal
题目大意:给定二叉树前序遍历和后序遍历的两个序列,要求通过这两个序列还原出二叉树解题思路:递归求每个子树的根节点/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(in
2015-04-07 12:17:03
523
原创 Binary Tree Zigzag Level Order Traversal
题目大意:按从左到右,然后从右到左层次遍历二叉树解题思路:用两个栈来保存每层的子节点。用left2right表示从左到右的栈right2left表示从右到左的栈。当left2right 不为空时,顺序弹出left2right 中的元素,并把它的左节点和右节点顺序压入right2left栈中否则当right2left不为空时,顺序弹出right2left中的元素,并把它的右节点和
2015-04-07 11:47:33
413
原创 Validate Binary Search Tree
题目大意: 判断一个二叉树是否是个排序二叉树,即根节点大于左节点,小于右节点,同时它的左右子树也满足这个要求解题思路:中序遍历,如果当前节点小于等于左子树的最大节点,则不符合要求,若当前节点大于等于右子树的最小节点,则不符合要求/** * Definition for binary tree * struct TreeNode { * int val; *
2015-04-06 18:38:43
440
原创 Unique Binary Search Trees II
题目大意:给定一个数n表示二叉树的节点数,求这么多个节点能够表示的所有二叉树解题思路:先求出这些二叉树的结构,再用中序遍历去给这些二叉树节点赋值/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; *
2015-04-06 15:58:22
1241
原创 Unique Binary Search Trees
题目大意:给定一个数n表示二叉树的节点数,求这么多个节点能够表示多少种不同结构的二叉树class Solution {public: int numTrees(int n) { vector dp(n + 1, 0); dp[1] = 1; dp[0] = 1; for(int i = 2; i <= n; i++) {
2015-04-06 14:49:08
394
原创 Binary Tree Inorder Traversal
中序遍历二叉树/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
2015-04-06 13:57:21
425
原创 Restore IP Addresses
题目大意:给定一个数字串,求这个数字串能表示的所有ip地址解题思路:深度遍历递归class Solution {public: vector restoreIpAddresses(string s) { string ipAddress; vector result; if(s.empty()) {
2015-04-06 12:20:58
468
原创 Reverse Linked List II
题目大意:单链表反转/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:
2015-04-06 11:13:33
331
原创 Decode Ways
求一个数字字符串最多能表示多少个字母组成的字符串。动态规划.dp[i] 表示从0~ i所能表示的最大字符串的种类数class Solution {public: int numDecodings(string s) { if(s.empty()) { return 0; } vector dp(s.size(), 0); if(s[0
2015-04-05 23:27:34
435
原创 Subsets II
题目大意:求一个集合的所有子集,这个集合中有重复的元素出现解题思路:深度遍历class Solution {public: vector > subsetsWithDup(vector &S) { vector > result; if(S.empty()) { return result;
2015-04-04 00:14:30
506
原创 Gray Code
解题思路:按照http://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81 wiki里面的镜像排列方式可以解决这个问题class Solution {public: vector grayCode(int n) { vector result; if(n <= 0) {
2015-04-03 13:16:45
400
转载 Sqrt(x)
转自:http://blog.csdn.net/linhuanmars/article/details/20089131class Solution {public: int sqrt(int x) { if(x < 0) { return -1; } if(x == 0) {
2015-03-29 23:22:44
498
原创 Remove Duplicates from Sorted List
题目大意:给定一个链表,要求删除重复的节点,保证相邻的两个值相同的节点只保留一个/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };
2015-03-28 15:08:14
441
原创 Remove Duplicates from Sorted List II
题目大意:给定一个链表,要求将相邻重复的节点给删除解题思路:最开始找到一个pre节点,这个pre节点表示从开始到pre这个节点,链表已经去重那么这个节点表示上一次不重复的节点/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; *
2015-03-28 14:51:45
608
原创 Search in Rotated Sorted Array II
题目大意:旋转数组中寻找给定的值解题思路:二分查找。class Solution {public: bool search(int A[], int n, int target) { return search(A, 0, n - 1, target); }private: bool search(int A[], int low, in
2015-03-28 13:36:16
345
原创 Remove Duplicates from Sorted Array II
题目大意:给定一个数组,要求去除多余的数字,保证去除多余的数字后只有可能两个相同的数字临接。class Solution {public: int removeDuplicates(int A[], int n) { int pre = -1; int len = 0; int num = 0; int spa
2015-03-28 12:39:20
347
原创 Word Search
题目大意:求一个字符串是否存在于由矩阵中,只能沿着上下左右四个方向查找思路:深度遍历class Solution {public: bool exist(vector > &board, string word) { int m = board.size(); int n = -1; if(m > 0) {
2015-03-28 11:25:42
428
原创 Subsets
题目大意:给定一个数组,要求它的所有子集解题思路:先对这个数组进行排序,然后用深度遍历class Solution {public: vector > subsets(vector &S) { vector > result; vector val; sort(S.begin(), S.end()); sub
2015-03-28 10:50:00
390
原创 Combinations
题目大意:从1 ~ n中选出k个不重复的数,求所有这些组合解题思路:深度递归class Solution {public: vector > combine(int n, int k) { vector > result; if(k > n) { return result; }
2015-03-28 09:35:39
371
原创 Sort Colors
题目大意:一个数组,0,1,2代表三种不同颜色(红,白,蓝),要求按颜色排序,红色排前面,白色排中间,蓝色排最后解题思路:可以模仿快速排序的策略,用两个指针p0, p1,分别指向数组的头和尾,p0代表0~p0这个区间的数全是0,p1代表p1~n-1这个区间的数全是2顺序遍历这个数组,如果当前的数是1,就继续遍历下一个数,如果当前的数是0,则将这个数和p0的下一个数交换class Sol
2015-03-26 23:09:33
426
原创 Search a 2D Matrix
题目大意:给定一个矩阵,矩阵每行的数都是从小到大排列的,并且矩阵每行的第一个数比上一行最后一个数大解题思路:将二维的矩阵看做是一个一维的有序数组,然后用二分查找class Solution {public: bool searchMatrix(vector > &matrix, int target) { if(matrix.empty() || matr
2015-03-26 21:49:59
461
转载 Set Matrix Zeroes
转自:http://blog.csdn.net/linhuanmars/article/details/24066199class Solution {public: void setZeroes(vector > &matrix) { if(matrix.empty() || matrix[0].empty()) { return;
2015-03-26 21:01:04
498
原创 Minimum Path Sum
题目也跟之前的http://blog.csdn.net/xiaoxiaoluo/article/details/44651923差不多,这回每个格子有一个值,求到最右下格子时,经过路径的这个格子数总和最小class Solution {public: int minPathSum(vector > &grid) { if(grid.empty() || grid[0
2015-03-26 17:04:16
427
原创 Unique Paths II
跟这题差不多http://blog.csdn.net/xiaoxiaoluo/article/details/44651923, 区别就是每个格子可能会有障碍物,不能到达只要特殊处理这些有障碍的格子就可以class Solution {public: int uniquePathsWithObstacles(vector > &obstacleGrid) {
2015-03-26 16:52:23
997
原创 Unique Paths
题目大意:给定一个矩阵方格,一个机器人在矩阵左上角,它只能向右或向下走,求它走到最右下角有多少种走法。解题思路:dp[i][j]表示走到方格(i, j)一共有多少走法。它至于上方相邻的方格和右边相邻的方格有关dp[i][j] = dp[i - 1][j] + dp[i][j - 1]我们可以把它降成一维的来求解class Solution {public:
2015-03-26 16:39:22
505
原创 Swap Nodes in Pairs
题目大意:链表中的两个数两两交换/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {pu
2015-03-26 16:27:03
960
原创 Rotate List
题目大意:链表的右移操作考虑右移k,k可能大于链表的长度。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class So
2015-03-26 15:54:17
323
转载 Permutation Sequence
转自:http://blog.csdn.net/lqcsp/article/details/23322951class Solution {public: string getPermutation(int n, int k) { vector num(n, 0); int total = 1; for(int i = 0;
2015-03-26 13:57:45
349
[现代编译原理C语言描述
2012-08-13
UNIX环境高级编程第二版.
2011-12-02
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人