三百六十五个日子里

leetcode_recode

main programming language: C++

1. Two Sum

Easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析:

  1. 我们可以建立一个 unorded_map 来存储数组里面每个值以及它所对应的位置关系。

  2. 我们用 other_num = target - nums[i]。然后如果不是重复元素,就去找是否存在,如果存在就直接压入 vector。如果是重复元素,就遍历整个 vector 来找到位置,返回。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> result;
vector<int> return_back;
int i = 0;
for(i = 0;i < nums.size();i++)
{
result.insert({nums[i],i});
}
for(i = 0;i < nums.size();i++)
{
int flag = 0;
auto other_num = target - nums[i];
if(other_num != nums[i])
{
auto it = result.find(other_num);
if(it == result.end())
{
continue;
}
else
{
return_back.push_back(i);
return_back.push_back(it->second);
flag = 1;
}
if(flag == 1)
{
break;
}
}
else
{
if(count(nums.begin(),nums.end(),other_num) > 1)
{
for(i = 0;i<nums.size();i++)
{
if(nums[i] == other_num)
{
return_back.push_back(i);
}
}
}
else
{
continue;
}
}
}
return return_back;
}
};

2. Add Two Numbers

Medium

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

分析:

  1. 这题是一个链表的形式的加法题
  2. 整体就是一个加法进位,一个加法余位,两个位置分别保存。这题主要是长度的分类,我自己的思路就是对于较长的链表遍历完才结束遍历。对于短的链表就不停的加值为 0 的结点。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int l1_num = 0,l2_num = 0,sum_result = 0,carry = 0;
ListNode *head = l1;
while(1)
{
sum_result = (l1->val + l2->val + carry) % 10;
carry = (l1->val + l2->val + carry) / 10;
l1->val = sum_result;
if(l1->next == NULL && l2->next != NULL)
{
l1->next = new ListNode(0);
}
else if(l1->next != NULL && l2->next == NULL)
{
l2->next = new ListNode(0);
}
else if(l1->next == NULL && l2->next == NULL)
{
if(carry)
{
l1->next = new ListNode(carry);
}

break;
}
l1 = l1->next;
l2 = l2->next;
}
return head;
}
};

3. Longest Substring Without Repeating Characters

Medium

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析:

  1. 这题是一个最长字符子串的问题。我个人想法使用一个字典来记录某字符出现次数。
  2. 我们用 i、j 指向头部,不断增加 j 的大小,不断增加字典中字符的次数,如果出现某一个字符串出现次数大于两次,就不断移动 i 直到没有重复字符串为止。最后 maxlen 不停更新为最大的值。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> sub_m;
int i = 0,j = 0;
int maxlen = 0;
for(i = 0,j = 0;j<s.size();j++)
{
++sub_m[s[j]];
while(sub_m[s[j]] > 1)
{
sub_m[s[i]]--;
i++;
}
maxlen = max(maxlen,j-i+1);
}
return maxlen;
}
};

4. Median of Two Sorted Arrays

Hard

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

分析:

  1. 这题我个人的思路是非常蠢的。。。先合并,在排序,在去取值
  2. 我在写这个文档的时候,也是不知道当时做这题是怎么想的。为什么用这种奇怪的方法,复杂度还高。
  3. !去看一下 find_k 算法

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i = 0,j = 0;
nums1.insert(nums1.end(), nums2.begin(), nums2.end());
multiset<double> num(nums1.cbegin(), nums1.cend());
multiset<double>::iterator set_it = num.begin();
double result = 0;
if (nums1.size() % 2 == 0)
{
i = (nums1.size() / 2) -1;
for (j = 0; j < i; j++)
{
++set_it;
}
result = (*set_it + *(++set_it)) / 2;
}
else
{
i = (nums1.size() - 1) / 2;
for (j = 0; j < i; j++)
{
++set_it;
}
result = *set_it;
}
return result;
}
};

5. Longest Palindromic Substring

