Skip to content

Commit 86322be

Browse files
begeekmyfriendbegeekmyfriend
committed
Add C++ implementation
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parent d8fb0eb commit 86322be

File tree

33 files changed

+1156
-0
lines changed

33 files changed

+1156
-0
lines changed

‎001_two_sum/two_sum.cc

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
vector<int> twoSum(vector<int>& nums, int target) {
8+
vector<int> res;
9+
unordered_map<int, int> ht;
10+
for (int i = 0; i < nums.size(); i++) {
11+
int other = target - nums[i];
12+
if (ht.find(other) != ht.end()) {
13+
/* Only one solution for purpose of this problem */
14+
res.append(ht[other]);
15+
res.append(i);
16+
return res;
17+
}
18+
ht[nums[i]] = i;
19+
}
20+
return res;
21+
}
22+
};

‎002_add_two_numbers/add_two_numbers.cc

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
/**
6+
* Definition for singly-linked list.
7+
* struct ListNode {
8+
* int val;
9+
* ListNode *next;
10+
* ListNode() : val(0), next(nullptr) {}
11+
* ListNode(int x) : val(x), next(nullptr) {}
12+
* ListNode(int x, ListNode *next) : val(x), next(next) {}
13+
* };
14+
*/
15+
class Solution {
16+
public:
17+
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
18+
int carry = 0;
19+
struct ListNode dummy;
20+
struct ListNode *p = l1, *prev = &dummy;
21+
22+
dummy.next = p;
23+
while (l1 != nullptr || l2 != nullptr) {
24+
int sum = 0;
25+
26+
if (l1 != nullptr) {
27+
sum += l1->val;
28+
l1 = l1->next;
29+
}
30+
31+
if (l2 != nullptr) {
32+
if (p == nullptr) {
33+
/* l2 longer than l1 */
34+
prev->next = l2;
35+
p = l2;
36+
}
37+
sum += l2->val;
38+
l2 = l2->next;
39+
}
40+
41+
sum += carry;
42+
carry = sum / 10;
43+
p->val = sum % 10;
44+
prev = p;
45+
p = p->next;
46+
}
47+
48+
if (carry) {
49+
p = new ListNode(carry);
50+
prev->next = p;
51+
}
52+
53+
return dummy.next;
54+
}
55+
};

‎003_longest_substring_without_repeat/longest_substring_without_repeat.cc

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
int lengthOfLongestSubstring(string s) {
8+
vector<int> indexes(128, -1);
9+
int max_len = 0;
10+
int len = 0;
11+
12+
for (int i = 0; i < s.length(); i++) {
13+
if (indexes[s[i]] == -1) {
14+
len++;
15+
} else {
16+
if (i - indexes[s[i]] > len) {
17+
/* not included in sliding window, go on increasing */
18+
len++;
19+
} else {
20+
/* repetition in sliding window, count from scratch */
21+
len = i - indexes[s[i]];
22+
}
23+
}
24+
max_len = max(max_len, len);
25+
indexes[s[i]] = i;
26+
}
27+
28+
return max_len;
29+
}
30+
};

‎004_median_of_two_sorted_array/median_of_two_sorted_array.cc

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
8+
int sum = nums1.size() + nums2.size();
9+
vector<int> nums;
10+
int i = 0, j = 0, k;
11+
int half = sum / 2 + 1;
12+
for (k = 0; k < half; k++) {
13+
int n;
14+
if (i < nums1.size() && j < nums2.size()) {
15+
n = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
16+
} else if (i < nums1.size()) {
17+
n = nums1[i++];
18+
} else if (j < nums2.size()) {
19+
n = nums2[j++];
20+
}
21+
nums.push_back(n);
22+
}
23+
24+
if (sum % 2) {
25+
return nums[k-1];
26+
} else {
27+
return (nums[k-1] + nums[k-2]) / 2.0;
28+
}
29+
}
30+
};

‎006_zigzag_conversion/zigzag_conversion.cc

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
string convert(string s, int numRows) {
8+
if (numRows <= 1) {
9+
return s;
10+
}
11+
12+
string new_s;
13+
for (int row = 0; row < numRows; row++) {
14+
int delta;
15+
int interval1 = numRows + (numRows - 2) - row * 2;
16+
int interval2 = 2 * row;
17+
bool flag = false;
18+
for (int i = row; i < s.length(); i += delta) {
19+
new_s.push_back(s[i]);
20+
do {
21+
delta = !flag ? interval1 : interval2;
22+
flag = !flag;
23+
} while (delta == 0);
24+
}
25+
}
26+
27+
return new_str;
28+
}
29+
};

