1、判斷鏈表循環(huán)

141、 Linked List Cycle

判斷鏈表是否是循環(huán)鏈表。思路主要有兩種，第一種是將所有的節(jié)點(diǎn)的next指向head，如果存在環(huán)則會(huì)出現(xiàn)某個(gè)節(jié)點(diǎn)的next是head，否則最后一個(gè)元素next為None，非環(huán)。

# 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

第二種思路是使用兩個(gè)指針，一個(gè)快指針和一個(gè)慢指針，但效率并不是很高，因?yàn)椴灰欢〞?huì)在一個(gè)回合內(nèi)相遇，可能需要幾個(gè)遍歷才能相遇。

 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中第一種方法就不能使用。由于第二種方法相遇節(jié)點(diǎn)并不一定是起始節(jié)點(diǎn)，需要特殊分析，如下：

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、兩數(shù)之和、三數(shù)之和

1、two sum

找到兩數(shù)之和為target值的下標(biāo)號(hào)列表。最簡(jiǎn)單的方法就是哈希表，如下：

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還有一種方法是雙指針，一頭一尾，但是需要對(duì)元素進(jìn)行排序。這樣的話如果不考慮排序時(shí)間復(fù)雜度，可以在O(n)內(nèi)解決。

15. 3Sum

找到三數(shù)之和為0的所有組合，先要對(duì)數(shù)組進(jìn)行排序，確定一個(gè)數(shù)后再利用two sum，由于數(shù)組是排序，解決two sum問題可以采用雙指針，從前和后兩個(gè)方向查找。同時(shí)，這個(gè)題目需要注意去重問題，具體到實(shí)現(xiàn)上在兩個(gè)地方，如下：

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

找到三個(gè)數(shù)使之與指定target值最接近，思路和15題類似，先固定一個(gè)數(shù)，找另外兩個(gè)數(shù)，使用雙指針的方法，確定判斷指針移動(dòng)條件時(shí)需要注意。

3、house rober問題

題意要求不能連續(xù)搶相鄰兩家。

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)

加入約束條件，第一家和最后一家不能同時(shí)搶。

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）存在問題，是否有路徑和為某一個(gè)數(shù)

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)

需要注意的是一定是判斷到葉子節(jié)點(diǎn)（左右子樹均為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:
    # 返回二維列表，內(nèi)部每個(gè)列表表示找到的路徑
    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()

其實(shí)，leetcode 112是DFS的具體應(yīng)用，遍歷每一種情況，而leetcode 113中下面解法是回溯。

5、全排列問題

leetcode中46題，可以比較方便使用回溯，但有個(gè)前提，就是所有的數(shù)字都是不相同的。

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']]

理論基礎(chǔ)：

image.png

而在劍指offer中的26題，情況不一樣，要無(wú)重復(fù)，并且輸入是字符串，如果用交換方法的化在python中不行，因?yàn)閜ython中不能給字符串賦值。

# -*- 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、動(dòng)態(tài)規(guī)劃路徑問題

給定一個(gè) m x n 矩陣，求出左上節(jié)點(diǎn)到右下節(jié)點(diǎn)的一條最小路徑。
這樣的題目看起來是要找到一條路徑，但還是需要將所有的中間節(jié)點(diǎ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]

第一種方法是簡(jiǎn)單直接的，使用一個(gè)二維數(shù)組保存中間結(jié)果，如果原數(shù)組可以直接修改的話可以不用創(chuàng)建一個(gè)新的數(shù)組。第二種方法只用了一個(gè)一維數(shù)組，不難理解。
一維數(shù)組優(yōu)化方法詳細(xì)參考 https://blog.csdn.net/happyaaaaaaaaaaa/article/details/50856112

8、排序鏈表刪除問題

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
# 重復(fù)的節(jié)點(diǎn)不保存
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

# 刪除重復(fù)節(jié)點(diǎn)，包括本身節(jié)點(diǎn)
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

上面為兩種場(chǎng)景，第一是保存一個(gè)重復(fù)節(jié)點(diǎn)，第二是不保存。需要注意的是一些細(xì)節(jié)。
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;
    }
    // 刪除重復(fù)節(jié)點(diǎn)但保留一個(gè)
    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;
    }
}