Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit87b82ea

Browse files
authored
Merge branch 'main' into main
2 parents8a14a06 +4bf0608 commit87b82ea

File tree

191 files changed

+8199
-70
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

191 files changed

+8199
-70
lines changed

‎.gitignore‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
.DS_Store

‎130-Surrounded-Regions.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
classSolution {
2+
publicvoidsolve(char[][]board) {
3+
intnRows =board.length;
4+
intnCols =board[0].length;
5+
6+
// 1a) Capture unsurrounded regions - top and bottom row (O -> T)
7+
for (inti =0;i <nCols;i++) {
8+
if (board[0][i] =='O')dfs(board,0,i);
9+
if (board[nRows-1][i] =='O')dfs(board,nRows-1,i);
10+
}
11+
12+
// 1b) Capture unsurrounded regions - Left and right columns (O -> T)
13+
for (inti =0;i <nRows;i++) {
14+
if (board[i][0] =='O')dfs(board,i,0);
15+
if (board[i][nCols-1] =='O')dfs(board,i,nCols-1);
16+
}
17+
18+
for (intr =0;r <nRows;r++) {
19+
for (intc =0;c <nCols;c++) {
20+
if (board[r][c] =='O')board[r][c] ='X';// 2) Capture surrounded regions (O -> X)
21+
if (board[r][c] =='T')board[r][c] ='O';// 3) Uncapture unsurrounded regions (T- O)
22+
}
23+
}
24+
}
25+
26+
privatevoiddfs(char[][]board,intr,intc) {
27+
intnRows =board.length;
28+
intnCols =board[0].length;
29+
if (r <0 ||c <0 ||r >=nRows ||c >=nCols ||board[r][c] !='O')return;
30+
31+
board[r][c] ='T';
32+
dfs(board,r+1,c);
33+
dfs(board,r-1,c);
34+
dfs(board,r,c+1);
35+
dfs(board,r,c-1);
36+
}
37+
}

