目录
- Chapter 1 基础
- Chapter 2 排序
- Chapter 3 搜索
- Chapter 4 图
- Chapter 5 字符串
- Chapter 6 Context
- Chapter 7 递归
- 5 参考资料
- 6 template
Chapter 1 基础
(002) Add Two Numbers
Add Two Numbers: 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.
For example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4),
Output: 7 -> 0 -> 8,
分析：本题的本质是Chapter 1 基础里的LinkedList的运用。分两步：第1步是扫描完l1和l2，需要考虑l1和l2长度不相等的情况；第2步是第1步结束后，看看有没有进位，如果有，再增加1个ListNode(1)。tricky的地方在于第1步while里如何协调root的初始化和n的新建，解决方式之一是root的初始化在while前面，while里面n正常新建，但是最后返回的是root.next而不是root。有人将step2合并到step1里，我觉得分开逻辑更清楚。
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
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
root = ListNode(0)
n = root
carry = 0
while l1 or l2: # step 1: until all the node l1 and l2 are scanning over
n.next = ListNode(0)
n = n.next
v1, v2 = 0, 0
if l1:
v1, l1 = l1.val, l1,next
if v2:
v2, l2 = l2.val, l2.next
carry, n.val = divmod(v1+v2+carry,10)
if carry: # step2: after step, if exists carry, add one more node
n.next = ListNode(1)
return root.next
(007) Reverse Integer
Reverse Integer:Reverse digits of an integer.
Example1
x = 123, return 321
Example2
x = -123, return -321,
Note: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.
分析：本题本质是对整数的操作。Python里对溢出判断需要仔细考虑。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
tempX = abs(x)
ans = 0
while(tempX > 0):
digit = tempX % 10
tempX = tempX // 10
ans = ans*10 + digit
if x < 0:
ans = -ans
if ans > 0x7FFFFFFF or ans < -0x80000000:
return 0
return ans
class Solution(object):
(011) Container With Most Water
Container With Most Water: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.
Example1
height = [1,1], return 1
Example2
height = [1,2,4,3], return 2
分析：本题本质是双指针操作。如果用暴力算法，两两比较，需要$O(N^2)$时间复杂度。如何降低呢。通过分析我们知道$area = \Delta x× min(y_1,y_2)$，因此我们可以用两个指针l,r初始分别指向最左边和最右边的直线：若$y_l$小于$y_r$的高度，则将l向右移(所有l和r-n的直线的面积都会小于(l,r)，因为$\Delta x$变小同时$min(y_l,y_r-n)$小于或等于$y_l$)；同理，若$y_r$小于$y_l$的高度，则将r向左移。每次移动后更新最大面积。最后时间复杂度是O(N)。这里有图示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l,r = 0, len(height)-1
maxArea = (r-l)*min(height[l],height[r])
while(l<r):
area = (r-l)*min(height[l],height[r])
if area > maxArea:
maxArea = area
if (height[l] < height[r]):
l += 1
else:
r -= 1
return maxArea
(015) 3Sum
3Sum: Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
For example
given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
分析：本题是KSUM系列。蛮力法是3重遍历，复杂度是$O(N^3)$，这里就不赘述了。这里我们介绍两种方法。第一种复杂度是$O(N^2logN)$，先将数组排序，然后双重嵌套，再用二分法找第三个数(-(nums[i]+nums[j]))，注意要去重。第二种方法复杂度是$O(N^2)$，先将数组排序$O(NlogN)$，然后从小到大进行2SUM问题。而排序好的2SUM可以用$O(N)$双重指针来实现(l=i+1,r=len(nums)-1，当相加小于target，则l+=1，若大于，则r-=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
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums = sorted(nums)
result = []
for i in range(len(nums)):
if i > 0 and nums[i-1]==nums[i]: continue
l,r = i+1,len(nums)-1
target = - nums[i]
while(l < r):
if nums[l]+nums[r] == target:
ans = [nums[i],nums[l],nums[r]]
result.append(ans)
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r-1] == nums[r]: r -= 1
l += 1
r -= 1
elif nums[l]+nums[r] < target:
l += 1
else:
r -= 1
return result
(016) 3Sum Closest
3Sum Closest: Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example
given array S = {-1 2 1 -4}, and target = 1,
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
分析：本题是KSUM系列，和15题类似。关键是双指针要步步逼近target，不能有遗漏的case。在这过程中update最接近的值，若match则立即返回。
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 threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums = sorted(nums)
result = nums[0]+nums[1]+nums[2]
for i in range(len(nums)-1):
l,r = i+1, len(nums)-1
while(l < r):
sum = nums[i] + nums[l] + nums[r]
if abs(target-sum) < abs(target-result): # update closest result
result = sum
if sum == target:
result = sum
return result
elif sum < target:
l += 1
elif sum > target:
r -= 1
return result
(018) 4Sum
4Sum: Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
For example
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
分析：本题是KSUM系列，和15题类似。关键是双指针要步步逼近target，不能有遗漏的case。在这过程中update最接近的值，若match则立即返回。
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(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums = sorted(nums)
result = []
print(nums)
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]: continue
for j in range(i+1,len(nums)-2):
if j > i+1 and nums[j] == nums[j-1]: continue
l,r = j+1,len(nums)-1
while(l < r):
sum = nums[i]+nums[j]+nums[l]+nums[r]
if sum == target:
result.append([nums[i],nums[j],nums[l],nums[r]])
while (l < r and nums[l] == nums [l+1]): l += 1
while (l < r and nums[r] == nums[r -1]): r -= 1
r -= 1
l += 1
elif sum > target:
r -= 1
else:
l +=1
return result
(019) Remove Nth Node From End of List
Remove Nth Node From End of List: Given a linked list, remove the nth node from the end of list and return its head.
For example
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.
分析：本题本质是链表。可以用双指针，first先行n步。难点是需要考虑倒数n个元素是head的情况，通过在head前面增加1个root节点的技巧，将head普通化就可以和其它node一致处理了。
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 removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
N = n
root = ListNode(0)
root.next = head
first = second = root
while(N > 0):
first = first.next
N -= 1
if first is None:
return None
while(first.next):
first = first.next
second = second.next
second.next = second.next.next
return root.next
(020) Valid Parentheses
Valid Parentheses: Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
For example
"()[]{}" are all valid;
"(]" and "([)]" are not valid;
分析：本题本质是stack。
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 isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if s is None:
return True
code = {
'(': ')',
'[': ']',
'{': '}',
}
container = []
for p in s:
if p not in [")","]","}"]:
container.append(p)
else:
if not container:
return False
elif code[container[-1]] == p:
del container[-1]
return container == []
(021) Merge Two Sorted Lists
Merge Two Sorted Lists: 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.
For example
input: 1->4->9 and 2->3
return 1->2->3->4->9
分析：本题本质是List。用尾递归思路比较清晰。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def mergeTwoLists2(l1, l2, root, head):
if not l1 and not l2:
return root
elif l1 and not l2:
head.next = l1
return root
elif l2 and not l1:
head.next = l2
return root
else:
if l1.val < l2.val:
head.next = l1
return mergeTwoLists2(l1.next,l2,root,head.next)
else:
head.next = l2
return mergeTwoLists2(l1,l2.next,root,head.next)
root = ListNode(0)
return mergeTwoLists2(l1,l2,root,root).next
(024) Swap Nodes Pairs
Swap Nodes Pairs: Given a linked list, swap every two adjacent nodes and return its head.
For example
input: 1->2->3->4
return 2->1->4->3
分析：本题本质是List。设置pre和tail比较清楚。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def swapPairs(self, head):
"""
:type pre: ListNode
:rtype: ListNode
"""
root,root.next = ListNode(0),head
pre, pre.next = root, root.next
while(pre.next and pre.next.next):
a = pre.next
b = pre.next.next
tail = pre.next.next.next
pre.next, b.next, a.next = b, a, tail
pre = a
return root.next
(026) Remove Duplicates from Sorted Array
Swap Nodes Pairs: Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.
For example
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
分析：本题本质是Array。设置双指针，l指向结果的尾巴，tail用来扫数组比较清楚。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def swapPairs(self, head):
"""
:type pre: ListNode
:rtype: ListNode
"""
root,root.next = ListNode(0),head
pre, pre.next = root, root.next
while(pre.next and pre.next.next):
a = pre.next
b = pre.next.next
tail = pre.next.next.next
pre.next, b.next, a.next = b, a, tail
pre = a
return root.next
(027) Remove Element
Swap Nodes Pairs: Given an array and a value, remove all instances of that value in place and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length..
For example
Given input array nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
分析：本题本质是Array。和额外的数组的移动一样，只需要将原来数组当做额外的数组用。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
tail = 0
for i in range(len(nums)):
if nums[i] != val:
nums[tail] = nums[i]
tail += 1
return tail
Chapter 2 排序
Chapter 3 搜索
(001) Two Sum
Two Sum: 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.
For example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
分析：本题的本质是搜索。因此读取array时，将array存储为key(大小),value(位置)的HashTable。从数组左边scan到右边，当发现有与当前整数相加等于target的key(HashTable查找key平均是O(1)复杂度)时，返回相应位置；否则加入HashTable。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
entries,i = dict(), 0
for x in nums:
compl = target - x
if compl in entries:
return [i, entries[compl]]
else:
entries[x],i = i,i+1
return [0,0]
(004) Median of Two Sorted Arrays
Median of Two Sorted Arrays: 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)).
Example1
nums1 = [1, 3],
nums2 = [2],
The median is 2.0
Example2
nums1 = [1, 2],
nums2 = [3, 4],
The median is 2.5
分析：乍一看，这其实是一个归并+取中位数的问题。依据归并算法，两个排序号的子数组merge，复杂度是O(M+N)，可以实现。那么如何实现O(log(m+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
29
30
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
i = j = 0
merged = []
while(i < len(nums1) or (j < len(nums2))):
if i >= len(nums1):
merged.append(nums2[j])
j += 1
elif j >= len(nums2):
merged.append(nums1[i])
i +=1
elif(nums1[i] <= nums2[j]):
merged.append(nums1[i])
i += 1
elif(nums1[i] > nums2[j]):
merged.append(nums2[j])
j += 1
isOdd = len(merged)%2 == 0
print(isOdd)
print(merged)
if isOdd:
index = len(merged)//2
return (merged[index] + merged[index-1])/2
else:
return merged[len(merged)//2]
(017) Letter Combinations of a Phone Number
Letter Combinations of a Phone Number: TGiven a digit string, 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..
Example1
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
分析：本题比较简单，硬要说出个涉及的算法，那就是hashTable搜索。另外函数式编程的reduce非常优雅的一行解决问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from functools import reduce
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
code = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
return reduce(lambda acc, digit: [x+y for x in acc for y in code[digit]], digits, [""])
(034) Search For a Range
Search For a Range: Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].
Example1
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
分析：本题本质是搜索。用尾递归逻辑比较清晰。所有符合的下标保存在result里，然后返回头尾两个。
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 searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
result = []
def search(lo,hi):
if lo > hi:
return
mid = (lo + hi)//2
if nums[mid] < target:
search(mid+1,hi)
elif nums[mid] > target:
search(lo,mid-1)
else:
search(lo,mid-1)
result.append(mid)
search(mid+1,hi)
search(0,len(nums)-1)
return [result[0],result[-1]] if result !=[] else [-1,-1]
(035) Search Insert Position
Search Insert Position: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array..
Example1
[1,3,5,6], 5 → 2,
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
分析：本题本质是搜索。用尾递归逻辑比较清晰。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
def search(lo,hi):
if lo > hi: return hi+1
mid = (lo + hi)//2
if (nums[mid] < target):
return search(mid+1,hi)
elif nums[mid] > target:
return search(lo,mid-1)
else: return mid
return search(0,len(nums)-1)
Chapter 4 图
Chapter 5 字符串
(005) Longest Palindromic Substring
Longest Palindromic Substring:Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example1
Input: "babad",
Output: "bab",
Note: "aba" is also a valid answer.
Example2
Input: "cbbd",
Output: "bb".
分析：本题本质是string的操作。思路比较单一，就是遍历每个字符，对字符c的左右进行匹配，直到左右不相等，记录最长的长度和左边起始位置。tricky的地方是需要考虑回文是偶数个还是基数个的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
self.start = 0
self.length = 1
def checkPal(l,r):
while(l >= 0 and r <=len(s)-1 and s[l]==s[r]):
l -=1
r +=1
if(r-l-1 > self.length):
self.length = r-l-1
self.start = l + 1
for i in range(len(s)-1):
checkPal(i,i)
checkPal(i,i+1)
return s[self.start:self.start+self.length]
(014) Longest Common Prefix
Longest Palindromic Substring:Write a function to find the longest common prefix string amongst an array of strings
Example1
Input: ["a","a","b"],
Output: "",
Example2
Input: ["a","a"],
Output: "a".
分析：本题本质是string的操作和函数式的应用。刚开始以为找两两之间最长的LCP，后来才发现应该是所有字符串的LCP，感觉题目没说清楚。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
def lcp(s1,s2):
if len(s1) > len(s2):
s1, s2 = s2, s1
for i in range(len(s1)):
if(s1[i]!=s2[i]):
return s1[:i]
return s1
return reduce(lcp,strs) if strs else ""
Chapter 6 Context
Chapter 7 递归
(022) Generate Parentheses
Generate Parentheses:Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example1
given n = 3, a solution set is
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()",
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
def insert(state,left,right,result=[]):
if left == 0 and right == 0: result.append(state)
if left > 0:
insert(state + "(",left-1,right,result)
if right >0 and right > left:
insert(state + ")",left,right-1,result)
return result
return insert("",n,n)
(039) Combination Sum
Combination Sum: Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.
Example1
given candidate set [2, 3, 6, 7] and target 7
A solution set is:
[
[7],
[2, 2, 3]
]
分析：本题本质是递归。用尾递归逻辑比较清晰，需要注意backtracking有两个地方，1是state相加大于target，2是state不是按照从小到大排列(去重，[2,2,3],[2,3,2],[3,2,2]只有[2,2,3]符合)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = sorted(candidates)
result = []
def combine(state):
if sum(state) > target:
return
elif sum(state) == target:
result.append(state)
else:
for i in candidates:
if state and state[-1] > i: continue
combine(state+[i])
combine([])
return result
(040) Combination Sum II
Combination Sum II: Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations..
Example1
given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
分析：本题本质是递归。
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 combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = sorted(candidates)
result=[]
def combine(state,remain):
if sum(state) > target:
return
elif sum(state) == target:
result.append(state)
return
else:
for i in range(len(remain)):
if state and state[-1] > remain[i]: continue
if i > 0 and remain[i-1] == remain[i]:continue
newValue = remain[i]
newRemain = list(remain)
del newRemain[i]
combine(state+[newValue],newRemain)
combine([],candidates)
return result
(046）Permutations
Permutations:Given a collection of distinct numbers, return all possible permutations.
Example1
Input: [1,2,3] have the following permutations:
Output: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
分析：本题的本质是递归。可以看参考SICP对于procedure的抽象
用递归表示当前的组合state和还剩下的可能的元素remain，逻辑非常清楚。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
def permutation(state,remain):
if len(state) > len(nums):
return
elif len(state) == len(nums):
result.append(state)
return
else:
for i in range(len(remain)):
next = remain[i]
new_remain = list(remain)
del new_remain[i]
permutation(state+[next],new_remain)
permutation([],nums)
return result
(051）N Queuens
N Queuens:The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other in any vertical, horizontal or diaganol directions.
Example1
Input: 4,
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
分析：本题的本质是递归。可以看参考SICP对于procedure的抽象 用递归表示寻找NQueues的逻辑非常清晰和简洁，当state长度为N时返回，否则判断新加入的第i行的尝试的pos是否和原来state冲突(若冲突，则尝试第i行的尝试的pos+1;若不冲突，继续上述操作，直到state长度为N，加入到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
32
33
34
35
36
37
38
39
40
41
42
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.results = []
def conflict(state, col):
row = len(state)
for i in range(row):
if abs(state[i] - col) in (0, row - i):
return True
return False
def queuen(nums=8, state=()):
if len(state) == nums:
self.results.append(state)
return
for pos in range(nums):
if conflict(state, pos):
continue
else:
queuen(nums, state + (pos,))
def toString(list):
list_string = []
for oneAns in list:
oneAns_string = []
for col in range(len(oneAns)):
col_string = ""
for id in range(len(oneAns)):
if id == oneAns[col]:
col_string += "Q"
else:
col_string +="."
oneAns_string.append(col_string)
list_string.append(oneAns_string)
return list_string
queuen(n)
return toString(self.results)
5 参考资料
6 template
(005) Longest Palindromic Substring
Longest Palindromic Substring:Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example1
Input: "babad",
Output: "bab",
Note: "aba" is also a valid answer.
Example2
Input: "cbbd",
Output: "bb".
1
class Solution(object):
