Skip to content

Commit 30bf4bc

Browse files
lintcoderlintcoder
committed
15 problems solved.
1 parent 65fedc3 commit 30bf4bc

File tree

15 files changed

+342
-0
lines changed

15 files changed

+342
-0
lines changed

‎src/1.cpp

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
vector<int> twoSum(vector<int>& nums, int target) {
2+
int len = nums.size();
3+
struct Elem
4+
{
5+
int val;
6+
int pos;
7+
Elem(int v, int p):val(v), pos(p){}
8+
};
9+
auto cmp = [=](const Elem& a, const Elem& b) {
10+
return a.val < b.val;
11+
};
12+
auto binsearch = [=](const vector<Elem>& vec, int p, int q, int v) {
13+
while (p <= q)
14+
{
15+
int mid = (p + q) / 2;
16+
if (vec[mid].val == v)
17+
return vec[mid].pos;
18+
else if (vec[mid].val < v)
19+
p = mid + 1;
20+
else
21+
q = mid - 1;
22+
}
23+
return -1;
24+
};
25+
26+
vector<Elem> vec;
27+
for (int i = 0; i < len; ++i)
28+
vec.push_back(Elem(nums[i], i));
29+
30+
vector<int> res;
31+
sort(vec.begin(), vec.end(), cmp);
32+
int pos = 0;
33+
for (int i = 0; i < len; ++i)
34+
{
35+
if ((pos = binsearch(vec, i+1, len - 1, target - vec[i].val)) != -1)
36+
{
37+
res.push_back(vec[i].pos);
38+
res.push_back(pos);
39+
break;
40+
}
41+
}
42+
return res;
43+
}

‎src/110.cpp

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
bool isBalanced(TreeNode* root) {
2+
int depth = 0;
3+
return doisBalanced(root, depth);
4+
}
5+
6+
bool doisBalanced(TreeNode* node, int& depth)
7+
{
8+
if (node == NULL)
9+
return true;
10+
int depth1 = depth, depth2 = depth;
11+
if (!doisBalanced(node->left, depth1) || !doisBalanced(node->right, depth2) || abs(depth1 - depth2) > 1)
12+
return false;
13+
depth = depth1 > depth2 ? depth1 + 1 : depth2 + 1;
14+
return true;
15+
}

‎src/119.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
vector<int> getRow(int rowIndex) {
2+
if (rowIndex < 0)
3+
return vector<int>();
4+
vector<int> res[2];
5+
res[0].resize(rowIndex + 1);
6+
res[1].resize(rowIndex + 1);
7+
res[0][0] = res[0][rowIndex] = 1;
8+
9+
int i = 1;
10+
int pos = 0;
11+
while (i <= rowIndex)
12+
{
13+
pos = 1 - i % 2;
14+
res[pos][0] = 1;
15+
for (int j = 0; j < i - 1; ++j)
16+
res[pos][j + 1] = res[1 - pos][j] + res[1 - pos][j + 1];
17+
res[pos][i] = 1;
18+
++i;
19+
}
20+
return res[pos];
21+
}

‎src/198.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
int rob(vector<int>& nums) {
2+
int sz = nums.size();
3+
if (sz <= 0)
4+
return 0;
5+
vector<vector<int>> subsum(sz, vector<int>(sz, -1));
6+
return collectmoney(nums, 0, sz - 1, subsum);
7+
}
8+
9+
int collectmoney(const vector<int>& money, int p, int q, vector<vector<int>>& subsum)
10+
{
11+
if(subsum[p][q] != -1)
12+
return subsum[p][q];
13+
if (p == q - 1)
14+
{
15+
subsum[p][q] = money[p] > money[q] ? money[p] : money[q];
16+
}
17+
else if (p == q)
18+
{
19+
subsum[p][q] = money[p];
20+
}
21+
else
22+
{
23+
int sum1 = money[p] + collectmoney(money, p + 2, q, subsum);
24+
int sum2 = collectmoney(money, p + 1, q, subsum);
25+
subsum[p][q] = sum1 > sum2 ? sum1 : sum2;
26+
}
27+
28+
return subsum[p][q];
29+
}

‎src/232.cpp

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
class Queue {
2+
public:
3+
// Push element x to the back of queue.
4+
stack<int> first, second;
5+
void push(int x) {
6+
first.push(x);
7+
}
8+
9+
// Removes the element from in front of queue.
10+
void pop(void) {
11+
if (second.empty())
12+
{
13+
while (!first.empty())
14+
{
15+
second.push(first.top());
16+
first.pop();
17+
}
18+
}
19+
second.pop();
20+
}
21+
22+
// Get the front element.
23+
int peek(void) {
24+
if (second.empty())
25+
{
26+
while (!first.empty())
27+
{
28+
second.push(first.top());
29+
first.pop();
30+
}
31+
}
32+
return second.top();
33+
}
34+
35+
// Return whether the queue is empty.
36+
bool empty(void) {
37+
return first.empty() && second.empty();
38+
}
39+
};

‎src/263.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
bool isUgly(int num) {
2+
if (num <= 0)
3+
return false;
4+
if (num == 1)
5+
return true;
6+
else
7+
{
8+
while (num > 1)
9+
{
10+
if (num % 2 == 0)
11+
num /= 2;
12+
else if (num % 3 == 0)
13+
num /= 3;
14+
else if (num % 5 == 0)
15+
num /= 5;
16+
else
17+
return false;
18+
}
19+
return true;
20+
}
21+
}

