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

Commit840e429

Browse files
Merge branch 'neetcode-gh:main' into patch-2
2 parents4863935 +e7fbd4b commit840e429

File tree

47 files changed

+1257
-182
lines changed

Some content is hidden

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

47 files changed

+1257
-182
lines changed

‎.github/workflows/build-readme.yml‎

Lines changed: 3 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -10,27 +10,23 @@ jobs:
1010
Build:
1111
runs-on:ubuntu-latest
1212

13-
strategy:
14-
matrix:
15-
node-version:[16.x]
16-
1713
steps:
1814
-uses:actions/checkout@v3
1915
with:
2016
ref:${{ github.head_ref }}
2117
fetch-depth:1
2218

2319
-name:Use Node.js (dependency)
24-
uses:actions/setup-node@v1
20+
uses:actions/setup-node@v3
2521
with:
26-
node-version:${{ matrix.node-version }}
22+
node-version:16
2723

2824
-name:Completion Table
2925
run:node ./.github/workflows/updateCompletionTable.js;
3026

3127
-name:Check for modified files
3228
id:git-check
33-
run:echo::set-output name=modified::$(if git diff-index --quiet HEAD --; then echo "false"; else echo "true"; fi)
29+
run:echo modified=$(if git diff-index --quiet HEAD --; then echo "false"; else echo "true"; fi) >> $GITHUB_OUTPUT
3430

3531
-name:Push
3632
if:steps.git-check.outputs.modified == 'true'

‎README.md‎

Lines changed: 16 additions & 16 deletions
Large diffs are not rendered by default.

