本篇文章置顶,长期更新,用于记录日常刷题题解以及需要注意的tip。

2019年的关键词:思路要紧!


28/5/2019

116.Populating Next Right Pointers in Each Node,117

这一题看leetcode上的表示方式十分的唬人,实际上还算是比较简单。思路就是层次遍历,然后每次遍历用两个数来维护每一层的遍历次数。在元素进队列的时候进行左右的连接。(116的树为完全树,117的树不是完全树,同样的做法)

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
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if root == None:
return root
que = []
que.append(root)
count = 1
record = 0
while len(que) > 0:
node = que.pop(0)
count -= 1
if node.left:
que.append(node.left)
record += 1
if len(que)>1:
que[-2].next = que[-1]
if node.right:
que.append(node.right)
record += 1
if len(que)>1:
que[-2].next = que[-1]

if count == 0:
node.next = None
count = record
record = 0
return root

21/5/2019

103. Path Sum II

思路:这一题可以沿着深度遍历的方向去做,然后在遍历的过程中,记录下路径。然后判断,当前path上的元素之和是否等于sum,并且当前节点是叶子结点。划重点:sum(path) + root.val 之和来判断,而不是把所有val都加到path上。

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def __init__(self):
self.result = []
def find_path(self,root,sums,path):
if root == None:
return
if sum(path) + root.val == sums and root.left == None and root.right == None:
self.result.append((path+[root.val])[:])
return

path.append(root.val)
self.find_path(root.left,sums,path)
self.find_path(root.right,sums,path)
if path!=[]:
path.pop()


def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
path = []
self.find_path(root,sum,path)
return self.result

114.Flatten Binary Tree to Linked List

思路:这一题太巧妙啦,要把所有节点压到右支上,这时候用的方法是先后续遍历,用一个变量记录上一个节点,然后作为当前节点的右节点,同时砍掉当前的左节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
self.prev = None
def dfs(root):
if root == None:
return None
dfs(root.right)
dfs(root.left)
root.right = self.prev
root.left = None
self.prev = root
dfs(root)

19/4/2019

107. Binary Tree Level Order Traversal II

思路:哇,类似的专题好多啊,这一题要求按层次,从最后一层依次打印到第一层,与前面几题的区别在于,每次将层插入第一个位置。

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
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
line =[root]
if root == None:
return res
num = 1
val = []
while len(line):
node = line.pop(0)
num-=1
val.append(node.val)
if node.left:
line.append(node.left)
if node.right:
line.append(node.right)
if num == 0:
res.insert(0,val[:])
val = []
num = len(line)
return res

18/4/2019

102. Binary Tree Level Order Traversal

思路:层次遍历一棵树,最近做的题都比较接地气啊,都是大一做的题,哈哈我感觉记得这么清楚全要谢谢林老师。这一题要求把每一行的的元素依次打印出来,每一行一个list。

用队列结构来处理这个问题。首先从根节点开始,依次进队列,每次循环头节点出队列,并将其子节点进队列。然后维护一个计数器,计数器初始化为每一行list长度,当这个变量变成0的时候说明这一行已经遍历完成了。重新开一个list。

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
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
if root == None:
return res
line = []
line.append(root)
val = []
num = 1
while len(line):
node = line.pop(0)
val.append(node.val)
num -= 1
if node.left != None:
line.append(node.left)
if node.right != None:
line.append(node.right)
if num == 0:
res.append(val)
val = []
num = len(line)
return res

103. Binary Tree Zigzag Level Order Traversal

思路:这一题沿着Z字形进行输出,只需要在上一题的基础上加一个记录层数的变量即可。

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(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
if root == None:
return res
line = []
line.append(root)
val = []
num = 1
level = 0
while len(line):
node = line.pop(0)
num -= 1
val.append(node.val)
if node.left:
line.append(node.left)
if node.right:
line.append(node.right)
if num == 0:
num = len(line)
if level%2 == 1:
val.reverse()
res.append(val)
else:
res.append(val)
val = []
level += 1
return res

15/4/2019

96. Unique Binary Search Trees

思路:这一题说给一个数字,求出所有平衡二叉树的个数。根据平衡二叉树的性质可以知道,左子树小于根节点,右子树大于根节点。因此有这种关系:

f(1) = f(0) x f(2), f(2)=f(1) x f(1), … f(n) = f(n-1)xf(0)

1
2
3
4
5
6
7
8
class Solution(object):
def numTrees(self,n):
res = [0] *(n+1)
res[1] = 1
for i in range(1,n+1):
for j in range(j):
res[i] += res[j]*res[i-j-1]
return res

94. Binary Tree Inorder Traversal

这一题要求按中序遍历的方式输出一颗二叉树。可用递归的方式解决。想起这道题,林老师上课的画面迎面而来,哈哈。

中序遍历思路为沿着树的枝往下走,当回溯时,第二次遇到这个节点的时候返回,此时记录下遍历的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def __init__(self):
self.res = []
def dfs(self,root):
if root == None:
return
self.dfs(root.left)
self.res.append(root.val)
self.dfs(root.right)

def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.dfs(root)
return self.res

101. Symmetric Tree

思路:这一题判断树是否是镜像。用树的结构进行递归,每次递归判断是否为镜像,如果不是则返回False。每次进行递归的时候传入树的对称边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def dfs(self,left,right):
if left == None or right == None:
if left != right:
return False
else:
return True
if left.val != right.val:
return False
return self.dfs(left.left,right.right) and self.dfs(left.right,right.left)

def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
return self.dfs(root.left,root.right)

25/3/2019

92. Reverse Linked List II

分析:这一题需要定义头节点,关于元素的调换的问题,都需要定义头节点。然后记住tail,head,思路清晰一点,就很好做了。

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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
if m == n:
return head
dummy = ListNode(-1)
dummy.next = head
p = dummy
newhead = p
for i in range(m):
newhead = p
p = p.next
tail = p
q = p
p = p.next
for i in range(n-m):
p_pre = p.next
p.next = q
q = p
p = p_pre
tail.next = p_pre
newhead.next = q
return dummy.next

93. Restore IP Addresses

分析:这一题蛮有意思的我感觉。它的内循环是从1到3,即截取的字符长度,每个截取的长度都作为ip地址的一部分。每次截取子串的时候需要对他们进行合法性判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def __init__(self):
self.res = []
def helper(self,s,ret,index,count):
if count>4:
return
if count == 4 and index == len(s):
self.res.append(res[:-1])
for i in range(1,4):
if i + index > len(s):
break
temp = s[index,index+i]
if (temp[0] == '0' and len(temp)>1) and (len(temp) and int(temp)>=256):
continue
helper(s,ret+temp+'.',index+i,count+1)
def restoreIpAddresses(self,s):
self.helper(s,'',0,0)
return self.res

24/3/2019

91. Decode Ways

分析:这一题是典型的动态规划题,主要就是想到状态转移方程该怎么写就行了。有几种情况要进行分析。首先当前位置上为0的时候,当前的字母需要与前一个字母组成一个合法数据才行。否则就是按照正常的方式单个字母,两个字母的方式。

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
class Solution(object):
def numDecodings(self, s): # 动态规划
"""
:type s: str
:rtype: int
"""
if len(s) == 0 or s[0] == '0':
return 0
dp = [0]*len(s)
dp[0] = 1
for i in range(1,len(s)):
if s[i] == '0':
# 必须与前一个组成一个二位数
if s[i-1] == '2' or s[i-1] == '1' :
if i == 1:
dp[i] = 1
else:
dp[i] = dp[i-2]
elif int(s[i-1:i+1])<=26 and s[i-1]!='0':
if i == 1:
dp[i] = 2
else:
dp[i] = dp[i-1]+dp[i-2]
else:
dp[i] = dp[i-1]

return dp[len(s)-1]

23/3/2019

这两天的状态和前两天一样,没办法调整🤢

90. Subsets II

这题用递归的方法做,我觉得在做题的时候应该要多总结思路,首先就要确定这一题是什么类型的题目。然后向方法,一定唔要无头苍蝇似的,面试题差不多就median了,加油咯⛽️。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def dfs(self,nums,pos,temp,res):
if sorted(temp) not in res:
res.append(sorted(temp))
for i in range(pos,len(nums)):
temp.append(nums[i])
self.dfs(nums,i+1,temp,res)
temp.pop()

def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
if len(nums) == 0:
return []
self.dfs(nums,0,[],res)
return res

这一题有一个地方,需要注意一下,就是深浅拷贝的问题。(错过的问题)

1
2
3
4
5
6
7
8
temp = [1,2,3]
a = temp # 浅拷贝,a随着temp而变化
a = temp[:] # 深拷贝,a与temp无关
import copy
a = copy.deepcopy(temp) # 深拷贝
## 排序问题
a.sort() # 直接改变a
sorted(a) # 返回值为排序后的结果

89. Gray Code

分析:这一题本来想要递归的方法来做,但是奈何,递归不满足格雷码依次变一位的原则。因此本题采用格雷码的公式求解。G(i) = i ^ (i/2)

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
res = []
for i in range(1<<n):
res.append(i^i>>1)
return res

21/3/2019

100. Same Tree

最近有点儿奇怪呀, 明天想着做的事情,都没能做起来。

分析: 这一题用递归调用的方式求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p == None:
return q==None
if q == None:
return False
if p.val != q.val:
return False
return self.isSameTree(p.right,q.right) and self.isSameTree(p.left,q.left)

18/3/2019

73. Set Matrix Zeroes

一直想刷题一直没刷,很惭愧。

分析: 这一题是找出行活列含1的数,然后将整行置0。对呀python的数组,可以整行整行的赋值:

1
2
3
4
matrix[key] = [0]*n   # 对key这一行整行赋值
#对列赋值,不可以整行
for i in range(n):
matrix[i][key] = 1
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
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
dict_x = {}
dict_y = {}
if len(matrix) == 0:
return
if len(matrix[0]) == 0:
return
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
if i not in dict_x:
dict_x[i] = 1
if j not in dict_y:
dict_y[j] = 1
for key in dict_x.keys():
matrix[key] = [0]*n
for key in dict_y.keys():
for i in range(m):
matrix[i][key] = 0

77. Combinations

分析:这一题目的就是用递归的方式来求解,需要记住的是上一次的递归起点。需要注意的一点是,当一个list要添加另一个list作为一项时,使用:list.append(list1[:])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def dfs(self,n,idx,k,res,cur):
if k == 0:
res.append(cur[:])
else:
for i in range(idx,n):
if k > n-i:
return []
cur.append(i+1)
self.dfs(n,i+1,k-1,res,cur)
cur.pop()
def combine(self,n,k):
res = []
cur = []
dfs(n,0,k,res,cur)
return res

78. Subsets

分析:这一题的思路是,看到这种递归问题,想到需要用循环来做。需要所有长度的情况都考虑进去。需要把所有的长度都考虑进去。因此要维护一个长度,由于不重复,因此需要维护一个下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def dfs(self,nums,idx,ilen,res,cur):
if ilen > len(nums):
return
if len(cur) == ilen:
res.append(cur[:])
for i in range(idx,len(nums)):
cur.append(nums[i])
self.dfs(nums,i+1,ilen+1,res,cur)
cur.pop()

def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
cur = []
self.dfs(nums,0,0,res,cur)
return res

80. Remove Duplicates from Sorted Array II

这题从头扫描到尾巴,当情况符合的时候进行覆盖。le表示重复的个数,每一次覆盖条件满足都需要覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
le = 0
pos = 0
for i in range(1,len(nums)):
if nums[i-1] == nums[i]:
le += 1
if le<2:
pos+=1
nums[pos] = nums[i]
else:
le = 0
pos+=1
nums[pos] = nums[i]
# nums[pos] = nums[len(nums)-1]
return pos+1

14/3/2019

分析: 犹豫要不要用python刷题,发现python实在是方便,这一题用stack的思路来做。首先用/把字符进行分割,然后用一个dict组织。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
str = path.split('/')
res = []
for ch in str:
if ch == '..':
if len(res) != 0:
res.pop()
elif ch!='' and ch!='.':
res.append(ch)
ans = '/'
for ch in res:
ans += ch+'/'
if len(ans) == 1:
return ans
return ans[:len(ans)-1]

11/3/2019

63. Unique Paths II

分析:用动态规划做,递推公式为:$path[i][j] = path[i-1][j]+path[i][j-1]$。需要先把第一行和第一列先填上1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if(obstacleGrid.size() == 0||obstacleGrid[0].size() == 0) return 0;
if(obstacleGrid[0][0] == 1 ) return 0;
int height = obstacleGrid.size();
int width = obstacleGrid[0].size();
vector<vector<double>> path(height,vector<double>(width,0));
for(int i = 0;i<width&&obstacleGrid[0][i]!=1;i++){
path[0][i] = 1;
}
for(int i = 1;i<height&&obstacleGrid[i][0]!=1;i++){
path[i][0] = 1;
}
for(int i = 1;i<height;i++){
for(int j = 1;j<width;j++){
if(obstacleGrid[i][j] == 1) continue;
path[i][j] = path[i-1][j]+path[i][j-1];
}
}
return path[height-1][width-1];
}
};

64. Minimum Path Sum

分析:这一题和上一题差不多,唯一的区别在于这一题是找到最小的代价,因此去min就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0 || grid[0].size() == 0) return 0;
int height = grid.size();
int width = grid[0].size();
for(int i = 1;i<width;i++){
grid[0][i] += grid[0][i-1];
}
for(int j = 1;j<height;j++){
grid[j][0] += grid[j-1][0];
}
for(int i = 1 ;i<height;i++){
for(int j = 1;j<width;j++){
grid[i][j] += min(grid[i-1][j],grid[i][j-1]);
}
}
return grid[height-1][width-1];
}
};

65. Valid Number

