LeetCode [332] Reconstruct Itinerary

332. Reconstruct Itinerary

Medium

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { Map<String, PriorityQueue<String>> targets = new HashMap<>(); List<String> route = new LinkedList(); public List<String> findItinerary(List<List<String>> tickets) { for (List<String> ticket : tickets) targets.computeIfAbsent(ticket.get(0), k -> new PriorityQueue()).add(ticket.get(1)); visit("JFK"); return route; } void visit(String airport) { while(targets.containsKey(airport) && !targets.get(airport).isEmpty()) visit(targets.get(airport).poll()); route.add(0, airport); } }

LeetCode [329] Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

Hard

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { vector<vector<int>> dir{{1,0},{-1,0},{0,-1},{0,1}}; public: int longestIncreasingPath(vector<vector<int>>& matrix) { int m = matrix.size(); if(m==0) return 0; int n = matrix[0].size(); if(n==0) return 0; vector<vector<int>> dp(m, vector<int>(n, -1)); int ret = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(dp[i][j]<0){ dfs(matrix, dp, i, j, m, n); } ret = max(ret, dp[i][j]); } } return ret; } void dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j, int m, int n){ dp[i][j] = 1; for(auto d:dir){ int ii = i+d[0], jj = j+d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n && matrix[i][j]<matrix[ii][jj]){ if(dp[ii][jj]<0){ dfs(matrix, dp, ii, jj, m, n); } dp[i][j] = max(dp[i][j], 1+dp[ii][jj]); } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

//Java class Solution { int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; int ret = 0; int m, n; int[][] dp; public int longestIncreasingPath(int[][] matrix) { m = matrix.length; if(m==0) return 0; n = matrix[0].length; if(n==0) return 0; dp = new int[m][n]; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ dp[i][j] = -1; } } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(dp[i][j]<0) helper(matrix, i, j); ret = Math.max(ret, dp[i][j]); } } return ret; } void helper(int[][] matrix, int i, int j){ dp[i][j] = 1; for(int[] d : dir){ int ii = i + d[0]; int jj = j + d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n && matrix[i][j]<matrix[ii][jj]){ if(dp[ii][jj]<0){ helper(matrix, ii, jj); } dp[i][j] = Math.max(dp[i][j], dp[ii][jj]+1); } } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

//O((mn)^2) class Solution { int m, n; int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; public int longestIncreasingPath(int[][] matrix) { m = matrix.length; if(m == 0) return 0; n = matrix[0].length; if(n == 0) return 0; int[][] dp = new int[m][n]; for(int i=0; i<m; ++i){ Arrays.fill(dp[i], 1); } boolean cont = true; while(cont){ cont = false; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ for(int[] d : dirs){ int ii = i+d[0], jj = j+d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n){ if(matrix[ii][jj]>matrix[i][j]){ if(dp[ii][jj]<dp[i][j]+1){ cont = true; dp[ii][jj] = dp[i][j]+1; } } } } } } } int ret = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ ret = Math.max(ret, dp[i][j]); } } return ret; } }

LeetCode [306] Additive Number

Ref
[1] https://leetcode.com/problems/additive-number/
OJ

LeetCode [305] Number of Islands II

======================= =====================

Note:
    1. differentiate the islands by "id"
    2. "islands" records the total number of islands
    3, "state" records the ids of the islands
Example:  
 0  0  0  0
 0  0  0  0
 0  0  0  0
 0  0  0  0

step 1: [0, 1]
 0  1  0  0
 0  0  0  0
 0  0  0  0
 0  0  0  0
islands = 1

step 2: [1, 0]
 0  1  0  0
 2  0  0  0
 0  0  0  0
 0  0  0  0
islands = 2

step 3: [2, 1]
 0  1  0  0
 2  0  0  0
 0  3  0  0
 0  0  0  0
islands = 3

step 4: [1, 1]
at this step, id_t = 1, id_l = 2, id_b = 3 and id_r = 0
thus, id is set to the minimal minimum one, which is 1
since the new island (1,1) connects the other 3 existing islands
merge them into one island and update their ids accordingly
after step 4, "state" becomes:
 0  1  0  0
 1  1  0  0
 0  1  0  0
 0  0  0  0
islands = 1

the set "merged" is used to avoid cases like
 0  2  0  0  0
 2  2  0  1  0
 0  2  2  0  0
 0  0  0  0  0
 0  0  0  0  0
currently, there are two islands 1 and 2.
if a new land [1, 2] is created, both id_l and id_b is 2
but "islands" should be decreased once
so after [1,2] is created
the state becomes:
 0  1  0  0  0
 1  1  1  1  0
 0  1  1  0  0
 0  0  0  0  0
 0  0  0  0  0


 Ref
[1] https://leetcode.com/problems/number-of-islands-ii/
OJ
[2] https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations

LeetCode [302] Smallest Rectangle Enclosing Black Pixels

Ref
[1] https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
[2] https://leetcode.com/discuss/68246/c-java-python-binary-search-solution-with-explanation

LeetCode [301] Remove Invalid Parentheses

301. Remove Invalid Parentheses

Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

class Solution { bool isvalid(string s){ int cnt = 0; for(auto c:s){ cnt += c=='('; cnt -= c==')'; if(cnt<0) return false; } return cnt==0; } public: vector<string> removeInvalidParentheses(string s) { int l = 0, r = 0; for(auto c:s){ if(c=='(') l++; else{ if(l==0) r += (c==')'); else l -= (c==')'); } } vector<string> ret; dfs(s, ret, 0, l, r); return ret; } void dfs(string s, vector<string>&ret, int pos, int l, int r){ if(l==0 && r==0 && isvalid(s)){ ret.push_back(s); return; } for(int i=pos; i<s.size(); ++i){ if(i>pos && s[i]==s[i-1]) continue; if(!(s[i]=='(' && l>0 || s[i]==')' && r>0)) continue; string s1 = s; s1.erase(i, 1); if(s[i]=='(' && l>0) dfs(s1, ret, i, l-1, r); else if(s[i]==')' && r>0) dfs(s1, ret, i, l, r-1); } } };

• http://zxi.mytechroad.com/blog/string/leetcode-301-remove-invalid-parentheses/

LeetCode [272] Closest Binary Search Tree Value II

Ref
[1] https://leetcode.com/problems/closest-binary-search-tree-value-ii/
[2] https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks

MJ [31] minSteps

Question:
Given a grid with 'o' and 'x'. Find minimum steps from top-left to bottom-right without touching 'x'.
   a) You can only move right or move down. (BFS or DP) (m+n-2)?
   b) You can move in all 4 directions. (BFS)

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33037695.html

