## 60天带你刷完Leetcode【第15天】530 ~ 521

2017-11-20 PKU GoodSpeed 美国加群小助手 美国加群小助手

530.Minimum Absolute Difference in BST
Question:一个BST, 找任意两个node之间的最小值。

```Input:

1
\
3
/
2Output:1Explanation:The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).```

Solution:
Though question asked for minimum difference between any two nodes, we know that the min diff will only occur between two adjacent node values if values are in ascending sorted order. Thus one in-order traversal with memorization of prev node value and global mean will do for this BST.

``````public class Solution {

int minDiff = Integer.MAX_VALUE;
TreeNode prev;

public int getMinimumDifference(TreeNode root) {
inorder(root);
return minDiff;
}

public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
prev = root;
inorder(root.right);
}

}``````

529.Minesweeper

This is a typical Search problem, Search rules:

If click on a mine (‘M’), mark it as ‘X’, stop further search.

If click on an empty cell (‘E’), depends on how many surrounding mine:

2.1 Has surrounding mine(s), mark it with number of surrounding mine(s), stop further search.

2.2 No surrounding mine, mark it as ‘B’, continue search its 8 neighbors.

DFS solution:

``````public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board.length;
int row = click, col = click;

if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}

if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = (char)(count + '0');
}
else { // Continue DFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'E') updateBoard(board, new int[] {r, c});
}
}
}
}

return board;
}
}``````

527.Word Abbreviation

`Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]`

Solution:

``````public class Solution {
public List<String> wordsAbbreviation(List<String> dict) {
Map<String, String> wordToAbbr = new HashMap<>();
Map<Integer, List<String>> groups = new HashMap<>();

// Try to group words by their length. Because no point to compare words with different length.
// Also no point to look at words with length < 4.
for (String word : dict) {
int len = word.length();
if (len < 4) {
wordToAbbr.put(word, word);
}
else {
List<String> g = groups.getOrDefault(len, new ArrayList<String>());
groups.put(len, g);
}
}

// For each group of words with same length, generate a result HashMap.
for (int len : groups.keySet()) {
Map<String, String> res = getAbbr(groups.get(len));
for (String word : res.keySet()) {
wordToAbbr.put(word, res.get(word));
}
}

// Generate the result list
List<String> result = new ArrayList<>();
for (String word : dict) {
}

return result;
}

private Map<String, String> getAbbr(List<String> words) {
Map<String, String> res = new HashMap<>();
int len = words.get(0).length();

// Try to abbreviate a word from index 1 to len - 2
for (int i = 1; i < len - 2; i++) {
Map<String, String> abbrToWord = new HashMap<>();
for (String s : words) {
if (res.containsKey(s)) continue;
// Generate the current abbreviation
String abbr = s.substring(0, i) + (len - 1 - i) + s.charAt(len - 1);
// Tick: use reversed abbreviation to word map to check if there is any duplicated abbreviation
if (!abbrToWord.containsKey(abbr)) {
abbrToWord.put(abbr, s);
}
else {
abbrToWord.put(abbr, "");
}
}

// Add unique abbreviations find during this round to result HashMap
for (String abbr : abbrToWord.keySet()) {
String s = abbrToWord.get(abbr);
// Not a unique abbreviation
if (s.length() == 0) continue;
res.put(s, abbr);
}
}

// Add all words that can't be shortened.
for (String s : words) {
if (!res.containsKey(s)) {
res.put(s, s);
}
}

return res;
}
}``````

For searching word problems, the first thing comes to my mind is always trie.
In this problem, we actually check if this word has prefix with other words that has same length, start and end;
The naive way is build the whole trie for all words, which require large space if there are many long words.
So my approach is,

Build a map, abbr->Trie, where abbr=s+len+s[len-1]

For a new word, if abbr is not in the map, create a new Trie for this abbr, but only push further to the 1st char, and then memorize the idx of the word at this trie node;

For a new word, if abbr is in the map, continue search in the trie till the current char can not be matched. And here we have 2 situation:

``````  (1) the idx memorized under this trie node is -1, which means that the word that has same prefix with current word has longer prefix with other words, then we just create a new trie node for the current word and memorize the current idx;
(2) the idx memorized under this trie node is not -1, which means that the word memorized here has same prefix with current word and currently they share the longest prefix in this abbr. Thus, we need to push further for both words until the 1st different char. And also, we need to set the idx memorized before to -1.``````

Since we do not build the suffix of the word in the trie until there is another word has same prefix, the space complexity for the trie with abbr is O(n*longestSamePrefixLength).
Code:

``````class Solution {
public List<String> wordsAbbreviation(List<String> dict) {
abbr2trie = new HashMap<>();
endIdx = new int[dict.size()];
for(int i = 0; i<dict.size(); ++i){
String cur = dict.get(i);
if(cur.length()<=3) endIdx[i] = cur.length();
else{
}
}
for(int i = 0; i<dict.size(); ++i){
String cur = dict.get(i);
else{
}
}
return res;
}
private Map<String, TrieNode> abbr2trie;
private int[] endIdx;
class TrieNode{
int stringIndex;
TrieNode[] next;
public TrieNode(){
stringIndex = -1;
next = new TrieNode;
}
public TrieNode(int i){
stringIndex = i;
next = new TrieNode;
}
}
private String str2abbr(String s){
return s.charAt(0)+String.valueOf(s.length())+s.charAt(s.length()-1);
}
private void addWord(String s, String abbr, int sidx, List<String> dict){
if(!abbr2trie.containsKey(abbr)){
// 1st word with this abbr
// Only create 1st char of the string in the trie
endIdx[sidx] = 1;
}
else{
TrieNode node = abbr2trie.get(abbr);
int idx = 0;
while(node.next[s.charAt(idx)-'a']!=null){
// Go through same preffix in the trie
node = node.next[s.charAt(idx++)-'a'];
}
int sidx2 = node.stringIndex;
if(sidx2==-1){
// This means that other words with this prefix have been pushed further, they have longer same prefix
// And this word could stop here and create next char to distinguish it
node.next[s.charAt(idx)-'a'] = new TrieNode(sidx);
endIdx[sidx] = idx+1;
return;
}
// Push further sidx2
node.stringIndex = -1;

String s2 = dict.get(sidx2);
while(s.charAt(idx)==s2.charAt(idx)){
node.next[s.charAt(idx) - 'a'] = new TrieNode();
node = node.next[s.charAt(idx++) -'a'];
}
endIdx[sidx]  = idx+1;
endIdx[sidx2] = idx+1;
node.next[s.charAt(idx)-'a'] = new TrieNode(sidx);
node.next[s2.charAt(idx)-'a'] = new TrieNode(sidx2);
}
}
}``````

526.Beautiful Arrangment
Question:从1-N,找出满足以下两条件的数的个数：

The number at the ith position is divisible by i.

i is divisible by the number at the ith position.

`Input: 2Output: 2Explanation: The first beautiful arrangement is [1, 2]:Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).The second beautiful arrangement is [2, 1]:Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.`

Solution: Bit matinpualtion + dp

``````class Solution {
int dp[1<<15];
int n;
int dfs(int p, int s){
if(p == n) return 1;
if(dp[p][s] >= 0) return dp[p][s];
dp[p][s] = 0;
for(int i=0;i<n;++i) if(!((s>>i)&1) && ((i+1)%(p+1)==0 || (p+1)%(i+1)==0)) dp[p][s] += dfs(p+1, s|(1<<i));
return dp[p][s];
}
public:
int countArrangement(int N) {
this->n = N;
memset(dp,-1,sizeof(dp));
return dfs(0, 0);
}
};``````

525.Contiguous Array
timu:一个只有0,1组成的数组，找到最长连续sub数组，0和1的个数相同。

Example 1:

`Input: [0,1]Output: 2Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.`

Example 2:

`Input: [0,1,0]Output: 2Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.`

tijie: same as 523

``````class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int ,int> pos;
int ans = 0;
pos = -1;
for(int i=0, tmp = 0; i< nums.size(); ++i){
if(nums[i]) ++tmp;
else --tmp;
if(pos.count(tmp)) ans = max(ans, i - pos[tmp]);
else pos[tmp] = i;
}
return ans;
}
};``````

524.Longest Word in Dictionary through Deleting
timu:给一个String和1个dictionary of strings。找到这个string 删减char得到dictionary中的最长单词。如果有相同长度的，按照lexical graphic order来取。

Example 1:

`Input:s = "abpcplea", d = ["ale","apple","monkey","plea"]Output: "apple"`

Example 2:

`Input:s = "abpcplea", d = ["a","b","c"]Output: "a"`

tijie: Same as the subsequence one

``````class Solution {
typedef vector<int> vi;
vector<vi> next;
int n;
static bool comp(const string&s1, const string &s2){
if(s1.size() != s2.size()) return s1.size()>s2.size();
return s1 < s2;
}
bool isSub(string a){
if(a.size() > n) return false;
int j = 0;
for(auto c:a){
j = next[int(c-'a')][j] + 1;
if(!j) return false;
}
return true;
}
public:
string findLongestWord(string s, vector<string>& d) {
sort(d.begin(), d.end(), comp);
this->n = (int)s.size();
next = vector<vi>(26,vi(n+1, -1));
for(int i=n-1;i>=0;--i){
for(int j=0;j<26;++j){
if(j == int(s[i]-'a')) next[j][i] = i;
else next[j][i] = next[j][i+1];
}
}
for(auto str:d) if(isSub(str)) return str;
return "";
}
};``````

523.Continuous Subarray Sum
timu:给一个数组，和一个数k，问数组数之和能否等于k^n，n为1～maxInt.

Example 1:

`Input: [23, 2, 4, 6, 7],  k=6Output: TrueExplanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.`

Example 2:

`Input: [23, 2, 6, 4, 7],  k=6Output: TrueExplanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.`

tijie: yong xia tong yu Zk, also need to consider the case when k == 0

``````class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if(!k){
for(int j=1;j<nums.size();++j) if(!nums[j] && !nums[j-1]) return true;
return false;
}
k = abs(k);
unordered_map<int, int> pos;
pos = 0;
for(int i=0, tmp = 0;i<nums.size();++i){
tmp += nums[i];
if(!pos.count(tmp%k)) pos[tmp%k] = i+1;
else if(i>pos[tmp%k]) return true;
}
return false;
}
};``````

522.Longest Uncommon Subsequence II
timu:给很多个sequences，找到longest uncommon sequence，这个sequence 不是所有别的sequence的subsequence。

`Input: "aba", "cdc", "eae"Output: 3`

tijie: Brute force

``````class Solution {
bool isSub(string a, string b){
if(b.empty() || b.size() < a.size()) return false;
if(b.find(a) != string::npos) return true;
auto j = b.find(b);
for(auto c:a){
j = b.find(c, j);
if(j == string::npos) return false;
j += 1;
}
return true;
}
public:
int findLUSlength(vector<string>& strs) {
int ans = -1;
for(int i=0;i<strs.size();++i){
bool ok = true;
for(int j=0;j<strs.size() && ok; ++j) if(i!=j){
if(isSub(strs[i], strs[j])) ok = false;
}
if(ok) ans = max(ans, (int)strs[i].size());
}
return ans;
}
};``````

521.Longest Uncommon Subsequence I
timu:给两个sequences，找到longest uncommon sequence，这个sequence 不是所有别的sequence的subsequence。

`Input: "aba", "cdc"Output: 3Explanation: The longest uncommon subsequence is "aba" (or "cdc"), because "aba" is a subsequence of "aba", but not a subsequence of any other strings in the group of two strings. `

tijie: Are you fucking kidding me?

``````class Solution {
public:
int findLUSlength(string a, string b) {
if(a == b) return -1;
return max(int(a.size()), int(b.size()));
}
};``````   