分析:字符串的转移这种问题很讨厌啊,情况太多了,总之思路就是从头到位扫一遍,判断很多边界情况。

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
class Solution {
public:
bool isNumber(string s) {
if( !s.empty() ){
s.erase(0,s.find_first_not_of(" "));
s.erase(s.find_last_not_of(" ") + 1);
}
if(s.size() == 0) return false;
if(s.size() == 1&&s[0] == '.') return false;
unordered_map<char,int> amap;
amap['-'] = 0;
amap['+'] = 0;
amap['.'] = 0;
amap['e'] = 0;
int i = 0;
int flag = 0;
while(i<s.size()){
if('0'<=s[i]&&s[i]<='9'){
flag = 1;
i++;
continue;
}
if(s[i] == '-'||s[i] == '+'){
if(amap['-'] + amap['+'] > 0){
if(i>0&&s[i-1]=='e'){
i++;
if(i>=s.size()) return false;
continue;
}else{
return false;
}
}
else{
if(i!= 0&&s[i-1]!='e') return false;
i++;
if(i>=s.size()) return false;
continue;
}
amap[s[i]]++;
i++;
if(i>=s.size()) return false;
continue;
}
if(s[i] == '.'){
if(amap['.'] != 0) return false;
if(amap['e']!=0) return false;
if(i==0||('0'<=s[i-1]&&s[i-1]<='9')){
i++;
amap['.']++;
continue;
}
if(s[i-1]=='-'||s[i-1]=='+'){
i++;
amap['.']++;
continue;
}
}
if(s[i] == 'e'){
if(amap['e']!=0) return false;
if(i>0&&('0'<=s[i-1]&&s[i-1]<='9')){
i++;
amap['e']++;
if(i>=s.size()) return false;
continue;
}
if(s[i-1]=='.'&&flag == 1){
i++;
amap['e']++;
if(i>=s.size()) return false;
continue;
}
}
return false;
}
if(amap['.']||amap['-']||amap['+']){
if(flag == 0) return false;
}
return true;
}
};

69. Sqrt(x)

分析:这一题用二分法做比较快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int mySqrt(int x) {

// int a = 0;
// a = sqrt(x);
// return a;
int l = 1;
int r = x;
while(l<=r){
int m = l+(r-l)/2;
if(m>(x/m)){
r = m-1;
}
else{
l = m+1;
}
}
return l-1;
}
};

10/3/2019

54. Spiral Matrix

分析:这一题用最简单的四个循环这种思路求救最合适!然后需要注意的是,在对边界进行缩减的时候,需要保证仍然满足begin<end的条件。

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
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if(matrix.size() == 0 || matrix[0].size() == 0)
return res;
int rowbegin = 0;
int rowend = matrix.size()-1;
int colbegin = 0;
int colend = matrix[0].size()-1;
while(rowbegin<=rowend&&colbegin<=colend){
for(int i = colbegin;i<=colend;i++){
res.push_back(matrix[rowbegin][i]);
}
rowbegin++;
for(int i = rowbegin;i<=rowend;i++){
res.push_back(matrix[i][colend]);
}
colend--;
if(rowbegin>rowend || colbegin>colend) return res;
for(int i = colend;i>=colbegin;i--){
res.push_back(matrix[rowend][i]);
}
rowend--;
if(rowbegin>rowend || colbegin>colend) return res;
for(int i = rowend;i>=rowbegin;i--){
res.push_back(matrix[i][colbegin]);
}
colbegin++;
}
return res;
}
};

55. Jump Game

分析:与某一题很类似,总之记住记住当前位置能达到的最远距离的方法来求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.size() <= 1){
return true;
}
int lastindex = 0;
int cur = 0;
while(lastindex<nums.size()){
cur = max(lastindex+nums[lastindex],cur);
if(cur>=nums.size()-1) return true;
if(cur==lastindex && nums[lastindex] == 0) return false;
lastindex++;
}
return true;
}
};

59. Spiral Matrix II

分析:这一题属于构造nxn的一个数组,可以按照读取的方式进行构造。

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
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n,vector<int>(n,0));
if(n==0) return matrix;
int rowbegin = 0;
int rowend = n-1;
int colbegin = 0;
int colend = n-1;
int count = 1;
while(rowbegin<=rowend && colbegin<=colend){
for(int i = colbegin;i<=colend;i++){
matrix[rowbegin][i] = count++;
}
rowbegin++;
for(int i = rowbegin;i<=rowend;i++){
matrix[i][colend] = count++;
}
colend--;
if(rowbegin>rowend && colbegin>colend)
return matrix;
for(int i = colend;i>=colbegin;i--){
matrix[rowend][i] = count++;
}
rowend--;
if(rowbegin>rowend && colbegin>colend){
return matrix;
}
for(int i = rowend;i>=rowbegin;i--){
matrix[i][colbegin] = count++;
}
colbegin++;
}
return matrix;
}
};

60. Permutation Sequence

分析:递归全排列,当满足长度的个数到达k个时得到结果。

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
class Solution {
public:
int count = 0;
string res = "";
string ans;
vector<int> visit;
void dfs(int n,int k){
if(res.size() == n){
count++;
if(count == k){
ans = res;
return;
}
}
if(count!=k){
for(int i = 1;i<=n;i++){
if(visit[i]==1) continue;
res += to_string(i);
visit[i] = 1;
dfs(n,k);
res = res.substr(0,res.size()-1);
visit[i] = 0;
}
}
}
string getPermutation(int n, int k) {
visit = vector<int>(n+1,0);
dfs(n,k);
return ans;
}
};

61. Rotate List

分析:这题需要处理掉循环插的情况,即取模即可。然后就是正常的链表。

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
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(k == 0||head == NULL) return head;
int n = 0;
auto p = head;
while(p!=NULL){
n++;
p = p->next;
}
k = k%n;
if(k == 0) return head;
p = head;
while(n - k -1 > 0){
p = p->next;
k++;
}
auto q = p->next;
auto ans = q;
p->next = NULL;
while(q->next!=NULL){
q = q->next;
}
q->next = head;
return ans;
}
};

70. Climbing Stairs

分析:动态规划法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int climbStairs(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
vector<int> dp(n,0);
dp[0] = 1;
dp[1] = 2;
for(int i = 2;i<n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n-1];
}
};

7/3/2019

不知道为什么漏了6号,我明明都有做🐸

51. N-Queens

N皇后递归最经典的问题,我觉得我在求解递归的问题的时候思路不是很清晰,总是做的不好,有必要总结一下。

递归

递归就是你需要确定一个循环机制,然后每次递归需要进行标记(不标记的话每次都执行一样的东西了),当然是根据条件进行标记的。因此对于递归的条件判断也需要十分注意,每次递归结束需要释放掉当前状况所添加的约束。

  1. 定义约束变量,比如visit矩阵用于判断是否遍历过
  2. 确定主循环,主循环指需要对所有的子问题进行完整解析
  3. 将当情况的约束加到visit上,进行递归
  4. 确定递归返回条件,比如temp.size()>=n
  5. 结束递归将当前约束释放掉
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
class Solution {
public:
//回溯法
vector<vector<string>> res;
vector<vector<int>> visit;
void dfs(vector<string> temp,int pos,int n){
if(temp.size() == n){
res.push_back(temp);
return;
}
if(pos>=n) return;
for(int i = 0;i<n;i++){
string s(n,'.');
if(pos == 0){
s[i] = 'Q';
temp.push_back(s);
visit[pos][i] = 1;
dfs(temp,pos+1,n);
temp.pop_back();
visit[pos][i] = 0;
}
else if((i==0||visit[pos-1][i-1]!=1)&&
(i+1==n||visit[pos-1][i+1]!=1)){
int flag = 0;
for(int j = 0;j<n;j++){
if(visit[j][i] == 1) {flag = 1;break;}
}
int tempi = i-1;
int tempj = pos-1;
while(tempj>=0&&tempi>=0){
if(visit[tempj--][tempi--] == 1){flag = 1;break;}
}
tempi = i+1;
tempj = pos+1;
while(tempj<n&&tempi<n){
if(visit[tempj++][tempi++] == 1) {flag = 1;break;}
}
tempi = i+1;
tempj = pos-1;
while(tempj>=00&&tempi<n){
if(visit[tempj--][tempi++] == 1) {flag = 1;break;}
}
tempi = i-1;
tempj = pos+1;
while(tempj<n&&tempi>=0){
if(visit[tempj++][tempi--] == 1) {flag = 1;break;}
}
if(flag == 0){
s[i] = 'Q';
temp.push_back(s);
visit[pos][i] = 1;
dfs(temp,pos+1,n);
temp.pop_back();
visit[pos][i] = 0;
}
}
else{
continue;
}
}
}
vector<vector<string>> solveNQueens(int n) {
if(n<=0) return res;
visit = vector(n,vector<int>(n,0));
vector<string> temp;
dfs(temp,0,n);
return res;
}
};

206. Reverse Linked List

递归题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL||head->next == NULL) return head;
ListNode* p = head->next;
ListNode* q = head;
q->next = NULL;
while(p){
auto temp = p->next;
p->next = q;
q = p;
p = temp;
}
return q;
//递归做法,先将所有的节点打散,然后从最后一个慢慢往前连接
/* if(head==NULL||head->next == NULL) return head;
auto last = head->next;
head->next = NULL;
ListNode* newhead = reverseList(last);
last->next = head;
return newhead;*/
}
};

226. Invert Binary Tree

分析:在每一次递归时进行左右交换。树的遍历方式算是递归的一种。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL) return NULL;
auto p = root->left;
root->left = root->right;
root->right = p;
invertTree(root->left);
invertTree(root->right);
return root;
}
};

104. Maximum Depth of Binary Tree

分析:每一次进步一个深度,然后如果为零返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxn = 0;
void dfs(TreeNode* root,int level){
if(root == NULL) return;
dfs(root->left,level+1);
dfs(root->right,level+1);
if(maxn<level) maxn = level;

}
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
dfs(root,1);
return maxn;
}
};

5/3/2019

49. Group Anagrams

49

分析:这道题使用哈希表来解决,记录是否有相同的元素被访问过。

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:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
if(strs.size() == 0) return res;
unordered_map<string,int> amap;
for(int i = 0;i<strs.size();i++){
auto temp = strs[i];
sort(temp.begin(),temp.end());
if(amap.count(temp) == 0){
amap[temp] = res.size();
vector<string> a;
a.push_back(strs[i]);
res.push_back(a);
}
else{
res[amap[temp]].push_back(strs[i]);
}
}
return res;
}
};

82. Remove Duplicates from Sorted List II

分析:这一题的思路其实很简单,就是当你要删除一个数的时候,你应该保证目前的指针指向要删除的数的前一个,因此需要保证next和next之后的数都不为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL) return head;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while(p->next && p->next->next){
if(p->next->val == p->next->next->val){
int same = p->next->val;
while(p->next&&p->next->val == same){
p->next = p->next->next;
}
}
else{
p = p->next;
}
}
return dummy->next;
}
}

83. Remove Duplicates from Sorted List

分析:这一题比较好做,唯一要注意的是不要判断p不为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL) return head;
auto p = head;
while(p->next){
if(p->next->val == p->val){
p->next = p->next->next;
}
else p = p->next;
}
return head;
}
}

86. Partition List

分析:我发现我链表的题做得还行。这一题思路是先走到链表尾巴,然后遇到比目标大的数,就截取下来放到最后。

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
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(head == NULL) return head;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
auto q = head;
int count = 0;
while(p->next){
p = p->next;
count++;
}
q = p;
p = dummy;
while(count){
count--;
if(p->next->val < x){
p = p->next;
}
else{
q->next = p->next;
p->next = p->next->next;
q = q->next;
}
}

q->next = NULL;
return dummy->next;
}
};

87. Scramble String

分析:这一题用递归的方法做,感觉所有用递归的方法其实都是最耗时的方法,更好的方法可能是动态规划方法。总之递归之后应该有一个动归才是。然后基本思路是做两次判断,第一次两个串切在同一个位置上,第二次在首尾位置上。

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
class Solution {
public:

bool isScramble(string s1, string s2) {
if(s1.size()==0||s2.size() == 0) return false;
if(s1 == s2) return true;

vector<int> letters(26);
for(int i = 0;i<s1.size();i++){
letters[s1[i]-'a']++;
letters[s2[i]-'a']--;
}
for(int i = 0;i<26;i++){
if(letters[i]!=0) return false;
}

for(int i = 1;i<s1.size();i++){
if(isScramble(s1.substr(0,i),s2.substr(0,i))&&
isScramble(s1.substr(i),s2.substr(i))) return true;

if(isScramble(s1.substr(0,i),s2.substr(s1.size()-i))&&
isScramble(s1.substr(i),s2.substr(0,s1.size()-i))) return true;
}
return false;
}
};

4/3/2019

46. Permutations


分析:这一题是典型的排列问题,用递归的方式完成,然后用一个数组来标记当前的位置是否被读取过。

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
class Solution {
public:
vector<vector<int>> res;
void dfs(vector<int> nums,vector<int> visit,vector<int> temp){
if(temp.size() == nums.size()){
res.push_back(temp);
return;
}
for(int i = 0;i<nums.size();i++){
if(visit[i] == 0){
visit[i] = 1;
temp.push_back(nums[i]);
dfs(nums,visit,temp);
temp.pop_back();
visit[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
if(nums.size() == 0) return res;
vector<int> visit(nums.size(),0);
vector<int> temp;
dfs(nums,visit,temp);
return res;
}
};

47. Permutations II


分析:这一题与上一题的一个改善是,有重复的数,去重复的一个方法是对数组排序,如果当前的元素与上一个元素相同,并且上一个元素没有被访问过(意味着上一个元素曾经在这个位置上),直接跳过这个位置进入下一个位置。

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:
// set<vector<int>> res;
vector<vector<int>> res;
void dfs(vector<int> nums,vector<int> visit,vector<int> temp){
if(temp.size() == nums.size()){
res.push_back(temp);
return;
}
for(int i = 0;i<nums.size();i++){
if(visit[i] == 0){
if(i>0&&nums[i-1] == nums[i]&&visit[i-1] == 0) continue;
temp.push_back(nums[i]);
visit[i] = 1;
dfs(nums,visit,temp);
visit[i] = 0;
temp.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
if(nums.size() == 0) return res;
vector<int> visit(nums.size(),0);
vector<int> temp;
sort(nums.begin(),nums.end());
dfs(nums,visit,temp);
return res;
}
};

45. Jump Game II


分析:这一题用动态规划或者greedy来做,具体看代码即可。dp中对i之前每个位置进行判断,时间复杂度为$O(n^2)$ , greedy中cur指当前能到最远位置,last指上一步能到最远位置。然后需要排除掉一步不走的情况。

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:
/* int jump(vector<int>& nums) {
if(nums.size() == 0) return 0;
vector<int> dp(nums.size(),INT_MAX);
dp[0] = 0;
for(int i = 0;i<nums.size() ;i++){
for(int j = 0;j<i;j++){
if(nums[j]>=i-j){
dp[i] = min(dp[i],dp[j]+1);
}
}
}
return dp[nums.size()-1];
}
*/
int jump(vector<int>& nums) {
if(nums.size() == 0) return 0;
int res = 0;
int last = 0;
int cur = 0;
for(int i = 0;i<nums.size()-1 ;i++){
cur = max(cur,i+nums[i]);
if(i == last){
last = cur;
res++;
if(last>=nums.size()-1) return res;
}
}
return res;
}
};

50. Pow(x, n)


分析:由于指数乘法可以由比他小的指数乘起来得到,一次可以用分治法来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
double myPow(double x, int n1) {
if(n1 == 0) return 1.0;
if(n1 == 1) return x;
long long n = n1;
if(n<0){
n = -n;
x = 1.0/x;
}
double res = myPow(x,n/2);
if(n%2 == 0) return res*res;
return res*res*x;

}
};


3/3/2019

40. Combination Sum II


分析:这一题用递归来求解,对于重复的问题,在执行一次递归之后,对重复的元素进行排除。

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
class Solution {
public:
vector<vector<int>> res;


void dfs(vector<int> candidates,vector<int> temp,int target,int pos){
if(target == 0){
res.push_back(temp);
return;
}
for(int i = pos;i<candidates.size()&&target>=candidates[i];i++){
temp.push_back(candidates[i]);
dfs(candidates,temp,target-candidates[i],i+1);
while(i+1<candidates.size()&&candidates[i] == candidates[i+1]) i++;
temp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
if(candidates.size() == 0) return res;
sort(candidates.begin(),candidates.end());
vector<int> temp;
dfs(candidates,temp,target,0);
return res;
}
};

42. Trapping Rain Water


分析:这一题之前做过,思路就是用两个数组,从左到右记录最大的val,从右到左记住最大的val,然后水坑的值就等于三个数组相减。

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 trap(vector<int>& height) {
if(height.size() == 0) return 0;
vector<int> left(height.size());
vector<int> right(height.size());
left[0] = height[0];
right[height.size()-1] = height[height.size()-1];
for(int i = 1;i<height.size();i++){
left[i] = max(left[i-1],height[i]);
}
for(int i = height.size()-2;i>=0;i--){
right[i] = max(right[i+1],height[i]);
}
int res = 0;
for(int i = 0;i<height.size();i++){
int temp = min(left[i],right[i])-height[i];
if(temp>0) res += temp;
}
return res;
}
};

44. Wildcard Matching


分析:字符串匹配问题多可以用动态规划来求解,思考动态规划问题的时候不要想太多步。就想着当前这一步有多少种情况就可以了。同时需要注意边界问题。
递推情况如下:
p[j] = '*':

  • s[i-1]和p[j-1]进行匹配,s[i]和p[j]进行匹配。此时考虑*表示1个字符。
  • s[i-1]已经和p[j]进行了匹配,s[i]也仍然和p[j]进行匹配。此时考虑*表示n个字符。
  • s[i]和p[j - 1]进行了匹配,此时考虑*表示0个字符。

p[j] = '?'等:
p[j-1]与s[i-1]进行匹配,p[j],s[i]匹配。

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:
bool isMatch(string s, string p) {
int m = s.size(),n = p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
dp[0][0] = true;
for(int i = 1;i<=n;i++){
if(p[i-1] == '*') dp[0][i] = dp[0][i-1]; // s为空,p为连续* 号
}
for(int i = 1;i<=m;i++){
for(int j = 1;j<=n;j++){
if(p[j-1] == '*'){
dp[i][j] = dp[i-1][j]||dp[i][j-1]||dp[i-1][j-1];
}
else if(p[j-1] == '?'||p[j-1] == s[i-1]){
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[m][n];
}
};

67. Add Binary


分析:做过类似的面试题,然后思路就是这样没错了。

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
class Solution {
public:
string addBinary(string a, string b) {
int n = a.size()-1;
int m = b.size()-1;
int add = 0;
string res = "";
while(n>=0&&m>=0){
int le = a[n] - '0';
int ri = b[m] - '0';
if(le+ri+add>=2){
res = to_string(le+ri+add -2) + res;
add = 1;
}
else{
res = to_string(le+ri+add) + res;
add = 0;
}
n--;
m--;
}
res = (n>=0? a.substr(0,n+1):b.substr(0,m+1)) + res;
if(add == 0) return res;
int left = n>=0? n:m;
while(left>=0){
if(res[left] == '0'){
res[left] = '1';
return res;
}
else{
res[left] = '0';
}
left--;
}
res = '1'+ res;
return res;
}
};


2/3/2019

32. Longest Valid Parentheses


分析:这一题括号匹配,用栈的结构来解决,每次将括号的下标存入栈的结构中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int longestValidParentheses(string s) {
if(s.size() == 0) return 0;
int maxn = 0;
stack<int> sta;
sta.push(-1);
for(int i = 0;i<s.size();i++){
if(s[i] == '('){
sta.push(i);
}
else{
sta.pop();
if(!sta.empty())
maxn = max(maxn,i-sta.top());
else{
sta.push(i);
}
}
}
return maxn;
}
};

34. Find First and Last Position of Element in Sorted Array


这一题题目要求复杂度是O(log(n)) 很显然就是用二分法来做的,然后如果找到了target,就往target的两边去找相同的元素。

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
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res = {-1,-1};
if(nums.size() == 0) return res;
int low = 0;
int high = nums.size()-1;
int mid;
while(low<=high){
mid = (low+high)/2;
if(nums[mid] == target) break;
else if(nums[mid]>target){
high = mid-1;
}
else{
low = mid+1;
}
}
if(low>high) return res;
int i = 0;
for(i = mid-1;i>=0;i--){
if(nums[i] != target) {break;}
}
res[0] = i+1;
for(i = mid + 1;i<nums.size();i++){
if(nums[i]!=target) { break;}
}
res[1] = i-1;
return res;
}
};

36. Valid Sudoku


分析:判断横排,竖排,里头九宫格即可。

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
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
if(board.size() == 0) return false;

//横排
for(int i = 0;i<9;i++){
unordered_map<char,int> amap;
for(int j = 0;j<9;j++){
if(amap.count(board[i][j]) != 0 &&board[i][j]!='.') return false;
amap[board[i][j]] = 1;
}
}
//竖排
for(int i = 0;i<9;i++){
unordered_map<char,int> amap;
for(int j = 0;j<9;j++){
if(amap.count(board[j][i])!=0&&board[j][i]!='.') return false;
amap[board[j][i]] = 1;
}
}
//九宫格
for(int i = 0;i<9;i += 3){
for(int j = 0;j<9;j+=3){
unordered_map<char,int> amap;
for(int h = i;h<i+3;h++){
for(int k = j;k<j+3;k++){
if(amap.count(board[h][k])!=0&&board[h][k]!='.') return false;
amap[board[h][k]] = 1;
}
}
}
}
return true;
}
};

39. Combination Sum


分析:经典的一道递归题,下次一定要会做才行,因为最基本的递归就长这个样子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<vector<int>> res;
void digui(vector<int>& candidates,int target,vector<int> temp,int pos){
if(target == 0) res.push_back(temp);
for(int i = pos;i<candidates.size();i++){
if(target>=candidates[i]){
temp.push_back(candidates[i]);
digui(candidates,target-candidates[i],temp,i);
temp.pop_back();
}
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if(candidates.size() == 0) return res;
vector<int> temp;
digui(candidates,target,temp,0);
return res;
}
};


1/3/2019

38. Count and Say


分析:这一题是递归的题,出口是n = 0 或 1,然后用for循环判断当前生成的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
string countAndSay(int n) {
if(n <= 0) return "";
if(n == 1) return "1";
string s = countAndSay(n-1);
string newS = "";
for(int i = 0;i<s.size();i++){
int count = 1;
while(i+1<s.size()&&s[i] == s[i+1]){
count++;
i++;
}
newS += to_string(count) + s[i];
}
return newS;
}
};


2/28/2019

30. Substring with Concatenation of All Words


分析:控制一个words的所有字符长度的子串,然后在子串里面看是否满足条件。用hash_map做。

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
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(s.empty()||words.size() == 0) return res;
int m = words[0].size();
int n = words.size();
unordered_map<string,int> m1;
for(int i = 0;i<words.size();i++){
++m1[words[i]];
}
for(int i = 0;i<=(int)s.size()-m*n;i++){
cout<<s.size();
unordered_map<string,int> m2;
int j = 0;
for(;j<words.size();j++){
string t = s.substr(i+j*m,m);
if(m1.find(t) == m1.end()) break;
++m2[t];
if(m2[t]>m1[t]) break;
}
if(j == words.size()) res.push_back(i);
}
return res;
}
};

2/26/2019

53. Maximum Subarray


分析:这一题时简单的DP问题,用一个数存之前的序列和,当和小于0时则清零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size() == 0) return 0;
int maxn = INT_MIN;
int ans = 0;
for(int i = 0;i<nums.size();i++){
if(ans<0) ans = 0;
ans += nums[i];
maxn = max(maxn,ans);
}
return maxn;
}
};

15. 3Sum

分析:这一题要找出所有的相加为0的组合,可以定义三个变量,用来控制数组中相加的数字,一个数字控制外循环,里头两个数字当遇到与前一个相同时,需要跳过。

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
if(nums.size() == 0) return res;

for(int i = 0;i<nums.size();i++){
int begin = i+1,end = nums.size()-1;
if(i>0&&nums[i-1]==nums[i]) continue;
while(begin<end){
int result = nums[i]+nums[end]+nums[begin];
if(i!=end&& result == 0){
vector<int> temp = {nums[i],nums[begin],nums[end]};
res.push_back(temp);
end--;
while(end>=0&&nums[end+1] == nums[end]) end--;
begin++;
while(begin<nums.size()&&nums[begin-1] == nums[begin]) begin++;
}
else if(i==end||result>0) end--;
else begin++;
}
}
return res;
}
};

16. 3Sum Closest


这一题是上一题的变形,省去了判断过滤重复的步骤,只要求一个绝对值最接近1就好。

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
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
int sum = INT_MAX;
int ans;
sort(nums.begin(),nums.end());
for(int i = 0;i<nums.size();i++){
int j = i+1,k = nums.size()-1;
while(j<k){
int result = nums[i]+nums[j]+nums[k];
if(i!=k&&abs(result-target)<=sum){
sum = abs(result-target);
ans = result;
if(result<target)j++;
else if(result>target) k--;
else return result;
}
else if(result>target) k--;
else j++;
}
}
return ans;

}
};

17. Letter Combinations of a Phone Number


这一题比较简单,把存结果的数组当作栈来用就行了。

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
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if(digits.size() == 0) return res;

vector<vector<char>> alphabet = {
{}, {},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},
{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}
};
vector<char> tem(alphabet[digits[0]-'0']);
string a ="";
for(int i = 0;i<tem.size();i++){
a += tem[i];
res.push_back(a);
a = "";
}
for(int i = 1;i<digits.size();i++){
vector<char> te(alphabet[digits[i]-'0']);
int resSize = res.size();
for(int j = 0;j<resSize;j++){
string ahead = res[0];
for(int k = 0;k<te.size();k++){
res.push_back(ahead+te[k]);
}
res.erase(res.begin());
}
}
return res;
}
};

18. 4Sum


分析:这一题是前面三个数的加强版,注意一些重复的判断就行了。

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
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
if(nums.size() < 4) return res;
sort(nums.begin(),nums.end());
for(int i = 0;i<nums.size();i++){
if(i>0&&nums[i] == nums[i-1]) continue;
for(int j = i+1;j<nums.size();j++){
if(j>i+1&&nums[j] == nums[j-1]) continue;
int begin = j+1,end = nums.size()-1;
while(begin<end){
int result = nums[i]+nums[j]+nums[begin]+nums[end];
if(result == target){
res.push_back({nums[i],nums[j],nums[begin],nums[end]});
begin++;
end--;
while(end>begin&&nums[end] == nums[end+1]) end--;
while(begin<end&&nums[begin-1] == nums[begin]) begin++;
}
else if(result > target) end--;
else begin++;
}
}
}
return res;
}
};

19. Remove Nth Node From End of List


分析:这一题要求执行一趟,删除掉倒数第n个节点。可以用两个指针来完成,第一个指针领先第二个指针n的位置,当第一个指针到达终点时,第二个指针的位置就是倒数n的位置。然后需要注意删除第一个元素的情况。

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
/**
* 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) {
if(head == NULL) return NULL;
ListNode* pre = head;
ListNode* last = head;
ListNode* pos = head;
while(n--){
pos = pos->next;
}
if(pos == NULL) return head->next; //当删除第一个元素时
while(pos!=NULL){
pre = last;
last = last->next;
pos = pos->next;
}
pre->next = last->next;
return head;
}
};

22. Generate Parentheses


分析:这是一道很经典的递归的题目,我做出一道就有感觉了。就是说看递归一定是这一步做了某种选择,待会还要回来。而且要比较注重递归程序的出口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int nn;
vector<string> ans;
void digui(string res,int left,int right){
if(res.size() == 2*nn){ ans.push_back(res);return;}
if(left<nn) digui(res+"(",left+1,right);
if(right<nn&&right<left) digui(res+")",left,right+1);

}
vector<string> generateParenthesis(int n) {
if(n == 0) return ans;
nn = n;
digui("",0,0);
return ans;
}
};

24. Swap Nodes in Pairs


调换两个数,需要三个指针,然后注意特殊情况只有一个数的时候的。直接放回head。

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == NULL) return NULL;
ListNode* pre = new ListNode(-1);
ListNode* first = head;
ListNode* second = head->next;
pre->next = head;
if(second == NULL) return head;
head = second;
while(second != NULL){
pre->next = second;
first->next = second->next;
second->next = first;
pre = first;
first = first->next;
if(first!=NULL) second = first->next;
else return head;
}
return head;
}
};

29. Divide Two Integers


分析:这一题由于有越界问题,可以用long long申请变量,保证不会溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int divide(int dividend, int divisors) {
long long divide = dividend;
long long divisor = divisors;
if(divisor == 0) return divide;
int sign = 1;
if(divisor<0) sign = -1,divisor *= -1;
if(divide<0) sign *= -1,divide *= -1;
long time = 0;
while(divide>=divisor){
time++;
divide -= divisor;
}
if(time*sign>INT_MAX) return INT_MAX;
if(time*sign<INT_MIN) return INT_MIN;
return time*sign;
}
};


4. median of two sorted array


分析:
这一题要找两个排序好的数组的中位数。

中位数有一个性质就是一定位于数列的中间位置,而且中位数左边的数都小于中位数,中位数右边的数都大于中位数

因此我们对数组位置进行分析时,需要保持中位数位置一定为数组长度的一半,又因为这道题对两个排序好的数组寻找中位数,因此可以分别对他们使用分治法求解。

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
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//首先拿到数组的长度,并设置nums1的长度大于nums2
int m = nums1.size();
int n = nums2.size();
if(m>n){
auto temp = nums1;
nums1 = nums2;
nums2 = temp;
swap(n,m);
}// n > m
int imin = 0,imax = m,half = (m+n+1)/2; //half保证了长度为数列的一半
//接下来在nums2数组中对中位数位置进行遍历
while(imin<=imax){
int i = (imax-imin)/2 + imin; // seperate nums1
int j = half - i; // j为num2的分割点,可以看出来j为一半的长度,不是下标
if(i<m && nums1[i]<nums2[j-1]) // i is too small
{
imin = i+1;
}
else if(i>0&&nums1[i-1]>nums2[j]){ // i is to big
imax = i-1;
}
else{ // ferfect
int max_left,min_right;
if(i == 0){
max_left = nums2[j-1];
}
else if(j == 0){
max_left = nums1[i-1];
}
else{
max_left = max(nums2[j-1],nums1[i-1]);
}

if((m+n)%2 == 1){
return max_left;
}
else{
if(i == m){
min_right = nums2[j];
}
else if(j == n){
min_right = nums1[i];
}
else{
min_right = min(nums1[i],nums2[j]);
}
return (min_right+max_left)/2.0;
}
}

}
return -1.0;
}
};

26. Remove Duplicates from Sorted Array

分析:
这一题思路比较简单,由于数组是排序过的,因此重复的数在相邻的位置上。所以做法就是用i遍历一边数组,用j保持数组不重复的长度,当出现不重复时j++,将不重复的数补充到j位置上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0) return 0;
int count = 0;
int j = 0;
for(int i = 1;i<nums.size();i++){
while(i<nums.size()&&nums[j] == nums[i]){
i++;
}
if(i<nums.size())
{
j++;nums[j] = nums[i];
}
}
return j+1;
}
};

837. New 21 Game

Alt text

分析:
先吐槽一下自己,最近刷题有点儿太慢了。
这一题的题意是说,Alice每次都可以在1~W之间随机选择一个数,当Alice选择的数累加起来大于等于K的时候,Alice停止游戏。这时候这个累加和如果大于N那么Alice就输了,小于等于N Alice就赢了。题目叫我们算Alice赢得概率,就是累加和小于等于N的概率。

这一题可以用DP来求解,维护一个累加和窗。设dp[i]为当前累加和为i的时候的概率。要求i的概率有下面关系:dp[i] = 1/w * (dp[i-1]+dp[i-2]...dp[i-w]),即我可以先选择i-1,然后选1。由于可以选择的数只有W个,因此窗口宽度为W。对于累加和有下面的关系:

  • i<K : Wsum += dp[i] 表明当前的i可以作为下一次两步选择的第一步
  • i-W>=0: Wsum -= dp[i-W] 表明对于下一个i来说,因为W的范围限定,取不到第dp[i-W]作为前两步选择的第一步,需要把概率减去,维护窗内概率。
  • N>= i >=K: res += dp[i];结果为res,即这个时候分数在K与N之间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
double new21Game(int N, int K, int W) {
if(K == 0) return 1;
// 共有N+1个状态
vector<double> dp(N+1);
double Wsum = 1.0; // 记录前W个数的概率
double res = 0.0;
dp[0] =1;
for(int i = 1;i<=N;i++){
dp[i] = Wsum/W;
if(i<K) Wsum+=dp[i]; // 当前的i可以作为下一次两步选择的第一步
else{
res += dp[i];
}
if(i-W>=0) Wsum -= dp[i-W]; //对于下一个i来说,当前的i-W下一个无法取到
}
return res;
}
};

481. Magical String

这一题的题意是说,1和2将会交替出现,最开始1先出现,然后去产生下面的数,最后会发现产生的数组和每一行数字的个数序列将会是同一个序列。最后统计一下序列中1的个数。
数字的产生规则如下:

  • 先产生1
  • 1与2交替出现
  • 当前字符串最末尾的数字控制添加入字符串的字符个数,如122,表示下一次将加入2个1,变成12211
  • 前三个数比较特殊,直接生成122
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int magicalString(int n) {
if(n == 0) return 0;
string s = "122";
int i = 2;
while(s.size()<n){
s+= string(s[i++]-'0',s.back() == '1'? '2':'1');
}
return count(s.begin(),s.begin()+n,'1');
}
};

有几个新函数记录一下:

1
2
s = string(char_num,char); //产生char_num个char
count(s.begin(),s.begin()+n,'1');//计算字符串s中含'1'的个数

2. Add Two Numbers


这一题题意说的是用链表表示数字,表头为个位。然后将两个链表相加,计算他们的和,返回一个新的链表。
这一题比较简单,要注意的有种情况:

  • 链表相加完,有一个链表长度还有剩余
  • 链表要记录进位,最后可能进位项还为1
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
/**
* 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) {
ListNode* head = new ListNode(-1);
auto p = head;
int step = 0;
while(l1!=NULL&&l2!=NULL){
int sum = l1->val + l2->val+step;
if(sum>=10){
sum -= 10;
step = 1;
}
else{
step = 0;
}
p->next = new ListNode(sum);
p = p->next;
l1 = l1->next;
l2 = l2->next;
}
auto l = l1 != NULL ? l1 : l2;
if(l!=NULL){
while(l!=NULL){
int sum = l->val +step;
if(sum>=10){
sum -= 10;
step = 1;
}
else{
step = 0;
}
p->next = new ListNode(sum);
p = p->next;
l = l->next;
}
}
if(step==1){
p->next = new ListNode(1);
}
return head->next;
}
};

数据大小及其表示的问题

  1. 整数int的上下界:

    1
    2
    最小的表示方式:-1<<31,INT_MIN
    最大的表示方式:1<<31 -1,INT_MAX
  2. 其他类型:

    1
    2
    3
    unsigned int ->UINT_MAX
    long->LONG_MAX
    unsigned long->ULONG_MAX
  3. 无穷大的选择:

    1
    const int INF = 0x7fffffff;

0x7fffffff 是32-bit int的最大值。

1
const int INF = 0x3f3f3f3f

0x3f3f3f3f的十进制是1061109567,是10^9级别的(和一个数量级),而一般场合下的数据都是小于10^9的,可以用来表示无穷大。此外,0x3f3f3f3f * 2 =2122219134,这非常大但却没有超过32-bit int的表示范围,所以0x3f3f3f3f能够满足“无穷大加无穷大还是无穷大”的需求。
如果我们想要将某个数组清零,我们通常会使用memset(a,0,sizeof(a))。但是当我们想将某个数组全部赋值为无穷大时,就不能使用memset函数而得自己写循环了,因为memset是按字节操作的。如果我们将无穷大设为0x3f3f3f3f,0x3f3f3f3f的每个字节都是0x3f!所以要把一段内存全部置为无穷大,我们只需要memset(a,0x3f,sizeof(a))。

1
2
3
#include<cstring>
memset(a,0,sizeof(a)); //给a数组置0
memset(a,0x3f,sizeof(a));//给a数组赋值正无穷
  1. 表示一个很小的数:
    1
    const long double eps = 1e-8;

1e-8 是0.00000001,用来表示一个很小很小的数,通常可以用来判断两个数是否相同,即精度的差距。


2/22/1019

3. Longest Substring Without Repeating Characters


分析:
这一题题目非常好理解,找到字符串中的最长非重复子串。一看这一题的题目就感觉会有大量的元素比较,重复计算,因此可以用DP来做,用一个数组存储子问题的解。

维护一个数组res[j],用来存储子问题的解,遍历原始数组,如果发现循环到的元素s[i]与res中最后一个位置所代表的元素不同,这res[j]++;如果发现相同这j++;res[j] = res[j-1]-1。具体写代码的时候里面有很多陷阱,看代码注释:

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
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
vector<int> res(s.size());
int j = 0;
res[0] = 1;
int flag = 0;
for(int i = 1;i<s.size();i++){
for(int k = j;k<i;k++){ //判断当前循环元素与子串中是否有重复
if(s[k]==s[i]){
flag = 1;
}
}
if(j>=i) continue; //由于底下有i--的操作,需要保证j<i
if(flag == 0){ // all different
res[j]++;
}
else{ //如果有重复
flag = 0;
j++; //res表示的子串向前缩减
i--; //当前遍历到的元素需要保留
res[j] = res[j-1]-1>0? res[j-1]-1 : 1; //保证res[j]最小为1
}
}
return *max_element(res.begin(),res.end());
}
};

tip:
关于vector找最大值最小值:

1
2
int maxValue = *max_element(s.begin(),s.end());
int minValue = *min_element(s.begin(),s.end());

5. Longest Palindromic Substring

分析:
找到最长的回文子串,可以用一个窗口去扫描,窗口的长度有2到字符串长度。该做法的时间复杂度为$O(n^2)$。

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:
string longestPalindrome(string s) {
if(s.size() == 0) return "";
int pos = 0;
int length = 1;
for(int l = 2;l<=s.size();l++){ // 回文的长度
cout<<l<<" ";
for(int i = 0;i<s.size()-l+1;i++){
int j = i+l-1;
int temp = i;
while(temp<j){ // 判断窗口内是否满足回文
if(s[temp]==s[j]){
temp++;
j--;
}
else{
break;
}
}
if(temp>=j){ //说明满足回文
pos = i;
length = l;
}
}
}
return s.substr(pos,length);
}
};

2/23/2019

6. ZigZag Conversion


分析:这一题题意要求生成zigZag字形的序列,如图。可以用下标间关系求解,规定i为行数,j为要输出位置的下标,则该序列中下标间存在以下关系:

  • V口向上: j += 2*(numRows-i-1)
  • V口向下:j +=2i
  • 第一行和最后一行处于V的交界位置,需要排除掉一种即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
string convert(string s, int numRows) {
if(s.size() == 0) return "";
if(numRows == 1) return s;
string res = "";
for(int i = 0;i<numRows;i++){
int j = i;
while(j<s.size()){
res += s[j];
j += 2*(numRows-i-1);
if(j<s.size()&&i!=0&&i!=numRows-1){
res += s[j];
}
j += 2*i;
}
}
return res;
}
};

8. String to Integer (atoi)


分析:这一题做的我很狼狈,可以按从头到尾扫描的方式来做,我的做法太蠢了。特例很多。

  • 从头到位扫描。
  • 当判断一个string 转成int是否超过精度的时候,可以申请一个long long类型的变量,判断他是否大于边界值。
  • char 转int的方式: str[i] - '0';即可。

我的做法:(不推荐,虽然挺快的)

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
class Solution {
public:
int myAtoi(string str) {
if(str.size() == 0) return 0;
string s = "";
for(int i = 0;i<str.size();i++){
if(s ==""&&str[i] == ' ') continue;
if(s==""){
if(isdigit(str[i])) s = str[i];
else if(str[i] =='-') s += '-';
else if(str[i] == '+') s += '+';
else return 0;
}
else{
if(!isdigit(str[i])) break;
s+=str[i];
}
}
if(s.size() == 0) return 0;
if(s.size() == 1 && s[0] == '-') return 0;
int flag = 1;
if((s[0]=='+'||s[0]=='-')&&!isdigit(s[1])) return 0;
if(s[0] == '-'){
flag = -1;
s = s.substr(1,s.size()-1);
}
else if(s[0] == '+')
{
s = s.substr(1,s.size()-1);
}
if(s.size()>1){
while(s.size()>1&&s[0]=='0'){
s = s.substr(1,s.size()-1);
}
}
string min = "2147483648";
if(s.size()>10) return flag == 1? INT_MAX:INT_MIN;
if(s.size()>=min.size()&&s>=min) return flag == 1? INT_MAX:INT_MIN;
else return stoi(s)*flag;
}
};

比较合理的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
int myAtoi(string str) {
if(str.size() == 0) return 0;
long long base = 0;
int sign = 1,i = 0;
while(str[i] == ' ') i++;
if(str[i] == '+') i++;
else if(str[i] == '-') sign = -1,i++;
while(i<str.size()&&str[i]>='0'&&str[i]<='9'){
base = base*10 + str[i++]-'0';
if(base>INT_MAX) return sign == 1?INT_MAX:INT_MIN;
}
return base*sign;
}

35. Search Insert Position


分析: 这一题可以用分治法来做,主要的点在于当要找的数不存在时,它如果比num[high]大,那么插入点为high(需要保证high>=0),如果比high小,插入点为high+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
int low = 0;
int high = nums.size()-1;
while(low<=high){
int mid = (high+low)/2;
if(nums[mid] == target) return mid;
else if(nums[mid]>target) high = mid -1;
else low = mid + 1;
}
if(high>=0&&nums[high]>target) return high;
else return high+1;
}
};


24/2/2019

10. Regular Expression Matching


这道题的题意是判断两个字符串是否能够匹配,由于*号可以替换多个字符,因此这一题有一个递归的过程,也就是说,替换的个数可能是1,2…等等。所以要用递归的方法求解。

  • p[1] == '*': 两种情况,*直接跳过;match一个字符;
  • p[1]!=*: 则两个字符对应位置match

递归解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool isMatch(string s, string p) {
if(p.empty())
return s.empty();
if(p[1]=='*'){
return isMatch(s,p.substr(2))||(!s.empty()&&(s[0] == p[0]||p[0]=='.')&&isMatch(s.substr(1),p));
}
else
return !s.empty()&&(s[0]==p[0]||p[0]=='.')&&isMatch(s.substr(1),p.substr(1));

}
};

动态规划法利用dp数组把所有的子情况都进行保存。有以下几种情形:

  • dp[i][j]: s(0,i) ,p(0,j)是否match
  • p[j-1] != *: dp[i][j] == d[i-1][j-1]&&s[i-1] == p[j-1]
  • p[j-1] == *: 两种:有替换或无替换:
    1
    2
    3
    dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a 
    dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
    dp[i][j] = dp[i][j-2] // in this case, a* counts as empty

动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool isMatch(string s, string p) {
if(p.empty())
return s.empty();
int len1=s.size(),len2=p.size();
vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));
dp[0][0]=true;
for(int i=0;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(p[j-1]=='*')
dp[i][j] = dp[i][j-2] || ( i>0 && dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.') );
else
dp[i][j] = i>0 && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
}
}
return dp[len1][len2];
}
};

12. Integer to Roman

分析:
这一题题意要求将普通数字表示称罗马数字,注意一一对应的关系即可。

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 intToRoman(int num) {
string res = "";
while(num>=1000){
res += "M";
num -= 1000;
}
if(num>=900){
res+= "CM";
num -= 900;
}
else if(num>=100){
if(num>=500) res+='D',num -= 500;
else if(num>=400) res += "CD",num -= 400;
while(num>=100){
res +='C';
num-=100;
}
}
if(num>=90){
res += "XC";
num -= 90;
}
else if(num>=10){
if(num>=50) res += 'L',num -= 50;
else if(num>=40)res+="XL",num -= 40;
while(num>=10){
res +='X';
num -= 10;
}
}
if(num>=9){
res += "IX";
num -= 9;
}
else if(num>=1){
if(num>=5) res += "V",num -= 5;
else if(num>=4)res +="IV",num-=4;
while(num>=1){
res +='I';
num -= 1;
}
}
return res;
}
};