每天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
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;
}
};
微信长按扫码加北美加群小助手公众号
微信扫一扫
关注该公众号