‎src/342.cpp

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
bool isPowerOfFour(int num) {
2+
return (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
3+
}

‎src/345.cpp

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
string reverseVowels(string s) {
2+
int sz = s.size();
3+
int i = 0, j = sz - 1;
4+
while (i < j)
5+
{
6+
while (i < j && !isvowel(s[i]))
7+
++i;
8+
while (i < j && !isvowel(s[j]))
9+
--j;
10+
if (i < j)
11+
{
12+
char tmp = s[i];
13+
s[i] = s[j];
14+
s[j] = tmp;
15+
++i;
16+
--j;
17+
}
18+
}
19+
20+
return s;
21+
}
22+
23+
bool isvowel(char c)
24+
{
25+
c = tolower(c);
26+
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
27+
}

‎src/35.cpp

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
int searchInsert(vector<int>& nums, int target) {
2+
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
3+
}

‎src/367.cpp

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
bool isPerfectSquare(int num) {
2+
int i = 1, j = num;
3+
while (i <= j)
4+
{
5+
long long mid = i / 2 + j / 2 + (i % 2 && j % 2);
6+
long long res = mid * mid;
7+
if (res == num)
8+
return true;
9+
else if (res < num)
10+
i = mid + 1;
11+
else
12+
j = mid - 1;
13+
}
14+
return false;
15+
}

‎src/437.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
int pathSum(TreeNode* root, int sum) {
2+
if (root == NULL)
3+
return 0;
4+
vector<int> sum_vec;
5+
sum_vec.push_back(root->val);
6+
int total = root->val == sum ? 1 : 0;
7+
return total + dopathSum(root->left, sum_vec, sum) + dopathSum(root->right, sum_vec, sum);
8+
}
9+
10+
int dopathSum(TreeNode* node, const vector<int>& vec, int sum)
11+
{
12+
if (node == NULL)
13+
return 0;
14+
else
15+
{
16+
int total = 0;
17+
vector<int> sum_vec(vec);
18+
int len = sum_vec.size();
19+
for (int i = 0; i < len; ++i)
20+
{
21+
sum_vec[i] = sum_vec[i] + node->val;
22+
if (sum_vec[i] == sum)
23+
++total;
24+
}
25+
sum_vec.push_back(node->val);
26+
if (node->val == sum)
27+
++total;
28+
return total + dopathSum(node->left, sum_vec, sum) + dopathSum(node->right, sum_vec, sum);
29+
}
30+
}

‎src/572.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
bool isSubtree(TreeNode* s, TreeNode* t) {
2+
return doisSubtree(s, t, false);
3+
}
4+
5+
bool doisSubtree(TreeNode* s, TreeNode* t, bool status) {
6+
if (s == nullptr && t == nullptr)
7+
return true;
8+
else if (s == nullptr && t != nullptr)
9+
return false;
10+
else if (s != nullptr && t == nullptr)
11+
return false;
12+
else
13+
{
14+
bool flag = false;
15+
if (s->val == t->val)
16+
{
17+
flag = doisSubtree(s->left, t->left, true) && doisSubtree(s->right, t->right, true);
18+
if (flag)
19+
return true;
20+
}
21+
if (status)
22+
return false;
23+
if (doisSubtree(s->left, t, false))
24+
return true;
25+
else
26+
return doisSubtree(s->right, t, false);
27+
}
28+
}

‎src/645.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
vector<int> findErrorNums(vector<int>& nums) {
2+
vector<int> res(2, 0);
3+
int len = nums.size();
4+
if (len <= 1)
5+
return res;
6+
vector<int> flag(len, 1);
7+
for (int i = 0; i < len; ++i)
8+
{
9+
if (flag[nums[i] - 1] == 1)
10+
flag[nums[i] - 1] = 0;
11+
else
12+
res[0] = nums[i];
13+
}
14+
for (int i = 0; i < len; ++i)
15+
if (flag[i] == 1)
16+
{
17+
res[1] = i+1;
18+
break;
19+
}
20+
return res;
21+
}

‎src/66.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
vector<int> plusOne(vector<int>& digits) {
2+
int sz = digits.size();
3+
vector<int> res(sz + 1, 0);
4+
int cnt = 1;
5+
for (int i = sz - 1; i >= 0; --i)
6+
{
7+
if (cnt != 0)
8+
{
9+
int sum = digits[i] + cnt;
10+
res[i + 1] = sum % 10;
11+
cnt =sum / 10;
12+
}
13+
else
14+
res[i + 1] = digits[i];
15+
}
16+
res[0] = cnt;
17+
if (res[0] != 0)
18+
return res;
19+
else
20+
return vector<int>(res.begin() + 1, res.end());
21+
}

‎src/83.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
ListNode* deleteDuplicates(ListNode* head) {
2+
if (head == NULL || head->next == NULL)
3+
return head;
4+
ListNode* h = head;
5+
int key = h->val;
6+
ListNode* p = h->next;
7+
ListNode* q = h;
8+
while (p != NULL)
9+
{
10+
while (p != NULL && p->val == key)
11+
{
12+
ListNode* k = p->next;
13+
delete p;
14+
p = k;
15+
}
16+
q->next = p;
17+
q = p;
18+
if (p != NULL)
19+
{
20+
key = p->val;
21+
p = p->next;
22+
}
23+
}
24+
25+
return h;
26+
}

0 commit comments

Comments
 (0)