Medium

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

分析:

  1. 这题我自己的做法,也是非常传统的想法实现,没有任何编程方面的技巧,就是硬想出来的

  2. 设置边界,需要找到相关的边界,来进行记录。首先跳过中间相同的字符,因为这个不影响是不是回文字符串

  3. 然后利用回文字符串的规则,进行比较,如果符合,就接着遍历。同时记录相关的位置信息

  4. 最后利用 substring 返回子字符串

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
string longestPalindrome(string s) {
int low_bound = 0,high_bound = 0,max_len = 0,temp = 0,result_low = 0;
if((s.empty()) || (s.size() == 1))
{
return s;
}
else
{
for(int i = 0;(high_bound+1) < s.size() && max_len <= s.size();)
{
low_bound = i;
high_bound = i;
while(s[high_bound] == s[high_bound + 1] && (high_bound + 1) < s.size())
{
i = high_bound + 1;
++high_bound;
}
for(;low_bound > 0 && (high_bound+1) < s.size() && s[low_bound - 1] == s[high_bound + 1];--low_bound,++high_bound);
temp = high_bound -low_bound + 1;
if(temp > max_len)
{
max_len = temp;
result_low = low_bound;
}
i++;
}
return s.substr(result_low,max_len);
}
}
};

6. ZigZag Conversion

Medium

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3
P   A   H   N
A P L S I I G
Y I R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

1
string convert(string s, int numRows);

Example 1:

1
2
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

1
2
3
4
5
6
7
8
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P I N
A L S I G
Y A H R
P I

分析:

  1. 感觉自己在前期做题的时候,确实没有想任何相关的编程技巧。都是自己想逻辑,然后自己把实现了。
  2. 这个自己的思路,就是申请一个 vector 来按一定的规则来存放传入的 s,因为我们看 Explanation 可以发现,这就是一种存储规则
  3. 存储完后,在用 for-each 循环再传入到一个result就可以了。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
string convert(string s, int numRows) {
vector<string> result(numRows);
string::iterator in = s.begin();
if (numRows > 1)
{
int cycle_num = 2 * numRows - 2;
for(int i = 0;i<cycle_num;)
{
if(in != s.end())
{
if(i < numRows)
{
result[i] += *in;
++in;
++i;
i = i%cycle_num;
}
else
{
result[cycle_num - i] += *in;
++in;
++i;
i = i%cycle_num;
}
}
else
{
break;
}
}
string result_str;
for(auto i : result)
{
result_str += i;
}
return result_str;
}
else
{
string result_str = s;
return result_str;
}

}
};

7. Reverse Integer

Easy

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

分析:

  1. 感觉自己也是挺赖的,用了 to_string 转字符串,然后还用了 stoi 转会 int。可能第一遍刷的时候确实只是在解决问题,却不是最好的解决问题。
  2. 这题也就是简单的情况判断。大于 0 以及 小于 0 的情况,末尾几位为 0 的情况,最后如果溢出如何操作。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int reverse(int x) {
int i = 0;
int temp = x;
string int_string = to_string(x);
int result = 0;
while (temp != 0)
{
if ((temp % 10) == 0)
{
++i;
temp = temp / 10;
}
else
{
break;
}
}
if (x >= 0)
{
std::reverse(int_string.begin(), int_string.end() - i);
}
else if (x < 0)
{
std::reverse(int_string.begin() + 1, int_string.end() - i);
}
string result_string(int_string,0,int_string.size()-i);
try
{
result = std::stoi(result_string);
}
catch(std::out_of_range err)
{
return 0;
}

return result;
}
};

8. String to Integer (atoi)

Medium

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

1
2
Input: "42"
Output: 42

Example 2:

1
2
3
4
Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.

Example 3:

1
2
3
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

1
2
3
4
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

1
2
3
4
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.

分析:

  1. 依然是自己硬想的逻辑,真的是太菜了。。。
  2. 这个题目也是不断的逻辑处理。先是删除掉前面的所有空格。分正负情况,将数字提取出来,然后判断有没有溢出,就完成了。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class Solution {
public:
int myAtoi(string str) {
int result = 0;
string s;
if(str.empty())
{
return 0;
}
else
{
str.erase(0,str.find_first_not_of(" "));
if(str[0] >= '0' && str[0] <= '9')
{
int i = 0;
while(str[i] >= '0' && str[i] <= '9' && i <str.size())
{
++i;
}
s = str.substr(0,i);
s.erase(0,s.find_first_not_of("0"));
if(s.empty())
{
return 0;
}
if(s.size() >= 10)
{
if(s.size() > 10)
{
return 2147483647;
}
else
{
if(s > "2147483647")
{
return 2147483647;
}
}
}
for(i = 0;i < s.size();i++)
{
result = (result * 10 + (s[i] - '0'));
}
return result;

}
else if(str[0] == '-')
{
int i = 1;
while(str[i] >= '0' && str[i] <= '9' && i < str.size())
{
s += str[i];
++i;
}
s.erase(0,s.find_first_not_of("0"));
if(s.empty())
{
return 0;
}
if(s.size() >= 10)
{
if(s.size() > 10)
{
return -2147483648;
}
else
{
if(s >= "2147483648")
{
return -2147483648;
}
}
}
for(i = 0;i < s.size();i++)
{
result = result * 10 + (s[i] - '0') ;
}
return -result;
}
else if(str[0] == '+')
{
int i = 1;
while(str[i] >= '0' && str[i] <= '9' && i < str.size())
{
s += str[i];
++i;
}
if(s.size() >= 10)
{
if(s.size() > 10)
{
return 2147483647;
}
else
{
if(s >= "2147483647")
{
return 2147483647;
}
}
}
for(i = 0;i < s.size();i++)
{
result = result * 10 + (s[i] - '0') ;
}
return result;
}
else
{
return 0;
}
}

}
};

9. Palindrome Number

Easy

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

1
2
Input: 121
Output: true

Example 2:

1
2
3
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

1
2
3
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

分析:

  1. 虽然题目说不要使用 integer to a string,但是那样自己想的办法也就是取出每一位,然后重新构造一个数,看是否相等。
  2. 我这里直接也就直接转 string 然后 reverse 判断是否相等。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool isPalindrome(int x) {
auto str_x = std::to_string(x);
std::string str_y(str_x);
reverse(str_y.begin(),str_y.end());
if(str_x == str_y)
{
return true;
}
else
{
return false;
}
}
};

10. Regular Expression Matching

Hard

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

1
2
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

1
2
3
4
5
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

1
2
3
4
5
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

1
2
3
4
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

分析 :

  1. 这题我个人觉得也是非常好,刚开始结合自己刚刚学习编译原理的原因,想弄个递归下降子程序,以及弹栈的思想。后来发现 * 不是很好处理,所以干脆直接递归处理,这也算是动态规划了吧。
  2. 首先将一些能直接返回的情况,判断完。然后就涉及到一些需要进一步判断的情况。
  3. 正常的字母匹配都不是关键的地方,这题的难度在于 .* 以及 [a-z]* 的 处理。
  4. 对于 [a-z]* 。因为 * 可以不匹配,所以我们还要判断不匹配的情况,是否能成功。这里直接使用递归,然后如果不匹配不成功的话,然后我们就需要接着判断到底匹配几个,这里又需要我们写循环,再循环里我们需要递归判断。成功的话,直接返回就好了。
  5. 对于 .* 。同样也是要判断表示是否匹配,以及匹配几个的问题。所以同样是递归来进行判断。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
class Solution {
public:
bool isMatch(string s, string p) {
if(s.empty() && p.empty())
{
return true;
}
if(s.empty() && (!p.empty()))
{
if(p.size() % 2 != 0)
{
return false;
}
else
{
for(int i = 1;i < p.size();i += 2)
{
if(p[i] != '*')
{
return false;
}
}
return true;
}
}
if((!s.empty()) && p.empty())
{
return false;
}
int i = 0,j = 0;
for(i = 0, j = 0;i < s.size() && j < p.size();)
{
if(j != (p.size()-1))
{
if(p[j] >= 'a' && p[j] <= 'z')
{
if(p[j+1] >= 'a' && p[j+1] <= 'z')
{
if(s[i] == p[j])
{
++i;
++j;
} else
{
return false;
}
}
else if(p[j+1] == '*')
{
while((j+3) < p.size())
{
if(p[j + 2] == p[j] && p[j+3] == '*')
{
j += 2;
}
else
{
break;
}
}
if(isMatch(s.substr(i),p.substr(j+2)))
{
return true;
}
else
{
while(s[i] == p[j])
{
if(isMatch(s.substr(i),p.substr(j + 2)))
{
return true;
}
++i;
}

j+=2;
}
}
else if(p[j+1] == '.')
{
if(s[i] == p[j])
{
++i;
++j;
}
else
{
return false;
}
}
}
else if(p[j] == '.')
{
if(p[j+1] >= 'a' && p[j+1] <= 'z')
{
++i;
++j;
}
else if(p[j+1] == '*')
{
if(p.substr(j + 2).empty())
{
return true;
}
else
{
while(i <= s.size())
{
if(isMatch(s.substr(i),p.substr(j+2)))
{
return true;
}
++i;
}
return false;
}
}
else if(p[j+1] == '.')
{
++i;
++j;
}
}
}
else if(j == p.size() - 1)
{
if(i == s.size() -1)
{
if((p[j] == '.') || (s[i] == p[j]))
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}

}
}
if(isMatch(s.substr(i),p.substr(j)))
{
return true;
}
else
{
return false;
}
}
};

11. Container With Most Water

Medium

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

img

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

1
2
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

分析:

  1. 这题就是一个数学题吧,整体思路也比较清晰。
  2. 首先从头尾开始往中间进行遍历,因为宽度一直在减小,如果高度还减小,肯定是没有前种情况大的。所以我们一直遍历到,高度比前面大的情况。可以大大减少时间复杂度。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0,j = (height.size()-1);
int min_height = 0;
int water = 0;
while(i < j)
{
min_height = min(height[i],height[j]);
water = max(water,min_height * (j-i));
while(height[i] <= min_height && i<j)
{
++i;
}
while(height[j] <= min_height && i<j)
{
--j;
}
}
return water;
}
};

12. Integer to Roman

Medium

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

1
2
Input: 3
Output: "III"

Example 2:

1
2
Input: 4
Output: "IV"

Example 3:

1
2
Input: 9
Output: "IX"

Example 4:

1
2
3
Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

1
2
3
Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

分析:

  1. 同样是正常的分类逻辑,完成逻辑即可

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
string intToRoman(int num) {
string result;
for(;num >= 1000;num = num - 1000,result += "M");
for(;num >= 500;)
{
num = num - 500;
if(num / 100 == 4)
{
result += "CM";
num = num - 400;
}
else
{
result += "D";
}
}
for(;num >= 100;)
{
if(num / 100 == 4)
{
result += "CD";
num = num - 400;
}
else
{
num = num - 100;
result += "C";
}

}
for(;num >= 50;)
{
num = num - 50;
if(num / 10 == 4)
{
result += "XC";
num = num - 40;
}
else
{
result += "L";
}
}
for(;num >= 10;)
{
if(num / 10 == 4)
{
result += "XL";
num = num - 40;
}
else
{
result += "X";
num -= 10;
}

}
for(;num >= 1;)
{
if(num >= 5)
{
if(num % 5 == 4)
{
result += "IX";
num -= 9;
}
else
{
num = num % 5;
result += "V";
}

}
else
{
if(num == 4)
{
result += "IV";
break;
}
else
{
result += "I";
num--;
}
}

}
return result;
}
};

13. Roman to Integer

Easy

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

1
2
Input: "III"
Output: 3

Example 2:

1
2
Input: "IV"
Output: 4

Example 3:

1
2
Input: "IX"
Output: 9

Example 4:

1
2
3
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

1
2
3
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

分析:

  1. 用两个 vector 来存储相关的字符与数字的对应关系。
  2. 我们整体逻辑就是取位置的差距,然后去另一个 vector 找对应的值。当然要判断是不是特殊情况,整体逻辑也不是很难。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
int romanToInt(string s) {
int num_result = 0;
vector<char> roman_char{ 'I','V','X','L','C','D','M' };
vector<int> romen_int{ 1,5,10,50,100,500,1000 };
string::reverse_iterator in = s.rbegin();

vector<char>::iterator iter = find(roman_char.begin(), roman_char.end(),*in);
auto dis = distance(roman_char.begin(), iter);

int temp = dis;
num_result += romen_int[dis];
++in;

for (unsigned int i = 1; i < s.size(); i++)
{
iter = find(roman_char.begin(), roman_char.end(), *in);
dis = distance(roman_char.begin(), iter);
if (dis >= temp)
{
num_result += romen_int[dis];
temp = dis;
++in;
}
else
{
num_result -= romen_int[dis];
temp = dis;
++in;
}
}
return num_result;
}
};

14. Longest Common Prefix

Easy

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

分析:

  1. 首先取所有字符串的最短长度

  2. 然后我们从 0 开始遍历,直到找到不是公共子串的长度。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty())
{
return "";
}
else
{
int min_size = strs[0].size();
int flag = 0;
string result;
for(auto i : strs)
{
if(i.size() < min_size)
{
min_size = i.size();
}
}
for(int j = 0;j < min_size;++j)
{
string temp = strs[0].substr(0,(j+1));
flag = 0;
for(auto str:strs)
{
if(str.substr(0,(j+1)) != temp)
{
++flag;
}
}
if(flag == 0)
{
result = temp;
}
}
return result;
}
}
};

15. 3Sum

Medium

Given an array nums of n integers, are there elements a, b, c in numssuch that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

分析:

  1. 这题我们需要将数组进行排序来减小时间复杂度
  2. 然后我们固定一个位置,将整个问题变成一个子问题。子问题就是在子数组里面找到对应的和为要求值的位置。然后不断增加 i 即可。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& num) {
vector<vector<int> > res;

std::sort(num.begin(), num.end());

for (int i = 0; i < num.size(); i++) {

int target = -num[i];
int front = i + 1;
int back = num.size() - 1;

while (front < back) {

int sum = num[front] + num[back];

if (sum < target)
front++;

else if (sum > target)
back--;

else {
vector<int> triplet(3, 0);
triplet[0] = num[i];
triplet[1] = num[front];
triplet[2] = num[back];
res.push_back(triplet);

while (front < back && num[front] == triplet[1]) front++;

while (front < back && num[back] == triplet[2]) back--;
}

}

while (i + 1 < num.size() && num[i + 1] == num[i])
i++;

}

return res;

}
};

16. 3Sum Closest

Medium

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

1
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

分析:

  1. 整体思路同样类似于上面那题

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {

int result = -2000000000; //返回保存结果
sort(nums.begin(),nums.end()); // 排序

for(int i = 0;i < (nums.size()-2);i++)
{
int low_margin = i + 1;
int high_margin = nums.size() - 1;
for(low_margin = i + 1 ; low_margin != high_margin ;) //遍历过程
{
int temp = (nums[i] + nums[low_margin] + nums[high_margin]);
int distance = abs(result - target);

if (temp == target) {
return target;
} else if (temp > target) {
if ((temp - target) < distance) {
result = temp;
}
--high_margin;
} else if (temp < target) {
if ((target - temp) < distance) {
result = temp;
}
++low_margin;
}
}
}
return result;
}
};

17. Letter Combinations of a Phone Number

Medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

img

Example:

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

分析:

  1. 这题主要就是如何完成笛卡尔积,当然 python 很好完成
  2. 在 c++ 中笛卡尔积可以用递归,或者我这种方法。就是将大小提取出来,然后写循环。

mySolution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
vector<string> letterCombinations(string digits) {

const vector<string> number_letter{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //声明一个包含规则的 vector
vector<string> temp_number_letter; //存储需要使用到的 vector
int total_size = 1; //存储笛卡尔积的 size 大小
vector<string> result;

if(digits.empty())
{
return result;
}

for(auto i:digits)
{
temp_number_letter.push_back(number_letter[ (i - '0') - 2]);
}

for(auto i:temp_number_letter)
{
total_size *= i.size();
}
for( int i = 0 ; i < total_size ; ++i )
{
string loop_temp;
int m = 0,n = i;

for(auto r_iter : temp_number_letter)
{
//n = n % temp_number_letter[r_iter].size();
//loop_temp += temp_number_letter[r_iter][n];
m = n % r_iter.size();
n = n / r_iter.size();
loop_temp += r_iter[m];
}
result.push_back((loop_temp));
}
sort(result.begin(),result.end());
return result;
}
};

18. 4Sum

Medium

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

分析:

  1. 我个人的想法就是将其转换成子问题
  2. 子问题就是 3sum,然后就可以完成了。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Solution {

private:
vector<vector<int>> threeSum(vector<int>& num,int target) { // 提供给下面 fourSum 的接口

vector<vector<int> > result; // 返回的值
//vector<int> temp; // 作为中间值添加进结果

//std::sort(num.begin(), num.end()); //将传进来的值排序

for(unsigned int i = 0 ; i < num.size() - 2 ; ++i)
{
unsigned int num_media = i + 1; // 中间的那个值
unsigned int num_right = num.size() - 1; // 右边的那个值

if(( num[i] + num[i+1] + num[i+2]) > target)
{
break;
}

if(( num[i] + num[num_right - 1] + num[num_right]) < target)
{
continue;
}

for( num_media = i + 1 ;num_media < num_right; )
{
int temp = num[i] + num[num_media] + num[num_right] ;
if( temp < target )
{
++num_media;
}
else if ( temp == target )
{
result.push_back({num[i],num[num_media],num[num_right]});
++num_media;
--num_right;
}
else if( temp > target )
{
--num_right;
}
}
}
return result;
}

public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {

vector<vector<int> > result; //返回值

if(nums.size() < 4)
{
return result;
}

std::sort(nums.begin(), nums.end()); //排序

for( unsigned int i = 0; i < (nums.size() - 3) ; ++i)
{
int threeSum_target = target - nums[i];
vector<vector<int>> threeSum_result;
vector<int> threeSum_num(nums.begin() + i + 1, nums.end());

if(( nums[i] + nums[i+1] + nums[i+2] + nums[i+3]) > target)
{
break;
}

if(( nums[i] + nums[nums.size() - 3] + nums[nums.size() - 2] + nums[nums.size() - 1]) < target)
{
continue;
}


threeSum_result = threeSum(threeSum_num, threeSum_target);

for(auto num:threeSum_result)
{
vector<int> temp;
temp.push_back( nums[i] );
temp.insert(temp.end(),num.begin(),num.end());
if( find(result.begin(),result.end(),temp) != result.end() )
{
continue;
}
else
{
result.push_back(temp);
}

}
}
return result;
}
};

19. Remove Nth Node From End of List

Medium

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

分析:

  1. 比较正常的链表题

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {

ListNode* temp = head;
int length = 1;

if(head == NULL)
{
return NULL;
}

while(temp->next != NULL)
{
temp = temp->next;
++length;
}

if(length == 1 && n == 1)
{
return NULL;
}

if(length == n)
{
head = head->next;
return head;
}


length = length - 1 - n;
temp = head;

while(length != 0)
{
temp = temp->next;
--length;
}

ListNode* del_node = temp->next;

temp->next = temp->next->next;

delete del_node;

return head;

}
};

20. Valid Parentheses

Easy

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

分析:

  1. 如果学习过编译原理,很好理解,利用栈的语法判断

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
bool isValid(string s) {
vector<char> stack;
for(auto i : s)
{
if(i == '(' || i == '{' || i == '[')
{
stack.push_back(i);
}
else if(i == ')')
{
if(stack.empty())
{
return false;
}
else if(stack.back() == '(')
{
stack.pop_back();
}
else
{
return false;
}
}
else if(i == '}')
{
if(stack.empty())
{
return false;
}
else if(stack.back() == '{')
{
stack.pop_back();
}
else
{
return false;
}
}
else if(i == ']')
{
if(stack.empty())
{
return false;
}
else if(stack.back() == '[')
{
stack.pop_back();
}
else
{
return false;
}
}
}
if(stack.empty())
{
return true;
}
else
{
return false;
}

}
};

21. Merge Two Sorted Lists

Easy

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

分析:

  1. 常规的链表题

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode* l1_temp = l1;
ListNode* l2_temp = l2;
ListNode* head = new ListNode(0);
ListNode* head_temp = head;

while(l1_temp != NULL && l2_temp != NULL)
{
if(l1_temp->val > l2_temp->val)
{
head_temp->next = l2_temp;
head_temp = head_temp->next;
l2_temp = l2_temp->next;
}
else if(l1_temp->val == l2_temp->val)
{
head_temp->next = l1_temp;
head_temp = head_temp->next;
l1_temp = l1_temp->next;
head_temp->next = l2_temp;
head_temp = head_temp->next;
l2_temp = l2_temp->next;
}
else if(l1_temp->val < l2_temp->val)
{
head_temp->next = l1_temp;
l1_temp = l1_temp->next;
head_temp = head_temp->next;
}
}
while(l1_temp != NULL)
{
head_temp->next = l1_temp;
head_temp = head_temp->next;
l1_temp = l1_temp->next;
}
while(l2_temp != NULL)
{
head_temp->next = l2_temp;
head_temp = head_temp->next;
l2_temp = l2_temp->next;
}
return head->next;
}
};

22. Generate Parentheses

Medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

分析:

这题是一道非常好的训练递归思想的题目。

  1. 我们确立是递归类型的问题
  2. 我们寻找递归的规律,我们发现整体思路,就是要想是合法的就得一直确保插入过程当中剩下的左括号的数量不能多于右括号(想不明白,可以自己仔细思考一下),所以就写出了以下程序。

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;

if (n <= 0)
{
return result;
}

recursive_func(n,n,"",result);

return result;
}

void recursive_func(int left_num , int right_num , string temp , vector<string> &result)
{
if( left_num == 0 && right_num == 0)
{
result.push_back(temp);
return ;
}
if( left_num > 0)
{
recursive_func( left_num-1 , right_num , temp+"(" ,result);
}
if( left_num < right_num)
{
recursive_func( left_num , right_num-1 , temp+")" ,result);
}
}
};

28. Implement strStr()

Easy

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

个人分析:

  1. 模拟strstr() 函数
  2. 我个人的想法可能就是寻找第一个字符匹配的位置,匹配后面。
  3. !KMP算法

mySolution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int strStr(string haystack, string needle) {
int i = 0,j = 0;
if(needle.empty())
{
return 0;
}
if((needle.size() > haystack.size()) || haystack.empty())
{
return -1;
}
for(i = 0;i < haystack.size();i++)
{
int temp = i ;
int temp_j = j;
while (haystack[temp] == needle[temp_j])
{
if(temp_j == needle.size() - 1)
{
return i;
}
temp++;
temp_j++;
}
}
return -1;
}
};