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

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

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

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

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

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

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

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

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

  10. 7 Sort Methods

    # -*- coding: utf-8 -*-
# 一、冒泡排序 BubbleSort，时间复杂度O(n2)
# 冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
# 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
# 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
# 针对所有的元素重复以上的步骤，除了最后一个。
# 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
def bubble_sort(arry):
    n = len(arry)
    for i in range(n):
        for j in range(1,n-i):    # 从第二个数到上次沉淀的数前的数，开始往前比较
            if arry[j-1] > arry[j]:
                arry ...
    read more

« Page 11 / 21 »

blogroll

social