Python 刷题（想练python的可

Surrounded Regions

这道题要求将完全由‘X’包围的‘O’全部置为‘X’，也就是将由‘X’包裹的‘O’连通块全部置为‘X’的意思。在矩阵中找连通块，直接进行bfs就可以，如果有任意的一个‘O’到了边界处，那么这个‘O’连通块就没有被‘X’完全包围，否则则将全部的‘O’置为‘X’。刚开始可能是坐标计算手贱了把X和Y打错了，TLE了，后来改了就过了。

好久没写这种类型的bfs，一时半会儿手生，弱死的节奏啊。

class Solution:
    # @param board, a 9x9 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        
        if board==None:
            return
        
        n = len(board)
        if n==0:
            return
        m = len(board[0])
        
        vis = [None]*len(board)
        for i in range(len(board)):
            vis[i] = [0]*len(board[0])
        
        for i in range(n):
            for j in range(m):
                if board[i][j]=='O' and vis[i][j]==0:
                    self.check(board, vis, i, j)
        
    def check(self, board, vis, x, y):
        n = len(board)
        m = len(board[0])
        
        dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        flag = True
        q = []
        q.append((x, y))
        vis[x][y] = 1
        while len(q)!=0:
            curx, cury = q[0]
            q.remove(q[0])
            
            for i in range(4):
                tx = curx+dir[i][0]
                ty = cury+dir[i][1]
                if tx==-1 or tx==n or ty==-1 or ty==m:
                    flag = False
                    continue
                
                if board[tx][ty]=='O' and vis[tx][ty]==0:
                    q.append((tx, ty))
                    vis[tx][ty] = 1
                    
        if flag==False:
            return
        
        q = []
        q.append((x, y))
        vis[x][y]=2
        while len(q)!=0:
            curx, cury = q[0]
            q.remove(q[0])
            
            board[curx][cury] = 'X'

            for i in range(4):
                tx = curx+dir[i][0]
                ty = cury+dir[i][1]
                
                if tx==-1 or tx==n or ty==-1 or ty==m:
                    pass
                else:
                    if board[tx][ty]=='O' and vis[tx][ty]!=2:
                        q.append((tx, ty))
                        vis[tx][ty] = 2

Distinct Subsequences

典型的动态规划，给定串S和T，问S中有多少种可能的子序列使得该子序列正好和T相同。比如说S='aacb'，T='ab'，那么结果就是2.

这种直观感觉可以通过依次递推上去的，或者说是具有最优子结构性质的问题都是通过动态规划的方法来求解。定义状态dp[i][j]表示T的子串T[0, i]在S子串S[0, j]出现的合法的次数，那么状态转移方程如下：

if T[i] != S[j]，dp[i][j]=dp[i][j-1]

else if T[i] == S[j], dp[i][j] = dp[i][j-1] + dp[i-1][j-1]

注意初始化dp[0][j]=1，也就是说任意的空串都在S[0,j]中出现一次。

按照上面的状态转移方程写出代码就行了。

class Solution:
    # @return an integer
    def numDistinct(self, S, T):
        if S==None or T==None:
            return 0
        if len(S)==0 or len(T)==0:
            return 0
        S = '.' + S
        T = '.' + T
        dp = [[0]*len(S) for i in range(len(T))]
        for i in range(len(S)):
            dp[0][i] = 1
        for i in range(1, len(T)):
            for j in range(i, len(S)):
                dp[i][j] = dp[i][j-1]
                if T[i] == S[j]:
                    dp[i][j] += dp[i-1][j-1]
        return dp[len(T)-1][len(S)-1]

#s = Solution()
#print(s.numDistinct('rabbbit', 'rabbit'))
#print(s.numDistinct('abc', 'ac'))
#print(s.numDistinct('abaccac', 'ac'))

Copy List with Random Pointer

这道题还是挺有意思的，咋一看题不知道考点在哪里？看了挺久才理解原来是random指针和深拷贝。所谓为深拷贝是需要重新申请一块内存，使其结构与原链表完全相同。也就是说对应链表中的节点的label值要对应相同，并且random指针指向的对象也要对应到新的对象。

由于需要将原链表中的对象对应到新生成的对象，所以用一个dict来map原来的对象到新的对象。于是进行两遍遍历，第一遍生成新的链表，并且对新链表中的label值和next指针进行赋值，next指针直接指向新生成的下一个对象；第二遍遍历，实现新链表中random指针的赋值。

注意读懂题目，找到问题的trick所在。这道题我是用python写的，可以使用对象名，如果使用C++写的话，对象的标识就是对象的指针了，写法上应该差不多。奉上python代码：

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        if head == None:
            return None
            
        myMap = {}
        nHead = RandomListNode(head.label)
        myMap[head] = nHead
        p = head
        q = nHead
        while p != None:
            q.random = p.random
            if p.next != None:
                q.next = RandomListNode(p.next.label)
                myMap[p.next] = q.next
            else:
                q.next = None
            p = p.next
            q = q.next
        
        p = nHead
        while p!= None:
            if p.random != None:
                p.random = myMap[p.random]
            p = p.next
        return nHead
        

Binary Tree Maximum Path Sum

在一棵二叉树中找到任意的一条路径，使得该条路径上的所有节点的值之和最大，该路径可以起始于树中任意节点，终止于树中的任意节点。

初一看显然有点像一个序列的最大连续子段和，这道题其实也有点类似。

我们知道，任意一个合法的路径，必然是通过某个节点，我们称之为root，从左子树的某个节点开始，通过该root走到右子树的某个节点终止达到最大的路径和。那么我们只需要记录从子树某个点开始连续走到当前节点的最大的和就行了，显然如果是走到该节点之前的最大值小于0，那么前面那一段的值就抛弃（丢弃前面一段小于0的路径肯定更优，这个和最大子段和的思路是一样的）。于是我们可以得到通过该节点的最大的子段和为root.val+leftMax+rightMax，然后用该值更新全局最优解就可以了。

奉上代码吧，比较简单。

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    #def __init__(self):
    #    self.ans = 0
    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        self.ans = -0xFFFFFFF
        self.dfs(root)
        return self.ans
        
    def dfs(self, root):
        if root == None:
            return 0
        if root.left == None and root.right == None:
            self.ans = max(self.ans, root.val)
            return root.val
        
        leftMax = rightMax = 0
        if root.left != None:
            leftMax = max(0, self.dfs(root.left))
        if root.right != None:
            rightMax = max(0, self.dfs(root.right))
        
        self.ans = max(self.ans, leftMax+rightMax+root.val)
        return root.val+max(leftMax, rightMax)