‎371-Sum-of-Two-Integers.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,4 +7,4 @@ public int getSum(int a, int b) {
77
}
88
returna;
99
}
10-
}
10+
}
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
/*
2+
Given int array, return true if any value appears at least twice
3+
Ex. nums = [1,2,3,1] -> true, nums = [1,2,3,4] -> false
4+
5+
If seen num previously then has dupe, else insert into hash set
6+
7+
Time: O(n)
8+
Space: O(n)
9+
*/
10+
11+
classSolution {
12+
public:
13+
boolcontainsDuplicate(vector<int>& nums) {
14+
unordered_set<int> s;
15+
16+
for (int i =0; i < nums.size(); i++) {
17+
if (s.find(nums[i]) != s.end()) {
18+
returntrue;
19+
}
20+
s.insert(nums[i]);
21+
}
22+
23+
returnfalse;
24+
}
25+
};
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/*
2+
Design algorithm to encode/decode: list of strings <-> string
3+
4+
Encode/decode w/ non-ASCII delimiter: {len of str, "#", str}
5+
6+
Time: O(n)
7+
Space: O(1)
8+
*/
9+
10+
classCodec {
11+
public:
12+
13+
// Encodes a list of strings to a single string.
14+
stringencode(vector<string>& strs) {
15+
string result ="";
16+
17+
for (int i =0; i < strs.size(); i++) {
18+
string str = strs[i];
19+
result +=to_string(str.size()) +"#" + str;
20+
}
21+
22+
return result;
23+
}
24+
25+
// Decodes a single string to a list of strings.
26+
vector<string>decode(string s) {
27+
vector<string> result;
28+
29+
int i =0;
30+
while (i < s.size()) {
31+
int j = i;
32+
while (s[j] !='#') {
33+
j++;
34+
}
35+
int length =stoi(s.substr(i, j - i));
36+
string str = s.substr(j +1, length);
37+
result.push_back(str);
38+
i = j +1 + length;
39+
}
40+
41+
return result;
42+
}
43+
private:
44+
};
45+
46+
// Your Codec object will be instantiated and called as such:
47+
// Codec codec;
48+
// codec.decode(codec.encode(strs));
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/*
2+
Given array of strings, group anagrams together (same letters diff order)
3+
Ex. strs = ["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]]
4+
5+
Count chars, for each string use total char counts (naturally sorted) as key
6+
7+
Time: O(n x l) -> n = length of strs, l = max length of a string in strs
8+
Space: O(n x l)
9+
*/
10+
11+
classSolution {
12+
public:
13+
vector<vector<string>>groupAnagrams(vector<string>& strs) {
14+
unordered_map<string, vector<string>> m;
15+
for (int i =0; i < strs.size(); i++) {
16+
string key =getKey(strs[i]);
17+
m[key].push_back(strs[i]);
18+
}
19+
20+
vector<vector<string>> result;
21+
for (auto it = m.begin(); it != m.end(); it++) {
22+
result.push_back(it->second);
23+
}
24+
return result;
25+
}
26+
private:
27+
stringgetKey(string str) {
28+
vector<int>count(26);
29+
for (int j =0; j < str.size(); j++) {
30+
count[str[j] -'a']++;
31+
}
32+
33+
string key ="";
34+
for (int i =0; i <26; i++) {
35+
key.append(to_string(count[i] +'a'));
36+
}
37+
return key;
38+
}
39+
};
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/*
2+
Given unsorted array, return length of longest consecutive sequence
3+
Ex. nums = [100,4,200,1,3,2] -> 4, longest is [1,2,3,4]
4+
5+
Store in hash set, only check for longer seq if it's the beginning
6+
7+
Time: O(n)
8+
Space: O(n)
9+
*/
10+
11+
classSolution {
12+
public:
13+
intlongestConsecutive(vector<int>& nums) {
14+
unordered_set<int> s;
15+
for (int i =0; i < nums.size(); i++) {
16+
s.insert(nums[i]);
17+
}
18+
19+
int result =0;
20+
21+
for (auto it = s.begin(); it != s.end(); it++) {
22+
int currNum = *it;
23+
if (s.find(currNum -1) != s.end()) {
24+
continue;
25+
}
26+
int currLength =1;
27+
while (s.find(currNum +1) != s.end()) {
28+
currLength++;
29+
currNum++;
30+
}
31+
result =max(result, currLength);
32+
}
33+
34+
return result;
35+
}
36+
};
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/*
2+
Given an integer array nums, return an array such that:
3+
answer[i] is equal to the product of all elements of nums except nums[i]
4+
Ex. nums = [1,2,3,4] -> [24,12,8,6], nums = [-1,1,0,-3,3] -> [0,0,9,0,0]
5+
6+
Calculate prefix products forward, then postfix backwards in a 2nd pass
7+
8+
Time: O(n)
9+
Space: O(1)
10+
*/
11+
12+
classSolution {
13+
public:
14+
vector<int>productExceptSelf(vector<int>& nums) {
15+
int n = nums.size();
16+
vector<int>result(n,1);
17+
18+
int prefix =1;
19+
for (int i =0; i < n; i++) {
20+
result[i] = prefix;
21+
prefix = prefix * nums[i];
22+
}
23+
24+
int postfix =1;
25+
for (int i = n -1; i >=0; i--) {
26+
result[i] = result[i] * postfix;
27+
postfix = postfix * nums[i];
28+
}
29+
30+
return result;
31+
}
32+
};
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/*
2+
Given an integer array nums & an integer k, return the k most frequent elements
3+
Ex. nums = [1,1,1,2,2,3] k = 2 -> [1,2], nums = [1] k = 1 -> [1]
4+
5+
Heap -> optimize w/ freq map & bucket sort (no freq can be > n), get results from end
6+
*/
7+
8+
// Time: O(n log k)
9+
// Space: O(n + k)
10+
11+
// class Solution {
12+
// public:
13+
// vector<int> topKFrequent(vector<int>& nums, int k) {
14+
// unordered_map<int, int> m;
15+
// for (int i = 0; i < nums.size(); i++) {
16+
// m[nums[i]]++;
17+
// }
18+
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
19+
// for (auto it = m.begin(); it != m.end(); it++) {
20+
// pq.push({it->second, it->first});
21+
// if (pq.size() > k) {
22+
// pq.pop();
23+
// }
24+
// }
25+
// vector<int> result;
26+
// while (!pq.empty()) {
27+
// result.push_back(pq.top().second);
28+
// pq.pop();
29+
// }
30+
// return result;
31+
// }
32+
// };
33+
34+
// Time: O(n)
35+
// Space: O(n)
36+
37+
classSolution {
38+
public:
39+
vector<int>topKFrequent(vector<int>& nums,int k) {
40+
int n = nums.size();
41+
42+
unordered_map<int,int> m;
43+
for (int i =0; i < n; i++) {
44+
m[nums[i]]++;
45+
}
46+
47+
vector<vector<int>>buckets(n +1);
48+
for (auto it = m.begin(); it != m.end(); it++) {
49+
buckets[it->second].push_back(it->first);
50+
}
51+
52+
vector<int> result;
53+
54+
for (int i = n; i >=0; i--) {
55+
if (result.size() >= k) {
56+
break;
57+
}
58+
if (!buckets[i].empty()) {
59+
result.insert(result.end(), buckets[i].begin(), buckets[i].end());
60+
}
61+
}
62+
63+
return result;
64+
}
65+
};
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
Given int array & target, return indices of 2 nums that add to target
3+
Ex. nums = [2,7,11,15] & target = 9 -> [0,1], 2 + 7 = 9
4+
5+
At each num, calculate complement, if exists in hash map then return
6+
7+
Time: O(n)
8+
Space: O(n)
9+
*/
10+
11+
classSolution {
12+
public:
13+
vector<int>twoSum(vector<int>& nums,int target) {
14+
unordered_map<int,int> m;
15+
vector<int> result;
16+
17+
for (int i =0; i < nums.size(); i++) {
18+
int complement = target - nums[i];
19+
if (m.find(complement) != m.end()) {
20+
result.push_back(m[complement]);
21+
result.push_back(i);
22+
break;
23+
}else {
24+
m.insert({nums[i], i});
25+
}
26+
}
27+
28+
return result;
29+
}
30+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp