10000 :rocket: 04-Oct-2020 · codezoned/Code@0b6e224 · GitHub
[go: up one dir, main page]
Skip to content

Commit 0b6e224

Browse files
sureshmangssureshmangs
committed
🚀 04-Oct-2020
1 parent 566ff5e commit 0b6e224

File tree

4 files changed

+324
-0
lines changed

4 files changed

+324
-0
lines changed

‎competitive programming/leetcode/1608. Special Array With X Elements Greater Than or Equal X.cpp

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.
2+
3+
Notice that x does not have to be an element in nums.
4+
5+
Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.
6+
7+
8+
9+
Example 1:
10+
11+
Input: nums = [3,5]
12+
Output: 2
13+
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.
14+
Example 2:
15+
16+
Input: nums = [0,0]
17+
Output: -1
18+
Explanation: No numbers fit the criteria for x.
19+
If x = 0, there should be 0 numbers >= x, but there are 2.
20+
If x = 1, there should be 1 number >= x, but there are 0.
21+
If x = 2, there should be 2 numbers >= x, but there are 0.
22+
x cannot be greater since there are only 2 numbers in nums.
23+
Example 3:
24+
25+
Input: nums = [0,4,3,0,4]
26+
Output: 3
27+
Explanation: There are 3 values that are greater than or equal to 3.
28+
Example 4:
29+
30+
Input: nums = [3,6,7,7,0]
31+
Output: -1
32+
33+
34+
Constraints:
35+
36+
1 <= nums.length <= 100
37+
0 <= nums[i] <= 1000
38+
39+
40+
41+
42+
43+
44+
45+
class Solution {
46+
public:
47+
int specialArray(vector<int>& nums) {
48+
int res=0;
49+
int n=nums.size();
50+
51+
int maxi= *max_element(nums.begin(), nums.end());
52+
53+
for(int i=0;i<=maxi;i++){
54+
int cnt=0;
55+
for(int j=0;j<n;j++){
56+
if(nums[j]>=res)
57+
cnt++;
58+
}
59+
if(cnt==res) return res;
60+
res++;
61+
}
62+
63+
return -1;
64+
}
65+
};

‎competitive programming/leetcode/1609. Even Odd Tree.cpp

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
1+
A binary tree is named Even-Odd if it meets the following conditions:
2+
3+
The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
4+
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
5+
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).
6+
Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.
7+
8+
9+
10+
Example 1:
11+
12+
13+
14+
Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
15+
Output: true
16+
Explanation: The node values on each level are:
17+
Level 0: [1]
18+
Level 1: [10,4]
19+
Level 2: [3,7,9]
20+
Level 3: [12,8,6,2]
21+
Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.
22+
Example 2:
23+
24+
25+
26+
Input: root = [5,4,2,3,3,7]
27+
Output: false
28+
Explanation: The node values on each level are:
29+
Level 0: [5]
30+
Level 1: [4,2]
31+
Level 2: [3,3,7]
32+
Node values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.
33+
Example 3:
34+
35+
36+
37+
Input: root = [5,9,1,3,5,7]
38+
Output: false
39+
Explanation: Node values in the level 1 should be even integers.
40+
Example 4:
41+
42+
Input: root = [1]
43+
Output: true
44+
Example 5:
45+
46+
Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
47+
Output: true
48+
49+
50+
Constraints:
51+
52+
The number of nodes in the tree is in the range [1, 105].
53+
1 <= Node.val <= 106
54+
55+
56+
57+
58+
59+
60+
/**
61+
* Definition for a binary tree node.
62+
* struct TreeNode {
63+
* int val;
64+
* TreeNode *left;
65+
* TreeNode *right;
66+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
67+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
68+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
69+
* };
70+
*/
71+
class Solution {
72+
public:
73+
74+
75+
bool check(vector<TreeNode*> v, int index){
76+
int n=v.size();
77+
78+
//for(int i=0;i<n;i++) cout<<v[i]->val<<" "; cout<<endl;
79+
80+
81+
if(index%2==0){
82+
if(v[0]->val%2==0 || v[n-1]->val%2==0) return false;
83+
for(int i=0;i<n-1;i++){
84+
if(v[i]->val%2==0 || v[i]->val>=v[i+1]->val) return false;
85+
}
86+
} else {
87+
if(v[0]->val%2!=0 || v[n-1]->val%2!=0) return false;
88+
for(int i=0;i<n-1;i++){
89+
if(v[i]->val%2!=0 || v[i]->val<=v[i+1]->val) return false;
90+
}
91+
}
92+
93+
return true;
94+
}
95+
96+
97+
bool isEvenOddTree(TreeNode* root) {
98+
queue<TreeNode*> q;
99+
100+
q.push(root);
101+
102+
int index=0;
103+
104+
while(!q.empty()){
105+
int size=q.size();
106+
107+
108+
vector<TreeNode*>v;
109+
while(!q.empty()){
110+
v.push_back(q.front());
111+
q.pop();
112+
}
113+
114+
for(auto &x: v) q.push(x);
115+
116+
if(!check(v, index)) return false;
117+
118+
while(size--){
119+
TreeNode *curr=q.front();
120+
if(curr->left) q.push(curr->left);
121+
if(curr->right) q.push(curr->right);
122+
q.pop();
123+
}
124+
index++;
125+
}
126+
127+
return true;
128+
}
129+
};

