1. 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

  2. 61. Rotate List

    # Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """

        if head==None:
            return head
        curNode = head
        size = 0
        while curNode!=None:
            size += 1
            curNode = curNode.next ...
    read more

  3. 60. Permutation Sequence

    class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """

    # if n=3, we have (3-1)! start with 1/2/3, and for 1/2/3+left part, left part have (2-1)! start with what is left
    # check the region that the sequence number ...
    read more

  4. 59. Spiral Matrix II

    class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        begin = 0
        nn=n*n
        nums=[]
        for i in range(nn,0,-1):
            nums.append(i)          # create a num list to use
        matrix=[[0 for x in range(n)] for y in range(n)]     # create an ...
    read more

  5. 58. Length of Last Word

    class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        l=s.split()
        return len(l[-1]) if len(l)>0 else 0

if __name__ == "__main__":
    answer=Solution()
    print answer.lengthOfLastWord("Hello World")
    read more

  6. 56. Merge Intervals

    # Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals.sort() # sort, firstly sort start, then end, example [2,19],[15,18]

        if len(intervals ...
    read more

  7. 55. Jump Game

    class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        length=len(nums)
        goal = length-1
        for i in range(length-1,-1,-1):
            if i+nums[i]>=goal:
                goal=i    # change goal to the position
        return goal==0   # fist position is possible


if __name__ == "__main__":
    answer ...
    read more

  8. 54. Spiral Matrix

    class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        begin=0
        m=len(matrix)-1
        if m<0:
            return []
        else:
            n = len(matrix[0])-1
            return self.rotate(matrix,begin,m,n)                     #-------|
                                                                     #|       |
    def rotate(self,l,start,end1,end2):  # traversal each peering   #|-------|
        r = []
        if ...
    read more

  9. 53. Maximum Subarray

    class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        else:
            curr=nums[0]
            largest=nums[0]
            for item in nums[1:]:
                curr=max(item,curr+item)
                largest=max(largest,curr)
        return largest

if __name__ == "__main__":
    answer=Solution()
    print answer.maxSubArray([1 ...
    read more

  10. infix-prefix-postfix

    # -*- coding: utf-8 -*-
from pythonds.basic.stack import Stack
# 中缀转后缀
def infixToPostfix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()

    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif ...
    read more

« Page 11 / 21 »

blogroll

social