‎007_reverse_integer/reverse_integer.cc

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
int reverse(int x) {
8+
int n = 0;
9+
while (x != 0) {
10+
// Checking the over/underflow.
11+
int r = x % 10;
12+
if (n > INT_MAX / 10 || (n == INT_MAX / 10 && r > 7)) {
13+
return 0;
14+
}
15+
if (n < INT_MIN / 10 || (n == INT_MIN / 10 && r < -8)) {
16+
return 0;
17+
}
18+
19+
n = n * 10 + r;
20+
x = x / 10;
21+
}
22+
return n;
23+
}
24+
};

‎008_atoi/atoi.cc

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
int myAtoi(string str) {
8+
long n = 0;
9+
int i, sign = 0;
10+
11+
for (i = 0; i < str.length(); i++) {
12+
if (str[i] != ' ' && str[i] != '\t') {
13+
break;
14+
}
15+
}
16+
17+
if (str[i] == '-') {
18+
if (isdigit(str[++i])) {
19+
sign = 1;
20+
} else {
21+
return 0;
22+
}
23+
}
24+
25+
if (str[i] == '+') {
26+
if (isdigit(str[++i])) {
27+
sign = 0;
28+
} else {
29+
return 0;
30+
}
31+
}
32+
33+
for (; i < str.length(); i++) {
34+
if (isdigit(str[i])) {
35+
int d = str[i] - '0';
36+
if (sign) {
37+
if (-n < (INT_MIN + d) / 10) {
38+
n = INT_MIN;
39+
break;
40+
}
41+
} else {
42+
if (n > (INT_MAX - d) / 10) {
43+
n = INT_MAX;
44+
break;
45+
}
46+
}
47+
n = n * 10 + d;
48+
} else {
49+
break;
50+
}
51+
}
52+
53+
return sign ? -n : n;
54+
}
55+
};

‎009_palindrome_number/palindrome_number.cc

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
bool isPalindrome(int x) {
8+
if (x == 0) {
9+
return true;
10+
}
11+
if (x < 0) {
12+
return false;
13+
}
14+
return x == reverse(x);
15+
}
16+
17+
private:
18+
int reverse(int x) {
19+
int n = 0;
20+
while (x != 0) {
21+
// Checking the over/underflow.
22+
int r = x % 10;
23+
if (n > INT_MAX / 10 || (n == INT_MAX / 10 && r > 7)) {
24+
return 0;
25+
}
26+
if (n < INT_MIN / 10 || (n == INT_MIN / 10 && r < -8)) {
27+
return 0;
28+
}
29+
30+
n = n * 10 + r;
31+
x = x / 10;
32+
}
33+
return n;
34+
}
35+
};

‎010_regular_expression_matching/regular_expression.cc

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
/* recursive version too slow thanks to substr() */
8+
bool isMatch(string s, string p) {
9+
vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
10+
dp[0][0] = true;
11+
for (int i = 1; i <= p.length(); i++) {
12+
dp[0][i] = p[0][i - 1] == '*' && i >= 2 && dp[0][i - 2];
13+
}
14+
15+
for (int i = 1; i <= s.length(); i++) {
16+
for (int j = 1; j <= p.length(); j++) {
17+
bool match;
18+
if (j >= 2 && p[j - 1] == '*') {
19+
match = (s[i - 1] == p[j - 2] || p[j - 2] == '.');
20+
dp[i][j] = dp[i][j - 2] || (match && dp[i - 1][j]);
21+
} else {
22+
match = (s[i - 1] == p[j - 1] || p[j - 1] == '.');
23+
dp[i][j] = match && dp[i - 1][j - 1];
24+
}
25+
}
26+
}
27+
28+
return dp[s.size()][p.size()];
29+
}
30+
};

‎011_container_with_most_water/container.cc

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
int maxArea(vector<int>& height) {
8+
int min = 0, max = height.size() - 1;
9+
int area_max = 0;
10+
while (min < max) {
11+
int area = (max - min) * (height[min] < height[max] ? height[min] : height[max]);
12+
area_max = area > area_max ? area : area_max;
13+
if (height[min] < height[max]) {
14+
min++;
15+
} else {
16+
max--;
17+
}
18+
}
19+
return area_max;
20+
}
21+
};

0 commit comments

Comments
 (0)