016/algorithm

/src/main/java/com/wen/algorithm/leetcode/LeetCode121.java
package com.wen.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
* 121. 买卖股票的最佳时机
*
* 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
*
* 如果你只允许进行两次交易，请设计一个算法来找出最大利润。
* 注意你不能同时参与多次交易（你必须在再次购买前出售掉之前的股票）。
*
* 示例 1:
*
* 输入: [3,3,5,0,0,3,1,4]
* 输出: 6
* 解释: 在第 4 天（股票价格 = 0）买入，在第 6 天（股票价格 = 3）卖出，利润 = 3-0 = 3。
* 接着在第 7 天（股票价格 = 1）买入，在第 8 天（股票价格 = 4）卖出，利润 = 4-1 = 3。
* 示例 2:
*
* 输入: [1,2,3,4,5]
* 输出: 4
* 解释: 在第 1 天（股票价格 = 1）买入，在第 5 天 （股票价格 = 5）卖出, 利润 = 5-1 = 4。
* 注意你不能在第一天买入股票，之后再买入一天再卖出。
* 示例 3:
*
* 输入: [7,6,4,3,1]
* 输出: 0
* 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
*/
public class LeetCode121 {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 0; i < prices.length - 1; i++) {
int currentPrice = prices[i];
int nextPrice = prices[i + 1];
if (nextPrice > currentPrice) {
profit += nextPrice - currentPrice;
}
}
return profit;
}
}

/src/main/java/com/wen/algorithm/leetcode/LeetCode92.java
package com.wen.algorithm.leetcode;

/**
* 92. 反转链表 II
*
* 给定一个链表，如果其上存在环，请找出该环的入口结点，否则，输出null。
*
* 注意：如果链表中存在环，我们保证链表是一个单链表。
*
* 进阶：能否不使用额外空间解决？
*/
public class LeetCode92 {
public ListNode entryNodeOfLoop(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}

slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}

/src/main/java/com/wen/algorithm/leetcode/LeetCode101.java
package com.wen.algorithm.leetcode;

/**
* 101. 对称二叉树
*
* 给定一个二叉树，检查它是否是镜像对称的。
*
* 示例 1:
*
* 如果二叉树能沿着中心轴分成两部分，每一部分都和另一部分是对称的，那么该二叉树就是对称的。
*
* 例如，这个是镜像对称的:
*
* 4
* / \
* 2 2
* / \ / \
* 1 3 3 1
* 但是，这个不是镜像对称的:
*
* 4
* / \
* 2 2
* \ \
* 3 3
* 进阶：你可以使用原地算法在 O(n) 时间复杂度和空间复杂度中解决吗？
*/
public class LeetCode101 {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
}

/src/main/java/com/wen/algorithm/leetcode/LeetCode111.java
package com.wen.algorithm.leetcode;

/**
* 111. 二叉树优化的最小深度
*
* 给定一个二叉树，找出其最小深度。
* 最小深度是从根节点到最近叶子节点的最短距离。
*
* 示例 1:
*
* 输入: root = [3,9,20,null,null,15,7]
* 输出: 2
* 示例 2:
*
* 输入: root = [2,null,3,null,4,null,5,null,6]
* 输出: