Leetcode Hacking Practice -- Solution in Python Part 1

第 41 樓 / webdriver

算法問題推薦解法來了...

DFS.

解法（Python）

代碼:


class Solution:

    def combine(self, n, k):

        return self.combineRecur([], n, k, 1)

        

    def combineRecur(self, current, n, k, i):

        if k == 0:

            return [current]

        if i > n:

            return []

        return self.combineRecur(current, n, k, i + 1) + self.combineRecur(current + [i], n, k - 1, i + 1)

贊

花籃

投訴

踩

第 42 樓 / webdriver

S算法問題: Construct Binary Tree from Inorder and Postorder Traversal
問題描述:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

贊

花籃

投訴

踩

第 43 樓 / webdriver

算法問題推薦解法來了...

Recursion.

解法（Python）

代碼:


class Solution:

    def buildTree(self, inorder, postorder):

        # using dictionary for index lookup improves the performance of algorithm from O(N^2) to O(N), where N = |postorder|

        lookup = {}

        for i in range(len(inorder)):

            lookup[inorder[i]] = i 

        return self.buildTreeRecur(lookup, inorder, postorder, 0, len(postorder) - 1, len(postorder) - 1)

        

    def buildTreeRecur(self, lookup, inorder, postorder, in_start, in_end, post_end):

        if in_start > in_end:

            return None

        current = TreeNode(postorder[post_end])

        i = lookup[postorder[post_end]]

        current.left = self.buildTreeRecur(lookup, inorder, postorder, in_start, i - 1, post_end - (in_end - i) - 1)

        current.right = self.buildTreeRecur(lookup, inorder, postorder, i + 1, in_end, post_end - 1)

        return current

贊

花籃

投訴

踩

第 44 樓 / webdriver

S算法問題: Construct Binary Tree from Preorder and Inorder Traversal
問題描述:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

贊

花籃

投訴

踩

第 45 樓 / webdriver

算法問題推薦解法來了...

Recursion.

解法（Python）

代碼:


class Solution:

    def buildTree(self, preorder, inorder):

        # using dictionary for index lookup improves the performance of algorithm from O(N^2) to O(N), where N = |preorder|

        lookup = {}

        for i in range(len(inorder)):

            lookup[inorder[i]] = i 

        return self.buildTreeRecur(lookup, preorder, inorder, 0, len(preorder) - 1, 0)

        

    def buildTreeRecur(self, lookup, preorder, inorder, in_start, in_end, pre_start):

        if in_start > in_end:

            return None

        current = TreeNode(preorder[pre_start])

        i = lookup[preorder[pre_start]]

        current.left = self.buildTreeRecur(lookup, preorder, inorder, in_start, i - 1, pre_start + 1)

        current.right = self.buildTreeRecur(lookup, preorder, inorder, i + 1, in_end, pre_start + i - in_start + 1)

        return current

贊

花籃

投訴

踩

第 46 樓 / webdriver

S算法問題: Container With Most Water
問題描述:
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

贊

花籃

投訴

踩

第 47 樓 / webdriver

算法問題推薦解法來了...

From both sides to the center.

解法（Python）

代碼:


class Solution:

    def maxArea(self, height):

        i, j, max_area = 0, len(height) - 1, 0

        while i < j:

            max_area = max(max_area, (j - i) * min(height[i], height[j]))

            if height[i] < height[j]:

                i += 1

            else:

                j -= 1

        return max_area

贊

花籃

投訴

踩

第 48 樓 / webdriver

S算法問題: Convert Sorted Array to Binary Search Tree
問題描述:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

贊

花籃

投訴

踩

第 49 樓 / webdriver

算法問題推薦解法來了...

Recursion.

解法（Python）

代碼:


class Solution:

    def sortedArrayToBST(self, num):

        if len(num) == 0:

            return None

        mid = len(num) / 2

        current = TreeNode(num[mid])

        current.left = self.sortedArrayToBST(num[:mid])

        current.right = self.sortedArrayToBST(num[mid + 1:])

        return current

贊

花籃

投訴

踩

第 50 樓 / webdriver

S算法問題: Convert Sorted List to Binary Search Tree
問題描述:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

贊

花籃

投訴

踩

上一頁 1 2 3 456 7 8 ...32 下一頁

快速回復

由於您是游客狀態, 無法實現此功能, 請點擊此處登錄

Facebook用戶留言

相關功能

論壇