Skip to content

Commit 7c6b486

Browse files
lintcoderlintcoder
committed
1.12 problems solved.
1 parent f08eb01 commit 7c6b486

File tree

12 files changed

+290
-0
lines changed

12 files changed

+290
-0
lines changed

‎496.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
2+
vector<int> res;
3+
int lhs_len = findNums.size();
4+
int rhs_len = nums.size();
5+
6+
map<int, int> mp;
7+
for (int i = 0; i < rhs_len; ++i)
8+
mp[nums[i]] = i;
9+
for (int i = 0; i < lhs_len; ++i)
10+
{
11+
int pos = mp[findNums[i]];
12+
if (pos == rhs_len - 1)
13+
res.push_back(-1);
14+
else
15+
{
16+
int j = 0;
17+
for (j = pos + 1; j < rhs_len; ++j)
18+
if (nums[j] > findNums[i])
19+
{
20+
res.push_back(nums[j]);
21+
break;
22+
}
23+
if (j == rhs_len)
24+
res.push_back(-1);
25+
}
26+
}
27+
28+
return res;
29+
}

‎557.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
string reverseWords(string s) {
2+
size_t len = s.size();
3+
if (len == 0)
4+
return s;
5+
size_t i = 0;
6+
size_t pos = s.find(' ', i);
7+
while (pos != string::npos)
8+
{
9+
reverse_str(s, i, pos - 1);
10+
i = pos + 1;
11+
pos = s.find(' ', i);
12+
}
13+
reverse_str(s, i, len - 1);
14+
return s;
15+
}
16+
17+
void reverse_str(string& s, size_t start, size_t end)
18+
{
19+
size_t lim = (start + end)/2;
20+
for (size_t i = start; i <= lim; ++i)
21+
{
22+
swap(s[i], s[end--]);
23+
}
24+
}

‎561.cpp

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
int arrayPairSum(vector<int>& nums) {
2+
sort(nums.begin(), nums.end());
3+
int sz = nums.size();
4+
int sum = 0;
5+
for (int i = 0; i < sz; i += 2)
6+
sum += nums[i];
7+
return sum;
8+
}

‎566.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
2+
int row = nums.size();
3+
if (row == 0)
4+
return nums;
5+
int col = nums[0].size();
6+
if (row * col != r * c || (row == r && col == c))
7+
return nums;
8+
9+
vector<vector<int> > res;
10+
vector<int> rownum(c, 0);
11+
int m = 0, n = 0;
12+
for (int i = 0; i < r; ++i)
13+
{
14+
for (int j = 0; j < c; ++j)
15+
{
16+
if (n == col)
17+
{
18+
m++;
19+
n = 0;
20+
}
21+
rownum[j] = nums[m][n];
22+
n++;
23+
}
24+
res.push_back(rownum);
25+
}
26+
27+
return res;
28+
}

‎575.cpp

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
int distributeCandies(vector<int>& candies) {
2+
size_t sz = candies.size();
3+
if (sz == 0)
4+
return 0;
5+
6+
sort(candies.begin(), candies.end());
7+
size_t kind = 1, i = 1;
8+
int num = candies[0];
9+
while (i < sz)
10+
{
11+
if (candies[i] != num)
12+
{
13+
num = candies[i];
14+
kind++;
15+
}
16+
++i;
17+
}
18+
return kind <= sz/2 ? kind : sz/2;
19+
}

‎606.cpp

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
string tree2str(TreeNode* t) {
2+
if (t == nullptr)
3+
return string();
4+
string res(to_string(t->val));
5+
6+
if (t->left != nullptr)
7+
res += transfersubtree(t->left);
8+
if (t->right != nullptr)
9+
{
10+
if (t->left == nullptr)
11+
res += "()" + transfersubtree(t->right);
12+
else
13+
res += transfersubtree(t->right);
14+
}
15+
16+
return res;
17+
}
18+
19+
string transfersubtree(TreeNode* node)
20+
{
21+
string str = "(" + to_string(node->val);
22+
if (node->left != nullptr)
23+
str += transfersubtree(node->left);
24+
if (node->right != nullptr)
25+
{
26+
if (node->left == nullptr)
27+
str += "()" + transfersubtree(node->right);
28+
else
29+
str += transfersubtree(node->right);
30+
}
31+
str += ")";
32+
33+
return str;
34+
}

