1. 75. Sort Colors

    # -*- coding: utf-8 -*-
# track两个index，一个是red的index，一个是blue的index，两边往中间走。
# i从0到blue index扫描，
# 遇到0，放在red index位置，red index后移；
# 遇到2，放在blue index位置，blue index前移；
# 遇到1，i后移。
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        red, blue = 0, len(nums)-1   # red means position ...
    read more

  2. 73. Set Matrix Zeroes

    class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if len(matrix)==0:
            return
        rownum = len(matrix)
        colnum = len(matrix[0])
        row = [False for i in range(rownum)]  # false * rownum
        col = [False for i in range(colnum ...
    read more

  3. 71. Simplify Path

    class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        places = [p for p in path.split("/") if p != "." and p != ""]
        l = []
        for p in places:
            if p != '..':
                l.append(p)
            else:
                if len(l) > 0:   # '..' means return parent path
                    l.pop()

        return '/' + '/'.join(l)

if __name__ == "__main__ ...
    read more

  4. 70. Climbing Stairs

    class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        stepLst = [1] * (n+1)
        start = 2
        while start <= n:
            stepLst[start] = stepLst[start-1] + stepLst[start-2]
            start += 1
        return stepLst[n]

if __name__ == "__main__":
    answer=Solution()
    print answer.climbStairs(3)
    read more

  5. 69. Sqrt(x)

    class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        sr = x
        while sr**2 > x:
            better = (sr+x/sr)/2
            sr = better
        return sr

if __name__ == "__main__":
    answer=Solution()
    print answer.mySqrt(2)
    read more

  6. 67. Add Binary

    class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        alist = [int(i) for i in list(str(a))]
        blist = [int(i) for i in list(str(b))]

        lengtha = len(alist)
        lengthb = len(blist)
        if lengtha < lengthb:
            alist, blist = blist, alist
            lengtha, lengthb = lengthb ...
    read more

  7. 66. Plus One

    class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        reverse_digits = digits[::-1]
        if reverse_digits[0] + 1 != 10:
            reverse_digits[0] += 1
            return reverse_digits[::-1]
        else:
            carry = 1
            for pos, val in enumerate(reverse_digits):
                if val + carry == 10:
                    reverse_digits[pos] = 0
                    carry = 1
                else:
                    reverse_digits[pos] = val ...
    read more

  8. 64. Minimum Path Sum

    class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        m = len(grid)
        n = len(grid[0])

        if m < 2 or n < 2: return sum([sum(i) for i in grid])  # single row or column

        for i in xrange(1, m):             # set first column
            grid[i ...
    read more

  9. 63. Unique Paths II

    class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        return self.unique(m,n,obstacleGrid,path={})

    def unique(self,m,n,obstacleGrid,path):
        if m == 1 and n == 1 and obstacleGrid[m-1][n-1] == 0:  # base statement ...
    read more

  10. 62. Unique Paths

    # have to step (m-1) on horizontal axis, step (n-1) on vertical axis.
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return self.unique(m,n,path={})   # must set path outside. can't set path inside a function, or it will initiate every ...
    read more

« Page 10 / 21 »

blogroll

social