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+
}

‎src/784.cpp

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
vector<string> letterCasePermutation(string S) {
2+
vector<string> res;
3+
vector<int> letterpos;
4+
5+
int len = S.size();
6+
int ct = 0;
7+
for (int i = 0; i < len; ++i)
8+
{
9+
if (isalpha(S[i]))
10+
{
11+
letterpos.push_back(i);
12+
++ct;
13+
}
14+
}
15+
if (ct == 0)
16+
{
17+
res.push_back(S);
18+
return res;
19+
}
20+
21+
doPermutation(S, 1, ct, letterpos, res);
22+
23+
return res;
24+
}
25+
26+
void doPermutation(string& S, int n, int ct, const vector<int>& pos, vector<string>& res)
27+
{
28+
if (n == ct)
29+
{
30+
res.push_back(S);
31+
if (islower(S[pos[n-1]]))
32+
S[pos[n-1]] = toupper(S[pos[n-1]]);
33+
else
34+
S[pos[n-1]] = tolower(S[pos[n-1]]);
35+
res.push_back(S);
36+
}
37+
else
38+
{
39+
doPermutation(S, n+1, ct, pos, res);
40+
if (islower(S[pos[n-1]]))
41+
S[pos[n-1]] = toupper(S[pos[n-1]]);
42+
else
43+
S[pos[n-1]] = tolower(S[pos[n-1]]);
44+
doPermutation(S, n+1, ct, pos, res);
45+
}
46+
}

‎src/796.cpp

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
bool rotateString(string A, string B) {
2+
int lenA = A.size();
3+
int lenB = B.size();
4+
if (lenA != lenB)
5+
return false;
6+
if (lenA == 0 && lenB == 0)
7+
return true;
8+
int index = 0;
9+
while (index < lenA && (index = B.find(A[0], index)) != string::npos)
10+
{
11+
if (A.substr(0, lenB - index) == B.substr(index) && A.substr(lenB-index) == B.substr(0, index))
12+
return true;
13+
index++;
14+
}
15+
return false;
16+
}

‎src/804.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
int uniqueMorseRepresentations(vector<string>& words) {
2+
const string morsecode[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",
3+
".---","-.-",".-..","--","-.","---",".--.","--.-",
4+
".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
5+
set<string> transformations;
6+
int len = words.size();
7+
for (int i = 0; i < len; ++i)
8+
{
9+
string trans;
10+
int sz = words[i].size();
11+
for (int j = 0; j < sz; ++j)
12+
trans += morsecode[words[i][j]-'a'];
13+
transformations.insert(trans);
14+
}
15+
16+
return transformations.size();
17+
}

‎src/806.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
vector<int> numberOfLines(vector<int>& widths, string S) {
2+
int len = S.size();
3+
int line = 1, sz = 0;
4+
for (int i = 0; i < len; ++i)
5+
{
6+
int n = widths[S[i]-'a'];
7+
if (sz + n <= 100)
8+
sz += n;
9+
else
10+
{
11+
line++;
12+
sz = n;
13+
}
14+
}
15+
16+
return {line, sz};
17+
}

‎src/811.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
vector<string> subdomainVisits(vector<string>& cpdomains) {
2+
int sz = cpdomains.size();
3+
map<string, int> mp;
4+
vector<string> res;
5+
6+
for (int i = 0; i < sz; ++i)
7+
{
8+
abstractdomains(cpdomains[i], mp);
9+
}
10+
11+
for (auto iter : mp)
12+
res.push_back(to_string(iter.second) + " " + iter.first);
13+
14+
return res;
15+
}
16+
17+
void abstractdomains(const string& cpdomain, map<string, int>& mp)
18+
{
19+
int index = cpdomain.find(' ');
20+
int ct = stoi(cpdomain.substr(0, index));
21+
mp[cpdomain.substr(index+1)] += ct;
22+
while ((index = cpdomain.find('.', index+1)) != string::npos)
23+
{
24+
mp[cpdomain.substr(index+1)] += ct;
25+
}
26+
}

0 commit comments

Comments
 (0)