- 2019-09-02
- 2019-09-03
- 2019-09-05
- 2019-09-08
- 2019-09-11
- 2019-09-17
- 2019-09-22
- 2019-09-23
- 2019-09-24
- 2019-09-25
- 64. Minimum Path Sum
- 2019-09-29
- 2019-09-30
2019-09-02
155. Min Stack
Description
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
Solution
class MinStack {
Stack<Integer> stack;
int min;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
if(x <= min){
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
int peek = stack.pop();
//right now the min value must be the one before cur position
//as the order theyt pushed into the stack.
if(peek == min){
min = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
2019-09-03
127. Word Ladder
Description
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:
Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
Solution
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<String>(wordList);
if(!wordSet.contains(endWord)) return 0;
Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();
int len = 1;
HashSet<String> visited = new HashSet<String>();
beginSet.add(beginWord);
endSet.add(endWord);
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
//exchange two set to ensure beginset is smaller so it will run faster.
if (beginSet.size() > endSet.size()) {
Set<String> set = beginSet;
beginSet = endSet;
endSet = set;
}
Set<String> temp = new HashSet<String>();
for (String word : beginSet) {
char[] chs = word.toCharArray();
for (int i = 0; i < chs.length; i++) {
for (char c = 'a'; c <= 'z'; c++) {
//main idea is to try every word and see if it's in the endSet.
char old = chs[i];
chs[i] = c;
String target = String.valueOf(chs);
//when it comes to end. endset is all word that can be reached.
if (endSet.contains(target)) {
return len + 1;
}
if (!visited.contains(target) && wordSet.contains(target)) {
temp.add(target);
visited.add(target);
}
chs[i] = old;
}
}
}
beginSet = temp;
len++;
}
return 0;
}
}
2019-09-05
322. Coin Change
Description
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note: You may assume that you have an infinite number of each kind of coin.
Solution
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1;i<=amount;i++){
for(int coin : coins){
//try each coin and see the min value of dp[i-coin]+1 or dp[i] itself.
if(coin <= i && dp[i-coin]!=Integer.MAX_VALUE){
dp[i] = Math.min(dp[i-coin]+1,dp[i]);
}
}
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}
}
986. Interval List Intersections
Description
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
(Formally, a closed interval [a, b] (a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)
Example 1:
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
Solution
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
if(null == A || null == B || A.length==0 || B.length==0){
return new int[][]{};
}
List<int[]> res = new ArrayList();
//main idea is two pointer.
int i = 0, j=0;
while(i<A.length && j<B.length){
int[] a = A[i];
int[] b = B[j];
//find interval.
int startMax = Math.max(a[0],b[0]);
int endMin = Math.min(a[1],b[1]);
if(startMax<=endMin){
res.add(new int[]{startMax,endMin});
}
//if the interval end is smaller, move on to the next.
if(endMin == a[1])i++;
if(endMin == b[1])j++;
}
int[][] res_b = new int[res.size()][2];
return res.toArray(res_b);
}
}
2019-09-08
221. Maximal Square
Description
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
Solution
class Solution {
public int maximalSquare(char[][] matrix) {
if(null == matrix || matrix.length==0){
return 0;
}
int yLength = matrix.length;
int xLength = matrix[0].length;
int[][] dp = new int[yLength+1][xLength+1];
int max = 0;
for(int i = 1;i<=yLength;i++){
for(int j = 1;j<=xLength;j++){
if(matrix[i-1][j-1]=='1'){
//dp[i][j] is limited by its neighbor.
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
max = Math.max(max,dp[i][j]);
}
}
}
return max * max;
}
}
2019-09-11
6. ZigZag Conversion
Description
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Solution
//Using slot.
class Solution {
public String convert(String s, int numRows) {
if(numRows==1){
return s;
}
int len = s.length();
int i = 0;
int index = 0;
boolean reverse = true;
StringBuilder[] sb = new StringBuilder[numRows];
for(int j = 0;j<numRows;j++){
sb[j] = new StringBuilder();
}
while(i<len){
sb[index].append(s.charAt(i));
if(index==numRows-1){
index--;
reverse = !reverse;
}else if(index==0){
index++;
reverse = !reverse;
}else{
if(reverse)index--;
else index++;
}
i++;
}
StringBuilder sbRes = new StringBuilder();
for(StringBuilder _sb:sb){
sbRes.append(_sb.toString());
}
return sbRes.toString();
}
}
364. Nested List Weight Sum II
Description
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
Example 1:
Input: [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:
Input: [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.
Solution
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
int weighted = 0, unweighted = 0;
while(!nestedList.isEmpty()){
List<NestedInteger> temp = new LinkedList<>();
for(NestedInteger n:nestedList){
if(n.isInteger()){
unweighted += n.getInteger();
}else{
temp.addAll(n.getList());
}
}
nestedList = temp;
weighted += unweighted;
}
return weighted;
}
}
412. Fizz Buzz
Description
Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
Example:
n = 15,
Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
Solution
//if using stringbuilder will be slower.
class Solution {
public List<String> fizzBuzz(int n) {
List<String> res = new ArrayList();
int fizz =0,buzz=0;
for(int i = 1;i<=n;i++){
StringBuilder sb = new StringBuilder();
fizz++;
buzz++;
if(fizz == 3 && buzz == 5){
res.add("FizzBuzz");
fizz = 0;
buzz = 0;
continue;
}else if(fizz ==3){
res.add("Fizz");
fizz = 0;
continue;
}else if(buzz == 5){
res.add("Buzz");
buzz = 0;
continue;
}
res.add(String.valueOf(i));
}
return res;
}
}
103. Binary Tree Zigzag Level Order Traversal
Description
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList();
if(null == root){
return res;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
boolean rev = false;
while(!q.isEmpty()){
Queue<TreeNode> temp = new LinkedList<TreeNode>();
Deque<Integer> ans = new LinkedList();
rev = !rev;
while(!q.isEmpty()){
TreeNode cur = q.poll();
if(rev){
ans.offerLast(cur.val);
}else{
ans.offerFirst(cur.val);
}
if(null!=cur.left){
temp.offer(cur.left);
}
if(null!=cur.right){
temp.offer(cur.right);
}
}
q = temp;
res.add(new LinkedList(ans));
}
return res;
}
}
2019-09-17
98. Validate Binary Search Tree
Description
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.
Example 1:
2 / \ 1 3
Input: [2,1,3] Output: true Example 2:
5 / \ 1 4
/ \
3 6
Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node’s value is 5 but its right child’s value is 4.
Solution
//basiclly is a inorder traversal and compare.
class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack();
TreeNode pre = null;
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre!=null && pre.val >= root.val) return false;
pre = root;
root = root.right;
}
return true;
}
}
class Solution {
TreeNode prev;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(prev != null && prev.val >= root.val){
return false;
}
prev = root;
if(!isValidBST(root.right)){
return false;
}
return true;
}
}
547. Friend Circles
Description
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.
Solution
class Solution {
public int findCircleNum(int[][] M) {
int[] visited = new int[M.length];
int count = 0;
for(int i = 0;i<M.length;i++){
//once go through a circle, all people will set as visited.
if(visited[i]==0){
dfs(M,visited,i);
count++;
}
}
return count;
}
//check circle and set all people in this circle to visited.
private void dfs(int[][] M, int[] visited, int i){
for(int j = 0;j<M.length;j++){
if(M[i][j] == 1 && visited[j] == 0){
visited[j] = 1;
dfs(M,visited,j);
}
}
}
}
43. Multiply Strings
Description
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = “2”, num2 = “3” Output: “6” Example 2:
Input: num1 = “123”, num2 = “456” Output: “56088” Note:
The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length();
int n = num2.length();
int[] pos = new int[m+n];
for(int i = m-1;i>=0;i--){
for(int j = n-1; j>=0;j--){
int mul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
int p1 = i+j;
int p2 = i+j+1;
int sum = mul + pos[p2];
pos[p1] += sum /10;
pos[p2] = sum % 10;
}
}
StringBuilder sb = new StringBuilder();
for(int p: pos){
if(!(sb.length()==0 && p == 0)){
sb.append(p);
}
}
return sb.length()==0?"0":sb.toString();
}
}
2019-09-22
236. Lowest Common Ancestor of a Binary Tree
Description
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
All of the nodes’ values will be unique. p and q are different and both values will exist in the binary tree.
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//It's recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!=null&&right != null){
return root;
}else if(left !=null){
return left;
}else{
return right;
}
}
}
92. Reverse Linked List II
Description
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Solution
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null){
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
//use pre is important or you will lose pre if you use cur.
for(int i = 0;i<m-1;i++){
pre = pre.next;
}
ListNode cur = pre.next;
ListNode then = cur.next;
for(int i= 0;i<n-m;i++){
cur.next = then.next;
then.next = pre.next;
pre.next = then;
then = cur.next;
}
return dummy.next;
}
}
692. Top K Frequent Words
Description
Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Example 1:
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.
Example 2:
Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
with the number of occurrence being 4, 3, 2 and 1 respectively.
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.
Follow up: Try to solve it in O(n log k) time and O(n) extra space.
Solution
class Solution {
public List<String> topKFrequent(String[] words, int k) {
List<String> result = new LinkedList<>();
Map<String, Integer> map = new HashMap<>();
for(int i=0; i<words.length; i++)
{
if(map.containsKey(words[i]))
map.put(words[i], map.get(words[i])+1);
else
map.put(words[i], 1);
}
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
//!!!!!!!!!!!!!!!!!!!!!!!
(a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue()
);
for(Map.Entry<String, Integer> entry: map.entrySet())
{
pq.offer(entry);
if(pq.size()>k)
pq.poll();
}
while(!pq.isEmpty())
result.add(0, pq.poll().getKey());
return result;
}
}
2019-09-23
93. Restore IP Addresses
Description
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Solution
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> solutions = new ArrayList<String>();
restoreIp(s, solutions, 0, "", 0);
return solutions;
}
private void restoreIp(String ip, List<String> solutions, int idx, String restored, int count) {
//already invalid.
if (count > 4) return;
//meet condition and push to res.
if (count == 4 && idx == ip.length()) solutions.add(restored);
//i = 1,2,3 for each component between two points XXX._ _ _.XXX.
for (int i=1; i<4; i++) {
//out of range.
if (idx+i > ip.length()) break;
String s = ip.substring(idx,idx+i);
//1. XXX.0 is valid while XXX.01 is not.
//2. XXX.256 is not valid.
if ((s.startsWith("0") && s.length()>1) || (i==3 && Integer.parseInt(s) >= 256)) continue;
restoreIp(ip, solutions, idx+i, restored+s+(count==3?"" : "."), count+1);
}
}
}
1048. Longest String Chain
Description
Given a list of words, each word consists of English lowercase letters.
Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, “abc” is a predecessor of “abac”.
A word chain is a sequence of words [word_1, word_2, …, word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.
Example 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".
Note:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.
Solution
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words,(a, b)->(a.length()-b.length()));
int res = 0;
Map<String,Integer> map= new HashMap<>();
for(String word: words){
int best = 0;
//try to delete every char and see what's the best solution.
for(int i = 0;i<word.length();i++){
String temp = word.substring(0,i)+ word.substring(i+1);
best = Math.max(best,map.getOrDefault(temp,0)+1);
}
map.put(word,best);
res = Math.max(res,best);
}
return res;
}
}
2019-09-24
152. Maximum Product Subarray
Description
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Solution
public class Solution {
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int max = A[0], min = A[0], result = A[0];
//start from 1, since 0 is already read.
//why it's continious? at a certain point, it meet a negative number
//and result before will be discarded and replaced by current number or min.
for (int i = 1; i < A.length; i++) {
int temp = max;
max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
if (max > result) {
result = max;
}
}
return result;
}
}
2019-09-25
695. Max Area of Island
Description
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
###Solution
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int _max = 0;
for(int y = 0;y<grid.length;y++){
for(int x = 0;x<grid[y].length;x++){
_max = Math.max(_max,maxArea(grid,x,y,0));
}
}
return _max;
}
private int maxArea(int[][] grid,int x, int y, int count){
if(y<0 || x<0 || y>=grid.length || x>=grid[0].length || grid[y][x] == 0)return 0;
count++;
grid[y][x] = 0;
count += maxArea(grid, x-1, y, 0);
count += maxArea(grid, x+1, y, 0);
count += maxArea(grid, x, y-1, 0);
count += maxArea(grid, x, y+1, 0);
return count;
}
}
64. Minimum Path Sum
Description
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
###Solution
class Solution {
public int minPathSum(int[][] grid) {
for(int i = 1;i<grid.length;i++){
grid[i][0] += grid[i-1][0];
}
for(int i = 1;i<grid[0].length;i++){
grid[0][i] += grid[0][i-1];
}
for(int y = 1; y<grid.length;y++){
for(int x = 1; x<grid[0].length;x++){
grid[y][x] = Math.min(grid[y-1][x],grid[y][x-1]) + grid[y][x];
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
34. Find First and Last Position of Element in Sorted Array
Description
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Solution
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1,-1};
if(nums.length==0){
return res;
}
int start = 0, end = nums.length-1;
while(start<end){
int mid = (start+end)/2;
if(nums[mid]<target){
//bias
start = mid+1;
}else{
end = mid;
}
}
if(nums[start]!=target){
return res;
}
res[0] = start;
end = nums.length-1;
while(start<end){
int mid = (start+end)/2 + 1;
if(nums[mid]>target){
//bias
end = mid-1;
}else{
start = mid;
}
}
res[1]=end;
return res;
}
}
300. Longest Increasing Subsequence
Descxription
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note:
There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity?
Solution
import java.util.*;
class Solution {
public int lengthOfLIS(int[] nums) {
if(null == nums || nums.length==0){
return 0;
}
SortedMap<Integer,Integer> map = new TreeMap<>();
int res = Integer.MIN_VALUE;
for(int n:nums){
int _min = 1;
Collection<Integer> t = map.subMap(Integer.MIN_VALUE,n).values();
for(int e: t){
_min = Math.max(_min,e+1);
}
map.put(n,_min);
res = Math.max(res,_min);
}
return res;
}
}
2019-09-29
438. Find All Anagrams in a String
Description
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Solution
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int len = p.length();
List<Integer> res = new ArrayList();
if(null == s || null ==p || s.length() ==0 || p.length()==0 || s.length()<len){
return res;
}
int[] sChar = new int[26];
int[] pChar = new int[26];
for(char chr: p.toCharArray()){
pChar[chr-'a']++;
}
for(int i=0;i<len;i++){
char c = s.charAt(i);
sChar[c-'a']++;
}
for(int i = 0;i<=s.length()-len;i++){
if(Arrays.equals(sChar,pChar)){
res.add(i);
}
if(i!=s.length()-len){
sChar[s.charAt(i)-'a']--;
sChar[s.charAt(i+len)-'a']++;
}
}
return res;
}
}
2019-09-30
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
public class Solution {
public int threeSumClosest(int[] num, int target) {
int result = num[0] + num[1] + num[num.length - 1];
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1, end = num.length - 1;
while (start < end) {
int sum = num[i] + num[start] + num[end];
if (sum > target) {
end--;
} else {
start++;
}
//select minimun.
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
}
}
return result;
}
}
148. Sort List
Description
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
Solution
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode prev=null,slow = head,fast=head;
while(fast!=null && fast.next!=null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merge(l1,l2);
}
private ListNode merge(ListNode l1,ListNode l2){
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(l1!=null && l2!=null){
if(l1.val>l2.val){
p.next = l2;
l2 = l2.next;
}else{
p.next = l1;
l1 = l1.next;
}
p = p.next;
}
if(l1 !=null){
p.next = l1;
}
if(l2 !=null){
p.next = l2;
}
return dummy.next;
}
}