Skip to content

Commit 48b3bda

Browse files
lintcoderlintcoder
committed
12 problems solved.
1 parent bd6f213 commit 48b3bda

File tree

12 files changed

+478
-0
lines changed

12 files changed

+478
-0
lines changed

‎src/101.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
bool isSymmetric(TreeNode* root) {
2+
if (root == NULL)
3+
return true;
4+
5+
return doisSymmetric(root->left, root->right);
6+
}
7+
8+
bool doisSymmetric(TreeNode* ln, TreeNode* rn)
9+
{
10+
if (ln == NULL && rn == NULL)
11+
return true;
12+
else if (ln != NULL && rn != NULL)
13+
{
14+
return ln->val == rn->val && doisSymmetric(ln->left, rn->right) && doisSymmetric(ln->right, rn->left);
15+
}
16+
else
17+
return false;
18+
}

‎src/118.cpp

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

‎src/191.cpp

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
int hammingWeight(uint32_t n) {
2+
bitset<32> bt(n);
3+
int sum = 0;
4+
for (int i = 0; i < 32; ++i)
5+
if (bt[i] == 1)
6+
sum++;
7+
8+
return sum;
9+
}

‎src/628.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
int maximumProduct(vector<int>& nums) {
2+
int len = nums.size();
3+
if (len == 3)
4+
return nums[0]*nums[1]*nums[2];
5+
6+
sort(nums.begin(), nums.end());
7+
if (nums[len-1] == 0)
8+
return 0;
9+
else if (nums[len-1] < 0)
10+
return nums[0]*nums[1]*nums[2];
11+
else
12+
{
13+
int p1 = nums[len-1]*nums[len-2]*nums[len-3];
14+
int p2 = 0;
15+
auto iter = lower_bound(nums.begin(), nums.end(), 0);
16+
if (iter - nums.begin() >= 2)
17+
p2 = nums[len-1]*nums[0]*nums[1];
18+
if (p1 > p2)
19+
return p1;
20+
else
21+
return p2;
22+
}
23+
}

‎src/661.cpp

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
2+
int row = M.size();
3+
if (row == 0)
4+
return M;
5+
int col = M[0].size();
6+
7+
vector<vector<int>> res(row, vector<int>(col, 0));
8+
for (int i = 0; i < row; ++i)
9+
{
10+
for (int j = 0; j < col; ++j)
11+
{
12+
int sum = M[i][j];
13+
int ct = 1;
14+
if (i > 0 && j > 0)
15+
{
16+
sum += M[i-1][j-1];
17+
ct++;
18+
}
19+
if (i > 0)
20+
{
21+
sum += M[i-1][j];
22+
ct++;
23+
}
24+
if (i > 0 && j < col-1)
25+
{
26+
sum += M[i-1][j+1];
27+
ct++;
28+
}
29+
if (j > 0)
30+
{
31+
sum += M[i][j-1];
32+
ct++;
33+
}
34+
if (j < col-1)
35+
{
36+
sum += M[i][j+1];
37+
ct++;
38+
}
39+
if (i < row-1 && j > 0)
40+
{
41+
sum += M[i+1][j-1];
42+
ct++;
43+
}
44+
if (i < row-1)
45+
{
46+
sum += M[i+1][j];
47+
ct++;
48+
}
49+
if (i < row-1 && j < col-1)
50+
{
51+
sum += M[i+1][j+1];
52+
ct++;
53+
}
54+
res[i][j] = sum/ct;
55+
}
56+
}
57+
58+
return res;
59+
}