LeetCode [261] Graph Valid Tree

Ref
[1] https://leetcode.com/problems/graph-valid-tree/
OJ

MJ [12] Print BST keys in the given range

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33010083.html
MJ
[2] http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/
Question

LeetCode [257] Binary Tree Paths

Ref
[1] https://leetcode.com/problems/binary-tree-paths/
OJ

LeetCode [211] Add and Search Word - Data structure design

 211. Design Add and Search Words Data Structure

Medium

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

 

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

 

Constraints:

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153

//C++: 46ms class TrieNode { public: bool isTail; char key; unordered_map<char, TrieNode*> children; // Initialize your data structure here. TrieNode():isTail(false){} TrieNode(char k):isTail(false),key(k){} bool findChild(char ch){ return children.find(ch)!=children.end(); } TrieNode * insertChildrend(char ch){ TrieNode *newNode = new TrieNode(ch); children.insert(pair<char, TrieNode*>(ch, newNode)); return newNode; } TrieNode * getChild(char ch){ return children[ch]; } }; class Trie { public: Trie() { root = new TrieNode(); } // Inserts a word into the trie. void insert(string s) { TrieNode *p = root; for(auto ch:s){ if(!p->findChild(ch)){ TrieNode *newNode = p->insertChildrend(ch); p = newNode; }else{ p = p->getChild(ch); } } if(p!=NULL){ p->isTail = true; } } // Returns if the word is in the trie. bool search(string key, TrieNode *p, int index) { if(index>key.size()) return false; if(index==key.size()){ if(p!=NULL && p->isTail) return true; else return false; } char ch = key[index]; if(ch!='.'){ if(p==NULL || !p->findChild(ch)){ return false; } TrieNode *q = p->getChild(ch); return search(key, q, index+1); }else{ for(auto it=p->children.begin(); it!=p->children.end(); ++it){ TrieNode *q = it->second; if(search(key, q, index+1)) return true; } return false; } } TrieNode* root; }; class WordDictionary { Trie trie; public: WordDictionary(){ Trie trie=Trie(); } // Adds a word into the data structure. void addWord(string word) { trie.insert(word); } // Returns if the word is in the data structure. A word could // contain the dot character '.' to represent any one letter. bool search(string word) { return trie.search(word, trie.root, 0); } }; class TrieNode{ public: char key; bool isLeaf = false; TrieNode* children[26] = {NULL}; TrieNode(){} TrieNode(char k):key(k){} }; class Trie{ public: TrieNode *root = new TrieNode(); Trie(){} void insert(string s){ TrieNode *p = root; for(int i=0; i<(int)s.size(); ++i){ char c = s[i]; if(p->children[c-'a']==NULL){ p->children[c-'a'] = new TrieNode(c); } p = p->children[c-'a']; } p->isLeaf = true; } bool search(string s){ return search(s, s.size(), 0, root); } bool search(string s, int n, int i, TrieNode* p){ if(i==n){ return p->isLeaf; }else{ char c = s[i]; if(c!='.'){ return p->children[c-'a']&&search(s, n, i+1, p->children[c-'a']); }else{ for(char cc='a'; cc<='z'; ++cc){ if(p->children[cc-'a']&&search(s, n, i+1, p->children[cc-'a'])) return true; } } return false; } } }; class WordDictionary { Trie trie; public: // Adds a word into the data structure. void addWord(string word) { trie.insert(word); } // Returns if the word is in the data structure. A word could // contain the dot character '.' to represent any one letter. bool search(string word) { return trie.search(word); } };