Skip to content

Commit be12b25

Browse files
lintcoderlintcoder
committed
15 problems solved.
1 parent 3c85785 commit be12b25

File tree

15 files changed

+509
-0
lines changed

15 files changed

+509
-0
lines changed

‎src/406.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
2+
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
3+
return a.first > b.first || (a.first == b.first && a.second < b.second);
4+
};
5+
6+
sort(people.begin(), people.end(), cmp);
7+
8+
list<pair<int, int>> list_people(people.begin(), people.end());
9+
10+
int len = list_people.size();
11+
auto iter = list_people.begin();
12+
int i = 0, j = 0;
13+
while (i < len)
14+
{
15+
if (i == iter->second)
16+
iter++;
17+
else
18+
{
19+
pair<int, int> p(*iter);
20+
iter = list_people.erase(iter);
21+
auto insertpos = list_people.begin();
22+
advance(insertpos, p.second);
23+
list_people.insert(insertpos, p);
24+
}
25+
++i;
26+
}
27+
28+
people.assign(list_people.begin(), list_people.end());
29+
return people;
30+
}

‎src/413.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
int numberOfArithmeticSlices(vector<int>& A) {
2+
int len = A.size();
3+
if (len < 3)
4+
return 0;
5+
6+
int i = 0;
7+
int sum = 0;
8+
while (i < len - 2)
9+
{
10+
int dif = A[i + 1] - A[i];
11+
int j = i + 1;
12+
while (j+1 < len && A[j+1] - A[j] == dif)
13+
++j;
14+
if (j - i >= 2)
15+
{
16+
int n = j - i + 1 - 3 + 1;
17+
sum += (1+n)*n/2;
18+
}
19+
i = j;
20+
}
21+
22+
return sum;
23+
}

‎src/442.cpp

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

‎src/451.cpp

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
string frequencySort(string s) {
2+
map<char, int> mp;
3+
for (auto c : s)
4+
mp[c]++;
5+
6+
struct Elem
7+
{
8+
char ch;
9+
int num;
10+
Elem(char c, int n) : ch(c), num(n){};
11+
};
12+
13+
vector<Elem> elemvec;
14+
for (auto m : mp)
15+
elemvec.push_back(Elem(m.first, m.second));
16+
17+
auto cmp = [=](const Elem& a, const Elem& b) {
18+
return a.num > b.num;
19+
};
20+
sort(elemvec.begin(), elemvec.end(), cmp);
21+
22+
int sz = elemvec.size();
23+
int pos = 0;
24+
string str(s.size(), '\0');
25+
for (int i = 0; i < sz; ++i)
26+
{
27+
int n = elemvec[i].num;
28+
for (int j = pos; j < pos + n; ++j)
29+
str[j] = elemvec[i].ch;
30+
pos += n;
31+
}
32+
33+
return str;
34+
}

‎src/513.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
int findBottomLeftValue(TreeNode* root) {
2+
int depth = 0;
3+
return dofindBottomLeftValue(root, depth);
4+
}
5+
6+
int dofindBottomLeftValue(TreeNode* node, int& depth)
7+
{
8+
int ldepth = depth, rdepth = depth;
9+
int lval = 0, rval = 0;
10+
11+
if (node->left == NULL && node->right == NULL)
12+
return node->val;
13+
if (node->left != NULL)
14+
{
15+
ldepth = depth + 1;
16+
lval = dofindBottomLeftValue(node->left, ldepth);
17+
}
18+
if (node->right != NULL)
19+
{
20+
rdepth = depth + 1;
21+
rval = dofindBottomLeftValue(node->right, rdepth);
22+
}
23+
24+
depth = ldepth >= rdepth ? ldepth : rdepth;
25+
return ldepth >= rdepth ? lval : rval;
26+
}

‎src/515.cpp

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
vector<int> largestValues(TreeNode* root) {
2+
vector<int> res;
3+
deque<TreeNode*> dq;
4+
5+
if (root == nullptr)
6+
return res;
7+
8+
res.push_back(root->val);
9+
if (root->left != nullptr)
10+
dq.push_back(root->left);
11+
if (root->right != nullptr)
12+
dq.push_back(root->right);
13+
int len = 0;
14+
while ((len = dq.size()) != 0)
15+
{
16+
TreeNode* node = dq[0];
17+
int maxval = node->val;
18+
if (node->left != nullptr)
19+
dq.push_back(node->left);
20+
if (node->right != nullptr)
21+
dq.push_back(node->right);
22+
for (int i = 1; i < len; ++i)
23+
{
24+
node = dq[i];
25+
if (node->val > maxval)
26+
maxval = node->val;
27+
if (node->left != nullptr)
28+
dq.push_back(node->left);
29+
if (node->right != nullptr)
30+
dq.push_back(node->right);
31+
}
32+
dq.erase(dq.begin(), dq.begin() + len);
33+
res.push_back(maxval);
34+
}
35+
36+
return res;
37+
}

