Skip to content

Commit 18d21d5

Browse files
lintcoderlintcoder
committed
1.15 problems solved.
1 parent 1235098 commit 18d21d5

File tree

15 files changed

+349
-0
lines changed

15 files changed

+349
-0
lines changed

‎src/107.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
vector<vector<int>> levelOrderBottom(TreeNode* root) {
2+
vector<vector<int>> res;
3+
if (root == NULL)
4+
return res;
5+
else
6+
{
7+
TreeNode* node = root;
8+
deque<TreeNode*> dq;
9+
dq.push_back(node);
10+
while (!dq.empty())
11+
{
12+
int len = dq.size();
13+
vector<int> vec;
14+
for (int i = 0; i < len; ++i)
15+
{
16+
TreeNode* t = dq.front();
17+
vec.push_back(t->val);
18+
if (t->left != NULL)
19+
dq.push_back(t->left);
20+
if (t->right != NULL)
21+
dq.push_back(t->right);
22+
dq.pop_front();
23+
}
24+
25+
res.push_back(vec);
26+
}
27+
reverse(res.begin(), res.end());
28+
return res;
29+
}
30+
}

‎src/121.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
int maxProfit(vector<int>& prices) {
2+
int len = prices.size();
3+
int max = 0;
4+
if (len >= 2)
5+
max = domaxProfit(prices, 0, len - 1);
6+
return max;
7+
}
8+
9+
int domaxProfit(vector<int>& prices, int p, int q)
10+
{
11+
if (p >= q - 1)
12+
return prices[q] > prices[p] ? prices[q] - prices[p] : 0;
13+
else
14+
{
15+
int mid = p / 2 + q / 2;
16+
int max1 = domaxProfit(prices, p, mid);
17+
int max2 = domaxProfit(prices, mid + 1, q);
18+
int submin = prices[p];
19+
int submax = 0;
20+
for (int i = p; i <= mid; ++i)
21+
if (prices[i] < submin)
22+
submin = prices[i];
23+
for (int i = mid + 1; i <= q; ++i)
24+
if (prices[i] > submax)
25+
submax = prices[i];
26+
int max3 = submax > submin ? submax - submin : 0;
27+
return max1 > max2 ? (max1 > max3 ? max1 : max3) : (max2 > max3 ? max2 : max3);
28+
}
29+
}

‎src/541.cpp

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
string reverseStr(string s, int k) {
2+
int len = s.size();
3+
int num = len / (2 * k);
4+
for (int i = 0; i < num; ++i)
5+
reverse(s.begin() + i * 2 * k, s.begin() + (2 * i + 1) * k);
6+
int remain = len % (2 * k);
7+
if (remain >= k)
8+
reverse(s.begin() + num * 2 * k, s.begin() + (num * 2 + 1) * k);
9+
else
10+
reverse(s.begin() + num * 2 * k, s.end());
11+
12+
return s;
13+
}

‎src/671.cpp

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
int findSecondMinimumValue(TreeNode* root) {
2+
if (root == nullptr)
3+
return -1;
4+
int val = root->val;
5+
if (root->left == nullptr)
6+
return -1;
7+
else
8+
{
9+
int min1 = root->left->val;
10+
int min2 = root->right->val;
11+
if (min1 == val && min2 != val)
12+
{
13+
min1 = findSecondMinimumValue(root->left);
14+
if (min1 == -1)
15+
return min2;
16+
else
17+
return min1 < min2 ? min1 : min2;
18+
}
19+
else if (min1 != val && min2 == val)
20+
{
21+
min2 = findSecondMinimumValue(root->right);
22+
if (min2 == -1)
23+
return min1;
24+
else
25+
return min1 < min2 ? min1 : min2;
26+
}
27+
else if (min1 != val && min2 != val)
28+
return min1 < min2 ? min1 : min2;
29+
else
30+
{
31+
min1 = findSecondMinimumValue(root->left);
32+
min2 = findSecondMinimumValue(root->right);
33+
34+
if (min1 == -1 && min2 == -1)
35+
return -1;
36+
else if (min1 == -1 && min2 != -1)
37+
return min2;
38+
else if (min1 != -1 && min2 == -1)
39+
return min1;
40+
else
41+
return min1 < min2 ? min1 : min2;
42+
}
43+
}
44+
}

‎src/674.cpp

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

‎src/717.cpp

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
bool isOneBitCharacter(vector<int>& bits) {
2+
int len = bits.size();
3+
int i = 0;
4+
while (i < len - 2)
5+
{
6+
if (bits[i] == 0)
7+
++i;
8+
else
9+
i += 2;
10+
}
11+
12+
return bits[i] != 1;
13+
}

‎src/728.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
vector<int> selfDividingNumbers(int left, int right) {
2+
vector<int> res;
3+
for (int i = left; i <= right; ++i)
4+
{
5+
if (isselfdivide(i))
6+
res.push_back(i);
7+
}
8+
9+
return res;
10+
}
11+
12+
bool isselfdivide(int num)
13+
{
14+
int n = num;
15+
while (n != 0)
16+
{
17+
int r = n % 10;
18+
if (r == 0 || num % r != 0)
19+
return false;
20+
n /= 10;
21+
}
22+
23+
return true;
24+
}

‎src/744.cpp

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
char nextGreatestLetter(vector<char>& letters, char target) {
2+
int len = letters.size();
3+
for (int i = 0; i < len; ++i)
4+
if (letters[i] > target)
5+
return letters[i];
6+
7+
return letters[0];
8+
}

‎src/766.cpp

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

‎src/771.cpp

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
int numJewelsInStones(string J, string S) {
2+
int len1 = J.size();
3+
int len2 = S.size();
4+
if (len1 == 0 || len2 == 0)
5+
return 0;
6+
set<char> jewels;
7+
for (int i = 0; i < len1; ++i)
8+
jewels.insert(J[i]);
9+
10+
int ct = 0;
11+
for (int i = 0; i < len2; ++i)
12+
if (jewels.find(S[i]) != jewels.end())
13+
++ct;
14+
15+
return ct;
16+
}

0 commit comments

Comments
 (0)