‎competitive programming/leetcode/2020-October-Challenge/Day-03-K-diff Pairs in an Array.cpp

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
2+
3+
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
4+
5+
0 <= i, j < nums.length
6+
i != j
7+
a <= b
8+
b - a == k
9+
10+
11+
Example 1:
12+
13+
Input: nums = [3,1,4,1,5], k = 2
14+
Output: 2
15+
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
16+
Although we have two 1s in the input, we should only return the number of unique pairs.
17+
Example 2:
18+
19+
Input: nums = [1,2,3,4,5], k = 1
20+
Output: 4
21+
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
22+
Example 3:
23+
24+
Input: nums = [1,3,1,5,4], k = 0
25+
Output: 1
26+
Explanation: There is one 0-diff pair in the array, (1, 1).
27+
Example 4:
28+
29+
Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
30+
Output: 2
31+
Example 5:
32+
33+
Input: nums = [-1,-2,-3], k = 1
34+
Output: 2
35+
36+
37+
Constraints:
38+
39+
1 <= nums.length <= 104
40+
-107 <= nums[i] <= 107
41+
0 <= k <= 107
42+
43+
44+
45+
46+
47+
48+
class Solution {
49+
public:
50+
int findPairs(vector<int>& nums, int k) {
51+
int cnt=0;
52+
set<pair<int, int> > s;
53+
int n=nums.size();
54+
sort(nums.begin(), nums.end());
55+
56+
for(int i=0;i<n;i++){
57+
for(int j=i+1;j<n;j++){
58+
if(nums[i]<=nums[j] && nums[j]-nums[i]==k)
59+
s.insert({nums[i], nums[j]});
60+
}
61+
}
62+
63+
return s.size();
64+
}
65+
};

‎competitive programming/leetcode/532. K-diff Pairs in an Array.cpp

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
2+
3+
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
4+
5+
0 <= i, j < nums.length
6+
i != j
7+
a <= b
8+
b - a == k
9+
10+
11+
Example 1:
12+
13+
Input: nums = [3,1,4,1,5], k = 2
14+
Output: 2
15+
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
16+
Although we have two 1s in the input, we should only return the number of unique pairs.
17+
Example 2:
18+
19+
Input: nums = [1,2,3,4,5], k = 1
20+
Output: 4
21+
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
22+
Example 3:
23+
24+
Input: nums = [1,3,1,5,4], k = 0
25+
Output: 1
26+
Explanation: There is one 0-diff pair in the array, (1, 1).
27+
Example 4:
28+
29+
Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
30+
Output: 2
31+
Example 5:
32+
33+
Input: nums = [-1,-2,-3], k = 1
34+
Output: 2
35+
36+
37+
Constraints:
38+
39+
1 <= nums.length <= 104
40+
-107 <= nums[i] <= 107
41+
0 <= k <= 107
42+
43+
44+
45+
46+
47+
48+
class Solution {
49+
public:
50+
int findPairs(vector<int>& nums, int k) {
51+
int cnt=0;
52+
set<pair<int, int> > s;
53+
int n=nums.size();
54+
sort(nums.begin(), nums.end());
55+
56+
for(int i=0;i<n;i++){
57+
for(int j=i+1;j<n;j++){
58+
if(nums[i]<=nums[j] && nums[j]-nums[i]==k)
59+
s.insert({nums[i], nums[j]});
60+
}
61+
}
62+
63+
return s.size();
64+
}
65+
};

0 commit comments

Comments
 (0)
0