‎c/4-Median-of-Two-Sorted-Arrays.c‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/*
2+
Time: log(min(n, m))
3+
Space: O(1)
4+
*/
5+
6+
#definemin(x,y) ((x < y) ? (x) : (y))
7+
#definemax(x,y) ((x > y) ? (x) : (y))
8+
9+
doublefindMedianSortedArrays(int*nums1,intnums1Size,int*nums2,intnums2Size){
10+
int*A=nums1;
11+
int*B=nums2;
12+
intASize=nums1Size;
13+
intBSize=nums2Size;
14+
15+
inttotal=nums1Size+nums2Size;
16+
inthalf=total /2;
17+
18+
if(nums2Size<nums1Size)
19+
{
20+
A=nums2;
21+
B=nums1;
22+
ASize=nums2Size;
23+
BSize=nums1Size;
24+
}
25+
26+
intl=0;
27+
intr=ASize-1;
28+
29+
while(true)
30+
{
31+
inti=l+ ((r-l-2+1) /2);// A Mid, round down instead of rounding towards 0
32+
intj=half-i-2;// B Mid
33+
34+
35+
intAleft=i >=0 ?A[i] :INT_MIN;
36+
intAright= (i+1)<ASize ?A[i+1] :INT_MAX;
37+
intBleft=j >=0 ?B[j] :INT_MIN;
38+
intBright= (j+1)<BSize ?B[j+1] :INT_MAX;
39+
40+
// partition is correct
41+
if(Aleft <=Bright&&Bleft <=Aright)
42+
{
43+
// Odd
44+
if(total %2)
45+
{
46+
returnmin(Aright,Bright);
47+
}
48+
49+
// Even
50+
return (max(Aleft,Bleft)+min(Aright,Bright)) /2.0;
51+
}
52+
elseif(Aleft>Bright)
53+
{
54+
r=i-1;
55+
}
56+
else
57+
{
58+
l=i+1;
59+
}
60+
}
61+
62+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
// Time and space complexity is O(n) where n is the size of the input string.
2+
classSolution {
3+
public:
4+
stringremoveDuplicates(string s,int k) {
5+
stack<pair<char ,int>> st;
6+
7+
for(int i =0 ; i < s.size(); i++)
8+
{
9+
int count =1;
10+
if(!st.empty() && st.top().first == s[i])
11+
{
12+
count += st.top().second;
13+
st.pop();
14+
}
15+
16+
st.push({s[i] , count});
17+
18+
if(count == k) st.pop();
19+
20+
}
21+
22+
string ans ="";
23+
while(!st.empty())
24+
{
25+
int freq = st.top().second;
26+
int c = st.top().first;
27+
while(freq >0)
28+
{
29+
ans += c;
30+
freq--;
31+
}
32+
33+
st.pop();
34+
}
35+
36+
reverse(ans.begin() , ans.end());
37+
return ans;
38+
}
39+
};

‎cpp/14-4Sum.cpp‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
classSolution {
2+
public:
3+
vector<vector<int>> res;
4+
5+
vector<vector<int>>fourSum(vector<int>& nums,int target) {
6+
7+
if(nums.size() <4)return res;
8+
9+
vector<int>quad;
10+
sort(nums.begin() , nums.end());
11+
kSum(0,4,target,nums,quad);
12+
return res;
13+
}
14+
15+
16+
voidkSum (int index ,int k ,longlong target, vector<int> nums , vector<int>&q)
17+
{
18+
19+
if(k ==2)
20+
{
21+
twoSum(index , target, q , nums);
22+
return;
23+
}
24+
25+
for(int i = index ; i < nums.size() - k +1; i++)
26+
{
27+
if(i > index && nums[i] == nums[i-1])continue;
28+
q.push_back(nums[i]);
29+
kSum(i+1 , k-1 , target-nums[i] , nums , q);
30+
q.pop_back();
31+
}
32+
33+
}
34+
35+
voidtwoSum (int start,longlong target,vector<int>&ans,vector<int>& nums)
36+
{
37+
int lo = start;
38+
int hi = nums.size()-1;
39+
40+
while(lo < hi)
41+
{
42+
int sum = nums[lo]+nums[hi];
43+
if(sum > target) hi--;
44+
elseif (sum < target) lo++;
45+
46+
else
47+
{
48+
ans.insert(ans.end() , {nums[lo] , nums[hi]});
49+
res.push_back(ans);
50+
51+
ans.pop_back();
52+
ans.pop_back();
53+
54+
lo++;
55+
while (lo < hi && nums[lo] == nums[lo -1]) lo++;
56+
}
57+
}
58+
}
59+
};

‎cpp/338-Counting-Bits.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
Differ by 1 bit, by removing LSB: f(x) = f(x / 2) + (x mod 2)
88
99
Time: O(n)
10-
Space: O(n)
10+
Space: O(1), the output array does not count towards space
1111
*/
1212

1313
classSolution {

‎cpp/402-Remove-K-Digits.cpp‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// Time Complexity is O(N) where N is the size of the input string.
2+
// Space complexity is O(N) as well
3+
classSolution {
4+
public:
5+
stringremoveKdigits(string num,int k) {
6+
int n = num.size();
7+
8+
stack<char>s;
9+
int count = k;
10+
11+
for(int i =0 ; i < n; i++)
12+
{
13+
while(!s.empty() && count >0 && s.top() > num[i])
14+
{
15+
s.pop();
16+
count--;
17+
}
18+
s.push(num[i]);
19+
}
20+
21+
// In case the num was already in a non increasing order (e.x: 123456)
22+
while(s.size() != n - k) s.pop();
23+
24+
string res ="";
25+
while(!s.empty())
26+
{
27+
res += s.top();
28+
s.pop();
29+
}
30+
reverse(res.begin() , res.end());
31+
// Remove the zeros from the left if they exist.
32+
while (res[0] =='0') res.erase(0 ,1);
33+
34+
35+
return (res =="") ?"0": res;
36+
}
37+
};
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
// Time Complexity is O(N).
2+
// Space Complexity is O(1).
3+
4+
classSolution {
5+
public:
6+
ListNode*deleteDuplicates(ListNode* head) {
7+
ListNode * fast = head;
8+
ListNode * slow = head;
9+
10+
while(slow !=NULL)
11+
{
12+
while(fast !=NULL && slow->val == fast->val)
13+
fast = fast -> next;
14+
15+
slow->next = fast;
16+
slow = slow -> next;
17+
}
18+
19+
return head;
20+
21+
}
22+
};

‎cpp/neetcode_150/05_binary_search/search_a_2d_matrix.cpp‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,3 +47,41 @@ class Solution {
4747
returnfalse;
4848
}
4949
};
50+
51+
// Same approach with implicit array linearization
52+
// T(n) = O(log_2(mn)) = O(log_2(m) + log_2(n))
53+
classSolution {
54+
public:
55+
boolsearchMatrix(vector<vector<int>>& matrix,int target) {
56+
57+
int left =0;
58+
int m = matrix.size();
59+
int n = matrix[0].size();
60+
int right = m * n -1;
61+
62+
while (left <= right){
63+
64+
int middle = right + (left - right) /2;
65+
66+
// compute sub-indices using matrix structure
67+
int row = middle / n;
68+
int col = middle % n;
69+
70+
71+
//ordinary binary search
72+
int middle_x = matrix[row][col];
73+
if (target > middle_x){
74+
left = ++middle;
75+
}elseif (target < middle_x){
76+
right = --middle;
77+
}else {
78+
returntrue;
79+
}
80+
81+
82+
}
83+
84+
returnfalse;
85+
86+
}
87+
};

0 commit comments

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