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

540.Single Element in a Sorted Array
题目：给定一个sorted array， 里面有一个数字出现了1次，其他出现了两次，求在O(log(n)) 的时间内找到单身的那个。

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

题解：在该数字之前，我们有 nums[2k]==nums[2*k+1] ， 之后这个条件就不满足了。利用这一点进行 bisection search .

#include<cassert>
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        assert(n%2);
        int k = n/2;
        if(n == 1) return nums[0];
        if(nums[2*k] != nums[2*k-1]) return nums[2*k];
        int l = -1, r = k;
        while(l<r-1){
            int c = (l+r)/2;
            if(nums[2*c] == nums[2*c+1]) l = c;
            else r = c;
        }
        return nums[2*r];
    }
};

539.Minimum Time Difference

题目:Find the minimum minutes difference between any two time points in List.

Example 1:

Input: ["23:59","00:00"]
Output: 1

题解:
引用shawngao大神解法，使用bucket sort, 所有timestamp记录成一个boolean array。loop 一遍找前后都有差值最小的timestamp. 语言Java. Running time(O(2460)), Space(O(2460))

public int findMinDifference(List<String> timePoints) {
    boolean[] mark = new boolean[24 * 60];
    for (String time : timePoints) {
        String[] t = time.split(":");
        int h = Integer.parseInt(t[0]);
        int m = Integer.parseInt(t[1]);
        if (mark[h * 60 + m]) return 0;
        mark[h * 60 + m] = true;
    }

    int prev = 0, min = Integer.MAX_VALUE;
    int first = Integer.MAX_VALUE, last = Integer.MIN_VALUE;
    for (int i = 0; i < 24 * 60; i++) {
        if (mark[i]) {
            if (first != Integer.MAX_VALUE) {
                min = Math.min(min, i - prev);
            }
            first = Math.min(first, i);
            last = Math.max(last, i);
            prev = i;
        }
    }

    min = Math.min(min, (24 * 60 - last + first));

    return min;
}

538.Convert BST to Greater Tree
题目：给定一个BST，要求把其中每一个节点的 value 改成这个 value 加上所有比 value 值大的数之和。
题解：就是一个 inorder traversal， 只不过是反着的：先右再根再左。

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13
Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int res = 0;
        stack<TreeNode *> stk;
        auto p = root;
        while(root || !stk.empty()){
            while(root){
                stk.push(root);
                root = root->right;
            }
            if(!stk.empty()){
                auto tmp = stk.top();
                stk.pop();
                res += tmp->val;
                tmp->val = res;
                root = tmp->left;
            }
        }
        return p;
    }
};

537.Complex Number Multiplication
题目：
给定两个代表两个复数的字符串。
你需要返回一个代表它们乘法的字符串。根据定义，注意i^2 = -1。

Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

题解：
使用公式:
(a+ib)×(x+iy)=ax+i2by+i(bx+ay)=ax−by+i(bx+ay)
code in java, running time && space both O(1)

class Solution {
    public String complexNumberMultiply(String a, String b) {
      String x[] = a.split("\\+|i");
      String y[] = b.split("\\+|i");
      int aReal = Integer.parseInt(x[0]);
      int aImg = Integer.parseInt(x[1]);
      int bReal = Integer.parseInt(y[0]);
      int bImg = Integer.parseInt(y[1]);
      return (aReal*bReal - aImg*bImg) + "+" + (aReal * bImg+aImg*bReal) + "i";
    }
 }

536.Construct Binary Tree from String

题目：把 string 转换成 binary tree
题解：用 recursion，就是每次要找每个左括号对应的右括号的位置。小编这个方法虽然好写，但比较慢。一个最简单的优化是，先 precompute 所有左括号对应的右括号的位置， 然后对 index 做 recursion。

Example:

Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5   

Note:

class Solution {
public:
    TreeNode* str2tree(string s) {
        if(s.empty()) return NULL;
        TreeNode *root = new TreeNode(stoi(s));
        auto j = s.find('(');
        if(j == string::npos) return root;
        int cnt = 1, k = (int)j+1;
        while(cnt && k<s.size()){
            if(s[k] == '(') cnt++;
            else if(s[k] == ')') cnt--;
            k++;
        }
        root->left = str2tree(s.substr(j+1,k-2-j));
        if(k<s.size()) root->right = str2tree(s.substr(k+1, s.size()-k-2));
        return root;
    }
};

535.Encode and Decode TinyURL
题目：让你设计一个class，可以 encode 和 decode， encode 是把一个long URL 转化成一个 short URL， decode 是 encode 的逆过程。做法很多，小编这个很无脑，直接用数字。

class Solution {
    int cnt = 0;
    unordered_map<string, int> p;
    unordered_map<int, string> r;
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if(p.count(longUrl)) to_string(p[longUrl]);
        else{
            p[longUrl] = cnt;
            r[cnt] = longUrl;
            cnt++;
            return to_string(cnt-1);
        }
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return r[stoi(shortUrl)];
    }
};

