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

Commitc5e22d7

Browse files
authored
Added tasks 300-543
1 parent553e7a2 commitc5e22d7

File tree

20 files changed

+710
-0
lines changed

20 files changed

+710
-0
lines changed
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Binary_Search
2+
// #Algorithm_II_Day_16_Dynamic_Programming #Binary_Search_II_Day_3 #Dynamic_Programming_I_Day_18
3+
// #Udemy_Dynamic_Programming #Big_O_Time_O(n*log_n)_Space_O(n)
4+
// #2024_05_22_Time_4_ms_(94.11%)_Space_12.9_MB_(61.94%)
5+
6+
#include<vector>
7+
#include<limits.h>
8+
usingnamespacestd;
9+
10+
classSolution {
11+
public:
12+
intlengthOfLIS(vector<int>& nums) {
13+
if (nums.empty()) {
14+
return0;
15+
}
16+
vector<int>dp(nums.size() +1, INT_MAX);
17+
int left =1;
18+
int right =1;
19+
20+
for (int curr : nums) {
21+
int start = left;
22+
int end = right;
23+
// binary search, find the one that is lower than curr
24+
while (start +1 < end) {
25+
int mid = start + (end - start) /2;
26+
if (dp[mid] > curr) {
27+
end = mid;
28+
}else {
29+
start = mid;
30+
}
31+
}
32+
// update our dp table
33+
if (dp[start] > curr) {
34+
dp[start] = curr;
35+
}elseif (curr > dp[start] && curr < dp[end]) {
36+
dp[end] = curr;
37+
}elseif (curr > dp[end]) {
38+
dp[++end] = curr;
39+
right++;
40+
}
41+
}
42+
return right;
43+
}
44+
};
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
300\. Longest Increasing Subsequence
2+
3+
Medium
4+
5+
Given an integer array`nums`, return the length of the longest strictly increasing subsequence.
6+
7+
A**subsequence** is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example,`[3,6,2,7]` is a subsequence of the array`[0,3,1,6,2,2,7]`.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[10,9,2,5,3,7,101,18]
12+
13+
**Output:** 4
14+
15+
**Explanation:** The longest increasing subsequence is[2,3,7,101], therefore the length is 4.
16+
17+
**Example 2:**
18+
19+
**Input:** nums =[0,1,0,3,2,3]
20+
21+
**Output:** 4
22+
23+
**Example 3:**
24+
25+
**Input:** nums =[7,7,7,7,7,7,7]
26+
27+
**Output:** 1
28+
29+
**Constraints:**
30+
31+
*`1 <= nums.length <= 2500`
32+
* <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>
33+
34+
**Follow up:** Can you come up with an algorithm that runs in`O(n log(n))` time complexity?
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Breadth_First_Search
2+
// #Algorithm_II_Day_18_Dynamic_Programming #Dynamic_Programming_I_Day_20
3+
// #Level_2_Day_12_Dynamic_Programming #Big_O_Time_O(m*n)_Space_O(amount)
4+
// #2024_05_22_Time_12_ms_(97.65%)_Space_16_MB_(67.57%)
5+
6+
#include<vector>
7+
#include<algorithm>
8+
usingnamespacestd;
9+
10+
classSolution {
11+
public:
12+
intcoinChange(vector<int>& coins,int amount) {
13+
vector<int>dp(amount +1,0);
14+
dp[0] =1;
15+
for (int coin : coins) {
16+
for (int i = coin; i <= amount; ++i) {
17+
int prev = dp[i - coin];
18+
if (prev >0) {
19+
if (dp[i] ==0) {
20+
dp[i] = prev +1;
21+
}else {
22+
dp[i] =min(dp[i], prev +1);
23+
}
24+
}
25+
}
26+
}
27+
return dp[amount] -1;
28+
}
29+
};
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
322\. Coin Change
2+
3+
Medium
4+
5+
You are given an integer array`coins` representing coins of different denominations and an integer`amount` representing a total amount of money.
6+
7+
Return_the fewest number of coins that you need to make up that amount_. If that amount of money cannot be made up by any combination of the coins, return`-1`.
8+
9+
You may assume that you have an infinite number of each kind of coin.
10+
11+
**Example 1:**
12+
13+
**Input:** coins =[1,2,5], amount = 11
14+
15+
**Output:** 3
16+
17+
**Explanation:** 11 = 5 + 5 + 1
18+
19+
**Example 2:**
20+
21+
**Input:** coins =[2], amount = 3
22+
23+
**Output:** -1
24+
25+
**Example 3:**
26+
27+
**Input:** coins =[1], amount = 0
28+
29+
**Output:** 0
30+
31+
**Constraints:**
32+
33+
*`1 <= coins.length <= 12`
34+
* <code>1 <= coins[i] <= 2<sup>31</sup> - 1</code>
35+
* <code>0 <= amount <= 10<sup>4</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// #Easy #Dynamic_Programming #Bit_Manipulation #Udemy_Bit_Manipulation
2+
// #Big_O_Time_O(num)_Space_O(num) #2024_05_22_Time_0_ms_(100.00%)_Space_8.9_MB_(80.27%)
3+
4+
#include<vector>
5+
usingnamespacestd;
6+
7+
classSolution {
8+
public:
9+
vector<int>countBits(int num) {
10+
vector<int>result(num +1,0);
11+
int borderPos =1;
12+
int incrPos =1;
13+
for (int i =1; i <= num; ++i) {
14+
// when we reach power of 2, reset borderPos and incrPos
15+
if (incrPos == borderPos) {
16+
result[i] =1;
17+
incrPos =1;
18+
borderPos = i;
19+
}else {
20+
result[i] =1 + result[incrPos++];
21+
}
22+
}
23+
return result;
24+
}
25+
};
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
338\. Counting Bits
2+
3+
Easy
4+
5+
Given an integer`n`, return_an array_`ans`_of length_`n + 1`_such that for each_`i` (`0 <= i <= n`)_,_`ans[i]`_is the**number of**_`1`_**'s** in the binary representation of_`i`.
6+
7+
**Example 1:**
8+
9+
**Input:** n = 2
10+
11+
**Output:**[0,1,1]
12+
13+
**Explanation:**
14+
15+
0 --> 0
16+
1 --> 1
17+
2 --> 10
18+
19+
**Example 2:**
20+
21+
**Input:** n = 5
22+
23+
**Output:**[0,1,1,2,1,2]
24+
25+
**Explanation:**
26+
27+
0 --> 0
28+
1 --> 1
29+
2 --> 10
30+
3 --> 11
31+
4 --> 100
32+
5 --> 101
33+
34+
**Constraints:**
35+
36+
* <code>0 <= n <= 10<sup>5</sup></code>
37+
38+
**Follow up:**
39+
40+
* It is very easy to come up with a solution with a runtime of`O(n log n)`. Can you do it in linear time`O(n)` and possibly in a single pass?
41+
* Can you do it without using any built-in function (i.e., like`__builtin_popcount` in C++)?
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Hash_Table #Sorting #Heap_Priority_Queue #Counting
2+
// #Divide_and_Conquer #Quickselect #Bucket_Sort #Data_Structure_II_Day_20_Heap_Priority_Queue
3+
// #Big_O_Time_O(n*log(n))_Space_O(k) #2024_05_22_Time_11_ms_(69.14%)_Space_16.3_MB_(88.53%)
4+
5+
#include<vector>
6+
#include<queue>
7+
#include<algorithm>
8+
usingnamespacestd;
9+
10+
classSolution {
11+
public:
12+
vector<int>topKFrequent(vector<int>& nums,int k) {
13+
sort(nums.begin(), nums.end());
14+
15+
// Min heap of <number, frequency>
16+
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
17+
18+
// Filter with min heap
19+
int j =0;
20+
for (int i =0; i <= nums.size(); ++i) {
21+
if (i == nums.size() || nums[i] != nums[j]) {
22+
minHeap.push({i - j, nums[j]});
23+
if (minHeap.size() > k) {
24+
minHeap.pop();
25+
}
26+
j = i;
27+
}
28+
}
29+
30+
// Convert to int array
31+
vector<int>result(k);
32+
for (int i = k -1; i >=0; --i) {
33+
result[i] = minHeap.top().second;
34+
minHeap.pop();
35+
}
36+
37+
return result;
38+
}
39+
};
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
347\. Top K Frequent Elements
2+
3+
Medium
4+
5+
Given an integer array`nums` and an integer`k`, return_the_`k`_most frequent elements_. You may return the answer in**any order**.
6+
7+
**Example 1:**
8+
9+
**Input:** nums =[1,1,1,2,2,3], k = 2
10+
11+
**Output:**[1,2]
12+
13+
**Example 2:**
14+
15+
**Input:** nums =[1], k = 1
16+
17+
**Output:**[1]
18+
19+
**Constraints:**
20+
21+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
22+
*`k` is in the range`[1, the number of unique elements in the array]`.
23+
* It is**guaranteed** that the answer is**unique**.
24+
25+
**Follow up:** Your algorithm's time complexity must be better than`O(n log n)`, where n is the array's size.
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
// #Medium #Top_100_Liked_Questions #String #Stack #Recursion #Level_1_Day_14_Stack #Udemy_Strings
2+
// #Big_O_Time_O(n)_Space_O(n) #2024_05_22_Time_0_ms_(100.00%)_Space_7.6_MB_(79.31%)
3+
4+
#include<string>
5+
#include<cctype>
6+
usingnamespacestd;
7+
8+
classSolution {
9+
private:
10+
int i =0;
11+
12+
public:
13+
stringdecodeString(const string& s) {
14+
int count =0;
15+
string result;
16+
while (i < s.length()) {
17+
char c = s[i];
18+
++i;
19+
if (isalpha(c)) {
20+
result += c;
21+
}elseif (isdigit(c)) {
22+
count = count *10 + (c -'0');
23+
}elseif (c ==']') {
24+
break;
25+
}elseif (c =='[') {
26+
// sub problem
27+
string repeat =decodeString(s);
28+
while (count >0) {
29+
result += repeat;
30+
--count;
31+
}
32+
}
33+
}
34+
return result;
35+
}
36+
};
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
394\. Decode String
2+
3+
Medium
4+
5+
Given an encoded string, return its decoded string.
6+
7+
The encoding rule is:`k[encoded_string]`, where the`encoded_string` inside the square brackets is being repeated exactly`k` times. Note that`k` is guaranteed to be a positive integer.
8+
9+
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
10+
11+
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,`k`. For example, there won't be input like`3a` or`2[4]`.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "3[a]2[bc]"
16+
17+
**Output:** "aaabcbc"
18+
19+
**Example 2:**
20+
21+
**Input:** s = "3[a2[c]]"
22+
23+
**Output:** "accaccacc"
24+
25+
**Example 3:**
26+
27+
**Input:** s = "2[abc]3[cd]ef"
28+
29+
**Output:** "abcabccdcdcdef"
30+
31+
**Example 4:**
32+
33+
**Input:** s = "abc3[cd]xyz"
34+
35+
**Output:** "abccdcdcdxyz"
36+
37+
**Constraints:**
38+
39+
*`1 <= s.length <= 30`
40+
*`s` consists of lowercase English letters, digits, and square brackets`'[]'`.
41+
*`s` is guaranteed to be**a valid** input.
42+
* All the integers in`s` are in the range`[1, 300]`.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Level_2_Day_13_Dynamic_Programming
2+
// #Big_O_Time_O(n*sums)_Space_O(n*sums) #2024_05_22_Time_199_ms_(41.03%)_Space_12.3_MB_(92.82%)
3+
4+
#include<vector>
5+
usingnamespacestd;
6+
7+
classSolution {
8+
public:
9+
boolcanPartition(vector<int>& nums) {
10+
int sums =0;
11+
for (int num : nums) {
12+
sums += num;
13+
}
14+
if (sums %2 ==1) {
15+
returnfalse;
16+
}
17+
sums /=2;
18+
vector<bool>dp(sums +1,false);
19+
dp[0] =true;
20+
for (int num : nums) {
21+
for (int sum = sums; sum >= num; --sum) {
22+
dp[sum] = dp[sum] || dp[sum - num];
23+
}
24+
}
25+
return dp[sums];
26+
}
27+
};

0 commit comments

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