leetCode解题报告5道题(八)
source link: https://blog.csdn.net/ljphhj/article/details/25868181
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目一：
Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
分析：
题意给我们一棵“完全二叉树”，让我们把二叉树中每个结点的next域根据如例子那样给它赋值。
看到这个题目，我们的第一反应可能是
1、层次遍历二叉树（这样要用到一个queue队列，并不满足题意的对空间的要求）
2、递归方法(这个是可以的)
但因为这道题目很特殊，二叉树是一棵完全二叉树，所以我们现在要用循环迭代的方法来求解这道题。
具体看代码中的注释
AC代码:
题目二：
Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
分析：
这题跟上面那个题目的区别在于条件“所给二叉树并不一定是完全二叉树”了，这样子，在上一题的基础上，我们需要去找到每一层的第一个结点，找到这个第一个满足的结点，其他的思路跟上一题是一样的。
AC代码：
题目三：
Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
AC代码：
题目四：Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
分析：
这道题目和上面那道题目的思路基本上是一样的arrays[i] = arrays[i] + arrays[i-1].但是由于题目要求给我们的空间就O(k)，也就是说当我们想改变下一行的值arrays[i]的话我们必须从中间向左边改变，然后右边用r-i 来对称设置值，程序一开始我们先设置出k个位置的值，每个值都为1。
比如 我们要求的K=4 则
r <= k;
r=0： [1,1,1,1,1]
r=1： [1,1,1,1,1];
r=2：[1,2,1,1,1];
r=3：[1,3,3,1,1];
k=4 ：[1,4,6,4,1]
大家看看我的代码，如果我们不用 “从中间向左边改变，然后右边用r-i 来对称设置值”这样的话，会出现什么问题！
AC代码：
题目五：
Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
分析：
这题为典型的DP问题，求最短路径长度，也可以用递归的方法来求.
设用一个数组arr[i][j] 来存储这个三角形。
主要思想：动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。
则从三角形的最后一行向上求出每个点对应的最短路径，并把值存下来，最终arr[0][0]就为我们要得到的值
最后一行的arr[3][] = {4,1,8,3};
则当到倒数第二行时，每个结点arr[2][i] 的最短路径为 arr[2][i] = min{arr[2][i] + arr[2+1][i] , arr[2][i] + arr[2+1][i+1] };
这样我们就可以得到倒数第二行的所有点到叶子的最短路径长度了，一直往上，直到第一行就得到了最后的结果arr[0][0]
AC代码：
Recommend
-
8
leetCode解题报告之构造二叉树(递归)_快乐de胖虎-CSDN博客此博文主要讲述了构造二叉树的两种方法： 1、通过先序和中序构造出二叉树( 来自leetCode OJ上的 题目：
-
9
比较简单的几道题，不做详细的解释，只为之后可以回头看看自己之前的代码!! 虽然几道题都比较简单，但感觉自己写得不好，希望博文如果被哪位大神看到，可以留言下写下你的做法！ 题目一： Reverse Linked List II Reverse a link...
-
7
题目一：Valid Number Validate if a given string is numeric. Some examples:"0" => true" 0.1 " => true"abc" => false
-
9
题目一：Combinations Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3],...
-
7
题目一： Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters fo...
-
7
题目一：Subsets Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order.The solution set must not cont...
-
4
题目一：Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = "aabcc", s2 = "dbbca", When s3 =
-
8
题目一： Path Sum Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the bel...
-
10
题目一： Longest Consecutive Sequence Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2]
-
7
题目一： Binary Tree Zigzag Level Order Traversal Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and altern...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK