leetcode刷算法题已经全部迁移到这个项目下了:Algorithm-In-Leetcode

Combination Sum III

想了半天,最后使用了递归形式的回溯法来解决,其实本质还是一种遍历吧,每一个元素位上去找可能成立的元素,后一个元素位上的元素肯定比前一个大,然后有一些限制条件,就可以得出来结果。回溯法从这里看来就是一种dfs,找到最后一个元素上。然后再回到上一层元素去找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
def backtrack(result, ans, start, k, target):
if target == 0 and k == 0:
# 当结果和最终的定位都是0,说明是一个结果
result.append(list(ans))
return
# 在这里进行遍历可能的组合
for i in range(start, target+1):
if i > 10 - k:
break
ans.append(i)
# 查看下一个元素是否可以完成任务,如果可以则会将ans添加到结果集,
backtrack(result, ans, i+1, k-1, target-i)
ans.pop()
result = []
ans = []
backtrack(result, ans, 1, k, n)
return result

Runtime: 39 ms Your runtime beats 42.64 % of python submissions.

Magical String

这道题主要是要发现规律,根据规律行事,通过观察可以得出这个字符串从第三位开始生成,比如1221121,第三位是2,所以后面生成2个1,现在结果是12211, 然后第四位是1,所以后面加一个2(要和目前最后一位的值不一样,所以是2),现在结果是122112,第五位是1,所以后面加一个1,结果是1221121,哈哈,这样直到规律,就开始编码吧。

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 magicalString(self, n):
"""
:type n: int
:rtype: int
"""
start = "122"
if n == 0:
return 0
elif n <= 3:
return start.count('1')
else:
# 在这里生成
res = start
pos = 2
while len(res) <= n:
if res[pos] == "2":
res += '1' * 2 if res[-1] == '2' else '2' * 2
elif res[pos] == '1':
res += '2' if res[-1] == '1' else '1'
pos += 1
return res[:n].count('1')

结果也是相当高效的,Runtime: 145 ms Your runtime beats 94.27 % of python submissions.