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

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

每天30分钟 关注【北美加群小助手Jogchat.com】60天就能刷完Leetcode,学渣学酥也能跻身硅谷一线公司、升职加薪、当上总经理、出任CEO、迎娶白富美、从此走上人生巅峰!想想还有点小激动😏

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

Input:

   1
    \
     3
    /
   2
Output:1
Explanation:
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.
引用 compton_scatter大神

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
题目:扫雷游戏的update function.


题解:
引用shawngao 大神解法
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[0].length;
        int row = click[0], col = click[1];

        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

题目:给一个很长的单词array,对它进行abbreviation 操作。

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

Solution:
引 用shawn gao大神的解法,建立 word to abbreviation hashmap。把word按照length分组,<=3的不需要abbreviate. 同样length 的word从hashmap里面找. 用Map < word, Trie> 也是可以做的,但需要更多的改动“ I thought about Trie at the beginning. But the abbreviation must contain the last letter. It makes the problem difficult by using Trie (Prefix Tree). Then I gave it up.”(shawn gao)。而shawn gao使用分组讨论的原因是pagination的思想,避免Map

过大导致内存溢出。这样达到了一个内存不过大,又能消减重复case运算时间的平衡,从而passs。
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>());
                g.add(word);
                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) {
            result.add(wordToAbbr.get(word));
        }

        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;
    }
}

引用Luffy_Tse 的Trie解法,使用更大的内存,来提高速度。2的内存优化,在节点只记录idx of word而不是把整个word都写出,是内存优化重要一步。否则会溢出。传说这种解法beat100%。
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[0]+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{
            addWord(cur, str2abbr(cur), i, dict);
        }
    }
    List<String> res = new LinkedList<>();
    for(int i = 0; i<dict.size(); ++i){
        String cur = dict.get(i);
        if(cur.length()-endIdx[i]-1<=1) res.add(cur);
        else{
            res.add(cur.substring(0, endIdx[i])+(cur.length()-endIdx[i]-1)+cur.charAt(cur.length()-1));
        }
    }
    return res;
}
private Map<String, TrieNode> abbr2trie;
private int[] endIdx;
class TrieNode{
    int stringIndex;
    TrieNode[] next;
    public TrieNode(){
        stringIndex = -1;
        next = new TrieNode[26];
    }
    public TrieNode(int i){
        stringIndex = i;
        next = new TrieNode[26];
    }
}
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
        TrieNode head = new TrieNode();
        abbr2trie.put(abbr, head);
        head.next[s.charAt(0)-'a'] = new TrieNode(sidx);
        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: 2
Output:
2
Explanation:

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[15][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:
2
Explanation:
[0, 1] is the longest contiguous subarray
with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output:
2
Explanation:
[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[0] = -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=6
Output:
True
Explanation:
Because [2, 4] is a continuous subarray
of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output:
True
Explanation: 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] = 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[0]);
        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:
3
Explanation: 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()));
    }
};

微信长按扫码加北美加群小助手服务号


微信长按扫码加美国加群小助手订阅号

微信扫一扫
关注该公众号