Skip to content

Commit f08eb01

Browse files
lintcoderlintcoder
committed
1.Another 16 problems solved.
1 parent f351cd2 commit f08eb01

File tree

16 files changed

+387
-0
lines changed

16 files changed

+387
-0
lines changed

‎167.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
vector<int> twoSum(vector<int>& numbers, int target) {
2+
vector<int> res(2, -1);
3+
int len = numbers.size();
4+
for (int i = 0; i < len; ++i)
5+
{
6+
int index = 0;
7+
if (BSearch(numbers, i + 1, len - 1, target - numbers[i], index))
8+
{
9+
res[0] = i + 1;
10+
res[1] = index + 1;
11+
break;
12+
}
13+
}
14+
return res;
15+
}
16+
17+
bool BSearch(vector<int>& numbers, int p, int q, int val, int& index)
18+
{
19+
while (p <= q)
20+
{
21+
int mid = (p + q) / 2;
22+
if (numbers[mid] == val)
23+
{
24+
index = mid;
25+
return true;
26+
}
27+
else if (numbers[mid] < val)
28+
p = mid + 1;
29+
else
30+
q = mid - 1;
31+
}
32+
return false;
33+
}

‎169.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
string convertToBase7(int num) {
2+
if (num == 0)
3+
return "0";
4+
string res;
5+
bool flag = true;
6+
if (num < 0)
7+
{
8+
flag = false;
9+
num = -num;
10+
}
11+
while (num != 0)
12+
{
13+
res.push_back(char(num % 7 + '0'));
14+
num /= 7;
15+
}
16+
reverse(res.begin(), res.end());
17+
if (flag == false)
18+
res = "-" + res;
19+
20+
return res;
21+
}

‎206.cpp

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

‎217.cpp

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
bool containsDuplicate(vector<int>& nums) {
2+
map<int, int> mp;
3+
int len = nums.size();
4+
for (int i = 0; i < len; ++i)
5+
{
6+
mp[nums[i]]++;
7+
if (mp[nums[i]] > 1)
8+
return true;
9+
}
10+
return false;
11+
}

‎268.cpp

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
int missingNumber(vector<int>& nums) {
2+
int len = nums.size();
3+
long long sum = 0;
4+
for (int i = 0; i < len; ++i)
5+
sum += i - nums[i];
6+
return sum + len;
7+
}

‎350.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
2+
map<int, int> mp;
3+
vector<int> res;
4+
int len1 = nums1.size();
5+
int len2 = nums2.size();
6+
for (int i = 0; i < len1; ++i)
7+
mp[nums1[i]]++;
8+
for (int i = 0; i < len2; ++i)
9+
{
10+
if (mp.find(nums2[i]) != mp.end() && mp[nums2[i]] != 0)
11+
{
12+
res.push_back(nums2[i]);
13+
mp[nums2[i]]--;
14+
}
15+
}
16+
return res;
17+
}

‎401.cpp

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
vector<string> readBinaryWatch(int num) {
2+
vector<string> res;
3+
const int weight[6] = {1, 2, 4, 8, 16, 32};
4+
if (num == 0)
5+
res.push_back("0:00");
6+
else
7+
{
8+
int beginpos = num >= 7 ? num - 6 : 0;
9+
int endpos = num >= 4 ? 4 : num;
10+
for (int i = beginpos; i <= endpos; ++i)
11+
{
12+
vector<string> hour, minute;
13+
combination(4, i, weight, hour);
14+
combination(6, num - i, weight, minute);
15+
int len1 = hour.size(), len2 = minute.size();
16+
for (int j = 0; j < len1; ++j)
17+
{
18+
for (int k = 0; k < len2; ++k)
19+
res.push_back(hour[j] + ":" + minute[k]);
20+
}
21+
}
22+
}
23+
return res;
24+
}
25+
26+
void combination(int total, int n, const int* weight, vector<string>& vec)
27+
{
28+
if (n == 0)
29+
{
30+
if (total == 4)
31+
vec.push_back("0");
32+
else
33+
vec.push_back("00");
34+
}
35+
else
36+
{
37+
docombination(total, n, 0, 0, weight, vec, 0);
38+
}
39+
}
40+
41+
void docombination(int total, int n, int pos, int subsum, const int* weight, vector<string>& vec, int ct)
42+
{
43+
if (ct == n)
44+
{
45+
if (total == 4 && subsum <= 11)
46+
{
47+
if (subsum < 10)
48+
vec.push_back(string(1, subsum + '0'));
49+
else
50+
vec.push_back(int2str(subsum));
51+
}
52+
else if (total == 6 && subsum <= 59)
53+
{
54+
if (subsum < 10)
55+
vec.push_back("0" + string(1, subsum + '0'));
56+
else
57+
vec.push_back(int2str(subsum));
58+
}
59+
}
60+
else
61+
{
62+
for (int i = pos; i <= total - n + ct; ++i)
63+
{
64+
int tmp = subsum + weight[i];
65+
docombination(total, n, i + 1, tmp, weight, vec, ct + 1);
66+
}
67+
}
68+
}
69+
70+
string int2str(int n)
71+
{
72+
string s;
73+
while (n != 0)
74+
{
75+
s.insert(s.begin(), n % 10 + '0');
76+
n /= 10;
77+
}
78+
return s;
79+
}

