1、判断链表循环
141、 Linked List Cycle
判断链表是否是循环链表。思路主要有两种，第一种是将所有的节点的next指向head，如果存在环则会出现某个节点的next是head，否则最后一个元素next为None，非环。
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
node = head
while node is not None:
if node.next == head:
return True
temp = node.next
node.next = head
node = temp
return False
第二种思路是使用两个指针，一个快指针和一个慢指针，但效率并不是很高，因为不一定会在一个回合内相遇，可能需要几个遍历才能相遇。
def hasCycle1(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
由于明确要求不能修改链表，所以141中第一种方法就不能使用。由于第二种方法相遇节点并不一定是起始节点，需要特殊分析，如下：
image.png
image.png
参考来源：http://blog.csdn.net/ebowtang/article/details/50507131
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if fast is None or fast.next is None:
return None
fast = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
2、两数之和、三数之和
1、two sum
找到两数之和为target值的下标号列表。最简单的方法就是哈希表，如下：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
lookup = {}
for i, item in enumerate(nums):
if target - item in lookup:
return [lookup[target-item], i]
lookup[item] = i
return [-1, -1]
two sum还有一种方法是双指针，一头一尾，但是需要对元素进行排序。这样的话如果不考虑排序时间复杂度，可以在O(n)内解决。
15. 3Sum
找到三数之和为0的所有组合，先要对数组进行排序，确定一个数后再利用two sum，由于数组是排序，解决two sum问题可以采用双指针，从前和后两个方向查找。同时，这个题目需要注意去重问题，具体到实现上在两个地方，如下：
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res, length = [], len(nums)
if length < 3:
return res
nums = sorted(nums)
for i in xrange(length-2):
if i > 0 and nums[i] == nums[i-1]:
continue
temp = 0 - nums[i]
left, right = i + 1, length - 1
while left < right:
if nums[left] + nums[right] == temp:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[right] == nums[right-1]:
right -= 1
while left < right and nums[left] == nums[left+1]:
left += 1
right -= 1
left += 1
elif nums[left] + nums[right] > temp:
right -= 1
else:
left += 1
return res
16、 3Sum Closest
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
res, length = -1, len(nums)
if length < 3:
return res
nums.sort()
res = float("inf")
for i in xrange(length-2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i + 1, length - 1
while left < right:
temp = nums[i]+nums[left]+nums[right]
if abs(temp - target) < abs(res - target):
res = temp
if temp > target:
right -= 1
elif temp < target:
left += 1
else:
return target
return res
找到三个数使之与指定target值最接近，思路和15题类似，先固定一个数，找另外两个数，使用双指针的方法，确定判断指针移动条件时需要注意。
3、house rober问题
题意要求不能连续抢相邻两家。
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
if len(nums) == 1:
return nums[0]
rob, notrob = nums[0], 0
for item in nums[1:]:
rob, notrob = notrob + item, max(notrob, rob)
return max(rob, notrob)
加入约束条件，第一家和最后一家不能同时抢。
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return sum(nums)
# situation 1 rob first
rob, notrob = nums[0], nums[0]
for item in nums[2:]:
rob, notrob = notrob + item, max(rob,notrob)
# situation 2 notrob first
rob1, notrob1 = nums[1], 0
for item in nums[2:]:
rob1, notrob1 = notrob1 + item, max(rob1, notrob1)
return max(notrob,rob1,notrob1)
4 path sum问题
1）存在问题，是否有路径和为某一个数
leetcode 112
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a boolean
def hasPathSum(self, root, sum):
if root is None:
return False
if root.left is None and root.right is None and root.val == sum:
return True
return self.hasPathSum(root.left, sum - root.val) or \
self.hasPathSum(root.right, sum - root.val)
需要注意的是一定是判断到叶子节点（左右子树均为None），然后利用树的天然递归性求解。
2）求解所有方案问题
leetcode 113
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root: return []
if root.left is None and root.right is None:
if sum == root.val:
return [[root.val]]
else:
return []
a = self.pathSum(root.left, sum - root.val) + \
self.pathSum(root.right, sum - root.val)
return [[root.val] + i for i in a]
上面的方法比较巧妙，但也比较难想得到。这种类型的问题首先想到的是遍历，类似回溯求解合适解，
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if root is None:
return []
self.res = []
self.helper(root, [], expectNumber)
return self.res
def helper(self, root, subres, number):
if number == root.val and root.left is None and root.right is None:
subres.append(root.val)
self.res.append(subres[:])
subres.pop()
return
if number < 0:
return
if root.left:
subres.append(root.val)
self.helper(root.left, subres, number-root.val)
subres.pop()
if root.right:
subres.append(root.val)
self.helper(root.right, subres, number - root.val)
subres.pop()
其实，leetcode 112是DFS的具体应用，遍历每一种情况，而leetcode 113中下面解法是回溯。
5、全排列问题
leetcode中46题，可以比较方便使用回溯，但有个前提，就是所有的数字都是不相同的。
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.result = []
sub = []
self.dfs(nums,sub)
return self.result
def dfs(self, nums, sub):
if len(sub) == len(nums):
print sub
self.result.append(sub[:])
for m in nums:
if m in sub:
continue
sub.append(m)
self.dfs(nums, sub)
sub.remove(m)
上面的方法比较直接，但是效率不高，有一种通用的方法：
class Solution:
def Permutation(self, ss):
# write code here
self.res = []
self.helper(list(ss), 0, len(ss))
return self.res
def helper(self, s, start, end):
if start > end:
return
if start == end:
self.res.append(s[:])
else:
for i in range(start, end):
s[start], s[i] = s[i], s[start]
self.helper(s, start + 1, end)
s[start], s[i] = s[i], s[start] # 也是回溯的思想
s = Solution()
print s.Permutation('abc')
输出为：
[['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'b', 'a'], ['c', 'a', 'b']]
理论基础：
image.png
而在剑指offer中的26题，情况不一样，要无重复，并且输入是字符串，如果用交换方法的化在python中不行，因为python中不能给字符串赋值。
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if ss == '':
return []
self.res = set()
self.helper(list(ss), 0, len(ss))
return sorted(self.res)
def helper(self, s, start, end):
if start > end:
return
if start == end:
self.res.add(''.join(s))
else:
for i in range(start, end):
s[start], s[i] = s[i], s[start]
self.helper(s, start + 1, end)
s[start], s[i] = s[i], s[start]
import itertools
class Solution2:
def Permutation(self, ss):
# write code here
result = []
if not ss:
return []
else:
res = itertools.permutations(ss)
for i in res:
if "".join(i) not in result:
result.append("".join(i))
return result
6、组合问题
7、动态规划路径问题
给定一个 m x n 矩阵，求出左上节点到右下节点的一条最小路径。
这样的题目看起来是要找到一条路径，但还是需要将所有的中间节点的值都求出来。
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
res = [[0 for _ in xrange(n)] for _ in xrange(m)]
res[0][0] = grid[0][0]
for i in xrange(1, m):
res[i][0] = res[i-1][0] + grid[i][0]
for j in xrange(1, n):
res[0][j] = res[0][j-1] + grid[0][j]
for i in xrange(1, m):
for j in xrange(1, n):
res[i][j] = min(res[i-1][j], res[i][j-1]) + grid[i][j]
return res[m-1][n-1]
def minpathsum2(self,grid):
'''
'''
res = grid[0]
m, n = len(grid), len(grid[0])
for j in xrange(1, n):
res[j] = res[j-1] + grid[0][j]
for i in xrange(1, m):
res[0] = res[0] + grid[i][0]
for j in xrange(1, n):
res[j] = min(res[j], res[j-1]) + grid[i][j]
return res[-1]
第一种方法是简单直接的，使用一个二维数组保存中间结果，如果原数组可以直接修改的话可以不用创建一个新的数组。第二种方法只用了一个一维数组，不难理解。
一维数组优化方法详细参考 https://blog.csdn.net/happyaaaaaaaaaaa/article/details/50856112
8、排序链表删除问题
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# 重复的节点不保存
class Solution:
def deleteDuplication(self, pHead):
# write code here
if pHead is None or pHead.next is None:
return pHead
head = pHead
while pHead and pHead.next:
if pHead.val != pHead.next.val:
pHead = pHead.next
else:
pHead.next = pHead.next.next
return head
# 删除重复节点，包括本身节点
class Solution1:
def deleteDuplication(self, pHead):
# write code here
if pHead is None or pHead.next is None:
return pHead
dummy = ListNode(-1)
dummy.next = pHead
pre, head = dummy, dummy
while pHead and pHead.next:
if pHead.val != pHead.next.val:
pHead = pHead.next
pre = pre.next
else:
while pHead and pHead.next and pHead.val == pHead.next.val:
pHead = pHead.next
pHead = pHead.next
pre.next = pHead
return dummy.next
上面为两种场景，第一是保存一个重复节点，第二是不保存。需要注意的是一些细节。
Java版
public class DeleteNodeInLinklist {
public static ListNode DeleteDupNode(ListNode node){
if(node==null || node.next==null)
return node;
ListNode dummy = new ListNode(-1);
dummy.next = node;
ListNode ptr = dummy;
while(node != null && node.next != null){
if(node.val != node.next.val){
node = node.next;
ptr = ptr.next;
}else {
while((node != null) && (node.next != null) && (node.val==node.next.val)){
node = node.next;
}
node = node.next;
ptr.next = node;
}
}
return dummy.next;
}
// 删除重复节点但保留一个
public static ListNode DeleteDupNodeWithOne(ListNode node){
if(node==null || node.next==null)
return node;
ListNode current = node;
while(current != null && current.next != null){
if(current.val == current.next.val)
current.next = current.next.next;
else
current = current.next;
}
return node;
}
}
网友评论