‎617.cpp

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
2+
if (t1 == nullptr)
3+
return t2;
4+
if (t2 == nullptr)
5+
return t1;
6+
TreeNode* node = new TreeNode(t1->val + t2->val);
7+
node->left = mergeTrees(t1->left, t2->left);
8+
node->right = mergeTrees(t1->right, t2->right);
9+
10+
return node;
11+
}

‎637.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
vector<double> averageOfLevels(TreeNode* root) {
2+
vector<double> res;
3+
if (root == nullptr)
4+
return res;
5+
deque<TreeNode*> dq;
6+
dq.push_back(root);
7+
8+
int sz = 0;
9+
while ((sz = dq.size()) != 0)
10+
{
11+
double sum = 0;
12+
for (int i = 0; i < sz; ++i)
13+
{
14+
TreeNode* node = dq[i];
15+
sum += node->val;
16+
if (node->left != nullptr)
17+
dq.push_back(node->left);
18+
if (node->right != nullptr)
19+
dq.push_back(node->right);
20+
}
21+
22+
dq.erase(dq.begin(), dq.begin() + sz);
23+
sum /= sz;
24+
res.push_back(sum);
25+
}
26+
27+
return res;
28+
}

‎653.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
bool findTarget(TreeNode* root, int k) {
2+
if (root == nullptr)
3+
return false;
4+
vector<int> elem;
5+
if (root->left != nullptr)
6+
getBSTValue(root->left, elem);
7+
elem.push_back(root->val);
8+
if (root->right != nullptr)
9+
getBSTValue(root->right, elem);
10+
11+
int len = elem.size();
12+
for (int i = 0; i < len; ++i)
13+
{
14+
if (elem[i] >= k - elem[i])
15+
break;
16+
if (binary_search(elem.begin() + i + 1, elem.end(), k - elem[i]))
17+
return true;
18+
}
19+
return false;
20+
}
21+
22+
void getBSTValue(TreeNode* node, vector<int>& vec)
23+
{
24+
if (node->left != nullptr)
25+
getBSTValue(node->left, vec);
26+
vec.push_back(node->val);
27+
if (node->right != nullptr)
28+
getBSTValue(node->right, vec);
29+
}

‎657.cpp

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
bool judgeCircle(string moves) {
2+
int right = 0, up = 0;
3+
int len = moves.size();
4+
if (len % 2 == 1)
5+
return false;
6+
7+
for (int i = 0; i < len; ++i)
8+
{
9+
if (moves[i] == 'R')
10+
right++;
11+
else if (moves[i] == 'L')
12+
right--;
13+
else if (moves[i] == 'U')
14+
up++;
15+
else
16+
up--;
17+
}
18+
19+
return right == 0 && up == 0;
20+
}

‎669.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
TreeNode* trimBST(TreeNode* root, int L, int R) {
2+
if (root == nullptr)
3+
return nullptr;
4+
int val = root->val;
5+
if (val < L)
6+
return trimBST(root->right, L, R);
7+
else if (val == L)
8+
{
9+
root->left = nullptr;
10+
root->right = trimBST(root->right, L, R);
11+
return root;
12+
}
13+
else if (val < R)
14+
{
15+
root->left = trimBST(root->left, L, R);
16+
root->right = trimBST(root->right, L, R);
17+
return root;
18+
}
19+
else if (val == R)
20+
{
21+
root->right = nullptr;
22+
root->left = trimBST(root->left, L, R);
23+
return root;
24+
}
25+
else
26+
{
27+
return trimBST(root->left, L, R);
28+
}
29+
}

‎682.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
int calPoints(vector<string>& ops) {
2+
int len = ops.size();
3+
vector<int> points(len, 0);
4+
5+
int sum = 0;
6+
int j = 0;
7+
for (int i = 0; i < len; ++i)
8+
{
9+
if (j > 0 && ops[i] == "C")
10+
{
11+
--j;
12+
}
13+
else if (j >= 1 && ops[i] == "D")
14+
{
15+
points[j] = points[j - 1]*2;
16+
++j;
17+
}
18+
else if (j >= 2 && ops[i] == "+")
19+
{
20+
points[j] = points[j - 2] + points[j - 1];
21+
++j;
22+
}
23+
else
24+
points[j++] = stoi(ops[i]);
25+
}
26+
27+
for (int i = 0; i < j; ++i)
28+
sum += points[i];
29+
30+
return sum;
31+
}

0 commit comments

Comments
 (0)