534.Design TinyURL
题目：设计一个tiny url的encoding, decoding service.

题 解：service涉及到sql. 下面的解法keep了一个6位char到url的hashmap. 每次url进来先看hashmap里是否存在6位对应string, 如果不存在，不断的generate，hashmap中不存在的6位string。这样保证了shorten url的key string为恒定长度。
因为是system design，所以还要提到构架：Browser <-> Web <-> Core <-> DB。以及各层之间的优化。

Database 设计：One table (id, long_url). id is the primary key, ordered by long_url
DNS优化：不同的位置使用不同的Web服务器和缓存服务器所有的区域共享一个数据库，当用户在缓存上未命中时，用户可以通过DNS（通过DNS）将其与最接近的Web服务器进行匹配。
Cache优化：使用Memcached来提高响应速度。获取long_url时，首先在缓存中搜索，然后搜索数据库。我们可以把90％的读取请求放在缓存上。

class Solution {
public:
    Solution() {
        dict = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        short2long.clear();
        long2short.clear();
        srand(time(NULL));
    }

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if (long2short.count(longUrl)) {
            return "http://tinyurl.com/" + long2short[longUrl];
        }
        int idx = 0;
        string randStr;
        for (int i = 0; i < 6; ++i) randStr.push_back(dict[rand() % 62]);
        while (short2long.count(randStr)) {
            randStr[idx] = dict[rand() % 62];
            idx = (idx + 1) % 5;
        }
        short2long[randStr] = longUrl;
        long2short[longUrl] = randStr;
        return "http://tinyurl.com/" + randStr;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        string randStr = shortUrl.substr(shortUrl.find_last_of("/") + 1);
        return short2long.count(randStr) ? short2long[randStr] : shortUrl;
    }

private:
    unordered_map<string, string> short2long, long2short;
    string dict;
};

533.Lonely Pixel II
题目：就是给定一个由 ‘B’ 跟 ‘W’ 组成的二维格点以及整数N，找这样的 r,c 对使得：

r 行与 c 列所包涵的 ‘B’ de 个数都是 N。

有 c 列相交与 ‘B’ 的行都与 r 行完全相同。

Example:

Input:                                            
[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']] 

N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index

Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

题解：题目很简单，就是根据要求用 brute force 找即可。 烦人的是，输入是 vector<vector> 而不是 vector, 后者更好处理一些。所以我在做的时候先做了一个copy, 其type 是 vector。</vector

class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int N) {
        if(picture.empty() && picture[0].empty()) return 0;
        int n = picture.size(), m = picture[0].size(), ans = 0;
        vector<string> pic(n);
        for(int i=0;i<n;++i) pic[i].assign(picture[i].begin(), picture[i].end());
        unordered_map<string, int> cnt;
        for(auto s:pic) if(count(s.begin(),s.end(),'B') == N) cnt[s]++;
        for(int j=0;j<m;++j){
            int ct = 0;
            string tmp;
            bool ok = true;
            for(int i=0;i<n && ok;++i) if(pic[i][j] == 'B'){
                ct++;
                if(!tmp.empty() && (tmp != pic[i] || !cnt.count(tmp))) ok = false;
                if(tmp.empty()) tmp = pic[i];
            }
            if(!ok || ct !=N) continue;
            ans += cnt[tmp];
        }
        return ans;
    }
};

532.K-diff Pairs in an Array
题目：给定一个array， count unique pairs that their absolute difference is k, where k is given.

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

题解：很简单，就是用一个 hash map 记录一下每个数是否出现过。注意 k = 0 和 k < 0 的情况即可。

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if(k<0) return 0;
        unordered_map<int, int> cnt;
        for(auto j:nums) cnt[j]++;
        int ans = 0;
        for(auto j:nums) if(cnt.count(j)){
            cnt[j]--;
            if(!cnt[j]) cnt.erase(j);
            if(cnt.count(j + k)) ans += 1;
            if(k && cnt.count(j-k)) ans += 1;
            cnt.erase(j);
        }
        return ans;
    }
};

531.Lonely Pixel I
题目：给定一个由 W 跟 B 组成的矩阵，求 lonely B 的个数

lonely　B 定义为，一个B 且其所在行列都没有其它 B.

题解：挨个找就行了

Example:

Input: [['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        if(picture.empty() || picture[0].empty()) return 0;
        vector<string> pic;
        for(auto vec:picture) pic.push_back(string(vec.begin(), vec.end()));
        int n = pic.size(), m = pic[0].size(), ans = 0;
        vector<bool> cidx(m,false);
        for(int j=0;j<m;++j){
            int cnt = 0;
            for(int i=0;i<n;++i) if(pic[i][j] == 'B'){
                cnt++;
                if(cnt>1) break;
            }
            if(cnt == 1) cidx[j] = true;
        }
        for(auto vec: pic){
            if(count(vec.begin(),vec.end(),'B') == 1 && cidx[vec.find('B')]) ans++;
        }
        return ans;
    }
};

微信长按扫码加北美加群小助手公众号