8000 20200816 · BoscoSuen/leetcode@cfc97c8 · GitHub
[go: up one dir, main page]
Skip to content

Commit cfc97c8

Browse files
BoscoSuenBoscoSuen
committed
20200816
1 parent 1cf255d commit cfc97c8

File tree

3 files changed

+104
-0
lines changed

3 files changed

+104
-0
lines changed

‎Java/1145.binary-tree-coloring-game.java

Lines changed: 50 additions & 0 deletions
< 10000 /tr>
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/*
2+
* @lc app=leetcode id=1145 lang=java
3+
*
4+
* [1145] Binary Tree Coloring Game
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
class Solution {
24+
/*
25+
如果一个节点确定之后，其subtree对方都不能访问
26+
将left, right, parent看作三个subtree
27+
比较是否有一边subtree的数量大于n/2
28+
if countLeft or countRight are bigger than n/2, player 2 chooses this child of the node and will win.
29+
If countLeft + countRight + 1 is smaller than n/2, player 2 chooses the parent of the node and will win;
30+
otherwise, lose
31+
*/
32+
int l, r;
33+
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
34+
count(root, x);
35+
return Math.max(l, Math.max(r, n - l - r - 1)) > n / 2;
36+
}
37+
38+
private int count(TreeNode root, int target) {
39+
if (root == null) return 0;
40+
int left = count(root.left, target);
41+
int right = count(root.right, target);
42+
if (root.val == target) {
43+
l = left;
44+
r = right;
45+
}
46+
return left + right + 1;
47+
}
48+
}
49+
// @lc code=end
50+

‎Java/123.best-time-to-buy-and-sell-stock-iii.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/*
2+
* @lc app=leetcode id=123 lang=java
3+
*
4+
* [123] Best Time to Buy and Sell Stock III
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
假设手上最开始只有0元钱，那么如果买入股票的价格为price，手上的钱需要减去这个price，如果卖出股票的价格为price，
11+
手上的钱需要加上这个price。然后不断更新第一次买，第一次卖，第二次买，第二次卖的钱。
12+
time: O(n)
13+
space: O(1)
14+
*/
15+
public int maxProfit(int[] prices) {
16+
if (prices == null || prices.length == 0) return 0;
17+
int buy1= Integer.MIN_VALUE, buy2= Integer.MIN_VALUE;
18+
int sell1 = 0, sell2 = 0;
19+
for (int price : prices) {
20+
buy1 = Math.max(buy1, -price);
21+
sell1 = Math.max(sell1, buy1 + price);
22+
buy2 = Math.max(buy2, sell1 - price);
23+
sell2 = Math.max(sell2, buy2 + price);
24+
}
25+
return sell2;
26+
}
27+
}
28+
// @lc code=end
29+

‎Java/1347.minimum-number-of-steps-to-make-two-strings-anagram.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
/*
2+
* @lc app=leetcode id=1347 lang=java
3+
*
4+
* [1347] Minimum Number of Steps to Make Two Strings Anagram
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
public int minSteps(String s, String t) {
10+
int[] count = new int[26];
11+
for (int i = 0; i < s.length(); ++i) {
12+
count[s.charAt(i) - 'a']++;
13+
count[t.charAt(i) - 'a']--;
14+
}
15+
int res = 0;
16+
for (int c : count) {
17+
if (c > 0) {
18+
res += c;
19+
}
20+
}
21+
return res;
22+
}
23+
}
24+
// @lc code=end
25+

0 commit comments

Comments
 (0)
0