102. 二叉树的层次遍历
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/description/
题目
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
解题思路：
层次遍历，没啥好说的，就是本题需要将层次区分开来。因此传统的方法，需要做一些修订。用一个队列保存当前层次的所有节点。
每一轮遍历的时候，依次出队所有的节点，存入结果，并遍历出队的所有节点，如果有子节点则存入队列，等待下一轮遍历。
也就是有两层的遍历，用一个临时的队列，保存中间结果
代码：
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
queue.add(root);
}
List<List<Integer>> result = new ArrayList<>();
while(!queue.isEmpty()){
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> tempQueue = new ArrayDeque<>(queue);
while (!tempQueue.isEmpty()){
TreeNode node = tempQueue.poll();
ans.add(node.val);
}
tempQueue = new ArrayDeque<>(queue);
queue.clear();
while(!tempQueue.isEmpty()){
TreeNode node = tempQueue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
result.add(ans);
}
return result;
}
122. 买卖股票的最佳时机 II
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解题思路：
dp题。尝试写出状态转移方程。
设s[i]，第i天股票的价格
1) dp[i], 到第i天，最优的股票收益。
dp[i] = max {max{ s[i] - s[j] + dp[j - 1]} j = 1...i - 1,
dp[i - 1]代表不卖，以及s[i] < s[j]的情况,算法复杂度O(n2)
代码：
public int maxProfit(int[] prices) {
if (prices.length == 0){
return 0;
}
int[] dp = new int[prices.length];
for (int i = 1 ; i < prices.length; i++){
int max = dp[i - 1];
for (int j = 0; j < i; j++){
int temp = prices[i] - prices[j];
temp = temp < 0 ? 0 : temp;
if (j > 0) {
if (temp > 0) {
temp += dp[j - 1];
} else {
temp = dp[j - 1];
}
}
if (temp > max){
max = temp;
}
}
dp[i] = max;
}
return dp[prices.length - 1];
}
169. 求众数
https://leetcode-cn.com/problems/majority-element/description/
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解题思路：
我的思路是，排序，然后逐一比对。直到找到众数为止。但是直觉告诉我应该有更优雅的方式。
这是一道求众数的问题，有很多种解法，其中我感觉比较好的有两种，一种是用哈希表，这种方法需要O(n)的时间和空间，另一种是用一种叫摩尔投票法 Moore Voting，需要O(n)的时间和O(1)的空间，比前一种方法更好。这种投票法先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将当前值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。不仔细弄懂摩尔投票法的精髓的话，过一阵子还是会忘记的，首先要明确的是这个叼炸天的方法是有前提的，就是数组中一定要有众数的存在才能使用，下面我们来看本算法的思路，这是一种先假设候选者，然后再进行验证的算法。我们现将数组中的第一个数假设为众数，然后进行统计其出现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果计数器减到了0，则更换当前数字为候选者。这是一个很巧妙的设定，也是本算法的精髓所在，为啥遇到不同的要计数器减1呢，为啥减到0了又要更换候选者呢？首先是有那个强大的前提存在，一定会有一个出现超过半数的数字存在，那么如果计数器减到0了话，说明目前不是候选者数字的个数已经跟候选者的出现个数相同了，那么这个候选者已经很weak，不一定能出现超过半数，我们选择更换当前的候选者。那有可能你会有疑问，那万一后面又大量的出现了之前的候选者怎么办，不需要担心，如果之前的候选者在后面大量出现的话，其又会重新变为候选者，直到最终验证成为正确的众数，佩服算法的提出者啊。
32. 最长有效括号
https://leetcode-cn.com/problems/longest-valid-parentheses/description/
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
代码：
public int longestValidParentheses(String s) {
int[] dp = new int[s.length()];
int max = 0;
for (int i = 1; i < s.length(); i++){
if (s.charAt(i) == '('){
dp[i] = 0;
}else{
if (dp[i - 1] != 0) {
int index = i - dp[i - 1] - 1;
if (index >= 0 && s.charAt(index) == '(') {
dp[i] = dp[i - 1] + 2;
if (index - 1 >= 0 ){
dp[i] += dp[index - 1];
}
}
}
if (s.charAt(i - 1) == '('){
if (i >= 2) {
dp[i] = dp[i] > dp[i - 2] + 2 ? dp[i] : dp[i - 2] + 2;
}else{
dp[i] = 2;
}
}
if (max < dp[i]){
max = dp[i];
}
}
}
return max;
}
39. 组合总和
https://leetcode-cn.com/problems/combination-sum/description/
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题目分析：
- 一看到这道题，就感觉要用递归来做，应该是回溯算法。百度证实无误。
- 然后自己还没有生写过回溯。想了一会儿，结果不对，和正确解法做了一下比较，修改了一下自己的算法。标答是C++的，在java上需要修改一下，一些特别的地方要处理一下。
直接上代码：
/**
* 核心算法
* @param candidates 数组
* @param target 当前递归子问题需要计算的target
* @param start 开始查找的index
* @param result 当前递归的result数组
* @param ans 最后的答案
*/
private void findOne(int[] candidates, int target, int start, List<Integer> result, List<List<Integer>> ans){
if (target == 0){
List<Integer> list = new ArrayList<>(result); //这里需要新开一个数组，否则会一直复用这个对象，导致结果不对
ans.add(list);
return;
}else if(target < candidates[start]){
return; //不符合的结果，不处理。
}else{
for (int i = start; i < candidates.length; i++){
result.add(candidates[i]);
findOne(candidates, target - candidates[i], i, result, ans);
result.remove(result.size() - 1);
//这里有点像树的遍历，这里就是要一个节点和不要一个节点的分支。然后可以重复使用元素，所以递归子问题，仍然从i开始。
}
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(candidates); //题目没有说排好序的数组，所以这里要先拍个序
findOne(candidates, target, 0, new ArrayList<>(), ans);
return ans;
}
Copyright © 2015 Powered by MWeb, Theme used GitHub CSS.