‎src/526.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
int countArrangement(int N) {
2+
if (N <= 2)
3+
return N;
4+
vector<int> arr(N, 0);
5+
int count = 0;
6+
int total = 0;
7+
8+
docountArrange(arr, N, count, total);
9+
10+
return total;
11+
}
12+
13+
void docountArrange(vector<int>& arr, int n, int count, int& total)
14+
{
15+
for (int i = 0; i < n; ++i)
16+
{
17+
if (arr[i] == 0)
18+
{
19+
if ((count + 1) % (i + 1) == 0 || (i + 1) % (count + 1) == 0)
20+
{
21+
arr[i] = 1;
22+
if (count+1 < n)
23+
docountArrange(arr, n, count+1, total);
24+
else
25+
total++;
26+
arr[i] = 0;
27+
}
28+
}
29+
}
30+
}

‎src/537.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
string complexNumberMultiply(string a, string b) {
2+
int len1 = a.size(), len2 = b.size();
3+
if (len1 == 0 || len2 == 0)
4+
return "";
5+
6+
size_t pos = 0;
7+
int real1 = stoi(a, &pos);
8+
int img1 = stoi(a.substr(pos + 1));
9+
10+
int real2 = stoi(b, &pos);
11+
int img2 = stoi(b.substr(pos + 1));
12+
int real = real1*real2 - img1*img2;
13+
int img = real1*img2 + real2*img1;
14+
15+
return to_string(real) + "+" + to_string(img) + "i";
16+
17+
}

‎src/540.cpp

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
int singleNonDuplicate(vector<int>& nums) {
2+
int len = nums.size();
3+
if (len == 1)
4+
return nums[0];
5+
int single = 0;
6+
doFindSingle(nums, 0, len - 1, single);
7+
return single;
8+
}
9+
10+
bool doFindSingle(vector<int>& nums, int p, int q, int& single)
11+
{
12+
if (p == q)
13+
{
14+
single = nums[p];
15+
return true;
16+
}
17+
else if (p == q - 1)
18+
return false;
19+
else
20+
{
21+
int mid = (p + q) / 2;
22+
bool flag = false;
23+
if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1])
24+
{
25+
single = nums[mid];
26+
return true;
27+
}
28+
else if (nums[mid] == nums[mid - 1])
29+
{
30+
if (mid - 2 >= p)
31+
flag = doFindSingle(nums, p, mid - 2, single);
32+
if (!flag)
33+
return doFindSingle(nums, mid + 1, q, single);
34+
else
35+
return flag;
36+
}
37+
else if (nums[mid] == nums[mid + 1])
38+
{
39+
if (mid + 2 <= q)
40+
flag = doFindSingle(nums, mid + 2, q, single);
41+
if (!flag)
42+
return doFindSingle(nums, p, mid - 1, single);
43+
else
44+
return flag;
45+
}
46+
}
47+
}

‎src/654.cpp

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
2+
int len = nums.size();
3+
if (len == 0)
4+
return nullptr;
5+
return constructSubMaxBTree(nums, 0, len - 1);
6+
}
7+
8+
TreeNode* constructSubMaxBTree(vector<int>& nums, int p, int q)
9+
{
10+
if (p > q)
11+
return nullptr;
12+
if (p == q)
13+
return new TreeNode(nums[p]);
14+
int r = p;
15+
int maxval = nums[p];
16+
for (int i = p + 1; i <= q; ++i)
17+
if (nums[i] > maxval)
18+
{
19+
maxval = nums[i];
20+
r = i;
21+
}
22+
TreeNode* node = new TreeNode(maxval);
23+
node->left = constructSubMaxBTree(nums, p, r - 1);
24+
node->right = constructSubMaxBTree(nums, r + 1, q);
25+
26+
return node;
27+
}

‎src/677.cpp

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
public:
2+
/** Initialize your data structure here. */
3+
MapSum() {
4+
5+
}
6+
7+
void insert(string key, int val) {
8+
if (mp.find(key) != mp.end())
9+
mp[key] = val;
10+
else
11+
mp.insert(pair<string, int>(key, val));
12+
}
13+
14+
int sum(string prefix) {
15+
int len = prefix.size();
16+
if (len == 0)
17+
return 0;
18+
19+
int count = 0;
20+
for (auto elem : mp)
21+
if (elem.first.substr(0, len) == prefix)
22+
count += elem.second;
23+
24+
return count;
25+
}
26+
private:
27+
map<string, int> mp;

0 commit comments

Comments
 (0)