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

Commitae4ffb6

Browse files
committed
Merge remote-tracking branch 'origin' into asim/islands
2 parents2b7787f +6f46719 commitae4ffb6

File tree

50 files changed

+1233
-25
lines changed

Some content is hidden

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

50 files changed

+1233
-25
lines changed
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* struct TreeNode {
4+
* int val;
5+
* TreeNode *left;
6+
* TreeNode *right;
7+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
8+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10+
* };
11+
*/
12+
13+
classSolution {
14+
public:
15+
vector<vector<int>>levelOrder(TreeNode* root) {
16+
queue< TreeNode* > q;
17+
q.push(root);
18+
vector<vector<int>> v;
19+
vector<int> k;
20+
TreeNode* c;
21+
int j;
22+
while(!q.empty() )
23+
{
24+
k.clear();
25+
j=q.size();
26+
for(int i=0;i<j;i++)
27+
{
28+
c=q.front();
29+
q.pop();
30+
if(c)
31+
{
32+
k.push_back(c->val);
33+
q.push(c->left);
34+
q.push(c->right);
35+
}
36+
}
37+
if(!k.empty())
38+
v.push_back(k);
39+
40+
}
41+
return v;
42+
43+
}
44+
};
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
classSolution {
2+
public:
3+
intmaxArea(vector<int>& height) {
4+
int i=0,j=height.size()-1;
5+
int maxA=0,minh;
6+
while(i<j)
7+
{
8+
minh=min(height[i],height[j]);
9+
if(minh*(j-i)>maxA)
10+
maxA=minh*(j-i);
11+
if(minh==height[i])
12+
i++;
13+
else
14+
j--;
15+
}
16+
return maxA;
17+
}
18+
};

‎cpp/110-Balanced-Binary-Tree.cpp‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* struct TreeNode {
4+
* int val;
5+
* TreeNode *left;
6+
* TreeNode *right;
7+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
8+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10+
* };
11+
*/
12+
classSolution {
13+
public:
14+
15+
intgetHeight(TreeNode* root, unordered_map<TreeNode*,int>& umap) {
16+
if (root==NULL)return0;
17+
if (umap.find(root) != umap.end())return umap[root];
18+
int res =max(getHeight(root->left, umap),getHeight(root->right, umap))+1;
19+
umap[root] = res;
20+
return res;
21+
}
22+
boolisBalanced(TreeNode* root) {
23+
unordered_map<TreeNode*,int> umap;
24+
if (root ==NULL)returntrue;
25+
if (abs(getHeight(root->left, umap) -getHeight(root->right, umap)) >1)returnfalse;
26+
returnisBalanced(root->left) &&isBalanced(root->right);
27+
}
28+
};
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
classSolution {
2+
public:
3+
intlongestConsecutive(vector<int>& nums) {
4+
unordered_set<int> hs;
5+
for (int n : nums) {
6+
hs.insert(n);
7+
}
8+
9+
int longest =0;
10+
for (int n : nums) {
11+
// if n-1 is not in the set, the element can be the start of a sequence
12+
if (hs.find(n -1) == hs.end()) {
13+
int length =1;
14+
while (hs.find(n + length) != hs.end())
15+
++length;
16+
longest =max(longest, length);
17+
}
18+
}
19+
return longest;
20+
}
21+
};

‎cpp/136-Single-Number.cpp‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
// Time complexity : O(n)
2+
// Space complexity : O(1)
3+
4+
classSolution {
5+
public:
6+
intsingleNumber(vector<int>& nums) {
7+
int res =0;
8+
for(int num : nums){
9+
res^=num;
10+
}
11+
return res;
12+
}
13+
};

‎cpp/141-Linked-List-Cycle.cpp‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* struct ListNode {
4+
* int val;
5+
* ListNode *next;
6+
* ListNode(int x) : val(x), next(NULL) {}
7+
* };
8+
*/
9+
classSolution {
10+
public:
11+
boolhasCycle(ListNode *head) {
12+
if(!head)return0;
13+
unordered_set<ListNode*> s;
14+
s.insert(head);
15+
ListNode * ptr=head->next;
16+
while(ptr)
17+
{
18+
if(s.find(ptr)==s.end())
19+
{
20+
s.insert(ptr);
21+
ptr=ptr->next;
22+
}
23+
else
24+
return1;
25+
}
26+
return0;
27+
28+
}
29+
};

‎cpp/15-3Sum.cpp‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
classSolution {
2+
public:
3+
vector<vector<int>>threeSum(vector<int>& nums) {
4+
sort(nums.begin(), nums.end());
5+
vector<vector<int>> res;
6+
for (int i =0; i < nums.size(); ++i) {
7+
int a = nums[i];
8+
// triplet should not contain duplicate elements
9+
if (i >0 && a == nums[i -1])
10+
continue;
11+
// 2 ptr approach
12+
int l = i +1, r = nums.size() -1;
13+
while (l < r) {
14+
int threeSum = a + nums[l] + nums[r];
15+
if (threeSum >0)
16+
r -=1;
17+
elseif (threeSum <0)
18+
l +=1;
19+
else {
20+
// found triplet
21+
res.push_back({ a, nums[l], nums[r] });
22+
l +=1;
23+
// skip duplicates
24+
while (nums[l] == nums[l -1] && l < r)
25+
l +=1;
26+
}
27+
}
28+
}
29+
return res;
30+
}
31+
};

‎cpp/155-Min-Stack.cpp‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
usingnamespacestd;
2+
classMinStack {
3+
public:
4+
stack<pair<int,int>> stk;
5+
int m;
6+
7+
MinStack() {
8+
m = INT_MAX;
9+
}
10+
11+
voidpush(int val) {
12+
stk.push({val,min(val, stk.empty()?INT_MAX:stk.top().second)});
13+
}
14+
15+
voidpop() {
16+
if(!stk.empty()) stk.pop();
17+
}
18+
19+
inttop() {
20+
return stk.top().first;
21+
}
22+
23+
intgetMin() {
24+
return stk.top().second;
25+
}
26+
};
27+
28+
/**
29+
* Your MinStack object will be instantiated and called as such:
30+
* MinStack* obj = new MinStack();
31+
* obj->push(val);
32+
* obj->pop();
33+
* int param_3 = obj->top();
34+
* int param_4 = obj->getMin();
35+
*/

‎cpp/202-Happy-Number.cpp‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/*
2+
Time Complexity: O(log n)
3+
Space Complexity: O(log n)
4+
*/
5+
6+
classSolution {
7+
public:
8+
boolisHappy(int n) {
9+
unordered_set<int> us;
10+
while (us.find(n) == us.end()) {
11+
us.insert(n);
12+
int temp =0;
13+
while (n >0) {
14+
int digit = n %10;
15+
digit = digit * digit;
16+
temp += digit;
17+
n = n /10;
18+
}
19+
n = temp;
20+
if (n ==1) {
21+
returntrue;
22+
}
23+
}
24+
returnfalse;
25+
}
26+
};
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
classSolution {
2+
public:
3+
vector<int>productExceptSelf(vector<int>& nums) {
4+
int n = nums.size();
5+
vector<int>res(n);
6+
7+
// compute with prefix
8+
int prefix =1;
9+
for (int i =0; i < n; ++i) {
10+
res[i] = prefix;
11+
prefix *= nums[i];
12+
}
13+
// compute with posfix
14+
int postfix =1;
15+
for (int i = n-1; i >=0; --i) {
16+
res[i] *= postfix;
17+
postfix *= nums[i];
18+
}
19+
return res;
20+
}
21+
};

0 commit comments

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