philokey的笔记

Search in Rotated Sorted Array

 2014-08-16 by philokey

解法：二分法，分别讨论左边单调递增还是右边单调递增。当有重复元素时， A[l] == A[m] 的情况要单独拿出来考虑， 因为有[l,m] => [1,3,1]这种情况

class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        l, r = 0, len(A) - 1
        while l <= r:
            m = (l + r) / 2
            if A[m] == target: return True
            if A[l] < A[m]:
                if A[l] <= target < A[m]:
                    r = m - 1
                else:
                    l = m + 1
            elif A[l] > A[m]:
                if A[m] < target <= A[r]:
                    l = m + 1
                else:
                    r = m - 1
            else :
                l += 1
        return False

Longest Valid Parentheses @ LeetCode
2014-08-14 by philokey

题意： 给出括号序列，问最长的连续合法括号子序列长度是多少

解法：用一个栈记录左括号, 右括号和在数组中的下标, 如果当前括号是右括号且栈顶是左括号, 则弹栈并更新答案

class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        sLen, stack, ret = len(s), [(-1, ')')], 0
        for i in range(sLen):
            if stack[-1][1] == '(' and s[i] == ')':
                stack.pop()
                ret = max(ret, i - stack[-1][0])
            else ...
read more

Unique Paths II @ LeetCode
2014-08-14 by philokey

题意：给n*m的格子，1有障碍物，0表示没有障碍物，问从左上角到右下角有几种走法，其中有障碍物的格子不能通过。

解法：

动态规划。

初始化第一行和第一列时遇到障碍物就停止

dp[i][j] = dp[i-1][j] + dp[i][j-1], 如果grid[i][j]有障碍物, dp[i][j] = 0

class Solution:
    # @param obstacleGrid, a list of lists of integers
    # @return an integer
    def uniquePathsWithObstacles(self, obstacleGrid):
        n, m = len(obstacleGrid), len(obstacleGrid ...
read more

Unique Binary Search Trees @ LeetCode
2014-08-13 by philokey

题意：给定 1-n 共n个数， 问可以组成多少种不同的二分查找树。

解法：动态规划。

dp[n] 表示有n个数时，构成不同二分查找树的个数。转移方程为：

$$ dp[n] = \sum_{i=0}^{n-1}dp[i]*dp[n-i-1] $$
class Solution:
    # @return an integer
    def numTrees(self, n):
        dp = [0 for i in range(n+1)]
        dp[0] = 1
        for i in range(1,n+1):
            for ...
read more