Skip to content

Commit b9bb156

Browse files
lintcoderlintcoder
committed
12 problems solved.
1 parent 18d21d5 commit b9bb156

File tree

12 files changed

+340
-0
lines changed

12 files changed

+340
-0
lines changed

‎src/160.cpp

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
2+
if (headA == NULL || headB == NULL)
3+
return NULL;
4+
int len1 = 0, len2 = 0;
5+
ListNode* p = headA, *q = headB;
6+
while (p != NULL)
7+
{
8+
p = p->next;
9+
len1++;
10+
}
11+
while (q != NULL)
12+
{
13+
q = q->next;
14+
len2++;
15+
}
16+
p = headA;
17+
q = headB;
18+
while (len1 < len2)
19+
{
20+
q = q->next;
21+
len2--;
22+
}
23+
while (len1 > len2)
24+
{
25+
p = p->next;
26+
len1--;
27+
}
28+
while (p != NULL && q != NULL)
29+
{
30+
if (p == q)
31+
return p;
32+
else
33+
{
34+
p = p->next;
35+
q = q->next;
36+
}
37+
}
38+
return NULL;
39+
}

‎src/168.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
string convertToTitle(int n) {
2+
char digit[26];
3+
digit[0] = 'Z';
4+
for (int i = 1; i < 26; ++i)
5+
digit[i] = 'A' + i - 1;
6+
string str;
7+
while (n > 0)
8+
{
9+
int pos = n % 26;
10+
str.push_back(digit[pos]);
11+
if (pos == 0)
12+
n = n / 26 - 1;
13+
else
14+
n = n / 26;
15+
}
16+
reverse(str.begin(), str.end());
17+
return str;
18+
}

‎src/189.cpp

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
void rotate(vector<int>& nums, int k) {
2+
int len = nums.size();
3+
k %= len;
4+
5+
if (k == 0)
6+
return;
7+
else
8+
{
9+
reverse(nums.begin(), nums.begin() + len - k);
10+
reverse(nums.begin() + len - k, nums.end());
11+
reverse(nums.begin(), nums.end());
12+
}
13+
}

‎src/190.cpp

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

‎src/204.cpp

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
int countPrimes(int n) {
2+
if (n <= 2)
3+
return 0;
4+
5+
int* arr = new int[n];
6+
for (int i = 0; i < n; ++i)
7+
arr[i] = 1;
8+
arr[0] = arr[1] = 0;
9+
10+
for (int i = 2; i < n - 2; i += 2)
11+
arr[i + 2] = 0;
12+
13+
int lim = sqrt(n - 1);
14+
int i = 3, j;
15+
while (i <= lim)
16+
{
17+
if (arr[i] == 1)
18+
{
19+
int lim2 = (n - 1) / i;
20+
for (j = i; j <= lim2; ++j)
21+
arr[i * j] = 0;
22+
23+
}
24+
i += 2;
25+
while (arr[i] == 0)
26+
i += 2;
27+
}
28+
29+
int count = 0;
30+
for (i = 0; i < n; ++i)
31+
if (arr[i] == 1)
32+
++count;
33+
delete[] arr;
34+
35+
return count;
36+
}

‎src/278.cpp

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

‎src/28.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
int strStr(string haystack, string needle) {
2+
int len1 = haystack.size();
3+
int len2 = needle.size();
4+
if (len1 < len2)
5+
return -1;
6+
if (len2 == 0)
7+
return 0;
8+
9+
int i = 0, pos = 0;
10+
bool flag = false;
11+
while (i < len1)
12+
{
13+
pos = haystack.find(needle[0], i);
14+
if (pos == string::npos || len1 - pos < len2)
15+
break;
16+
else
17+
{
18+
if (haystack.substr(pos, len2) == needle)
19+
{
20+
flag = true;
21+
break;
22+
}
23+
else
24+
i = pos + 1;
25+
}
26+
}
27+
if (flag)
28+
return pos;
29+
else
30+
return -1;
31+
}

‎src/400.cpp

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
int findNthDigit(int n) {
2+
if (n <= 0)
3+
return 0;
4+
long long num = 1, ct = 1;
5+
int predigits = 0, count = 9;
6+
long long digits = 9 * num * ct;
7+
while (n >= digits)
8+
{
9+
n -= digits;
10+
num *= 10;
11+
++ct;
12+
predigits += count;
13+
count *= 10;
14+
digits = 9 * num * ct;
15+
}
16+
17+
if (n == 0)
18+
return 9;
19+
else
20+
{
21+
int remain = n % ct;
22+
int val = n / ct;
23+
if (remain == 0)
24+
return (predigits + val) % 10;
25+
else
26+
return selectNthDigit(predigits + val + 1, remain, ct);
27+
}
28+
}
29+
30+
int selectNthDigit(int num, int pos, int totaldigit)
31+
{
32+
int n = totaldigit - pos;
33+
while (n > 0)
34+
{
35+
num /= 10;
36+
--n;
37+
}
38+
return num % 10;
39+
}

‎src/475.cpp

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
int findRadius(vector<int>& houses, vector<int>& heaters) {
2+
int num1 = houses.size();
3+
int num2 = heaters.size();
4+
if (num1 == 0 || num2 == 0)
5+
return 0;
6+
sort(houses.begin(), houses.end());
7+
sort(heaters.begin(), heaters.end());
8+
int min_radius = 0, rad = 0;
9+
int i = 0, j = 0;
10+
if (houses[i] < heaters[j])
11+
{
12+
min_radius = heaters[j] - houses[i];
13+
++i;
14+
while (i < num1 && houses[i] < heaters[j])
15+
++i;
16+
}
17+
while (i < num1)
18+
{
19+
if (houses[i] == heaters[j])
20+
++i;
21+
else
22+
{
23+
if (j == num2)
24+
break;
25+
else
26+
{
27+
int rlimit = heaters[j + 1];
28+
if (houses[i] < rlimit)
29+
{
30+
int lrad = houses[i] - heaters[j];
31+
int rrad = heaters[j + 1] - houses[i];
32+
int tmp = lrad < rrad ? lrad : rrad;
33+
if (tmp > rad)
34+
rad = tmp;
35+
++i;
36+
}
37+
else if (houses[i] == rlimit)
38+
++i;
39+
else
40+
{
41+
if (rad > min_radius)
42+
min_radius = rad;
43+
++j;
44+
}
45+
}
46+
}
47+
}
48+
if (rad > min_radius)
49+
min_radius = rad;
50+
if (i < num1)
51+
{
52+
int tmp = houses[num1 - 1] - heaters[num2 - 1];
53+
if (tmp > min_radius)
54+
min_radius = tmp;
55+
}
56+
57+
return min_radius;
58+
}

‎src/605.cpp

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

‎src/69.cpp

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
int mySqrt(int x) {
2+
if (x < 0)
3+
return -1;
4+
if (x <= 1)
5+
return x;
6+
int p = 1, q = x;
7+
while (p < q - 1)
8+
{
9+
long long mid = p/2 + q/2 + (p%2 && q%2);
10+
long long res = mid * mid;
11+
if (res == x)
12+
return mid;
13+
else if (res < x)
14+
p = mid;
15+
else
16+
q = mid - 1;
17+
}
18+
if (q <= x/q)
19+
return q;
20+
else
21+
return p;
22+
}

‎src/7.cpp

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

0 commit comments

Comments
 (0)