‎src/788.cpp

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
const int nogood[10] = {1, 2, 3, 3, 3, 4, 5, 5, 6, 7};
2+
const int good[10] = {4, 4, 7, 0, 0, 7, 7, 0, 4, 7};
3+
const int flag[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
4+
int rotatedDigits(int N) {
5+
int n = 0, num = N;
6+
while (num > 0)
7+
{
8+
num /= 10;
9+
++n;
10+
}
11+
int ct = 0;
12+
if (n == 1)
13+
return count1(N);
14+
else if (n == 2)
15+
return count2(N);
16+
else if (n == 3)
17+
return count3(N);
18+
else if (n == 4)
19+
return count4(N);
20+
else
21+
return count4(9999);
22+
}
23+
24+
int count1(int n)
25+
{
26+
if (n < 2)
27+
return 0;
28+
else if (n < 5)
29+
return 1;
30+
else if (n < 6)
31+
return 2;
32+
else if (n < 9)
33+
return 3;
34+
else
35+
return 4;
36+
}
37+
38+
int count2(int n)
39+
{
40+
int digit = n/10;
41+
int ct = 0;
42+
for (int i = 0; i < digit; ++i)
43+
ct += good[i];
44+
if (flag[digit] == 0)
45+
ct += count1(n%10);
46+
else if (flag[digit] == 1)
47+
ct += nogood[n%10];
48+
return ct;
49+
}
50+
51+
int count3(int n)
52+
{
53+
int digit = n/100;
54+
int ct = 0;
55+
for (int i = 0; i < digit; ++i)
56+
{
57+
if (flag[i] == 0)
58+
ct += 40;
59+
else if (flag[i] == 1)
60+
ct += 49;
61+
}
62+
if (flag[digit] == 0)
63+
ct += count2(n%100);
64+
else if (flag[digit] == 1)
65+
{
66+
for (int i = 0; i < n%100/10; ++i)
67+
if (flag[i] != -1)
68+
ct += 7;
69+
digit = n%100/10;
70+
if (flag[digit] != -1)
71+
ct += nogood[n%10];
72+
}
73+
return ct;
74+
}
75+
76+
int count4(int n)
77+
{
78+
int digit = n/1000;
79+
int ct = 0;
80+
int tmp = count3(999);
81+
for (int i = 0; i < digit; ++i)
82+
{
83+
if (flag[i] == 0)
84+
ct += tmp;
85+
else if (flag[i] == 1)
86+
ct += 343;
87+
}
88+
if (flag[digit] == 0)
89+
ct += count3(n%1000);
90+
else if (flag[digit] == 1)
91+
{
92+
digit = n%1000/100;
93+
for (int i = 0; i < digit; ++i)
94+
if (flag[i] != -1)
95+
ct += 49;
96+
if (flag[digit] != -1)
97+
{
98+
digit = n%100/10;
99+
for (int i = 0; i < digit; ++i)
100+
if (flag[i] != -1)
101+
ct += 7;
102+
if (flag[digit] != -1)
103+
ct += nogood[n%10];
104+
}
105+
}
106+
107+
return ct;
108+
}

‎src/819.cpp

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
string mostCommonWord(string paragraph, vector<string>& banned) {
2+
int len = paragraph.size();
3+
if (len == 0)
4+
return "";
5+
int num = banned.size();
6+
7+
const char* exclude = " !?',;.";
8+
map<string, int> mp;
9+
10+
int index = paragraph.find_first_not_of(exclude);
11+
if (index == string::npos)
12+
return "";
13+
14+
bool flag = false;
15+
while (index != string::npos && index < len)
16+
{
17+
int pos = paragraph.find_first_of(exclude, index);
18+
if (pos == string::npos)
19+
{
20+
flag = true;
21+
break;
22+
}
23+
24+
string s = paragraph.substr(index, pos - index);
25+
transform(s.begin(), s.end(), s.begin(), ::tolower);
26+
if (find(banned.begin(), banned.end(), s) == banned.end())
27+
mp[s]++;
28+
if (pos == len - 1)
29+
break;
30+
index = paragraph.find_first_not_of(exclude, pos+1);
31+
}
32+
if (flag)
33+
{
34+
string s = paragraph.substr(index);
35+
transform(s.begin(), s.end(), s.begin(), ::tolower);
36+
if (find(banned.begin(), banned.end(), s) == banned.end())
37+
mp[s]++;
38+
}
39+
40+
string res;
41+
int maxnum = 0;
42+
for (auto m : mp)
43+
{
44+
if (m.second > maxnum)
45+
{
46+
maxnum = m.second;
47+
res = m.first;
48+
}
49+
}
50+
51+
return res;
52+
}

‎src/821.cpp

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
vector<int> shortestToChar(string S, char C) {
2+
vector<int> res;
3+
vector<int> pos;
4+
int len = S.size();
5+
int ct = 0;
6+
for (int i = 0; i < len; ++i)
7+
{
8+
if (S[i] == C)
9+
{
10+
pos.push_back(i);
11+
ct++;
12+
}
13+
}
14+
15+
int i = 0;
16+
int j = 0;
17+
while (i < len)
18+
{
19+
if (S[i] == C)
20+
{
21+
res.push_back(0);
22+
++j;
23+
}
24+
else if (j == 0)
25+
{
26+
res.push_back(pos[j]-i);
27+
}
28+
else if (j < ct)
29+
{
30+
int p = pos[j]-i < i - pos[j-1] ? pos[j] - i : i - pos[j-1];
31+
res.push_back(p);
32+
}
33+
else
34+
res.push_back(i - pos[j-1]);
35+
++i;
36+
}
37+
38+
return res;
39+
}

‎src/824.cpp

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
string toGoatLatin(string S) {
2+
int len = S.size();
3+
if (len == 0)
4+
return S;
5+
6+
string res;
7+
int i = 0, j = 1;
8+
int pos = 0;
9+
while ((pos = S.find(' ', i)) != string::npos)
10+
{
11+
string str = S.substr(i, pos-i);
12+
if (isvowel(str[0]))
13+
res += str + "ma" + string(j, 'a') + ' ';
14+
else
15+
res += str.substr(1) + str[0] + "ma" + string(j, 'a') + ' ';
16+
++j;
17+
i = pos+1;
18+
}
19+
string str = S.substr(i);
20+
if (isvowel(str[0]))
21+
res += str + "ma" + string(j, 'a');
22+
else
23+
res += str.substr(1) + str[0] + "ma" + string(j, 'a');
24+
25+
return res;
26+
}
27+
28+
bool isvowel(char c)
29+
{
30+
c = tolower(c);
31+
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
32+
}

0 commit comments

Comments
 (0)