2019-08-04
121. Best Time to Buy and Sell Stock
Desc
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for(int price : prices){
minPrice = Math.min(price,minPrice);
maxProfit = Math.max(maxProfit,price - minPrice);
}
return maxProfit;
}
}
122. Best Time to Buy and Sell Stock II
Desc
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for(int i = 0;i<prices.length-1;i++){
if(prices[i]<prices[i+1]){
profit += (prices[i+1]-prices[i]);
}
}
return profit;
}
}
2019-08-11
22. Generate Parentheses
Desc
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
Solution
class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>();
backtrack(list, "", 0, 0, n);
return list;
}
public void backtrack(List<String> list, String str, int open, int close, int max){
//return condition that the length reach the limit.
if(str.length() == max*2){
list.add(str);
return;
}
//if open is still avaliable for append.
if(open < max)
backtrack(list, str+"(", open+1, close, max);
//if adding a close is still available.
if(close < open)
backtrack(list, str+")", open, close+1, max);
}
}
2019-08-13
11. Container With Most Water
Desc
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 max =0;
int i = 0;
int j = height.length - 1;
while(i<j){
int h = Math.min(height[i],height[j]);
max = Math.max(max, (j-i)*h);
while(height[i] <= h && i<j) i++;
while(height[j] <= h && i<j) j--;
}
return max;
}
}
2019-08-14
560. Subarray Sum Equals K
Desc
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
Solution
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> pre = new HashMap();
int sum = 0, count = 0;
pre.put(0,1);
for(int i=0;i<nums.length;i++){
sum += nums[i];
if(pre.containsKey(sum-k)){
count += pre.get(sum-k);
}
pre.put(sum,pre.getOrDefault(sum,0)+1);
}
return count;
}
}
2019-08-19
295. Find Median from Data Stream
Desc
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example, [2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far.
Example:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
Follow up:
If all integer numbers from the stream are between 0 and 100, how would you optimize it? If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
Solution
class MedianFinder {
Queue<Long> small, large;
/** initialize your data structure here. */
public MedianFinder() {
small = new PriorityQueue<Long>();
large = new PriorityQueue<Long>();
}
public void addNum(int num) {
//PriorityQueue has SMALLEST element on top.
//all number get into two bucket: small and large.
//where small contains smaller number.
//fisrt add to large one.
large.add((long)num);
//then small take the smallest one in large.
small.add(-large.poll());
//balance.
if(large.size() < small.size()){
large.add(-small.poll());
}
}
public double findMedian() {
//median is always the smallest one in large or 1/2 of two bucket
return large.size()>small.size()?
large.peek():
(large.peek() - small.peek())/2.0;
}
}
2019-08-20
394. Decode String
Desc
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
Solution
class Solution {
public String decodeString(String s) {
String res = "";
Stack<Integer> countStk = new Stack();
Stack<String> resStk = new Stack();
int index = 0;
while(index<s.length()){
if(Character.isDigit(s.charAt(index))){
int count = 0;
while(Character.isDigit(s.charAt(index))){
count = count * 10 + (s.charAt(index)-'0');
index++;
}
countStk.push(count);
}else if(s.charAt(index)=='['){
resStk.push(res);
res= "";
index++;
}else if(s.charAt(index)==']'){
StringBuilder sb = new StringBuilder(resStk.pop());
int repeat = countStk.pop();
for(;repeat>0;repeat--){
sb.append(res);
}
res = sb.toString();
index++;
}else{
res += s.charAt(index);
index++;
}
}
return res;
}
}
269. Alien Dictionary
Desc
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Example 2:
Input:
[
"z",
"x"
]
Output: "zx"
Example 3:
Input:
[
"z",
"x",
"z"
]
Output: ""
Explanation: The order is invalid, so return "".
Note:
You may assume all letters are in lowercase. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary. If the order is invalid, return an empty string. There may be multiple valid order of letters, return any one of them is fine.
###Solution
class Solution {
public static String alienOrder(String[] words) {
StringBuilder sb = new StringBuilder();
HashSet[] graph = new HashSet[26];
Map<Integer,Integer> degree = new HashMap();
// 首先全部出现的char都需要有入度，防止后面一一对应的时候不能访问到
// eg. wr wrf
for (String word:words){
for (char ch: word.toCharArray()){
degree.put(ch-'a',0);
}
}
for (int i=0;i<words.length-1;i++){
String w1 = words[i];
String w2 = words[i+1];
int len = Math.min(w1.length(),w2.length());
int k = 0;
while (k < len){
char ch1 = w1.charAt(k);
char ch2 = w2.charAt(k);
if ( ch1 != ch2){
if (graph[ch1 - 'a'] == null){
graph[ch1 - 'a'] = new HashSet<Integer>();
}
// 如果添加 说明该节点是第一次出现，需要对入度进行+1 否则就是重复的
// eg. w -> t , w -> t 出现两次
if (graph[ch1-'a'].add(ch2-'a'))
degree.put(ch2-'a',degree.getOrDefault(ch2-'a',0)+1);
// 只有当char前面是相同的时候，才能进行这一对char的比较
// abce abcd -> aeg adf 此时不能判断的情况
break;
}
k++;
}
}
Queue<Integer> queue = new LinkedList();
for (int node:degree.keySet()){
if (degree.get(node) == 0)
queue.offer(node);
}
while(!queue.isEmpty()){
int node = queue.poll();
sb.append((char)('a'+node));
HashSet<Integer> connect = graph[node];
// 如果相连节点为空，说明没有出度，只有入度，需要判空
if (connect == null)
continue;
for (int next:connect){
int nextDegree = degree.get(next) -1;
if (nextDegree == 0){
degree.put(next,0);
queue.offer(next);
}
else
// 记得更新degree的值
degree.put(next,nextDegree);
}
}
// 如果result和degree里面出现的节点数量相同，说明其中有矛盾的节点出现
// a->b b->a
if(sb.length()!=degree.size()) return "";
return sb.toString();
}
}
2019-08-25
91. Decode Ways
Desc
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Solution
class Solution {
public int numDecodings(String s) {
if(null == s || s.length() == 0){
return 0;
}
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = s.charAt(0)=='0'?0:1;
for(int i = 2;i<=n;i++){
int first = Integer.valueOf(s.substring(i-1,i));
int sec = Integer.valueOf(s.substring(i-2,i));
if(first>=1 && first <=9){
dp[i] += dp[i-1];
}
if(sec >=10 && sec<=26){
dp[i] += dp[i-2];
}
}
return dp[n];
}
}
2019-08-29
202. Happy Number
Desc
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example:
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Solution
class Solution {
public boolean isHappy(int n) {
Set<Integer> see = new HashSet<Integer>();
int num = n;
while(!see.contains(num)){
see.add(num);
num = calc(num);
if(num == 1){
return true;
}
}
return false;
}
private Integer calc(int num){
char[] numChar = Integer.toString(num).toCharArray();
int count = 0;
for(char c:numChar){
int n = c-'0';
count += n*n;
}
return count;
}
}