首页 > itarticle > 牛客网leetcode编程题

牛客网leetcode编程题

admin 12月 03, 2020 0

牛客网LeetCode编程题

Minimum Depth of Binary Tree

Description

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7], 

1
2
3
4
5
 
 3
 / 
9  20
  /  
 15   7

return its minimum depth = 2. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class (object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        else:
            if not root.left:
                return self.minDepth(root.right) + 1
            if not root.right:
                return self.minDepth(root.left) + 1
            left = self.minDepth(root.left)
            right = self.minDepth(root.right)
            return min(left, right) + 1

Evaluate Reverse Polish Notation

Description

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1: 

1
2
3
 
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2: 

1
2
3
 
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3: 

1
2
3
4
5
6
7
8
9
10
 
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
import operator

class (object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        numbers, operators = [], {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.div}
        for token in tokens:
            if token not in operators:
                numbers.append(int(token))
            else:
                y, x = numbers.pop(), numbers.pop()
                numbers.append(int(operators[token](x*1.0, y)))
        return numbers.pop()

Max Points on a Line

Description

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1: 

1
2
3
4
5
6
7
8
9
10
 
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2: 

1
2
3
4
5
6
7
8
9
10
11
 
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
import collections

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class (object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        n = len(points)
        max_points = 0
        for i in range(n):
            slope_dict, duplicate = collections.defaultdict(int), 1
            start = points[i]
            for j in range(i+1, n):
                end = points[j]
                if start.x == end.x and start.y == end.y:
                    duplicate += 1
                else:
                    slope = float('inf')
                    if end.x - start.x != 0:
                        slope = (end.y - start.y) * 1.0 / (end.x - start.x)
                    slope_dict[slope] += 1         
            max_current = duplicate
            if slope_dict:
                max_current = duplicate + max(slope_dict.values())
            max_points = max(max_points, max_current)
        return max_points

Sort List

Description

Sort a linked list in O(n log n) time using constant space complexity.

Example 1: 

1
2
 
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
 
Input: -1->5->3->4->0
Output: -1->0->3->4->5
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class (object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        else:
            if not head.next:
                return head
            else:
                slow, fast = head, head.next
                while fast and fast.next:
                    slow = slow.next
                    fast = fast.next.next
                h1, h2 = head, slow.next
                slow.next = None
                left = self.sortList(h1)
                right = self.sortList(h2)
                if left.val < right.val:
                    h = left
                    left = left.next
                else:
                    h = right
                    right = right.next
                p = h
                while left and right:
                    if left.val < right.val:
                        p.next = left
                        p = p.next
                        left = left.next
                    else:
                        p.next = right
                        p = p.next
                        right = right.next
                if left:
                    p.next = left
                if right:
                    p.next = right
                return h

Insertion Sort List

Description

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1: 

1
2
 
Input: 4->2->1->3
Output: 1->2->3->4

Example 2: 

1
2
 
Input: -1->5->3->4->0
Output: -1->0->3->4->5
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class (object):
    def isSortList(self, head):
        while head and head.next:
            if head.val > head.next.val:
                return False
            else:
                head = head.next
        return True
    
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if self.isSortList(head):
            return head
        else:
            dummy, tail, cur = ListNode(float('inf')), head, head.next
            dummy.next = head
            while cur:
                pre = dummy
                while pre.next and cur.val > pre.next.val:
                    pre = pre.next
                if pre == tail:
                    tail, cur = cur, cur.next
                else:
                    tail.next = cur.next
                    cur.next, pre.next = pre.next, cur
                    cur = tail.next
            return dummy.next

Binary Tree Postorder Traversal

Description

Given a binary tree, return the postorder traversal of its nodes’ values.

Example: 

1
2
3
4
5
6
7
8
 
Input: [1,null,2,3]
   1
    
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def postorder(root):
            if not root:
                return None
            else:
                stack_first = [root]
                stack_second = []
                while stack_first:
                    cur = stack_first.pop()
                    if cur.left:
                        stack_first.append(cur.left)
                    if cur.right:
                        stack_first.append(cur.right)
                    stack_second.append(cur)
                while stack_second:
                    self.result.append(stack_second.pop().val)
                return self.result
        postorder(root)
        return self.result

Binary Tree Preorder Traversal

Description

Given a binary tree, return the preorder traversal of its nodes’ values.

Example: 

1
2
3
4
5
6
7
8
 
Input: [1,null,2,3]
   1
    
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def preorder(root):
            cur, stack = root, []
            while cur or stack:
                while cur:
                    self.result.append(cur.val)
                    stack.append(cur)
                    cur = cur.left
                cur = stack.pop()
                cur = cur.right
        preorder(root)
        return self.result

Reorder List

Description

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1: 

1
 
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2: 

1
 
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if head and head.next:
            fast, slow, pre = head, head, None
            while fast and fast.next:
                fast, slow, pre = fast.next.next, slow.next, slow
            pre.next, pre = None, None
            cur = slow
            while cur != None:
                cur.next, pre, cur = pre, cur, cur.next
            l1, l2 = head, pre
            dummy = ListNode(0)
            cur = dummy
            while l1 and l2:
                cur.next, cur, l1 = l1, l1, l1.next
                cur.next, cur, l2 = l2, l2, l2.next
            head = dummy.next

Linked List Cycle II

Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast, slow = fast.next, slow.next
                return fast
        return None

Linked List Cycle

Description

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space? 

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                return True
        return False
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能