第28天--算法（Leetcode 116,118,121,122,123）
116.填充每个节点的下一个右侧节点
public Node connect(Node root) {
if(root == null) {
return null;
}
MyQueue myQueue = new MyQueue();
myQueue.add(root);
while(!myQueue.isEmpty()) {
Node pre = null;
int size = myQueue.size;
for(int i = 0;i < size;i ++) {
Node cur = myQueue.poll();
if(cur.left != null) {
myQueue.add(cur.left);
}
if(cur.right != null) {
myQueue.add(cur.right);
}
if(pre != null) {
pre.next = cur;
}
pre = cur;
}
}
return root;
}
class MyQueue {
Node head;
Node tail;
int size;
public MyQueue() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void add(Node node) {
size ++;
if(head == null) {
head = node;
tail = node;
}else {
tail.next = node;
tail = node;
}
}
public Node poll() {
size --;
Node n = head;
head = head.next;
n.next = null;
return n;
}
}
118.杨辉三角
public List> generate(int numRows) {
List> ans = new ArrayList<>();
for(int i = 0;i < numRows;i ++) {
List cur = new ArrayList<>();
cur.add(1);
ans.add(cur);
}
for(int i = 1;i < numRows;i ++) {
for(int j = 1;j < i;j ++) {
ans.get(i).add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
}
ans.get(i).add(1);
}
return ans;
}
121.买卖股票的最佳时机
public int maxProfit(int[] prices) {
int ans = 0;
int min = prices[0];
for(int i = 1;i < prices.length;i ++) {
int cur = prices[i] - min;
ans = Math.max(ans,cur);
min = Math.min(min,prices[i]);
}
return ans;
}
122.买卖股票的最佳时机2
public int maxProfit(int[] prices) {
if(prices.length == 1) {
return 0;
}
int ans = 0;
for(int i = 1;i < prices.length;i ++) {
if(prices[i] > prices[i - 1]) {
ans += prices[i] - prices[i - 1];
}
}
return ans;
}
122.买卖股票的最佳时机3
public int maxProfit(int[] prices) {
if(prices.length < 2) {
return 0;
}
int min = prices[0];
int doneOnceMaxAndBuy = -prices[0];
int doneOnceMax = 0;
int ans = 0;
for(int i = 0;i < prices.length;i ++) {
min = Math.min(min,prices[i]);
ans = Math.max(ans,doneOnceMaxAndBuy + prices[i]);
doneOnceMax = Math.max(doneOnceMax,prices[i] - min);
doneOnceMaxAndBuy = Math.max(doneOnceMaxAndBuy,doneOnceMax - prices[i]);
}
return ans;
}