Skip to content

Commit b1d3705

Browse files
lintcoderlintcoder
committed
8 problems solved.
1 parent bb25592 commit b1d3705

File tree

8 files changed

+235
-0
lines changed

8 files changed

+235
-0
lines changed

‎src/102.cpp

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

‎src/112.cpp

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
bool hasPathSum(TreeNode* root, int sum) {
2+
if (root == NULL)
3+
return false;
4+
return dohasPathSum(root, 0, sum);
5+
}
6+
7+
bool dohasPathSum(TreeNode* node, int subsum, int sum)
8+
{
9+
int val = node->val;
10+
TreeNode* lnode = node->left;
11+
TreeNode* rnode = node->right;
12+
bool flag = false;
13+
if (lnode == NULL && rnode == NULL)
14+
return subsum + val == sum;
15+
else if (lnode != NULL)
16+
flag = dohasPathSum(lnode, subsum + val, sum);
17+
if (!flag && rnode != NULL)
18+
flag = dohasPathSum(rnode, subsum + val, sum);
19+
return flag;
20+
}

‎src/141.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
bool hasCycle(ListNode *head) {
2+
ListNode* p = head;
3+
ListNode* q = head;
4+
while (p != NULL)
5+
{
6+
p = p->next;
7+
if (p == NULL)
8+
return false;
9+
if (p == q || p->next == q)
10+
return true;
11+
p = p->next;
12+
q = q->next;
13+
if (p == q)
14+
return true;
15+
}
16+
17+
return false;
18+
}

‎src/328.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
ListNode* oddEvenList(ListNode* head) {
2+
if (head == nullptr || head->next == nullptr)
3+
return head;
4+
5+
ListNode* hodd = head;
6+
ListNode* heven = head->next;
7+
ListNode* p = hodd, *q = heven;
8+
9+
while (q != nullptr && q->next != nullptr)
10+
{
11+
p->next = q->next;
12+
if (q->next == nullptr)
13+
break;
14+
else
15+
{
16+
p = q->next;
17+
q->next = p->next;
18+
q = p->next;
19+
}
20+
}
21+
22+
p->next = heven;
23+
return hodd;
24+
}

‎src/392.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
bool isSubsequence(string s, string t) {
2+
int len1 = s.size();
3+
int len2 = t.size();
4+
if (len1 > len2)
5+
return false;
6+
else if (len1 == len2)
7+
return s == t;
8+
else
9+
{
10+
int index = 0;
11+
int pos = 0;
12+
for (int i = 0; i < len1; ++i)
13+
{
14+
if (index == len2)
15+
return false;
16+
pos = t.find(s[i], index);
17+
if (pos == string::npos)
18+
return false;
19+
index = pos + 1;
20+
}
21+
22+
return true;
23+
}
24+
}

‎src/423.cpp

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
string originalDigits(string s) {
2+
int letters[26] = {0};
3+
int len = s.size();
4+
for (int i = 0; i < len; ++i)
5+
letters[s[i] - 'a']++;
6+
string res;
7+
8+
if (letters['z' - 'a'] != 0)
9+
{
10+
letters['e' - 'a'] -= letters['z' - 'a'];
11+
letters['r' - 'a'] -= letters['z' - 'a'];
12+
letters['o' - 'a'] -= letters['z' - 'a'];
13+
len -= 4*letters['z' - 'a'];
14+
res = string(letters['z' - 'a'], '0');
15+
letters['z' - 'a'] = 0;
16+
}
17+
if (letters['w' - 'a'] != 0)
18+
{
19+
letters['t' - 'a'] -= letters['w' - 'a'];
20+
letters['o' - 'a'] -= letters['w' - 'a'];
21+
len -= 3*letters['w' - 'a'];
22+
res += string(letters['w' - 'a'], '2');
23+
letters['w' - 'a'] = 0;
24+
}
25+
if (letters['u' - 'a'] != 0)
26+
{
27+
letters['f' - 'a'] -= letters['u' - 'a'];
28+
letters['o' - 'a'] -= letters['u' - 'a'];
29+
letters['r' - 'a'] -= letters['u' - 'a'];
30+
len -= 4*letters['u' - 'a'];
31+
res += string(letters['u' - 'a'], '4');
32+
letters['u' - 'a'] = 0;
33+
}
34+
if (letters['x' - 'a'] != 0)
35+
{
36+
letters['s' - 'a'] -= letters['x' - 'a'];
37+
letters['i' - 'a'] -= letters['x' - 'a'];
38+
len -= 3*letters['x' - 'a'];
39+
res += string(letters['x' - 'a'], '6');
40+
letters['x' - 'a'] = 0;
41+
}
42+
if (letters['g' - 'a'] != 0)
43+
{
44+
letters['e' - 'a'] -= letters['g' - 'a'];
45+
letters['i' - 'a'] -= letters['g' - 'a'];
46+
letters['h' - 'a'] -= letters['g' - 'a'];
47+
letters['t' - 'a'] -= letters['g' - 'a'];
48+
len -= 5*letters['g' - 'a'];
49+
res += string(letters['g' - 'a'], '8');
50+
letters['g' - 'a'] = 0;
51+
}
52+
if (letters['o' - 'a'] != 0)
53+
{
54+
res += string(letters['o' - 'a'], '1');
55+
}
56+
if (letters['t' - 'a'] != 0)
57+
{
58+
res += string(letters['t' - 'a'], '3');
59+
}
60+
if (letters['f' - 'a'] != 0)
61+
{
62+
letters['i' - 'a'] -= letters['f' - 'a'];
63+
letters['v' - 'a'] -= letters['f' - 'a'];
64+
letters['e' - 'a'] -= letters['f' - 'a'];
65+
len -= 4*letters['f' - 'a'];
66+
res += string(letters['f' - 'a'], '5');
67+
letters['f' - 'a'] = 0;
68+
}
69+
if (letters['s' - 'a'] != 0)
70+
{
71+
res += string(letters['s' - 'a'], '7');
72+
}
73+
if (letters['i' - 'a'] != 0)
74+
{
75+
res += string(letters['i' - 'a'], '9');
76+
}
77+
sort(res.begin(), res.end());
78+
79+
return res;
80+
}

‎src/441.cpp

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
int arrangeCoins(int n) {
2+
if (n <= 0)
3+
return 0;
4+
int lim = sqrt(2) * sqrt(n) - 1;
5+
int num = 0;
6+
if (lim % 2 == 1)
7+
num = (1 + lim) / 2 * lim;
8+
else
9+
num = lim / 2 * (1 + lim);
10+
while (n - num >= lim + 1)
11+
{
12+
++lim;
13+
n -= num;
14+
}
15+
return lim;
16+
}

‎src/9.cpp

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

0 commit comments

Comments
 (0)