在 Path Sum 和 Path Sum Ⅱ之后，Path Sum 大家庭又迎来了第三位成员。那么这个新成员又提出了什么样的要求呢？
题意是这样的：给出一棵二叉树和一个数值 sum，计算这棵树上的节点之和等于sum 的所有路径的条数。和之前不同的是，这道题中路径可以从树中的任何一个节点开始。 继续阅读“LeetCode-437-Path Sum Ⅲ”
LeetCode-646-Maxinum Length of Pair Chain
题意：给出 n 组数，每组有两个数，第一个数总是比第二个数字小。如果两组数 (a,b) 和 (c,d) 之间，有 b < c，那么就称 (a,b)和 (c,d) 之间形成了一个chain。求出这 n 组数中能形成的最长的 chain 的长度。
例子：输入[[1,2], [2,3], [3,4]]，因为[1,2] -> [3,4]，所以返回2。 继续阅读“LeetCode-646-Maxinum Length of Pair Chain”
LeetCode-494-Target Sum
这个题也是一道动态规划题目。题意是：给出一系列数和一个目标数，使用+和-来使这些数字的和等于给定的目标数，求总共可行的方法数。
例子：输入[1, 1, 1, 1, 1]，target = 3，那么：
|
1 2 3 4 5 6 |
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 |
所以最后的输出结果是：5 继续阅读“LeetCode-494-Target Sum”
LeetCode-120-Triangle
这道题的题意是：给定一个数组形成的三角形，在从三角形的顶部出发的路径中，求节点数值相加结果为最小的和。
例子：输入
|
1 2 3 4 5 6 7 |
[ [2], [3,4], [6,5,7], [4,1,8,3] ] |
那么从顶部到底部最小的一条路径和为：2+3+5+1=11。
思路：这是一道逆序的二维动态规划题，和之前看过的一道题–《龙与地下城》非常相似，都是逆序地从下往上求 DP数组。代码很简单，就不多做分析了，相信大家一看就能看懂。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { for (int i = triangle.size() - 2; i >= 0; i--) { for (int j = 0; j < i + 1; j++) { triangle[i][j] = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]; } } return triangle[0][0]; } }; |
LeetCode-279-Perfect Squares
又是一道非常典型的动态规划的题目。这道题的题意是：给定一个正整数n，那么总可以有若干个完全平方数之和等于n，求出最少的个数。如 n = 12, 12 = 4 + 4 + 4，因此返回3。又如 n = 13, 13 = 4 + 9，因此返回2。 继续阅读“LeetCode-279-Perfect Squares”
LeetCode-63-Unique Paths Ⅱ
这道题是Unique Path的续集。
题意：输入一个二维数组，这个二维数组的元素如果是0，表示对应网格处没有障碍，可以正常向下或向右移动；如果这个数字是1，表示对应网格处有个障碍，机器人?将不能通过。 继续阅读“LeetCode-63-Unique Paths Ⅱ”
LeetCode-62-Unique Paths
这道题是一道典型的动态规划问题。如图：
一个机器人的起始位置是左上方的网格，每次只能往下或者往右走。网格的长和高分别是 m 和 n，求机器人要走到图中的五角星处共有多少种走法？ 继续阅读“LeetCode-62-Unique Paths”
LeetCode-234-Palindrome Linked List
题意：判断一个链表是否是回文链表。
LeetCode-21-Merge Two Sorted Lists
这道题的要求是合并两个有序单链表。 继续阅读“LeetCode-21-Merge Two Sorted Lists”
LeetCode-7-Reverse Integer
这道题仍然属于一道简单题。题目描述是这样的：给定一个32位signed int类型的整数，将它进行反转，如输入123返回321，输入-123返回-321。另外，题目下的提示中也说明了一些特殊情况，一种是输入10、100这样末尾是0的数字时应该返回什么，另外一种是反转1000000003 时，结果有可能溢出。
首先我们先来思考一下为什么上面的结果会溢出。输入整数的类型为signed int，因此用二进制形式表示时，第一位是一个符号位，剩下的31位用来表示数字。231 = 2147483648，所以输入数字的范围是-2147483648 ~ 2147483647。而1000000003反转的结果是3000000001，超出了上述范围，因此发生了溢出，此时直接返回0即可。代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int reverse(int x) { long long res = 0; while(x) { res = res * 10 + x %10; x /= 10; } if (res > INT32_MAX || res < INT32_MIN) { return 0; } return res; } |