- 2020-05-01
- 2020-05-02
- 2020-05-04
- 2020-05-05
- 2020-05-07
- 2020-05-08
- 2020-05-10
- 2020-05-11
- 2020-05-12
- 2020-05-14
- 2020-05-15
2020-05-01
763. Partition Labels
Description
A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Example 1: Input: S = “ababcbacadefegdehijhklij” Output: [9,7,8] Explanation: The partition is “ababcbaca”, “defegde”, “hijhklij”. This is a partition so that each letter appears in at most one part. A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts. Note:
S will have length in range [1, 500]. S will consist of lowercase letters (‘a’ to ‘z’) only.
Solution
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> res = new ArrayList<>();
if (S == null || S.isEmpty()) {
return res;
}
int[] idx = new int[26];
//find last index of a char.
for (int i = 0; i < S.length(); i++) {
idx[S.charAt(i) - 'a'] = i;
}
int start = 0;
int end = 0;
for (int i = 0; i < S.length(); i++) {
//end of the current partition so far.
end = Math.max(end,idx[S.charAt(i)-'a']);
//if it's already the end, cut as a partition and add length to res.
if(end == i){
res.add(end-start+1);
start = i + 1;
}
}
return res;
}
}
55. Jump Game
Description
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 3 * 10^4 0 <= nums[i][j] <= 10^5
Solution
class Solution {
public boolean canJump(int[] nums) {
int dis = 0;
for (int i = 0; i <= dis; i++) {
dis = Math.max(dis, i + nums[i]);
if (dis >= nums.length-1) {
return true;
}
}
return false;
}
}
45. Jump Game II
Description
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
Solution
//This is an implicit bfs solution. i == curEnd means you visited all the items on the current level. Incrementing jumps++ is like incrementing the level you are on. And curEnd = curFarthest is like getting the queue size (level size) for the next level you are traversing.
class Solution {
public int jump(int[] nums) {
int jump = 0, curEnd = 0, farest = 0;
for (int i = 0; i < nums.length - 1; i++) {
//get farest possible position this level's children can reach
farest = Math.max(farest, i + nums[i]);
//early stop;
if (farest >= nums.length - 1) {
jump++;
break;
}
//end of the level traveral, jump to next level, and curEnd will be the farest we can reach for all children.
if (i == curEnd) {
jump++;
curEnd = farest;
}
}
return jump;
}
}
2020-05-02
135. Candy
Description
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?
Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Solution
//first check left neighbor then backwards to check right neighbor.
//It's due to the computation dependency. In the second scan, num[i-1]=max(num[i]+1,num[i-1]). In other words, num[i-1] depends on num[i]. So num[i] must be computed before num[i-1].
class Solution {
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0){
return 0;
}
int len = ratings.length;
int[] candies = new int[len];
Arrays.fill(candies,1);
for(int i = 1;i < len ;i++){
if(ratings[i] > ratings[i-1]){
candies[i] = candies[i-1] + 1;
}
}
//candies[i] will not be changed after this itera so can sum it up.
int sum = candies[len-1];
for(int i = len-1;i>0;i--){
if(ratings[i-1] > ratings[i]){
candies[i-1] = Math.max(candies[i-1],candies[i] + 1);
}
sum += candies[i];
}
return sum;
}
}
1111. Maximum Nesting Depth of Two Valid Parentheses Strings
Description
A string is a valid parentheses string (denoted VPS) if and only if it consists of “(“ and “)” characters only, and:
It is the empty string, or It can be written as AB (A concatenated with B), where A and B are VPS’s, or It can be written as (A), where A is a VPS. We can similarly define the nesting depth depth(S) of any VPS S as follows:
depth(“”) = 0 depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s depth(“(“ + A + “)”) = 1 + depth(A), where A is a VPS. For example, “”, “()()”, and “()(()())” are VPS’s (with nesting depths 0, 1, and 2), and “)(“ and “(()” are not VPS’s.
Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS’s (and A.length + B.length = seq.length).
Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.
Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.
Example 1:
Input: seq = "(()())"
Output: [0,1,1,1,1,0]
Example 2:
Input: seq = "()(())()"
Output: [0,0,0,1,1,0,1,1]
Constraints:
1 <= seq.size <= 10000
Solution
//main idea is to split seq into two subarrays which has the Min(Max(A,B)) where "(" +1 and ")" -1. In order to minimize, try to evenly distribute into two.
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int A = 0, B = 0;
int[] res = new int[seq.length()];
for(int i = 0;i<seq.length();i++){
char c = seq.charAt(i);
//will add 1, so pick the less one.
if(c == '('){
if(A > B){
B++;
res[i] = 1;
}else{
//res[i] default to be 0, no need to set res[i].
A++;
}
}else{
// will minius 1, pick the more one.
if(A < B){
B--;
res[i] = 1;
}else{
A--;
}
}
}
return res;
}
}
767. Reorganize String
Description
Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.
If possible, output any possible result. If not possible, return the empty string.
Example 1:
Input: S = "aab"
Output: "aba"
Example 2:
Input: S = "aaab"
Output: ""
Note:
S will consist of lowercase letters and have length in range [1, 500].
Solution
//only if the char with max count exceed (len+1)/2 will return ""
//if not then fill the res from 0,2,4,... then fill the rest regardless of the order.
class Solution {
public String reorganizeString(String S) {
int[] map = new int[26];
char max_key;
for(char c: S.toCharArray()){
map[c-'a']++;
}
int max = 0, letter = 0;
for (int i = 0; i < map.length; i++) {
if (map[i] > max) {
max = map[i];
letter = i;
}
}
if(max > (S.length()+1)/2){
return "";
}
char[] res = new char[S.length()];
int idx = 0;
while(map[letter]>0){
res[idx] = (char)(letter+'a');
map[letter]--;
idx += 2;
}
for(int i = 0;i< map.length;i++){
while(map[i]>0){
if(idx>=res.length){
idx = 1;
}
res[idx] = (char)(i+'a');
map[i]--;
idx+=2;
}
}
return String.valueOf(res);
}
}
759. Employee Free Time
Description
We are given a list schedule of employees, which represents the working time for each employee.
Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.
Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.
(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.
Example 1:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.
Example 2:
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
Constraints:
1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10^8
Accepted
Solution
/*
// Definition for an Interval.
class Interval {
public int start;
public int end;
public Interval() {}
public Interval(int _start, int _end) {
start = _start;
end = _end;
}
};
*/
//same idea as find intervals.
class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList();
if(schedule == null || schedule.size() == 0){
return res;
}
List<Interval> intervals = new ArrayList();
for(List<Interval> list : schedule){
intervals.addAll(list);
}
intervals.sort((a,b)->(a.start==b.start?a.end-b.end:a.start-b.start));
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for(int i = 1;i<intervals.size();i++){
Interval interval = intervals.get(i);
if(interval.start > end){
Interval temp = new Interval(end,interval.start);
res.add(temp);
start = interval.start;
end = interval.end;
}else{
end = Math.max(end, interval.end);
}
}
return res;
}
}
714. Best Time to Buy and Sell Stock with Transaction Fee
Description
Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.
Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Note:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
Solution
class Solution {
public int maxProfit(int[] prices, int fee) {
int days = prices.length;
int[] buy = new int[days];
int[] sell = new int[days];
buy[0] = -prices[0];
for(int i = 1;i<days;i++){
// keep the same as day i-1, or buy from sell status at day i-1
buy[i] = Math.max(buy[i-1],sell[i-1]-prices[i]);
// keep the same as day i-1, or sell from buy status at day i-1
sell[i] = Math.max(sell[i-1],buy[i-1]+prices[i]-fee);
}
return sell[days-1];
}
}
2020-05-04
861. Score After Flipping Matrix
Description
We have a two dimensional matrix A where each value is 0 or 1.
A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.
After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
Return the highest possible score.
Example 1:
Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
Note:
1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] is 0 or 1.
Solution
//main idea is to first toggle row so it start with 1 (change first idx to 1 will for sure larger the number)
//then count each column, the count for original or toggled will be either count or A.length-count, just max it, no need to change the array.
//then multiple the 1>>idx.
class Solution {
public int matrixScore(int[][] A) {
if(A == null || A.length == 0 || A[0].length==0){
return 0;
}
for(int i = 0;i<A.length;i++){
if(A[i][0]!=1){
toggle(A,i,true);
}
}
int res = 0;
for(int i = 0;i<A[0].length;i++){
int count = 0;
for(int j = 0;j<A.length;j++){
count += A[j][i];
}
res += Math.max(count,A.length-count) * (1<<(A[0].length-i-1));
}
return res;
}
private void toggle(int[][] A, int idx){
for(int i = 0;i<A[idx].length;i++){
if(A[idx][i]==1){
A[idx][i] = 0;
}else{
A[idx][i] = 1;
}
}
}
}
455. Assign Cookies
Description
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.
Example 1:
Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Solution
//main idea is to go through all the cookies and assign the least size to the least child.
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
for(int j = 0;i<g.length && j<s.length;j++){
if(g[i]<=s[j]) i++;
}
return i;
}
}
1221. Split a String in Balanced Strings
Description
Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.
Given a balanced string s split it in the maximum amount of balanced strings.
Return the maximum amount of splitted balanced strings.
Example 1:
Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.
Example 2:
Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.
Example 3:
Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".
Example 4:
Input: s = "RLRRRLLRLL"
Output: 2
Explanation: s can be split into "RL", "RRRLLRLL", since each substring contains an equal number of 'L' and 'R'
Constraints:
1 <= s.length <= 1000
s[i] = 'L' or 'R'
Solution
//once the sum reach 0, means it's balanced.
//"LRLR" is 0 but not balanced, because first LR already considered as one and second as other one.
class Solution {
public int balancedStringSplit(String s) {
int res = 0;
int sum = 0;
for(char c:s.toCharArray()){
if(c == 'L'){
sum++;
}else{
sum--;
}
if(sum == 0){
res++;
}
}
return res;
}
}
452. Minimum Number of Arrows to Burst Balloons
Description
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
Example:
Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2
Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Solution
//main idea is to find common lapse.
class Solution {
public int findMinArrowShots(int[][] points) {
if(points== null || points.length == 0){
return 0;
}
Arrays.sort(points,(a,b)->(a[0]-b[0]));
int start = points[0][0];
int end = points[0][1];
int res = 1;
for(int i = 1;i<points.length;i++){
int[] point = points[i];
//overlaped, find the min end
if(point[0]<=end){
start = point[0];
end = Math.min(end,point[1]);
}else{
//not overlaped, start a new interval and count++.
start = point[0];
end = point[1];
res++;
}
}
return res;
}
}
2020-05-05
279. Perfect Squares
Description
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Solution
//DP solution
//find the min step to go through i-j*j to j
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j*j<=i;j++){
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
//BFS solution
//whenever try to find a min path, always for for BFS
//starting from 0, level 1 will reach all the perfect square number.
//then for each of the perfect square number,
class Solution {
public int numSquares(int n) {
int[] cnt = new int[n+1];
//store all the perfect square number
List<Integer> perfectSq = new ArrayList();
Queue<Integer> queue = new LinkedList();
for(int i = 1;i*i<=n;i++){
queue.offer(i*i);
cnt[i*i] = 1;
perfectSq.add(i*i);
}
//if n is already perfect
if(perfectSq.get(perfectSq.size()-1) ==n){
return 1;
}
int level = 1;
while(!queue.isEmpty()){
int queueSize = queue.size();
level++;
//go through all the numbers at this level.
for(int j = 0;j<queueSize;j++){
int cur = queue.poll();
//from cur, jump perfSq and reach cur+perfSq
for(int perfSq : perfectSq){
//we reached it.
if(cur + perfSq == n){
return level;
//not reach the end and this number has not been explored.(uncheck will lead to loop)
}else if(cur+perfSq <n && cnt[cur+perfSq] == 0){
cnt[cur+perfSq] = level;
queue.offer(cur+perfSq);
}else if(cur+perfSq>n){
break;
}
}
}
}
return cnt[n];
}
}
107. Binary Tree Level Order Traversal II
Description
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
Solution
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList();
levelBuilder(root,0,res);
return res;
}
private void levelBuilder(TreeNode root, int level, List<List<Integer>> res){
if(root == null) return;
if(level >= res.size()){
res.add(0,new ArrayList<Integer>());
}
//go deep first
levelBuilder(root.left,level+1,res);
levelBuilder(root.right,level+1,res);
//add val to list.
//like backtraversal.
res.get(res.size()-level-1).add(root.val);
}
}
2020-05-07
773. Sliding Puzzle
Description
On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Examples:
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Input: board = [[3,2,4],[1,5,0]]
Output: 14
Note:
board will be a 2 x 3 array as described above.
board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].
Solution
//main idea is to use BFS to iterate through the possible next str.
class Solution {
public int slidingPuzzle(int[][] board) {
//depend on the zero index, all possible index to swap.
int[][] dirs = new int[][][[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
String end = "123450";
HashSet<String> visited = new HashSet();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
Queue<String> queue = new LinkedList<>();
queue.offer(start);
visited.add(start);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
//go through all str at this level.
for (int i = 0; i < size; i++) {
String cur = queue.poll();
//end condition
if (cur.equals(end)) {
return level;
}
int zero = cur.indexOf("0");
//all possible swap index
for (int dir : dirs[zero]) {
String nextStr = next(cur, zero, dir);
if (!visited.contains(nextStr)) {
queue.offer(nextStr);
visited.add(nextStr);
}
}
}
level++;
}
return -1;
}
private String next(String str, int i, int j) {
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(i, str.charAt(j));
sb.setCharAt(j, str.charAt(i));
return sb.toString();
}
}
207. Course Schedule
Description
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Constraints:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5
Solution
//main idea is to use topological sort to find out all reachable course.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] graph = new int[numCourses][numCourses];
int[] degree = new int[numCourses];
//build the graph and also degree.
//with degree 0 means no prerequiest and ready to be taken.
for(int[] edge : prerequisites){
if(graph[edge[1]][edge[0]]==0){
degree[edge[0]]++;
}
graph[edge[1]][edge[0]] = 1;
}
int count = 0;
Queue<Integer> queue = new LinkedList<>();
//find all course with no prerequisite
for(int i = 0; i<degree.length;i++){
if(degree[i]==0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
int cur = queue.poll();
count++;
//for all of the course next
for(int i = 0;i<numCourses;i++){
//if the course exist(graph[i][j]!=0) and also ready to be taken(--degree == 0)
if(graph[cur][i] != 0 && --degree[i]==0){
queue.offer(i);
}
}
}
//count the number has been taken.
return count == numCourses;
}
}
2020-05-08
111. Minimum Depth of Binary Tree
Description
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
Solution
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
//if one of the children is null, then the null one will return 0 and use the other child's depth plus 1.
//if both of the children are valid, then choose the min.
return (root.left==null || root.right == null)? leftDepth+rightDepth+1 : Math.min(leftDepth,rightDepth)+1;
}
}
529. Minesweeper
Description
Let’s play the minesweeper game (Wikipedia, online game)!
You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:
If a mine (‘M’) is revealed, then the game is over - change it to ‘X’. If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively. If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines. Return the board when no more squares will be revealed.
Example 1:
Input:
[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
Output:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Explanation:
Example 2:
Input:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Explanation:
Note:
The range of the input matrix’s height and width is [1,50]. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square. The input board won’t be a stage when game is over (some mines have been revealed). For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.
Solution
//main idea is to iterate through the board and explore recursively.
class Solution {
int[][] dirs = new int[][][[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
public char[][] updateBoard(char[][] board, int[] click) {
//if it's a mine, boom!
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
//if it's a 'B' or digit, nothing happen
if (board[click[0]][click[1]] != 'E') {
return board;
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(click);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int count = countMine(board, cur[0], cur[1]);
//if no adjacent mine, go expore its adjacent recursivly.
if (count == 0) {
board[cur[0]][cur[1]] = 'B';
for (int[] dir : dirs) {
int new_x = cur[0] + dir[0];
int new_y = cur[1] + dir[1];
if (new_x >= 0 && new_x < board.length && new_y >= 0 && new_y < board[new_x].length && board[new_x][new_y] == 'E') {
queue.offer(new int[]{new_x, new_y});
//very important so can avoid pushed into queue twice.
board[new_x][new_y] = 'B';
}
}
} else {
//have mine adjacent, change to digit.
board[cur[0]][cur[1]] = (char) (count + '0');
}
}
return board;
}
//helper function to count mines adjacent to certain point.
private int countMine(char[][] board, int i, int j) {
int count = 0;
for (int[] dir : dirs) {
int new_i = i + dir[0];
int new_j = j + dir[1];
if (new_i >= 0 && new_i < board.length && new_j >= 0 && new_j < board[new_i].length && board[new_i][new_j] == 'M') {
count++;
}
}
return count;
}
}
2020-05-10
690. Employee Importance
Description
You are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.
Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.
Note:
One employee has at most one direct leader and may have several subordinates.
The maximum number of employees won't exceed 2000.
Solution
/*
// Definition for Employee.
class Employee {
public int id;
public int importance;
public List<Integer> subordinates;
};
*/
class Solution {
public int getImportance(List<Employee> employees, int id) {
if(employees == null){
return 0;
}
HashMap<Integer,Employee> map = new HashMap();
for(Employee employee : employees){
map.put(employee.id,employee);
}
Queue<Employee> queue = new LinkedList<>();
queue.add(map.get(id));
int res = 0;
while(!queue.isEmpty()){
Employee cur = queue.poll();
res += cur.importance;
if(cur.subordinates!=null){
//since we have the restriction that one can only have one direct leader, no need to check cycle or dup.
for(int nextId : cur.subordinates){
queue.offer(map.get(nextId));
}
}
}
return res;
}
}
542. 01 Matrix
Description
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
[[0,0,0],
[0,1,0],
[0,0,0]]
Output:
[[0,0,0],
[0,1,0],
[0,0,0]]
Example 2:
Input:
[[0,0,0],
[0,1,0],
[1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]
Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.
Solution
//main idea is to first go through all the 0, find adjacent and do BFS.
//like go through all the levels and mark as closet level.
class Solution {
public int[][] updateMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length==0){
return matrix;
}
int[][] dirs = new int[][][[0,-1],[0,1],[-1,0],[1,0]];
Queue<int[]> queue = new LinkedList<>();
for(int i = 0;i<matrix.length;i++){
for(int j = 0; j< matrix[i].length;j++){
if(matrix[i][j]==0){
queue.offer(new int[]{i,j});
}else{
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
while(!queue.isEmpty()){
int[] cur = queue.poll();
for(int[] dir : dirs){
int new_i = cur[0] + dir[0];
int new_j = cur[1] + dir[1];
if(new_i < 0 || new_i >= matrix.length || new_j < 0 || new_j >= matrix[new_i].length || matrix[new_i][new_j] < matrix[cur[0]][cur[1]]+1){
continue;
}
matrix[new_i][new_j] = matrix[cur[0]][cur[1]]+1;
queue.offer(new int[]{new_i,new_j});
}
}
return matrix;
}
}
2020-05-11
417. Pacific Atlantic Water Flow
Description
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
The order of returned grid coordinates does not matter. Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
Solution
//since water can only fall down, we can trace back from the ocean and find all adjacent point which is higher or even so the water can go.
//find all points which can be reached fgrom P and A, then find the points can reach both P and A.
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
int iLen = matrix.length;
int jLen = matrix[0].length;
Queue<int[]> pQueue = new LinkedList<>();
Queue<int[]> aQueue = new LinkedList<>();
boolean[][] pVisited = new boolean[iLen][jLen];
boolean[][] aVisited = new boolean[iLen][jLen];
int[][] dirs = new int[][][[0, -1], [0, 1], [-1, 0], [1, 0]];
//add all boarder to queue and visited.
for (int i = 0; i < iLen; i++) {
pQueue.offer(new int[]{i, 0});
aQueue.offer(new int[]{i, jLen - 1});
pVisited[i][0] = true;
aVisited[i][jLen - 1] = true;
}
for (int j = 0; j < jLen; j++) {
pQueue.offer(new int[]{0, j});
aQueue.offer(new int[]{iLen - 1, j});
pVisited[0][j] = true;
aVisited[iLen - 1][j] = true;
}
//BFS from the boarder.
BFS(matrix, pQueue, pVisited, dirs);
BFS(matrix, aQueue, aVisited, dirs);
//find all points can reach both P and A.
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < iLen; i++) {
for (int j = 0; j < jLen; j++) {
if (pVisited[i][j] && aVisited[i][j]) {
List<Integer> temp = new ArrayList<>();
temp.add(i);
temp.add(j);
res.add(temp);
}
}
}
return res;
}
private void BFS(int[][] matrix, Queue<int[]> queue, boolean[][] visited, int[][] dirs) {
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int new_i = cur[0] + dir[0];
int new_j = cur[1] + dir[1];
//don't forget to check visited to avoid dup.
if (new_i < 0 || new_i >= matrix.length || new_j < 0 || new_j >= matrix[new_i].length || visited[new_i][new_j] || matrix[new_i][new_j] < matrix[cur[0]][cur[1]]) {
continue;
}
queue.offer(new int[]{new_i, new_j});
visited[new_i][new_j] = true;
}
}
}
}
863. All Nodes Distance K in Binary Tree
Description
We are given a binary tree (with root node root), a target node, and an integer value K.
Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation:
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.
Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.
Note:
The given tree is non-empty.
Each node in the tree has unique values 0 <= node.val <= 500.
The target node is a node in the tree.
0 <= K <= 1000.
Solution
Using graph to BFS
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
if (root == null) return null;
Map<Integer, List<Integer>> graph = new HashMap<>();
buildGraph(root, graph);
HashSet<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.offer(target.val);
visited.add(target.val);
for (int i = 0; i < K; i++) {
if (queue.isEmpty()) {
break;
}
int size = queue.size();
for (int j = 0; j < size; j++) {
int cur = queue.poll();
visited.add(cur);
for (int neighbor : graph.getOrDefault(cur, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
}
}
}
}
return new LinkedList<>(queue);
}
public void buildGraph(TreeNode root, Map<Integer, List<Integer>> graph) {
if (root == null) {
return;
}
if (root.left != null) {
addNeighbor(root, root.left, graph);
addNeighbor(root.left, root, graph);
buildGraph(root.left, graph);
}
if (root.right != null) {
addNeighbor(root, root.right, graph);
addNeighbor(root.right, root, graph);
buildGraph(root.right, graph);
}
}
private void addNeighbor(TreeNode parent, TreeNode child, Map<Integer, List<Integer>> graph) {
List<Integer> neighbors = graph.getOrDefault(parent.val, new ArrayList<Integer>());
neighbors.add(child.val);
graph.put(parent.val, neighbors);
}
}
Use DFS
//first find the path from root to target and store distance to target.
//then use DFS to traverse all nodes
//1. in subtree of the target: will start with length = 0 then do deeper to its child K level.
//2. parent or sibiling of target: will start from any node on the way from root to target, then go deep, so the length will be target-node + node-
class Solution {
Map<TreeNode, Integer> map = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> res = new LinkedList<>();
find(root, target);
dfs(root, target, K, map.get(root), res);
return res;
}
// find target node first and store the distance in that path that we could use it later directly
private int find(TreeNode root, TreeNode target) {
if (root == null) return -1;
if (root == target) {
map.put(root, 0);
return 0;
}
int left = find(root.left, target);
if (left >= 0) {
map.put(root, left + 1);
return left + 1;
}
int right = find(root.right, target);
if (right >= 0) {
map.put(root, right + 1);
return right + 1;
}
return -1;
}
private void dfs(TreeNode root, TreeNode target, int K, int length, List<Integer> res) {
if (root == null) return;
if (map.containsKey(root)) length = map.get(root);
if (length == K) res.add(root.val);
dfs(root.left, target, K, length + 1, res);
dfs(root.right, target, K, length + 1, res);
}
}
11. Container With Most Water
Description
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
Solution
class Solution {
public int maxArea(int[] height) {
int res = Integer.MIN_VALUE;
int i =0,j= height.length-1;
while(i<j){
int h = Math.min(height[i],height[j]);
res = Math.max(res, h * (j-i));
while(i<j && height[i]<=h) i++;
while(i<j && height[j]<=h) j--;
}
return res;
}
}
2020-05-12
16. 3Sum Closest
Description
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution
//keep two variables, one gap and one sum. so compare gap and store the closet sum.
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int len = nums.length;
int gap = Integer.MAX_VALUE;
int res = target;
for (int i = 0; i < len - 2; i++) {
int left = i + 1, right = len - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return target;
} else if (sum < target) {
left++;
} else {
right--;
}
if(Math.abs(sum-target) < gap){
gap = Math.abs(sum-target);
res = sum;
}
}
}
return res;
}
}
2020-05-14
287. Find the Duplicate Number
Description
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Solution
//restriction is: there's always one dup and array length n+1 and only contains 1->n inclusive.
//in that case the linkedlist will always be a loop and the start point is the dup number.
//[1,3,4,2,2] -> 1 -> 3 -> 2 -> 4 -> 2(cycle)
class Solution {
public int findDuplicate(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int slow = 0,fast = 0;
while(true){
slow = nums[slow];
fast = nums[nums[fast]];
if(slow == fast){
break;
}
}
slow = 0;
while(slow!=fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
382. Linked List Random Node
Description
Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
Example:
// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
Solution
//蓄水池算法:
// Basic idea:
// Choose 1, 2, 3, ..., k first and put them into the reservoir.
// For k+1, pick it with a probability of k/(k+1), and randomly replace a number in the reservoir.
// Repeat until k+i reaches n
//example: for choosing 1 out of [1,2,3,4,5]:
////probability: 1 * 1/2(for 1, there's a chance to be replaced) * 2/3(now the picked one will have 2/3 probability to be replaced) * 3/4 * 4/5
import java.util.Random;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
ListNode head;
Random rnd;
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
public Solution(ListNode head) {
this.head = head;
rnd = new Random();
}
/** Returns a random node's value. */
public int getRandom() {
int count = 0;
ListNode res = null, cur = head;
while(cur != null){
if(rnd.nextInt(++count)==0){
//replace the previous one.
res = cur;
}
cur = cur.next;
}
return res.val;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
28. Implement strStr()
Description
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
Solution
class Solution {
public int strStr(String haystack, String needle) {
int hLen = haystack.length();
int nLen = needle.length();
for (int i = 0; ; i++) {
for (int j = 0; ; j++) {
//j reached the end, all fit, return the start idx.
if (j == nLen) {
return i;
}
//reached the end, means no fit, and no need to i++
//since i+j is fit but j does not reached end -> there's no more chance to fit.
if (i + j == hLen) {
return -1;
}
if (needle.charAt(j) != haystack.charAt(i + j)) {
break;
}
}
}
}
}
86. Partition List
Description
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
Solution
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode less = new ListNode(0);
ListNode more = new ListNode(0);
ListNode less_cur = less, more_cur = more;
ListNode cur = head;
while(cur!=null){
if(cur.val<x){
less_cur.next = cur;
less_cur = less_cur.next;
}else{
more_cur.next = cur;
more_cur = more_cur.next;
}
cur = cur.next;
}
more_cur.next = null;
less_cur.next = more.next;
return less.next;
}
}
2020-05-15
72. Edit Distance
Description
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character Delete a character Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
Solution
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i = 1;i<=len1;i++){
dp[i][0] = i;
}
for(int j = 1; j<=len2;j++){
dp[0][j] = j;
}
for(int i = 1; i<=len1;i++){
for(int j = 1;j<=len2;j++){
//if the char are the same, nothing need to be done.
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
//if not equal, then you may:
//modify -> dp[i-1][j-1] + 1
//insert/delete -> dp[i-1][j]+1 / dp[i][j-1]+1
dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
}
}
}
return dp[len1][len2];
}
}
1140. Stone Game II
Description
Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.
Alex and Lee take turns, with Alex starting first. Initially, M = 1.
On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).
The game continues until all the stones have been taken.
Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.
Example 1:
Input: piles = [2,7,9,4,4]
Output: 10
Explanation: If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
Constraints:
1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4
Solution
//main idea to to use memo and bottom up.
//for the current step, the optimal will be to let the opponent to have the minium values.
//for can iterate through steps, from 1 to 2M, and find out the min value opponent can get.
class Solution {
int[] sums;
int[][] memo;
public int stoneGameII(int[] piles) {
if (piles == null || piles.length == 0) {
return 0;
}
int len = piles.length;
sums = new int[len];
memo = new int[len][len];
//sums are for calc sum from i to end.
sums[len - 1] = piles[len - 1];
for (int i = len - 2; i >= 0; i--) {
sums[i] = sums[i + 1] + piles[i];
}
return dp(piles,0,1);
}
public int dp(int[] piles, int i, int M) {
//already reached the end.
if (i >= piles.length) {
return 0;
}
//the current step can already take all stones altogether.
if (i + 2 * M >= piles.length) {
return sums[i];
}
//searched already.
if (memo[i][M] != 0) {
return memo[i][M];
}
int min_val = Integer.MAX_VALUE;
for (int x = 1; x <= 2 * M; x++) {
//to each gap x, find the min value the opponent can get.
min_val = Math.min(min_val, dp(piles, i + x, Math.max(x, M)));
}
memo[i][M] = sums[i] - min_val;
return memo[i][M];
}
}
263. Ugly Number
Description
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example 1:
Input: 6
Output: true
Explanation: 6 = 2 × 3
Example 2:
Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2
Example 3:
Input: 14
Output: false
Explanation: 14 is not ugly since it includes another prime factor 7.
Note:
1 is typically treated as an ugly number.
Input is within the 32-bit signed integer range: [−231, 231 − 1].
Solution
import java.util.HashMap;
//DP
class Solution {
HashMap<Integer, Boolean> dp = new HashMap<>();
int[] factors = new int[]{2, 3, 5};
public boolean isUgly(int num) {
if (num <= 0) {
return false;
}
dp.put(1, true);
return helper(num);
}
public boolean helper(int i) {
if (dp.containsKey(i)) {
return dp.get(i);
}
boolean res = false;
for (int j : factors) {
if (i % j == 0) {
res |= helper(i / j);
}
}
dp.put(i, res);
return res;
}
}
//Math
class Solution {
int[] factors = new int[]{2, 3, 5};
public boolean isUgly(int num) {
if(num <= 0)return false;
for(int factor : factors){
while(num%factor==0){
num /= factor;
}
}
return num==1;
}
}
375. Guess Number Higher or Lower II
Description
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8.
First round: You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round: You guess 9, I tell you that it's lower. You pay $9.
Game over. 8 is the number I picked.
You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Solution
//p[i][j] is the minimal cost to guess from range(i...j).
//When you choose an x where i <= x <= j, you may find the
//target number from left i...x-1, or you may find the target number from the x+1...j, //because you don't know which way should go, so to guarantee you have enough money to find //the target, you need to prepare the more, which is max(dp[i][x-1], dp[x+1][j]).
class Solution {
int[][] dp;
public int getMoneyAmount(int n) {
dp = new int[n+1][n+1];
return helper(1,n);
}
public int helper(int i, int j) {
if (i >= j) {
return 0;
}
if (dp[i][j] != 0) {
return dp[i][j];
}
int res = Integer.MAX_VALUE;
for (int x = i; x <= j; x++) {
//since it's ganrantee, can be seens as AT LEAST, so find min of max.
//go left and right to search as next step, means less or more.
res = Math.min(res, Math.max(helper(i, x -1), helper(x+1, j))+x);
}
dp[i][j] = res;
return res;
}
}
264. Ugly Number II
Description
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.
Solution
class Solution {
public int nthUglyNumber(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] dp = new int[n];
dp[0] = 1;
int t2 = 0, t3 = 0, t5 = 0;
for (int i = 1; i < n; i++) {
dp[i] = Math.min(dp[t2] * 2, Math.min(dp[t3] * 3, dp[t5] * 5));
if (dp[i] == dp[t2] * 2) {
t2++;
}
if (dp[i] == dp[t3] * 3) {
t3++;
}
if (dp[i] == dp[t5] * 5) {
t5++;
}
}
return dp[n - 1];
}
}
343. Integer Break
Description
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
Solution
import java.util.Arrays;
class Solution {
int[] dp;
public int integerBreak(int n) {
dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
int res = helper(n);
return res;
}
public int helper(int n) {
if (n <= 2) {
return 1;
}
if (dp[n] != 0) {
return dp[n];
}
for(int i = 1; i<=n/2;i++){
//use Max(helper(i),i) to support the case:
//3 = 1+2, max = 1*2, while helper(2) will return 1, so maybe the number itself is larger.
//i and n-i split or not will have 2 result.
dp[n] = Math.max(dp[n],Math.max(helper(i),i)*Math.max(helper(n-i),n-i));
}
return dp[n];
}
}