‎409.cpp

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
int longestPalindrome(string s) {
2+
int alpha[52] = {0};
3+
int len = s.size();
4+
for (int i = 0; i < len; ++i)
5+
{
6+
if (islower(s[i]))
7+
alpha[s[i] - 'a']++;
8+
else
9+
alpha[s[i] - 'A' + 26]++;
10+
}
11+
int sum = 0;
12+
int flag = 0;
13+
for (int i = 0; i < 52; ++i)
14+
{
15+
sum += alpha[i] / 2;
16+
if (!flag && alpha[i] % 2 == 1)
17+
flag = 1;
18+
}
19+
return sum * 2 + flag;
20+
}

‎448.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
vector<int> findDisappearedNumbers(vector<int>& nums) {
2+
int len = nums.size();
3+
int i = 0;
4+
while (i < len)
5+
{
6+
if (nums[i] != i + 1)
7+
{
8+
int pos = nums[i] - 1;
9+
while (nums[pos] != pos + 1)
10+
{
11+
int tmp = nums[pos];
12+
nums[pos] = pos + 1;
13+
pos = tmp - 1;
14+
}
15+
}
16+
++i;
17+
}
18+
int k = 0;
19+
for (int i = 0; i < len; ++i)
20+
if (nums[i] != i + 1)
21+
nums[k++] = i + 1;
22+
nums.resize(k);
23+
return nums;
24+
}

‎461.cpp

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
int hammingDistance(int x, int y) {
2+
bitset<32> xbit(x);
3+
bitset<32> ybit(y);
4+
int dist = 0;
5+
for (int i = 0; i < 32; ++i)
6+
if (xbit[i] != ybit[i])
7+
++dist;
8+
9+
return dist;
10+
}

‎476.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
int findComplement(int num) {
2+
bitset<32> val(num);
3+
int i = 31;
4+
while (i >= 0)
5+
{
6+
if (val[i] == 0)
7+
--i;
8+
else
9+
break;
10+
}
11+
int sum = 0;
12+
for (; i >= 0; --i)
13+
{
14+
sum = sum * 2 + 1 - val[i];
15+
}
16+
return sum;
17+
}

‎492.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
vector<int> constructRectangle(int area) {
2+
vector<int> length(2, 0);
3+
int limit = sqrt(area);
4+
int i = limit;
5+
while (i <= area)
6+
{
7+
if (area % i == 0)
8+
break;
9+
else
10+
++i;
11+
}
12+
int j = area / i;
13+
if (i > j)
14+
{
15+
length[0] = i;
16+
length[1] = j;
17+
}
18+
else
19+
{
20+
length[0] = j;
21+
length[1] = i;
22+
}
23+
return length;
24+
}

‎500.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
vector<string> findWords(vector<string>& words) {
2+
const int pos[26] = {1, 2, 2, 1, 0, 1, 1, 1, 0, 1, 1, 1, 2,
3+
2, 0, 0, 0, 0, 1, 0, 0, 2, 0, 2, 0, 2};
4+
vector<string> res;
5+
int len = words.size();
6+
for (int i = 0; i < len; ++i)
7+
{
8+
int p = pos[tolower(words[i][0]) - 'a'];
9+
int sz = words[i].size();
10+
int j;
11+
for (j = 1; j < sz; ++j)
12+
if (pos[tolower(words[i][j]) - 'a'] != p)
13+
break;
14+
if (j == sz)
15+
res.push_back(words[i]);
16+
}
17+
return res;
18+
}

‎504.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
string convertToBase7(int num) {
2+
if (num == 0)
3+
return "0";
4+
string res;
5+
bool flag = true;
6+
if (num < 0)
7+
{
8+
flag = false;
9+
num = -num;
10+
}
11+
while (num != 0)
12+
{
13+
res.push_back(char(num % 7 + '0'));
14+
num /= 7;
15+
}
16+
reverse(res.begin(), res.end());
17+
if (flag == false)
18+
res = "-" + res;
19+
20+
return res;
21+
}

‎506.cpp

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
vector<string> findRelativeRanks(vector<int>& nums) {
2+
vector<string> res;
3+
int len = nums.size();
4+
if (len == 0)
5+
return res;
6+
res.resize(len);
7+
struct Elem
8+
{
9+
int val;
10+
int pos;
11+
Elem(int v, int p):val(v), pos(p){}
12+
};
13+
vector<Elem> vec;
14+
for (int i = 0; i < len; ++i)
15+
vec.push_back(Elem(nums[i], i));
16+
auto cmp = [=](Elem& a, Elem& b) { return a.val > b.val;};
17+
sort(vec.begin(), vec.end(), cmp);
18+
for (int i = 0; i < len; ++i)
19+
{
20+
if (i == 0)
21+
res[vec[i].pos] = "Gold Medal";
22+
else if (i == 1)
23+
res[vec[i].pos] = "Silver Medal";
24+
else if (i == 2)
25+
res[vec[i].pos] = "Bronze Medal";
26+
else
27+
res[vec[i].pos] = num2str(i + 1);
28+
}
29+
30+
return res;
31+
}
32+
33+
string num2str(int num)
34+
{
35+
string str;
36+
while (num != 0)
37+
{
38+
str.push_back(char(num % 10 + '0'));
39+
num /= 10;
40+
}
41+
reverse(str.begin(), str.end());
42+
return str;
43+
}

0 commit comments

Comments
 (0)