Skip to content

Commit fd8348d

Browse files
lintcoderlintcoder
committed
10 problems solved.
1 parent 30bf4bc commit fd8348d

File tree

10 files changed

+240
-0
lines changed

10 files changed

+240
-0
lines changed

‎src/111.cpp

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
int minDepth(TreeNode* root) {
2+
if (root == NULL)
3+
return 0;
4+
if (root->left == NULL && root->right == NULL)
5+
return 1;
6+
else if (root->left != NULL && root->right == NULL)
7+
return 1 + minDepth(root->left);
8+
else if (root->left == NULL && root->right != NULL)
9+
return 1 + minDepth(root->right);
10+
else
11+
{
12+
int ldepth = minDepth(root->left);
13+
int rdepth = minDepth(root->right);
14+
return ldepth < rdepth ? ldepth + 1 : rdepth + 1;
15+
}
16+
}

‎src/172.cpp

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
int trailingZeroes(int n) {
2+
int sum = 0;
3+
while (n >= 5)
4+
{
5+
sum += n / 5;
6+
n /= 5;
7+
}
8+
9+
return sum;
10+
}

‎src/20.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
bool isValid(string s) {
2+
int sz = s.size();
3+
if (sz % 2 == 1)
4+
return false;
5+
stack<int> stk;
6+
for (int i = 0; i != sz; ++i)
7+
{
8+
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
9+
stk.push(s[i]);
10+
else
11+
{
12+
if (stk.empty() || ((s[i] == ')' && stk.top() != '(') || (s[i] == ']' && stk.top() != '[') || (s[i] == '}' && stk.top() != '{')))
13+
return false;
14+
stk.pop();
15+
}
16+
}
17+
return stk.empty();
18+
}

‎src/205.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
bool isIsomorphic(string s, string t) {
2+
map<char, char> dict;
3+
set<char> st;
4+
int sz = s.size();
5+
6+
for (int i = 0; i != sz; ++i)
7+
{
8+
map<char, char>::iterator miter = dict.find(s[i]);
9+
set<char>::iterator siter = st.find(t[i]);
10+
11+
if (miter == dict.end() && siter == st.end())
12+
{
13+
dict[s[i]] = t[i];
14+
st.insert(t[i]);
15+
}
16+
else if (miter != dict.end() && siter != st.end())
17+
{
18+
if (dict[s[i]] != t[i])
19+
return false;
20+
}
21+
else
22+
return false;
23+
}
24+
25+
return true;
26+
}

‎src/26.cpp

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

‎src/374.cpp

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
int guessNumber(int n) {
2+
int p = 1, q = n;
3+
while (p < q)
4+
{
5+
int mid = p / 2 + q / 2;
6+
int res = guess(mid);
7+
if (res == 0)
8+
return mid;
9+
else if (res < 0)
10+
q = mid - 1;
11+
else
12+
p = mid + 1;
13+
}
14+
return p;
15+
}

‎src/38.cpp

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
string countAndSay(int n) {
2+
if (n <= 0)
3+
return "";
4+
deque<int> dq;
5+
dq.push_back(1);
6+
7+
int i = 1;
8+
while (i < n)
9+
{
10+
int len = dq.size();
11+
int ct = 1, num = dq.at(0);
12+
for (int j = 1; j < len; ++j)
13+
{
14+
int val = dq.at(j);
15+
if (val == num)
16+
++ct;
17+
else
18+
{
19+
dq.push_back(ct);
20+
dq.push_back(num);
21+
num = val;
22+
ct = 1;
23+
}
24+
}
25+
dq.push_back(ct);
26+
dq.push_back(num);
27+
dq.erase(dq.begin(), dq.begin() + len);
28+
++i;
29+
}
30+
31+
int sz = dq.size();
32+
string res(sz + 1, '\0');
33+
for (int j = 0; j < sz; ++j)
34+
res[j] = dq.at(j) + '0';
35+
36+
return res;
37+
}

‎src/729.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
class MyCalendar {
2+
public:
3+
MyCalendar() {
4+
5+
}
6+
7+
bool book(int start, int end) {
8+
auto iter = lower_bound(interval_begin.begin(), interval_begin.end(), end);
9+
if (iter == interval_begin.begin())
10+
{
11+
interval_begin.insert(interval_begin.begin(), start);
12+
interval_end.insert(interval_end.begin(), end);
13+
return true;
14+
}
15+
else
16+
{
17+
int pos = iter-interval_begin.begin()-1;
18+
if (start < interval_end[pos])
19+
return false;
20+
interval_begin.insert(iter, start);
21+
interval_end.insert(interval_end.begin()+pos+1, end);
22+
return true;
23+
}
24+
}
25+
26+
private:
27+
vector<int> interval_begin;
28+
vector<int> interval_end;
29+
};

‎src/849.cpp

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
int maxDistToClosest(vector<int>& seats) {
2+
int len = seats.size();
3+
if (len == 1)
4+
return 0;
5+
6+
int maxDist = 0;
7+
int maxInterval = 0, interval = 0;
8+
int pos = 0, i = 0;
9+
if (seats[0] == 0)
10+
{
11+
while (i < len && seats[i] == 0)
12+
++i;
13+
maxDist = i;
14+
}
15+
pos = i;
16+
++i;
17+
while (i < len)
18+
{
19+
if (seats[i] == 1)
20+
{
21+
interval = i - pos - 1;
22+
pos = i;
23+
if (interval > maxInterval)
24+
{
25+
maxInterval = interval;
26+
}
27+
}
28+
++i;
29+
}
30+
interval = len-1-pos;
31+
if (interval > maxDist)
32+
maxDist = interval;
33+
34+
if (maxInterval > 0)
35+
{
36+
maxInterval = maxInterval%2 == 0 ? maxInterval/2 : maxInterval/2 + 1;
37+
if (maxInterval > maxDist)
38+
maxDist = maxInterval;
39+
}
40+
41+
return maxDist;
42+
}

‎src/937.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
vector<string> reorderLogFiles(vector<string>& logs) {
2+
int len = logs.size();
3+
if (len <= 1)
4+
return logs;
5+
6+
map<string, string> letter;
7+
for (int i = 0; i < len; ++i)
8+
{
9+
int index = logs[i].find(' ') + 1;
10+
letter[logs[i]] = logs[i].substr(index);
11+
}
12+
13+
auto cmp = [=](string& a, string& b) {
14+
char c1 = letter[a][0];
15+
char c2 = letter[b][0];
16+
if (isdigit(c2))
17+
return true;
18+
else if (isdigit(c1))
19+
return false;
20+
else
21+
return letter[a] < letter[b];
22+
};
23+
24+
sort(logs.begin(), logs.end(), cmp);
25+
return logs;
26+
}

0 commit comments

Comments
 (0)