题目

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1
2

Input: [10,2]
Output: "210"

Example 2:

1
2

Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

解题报告

首先，这是一个贪心问题，也就是说如果数字 a 和数字 b 比较 a 应该放在前面，那么整个字符串中 a 一定是会在 b 之前的；如果 a 比 b 前，b 比 c 前，a 一定会在 c 前面。这一点容易想到但是难以证明，因为这种比较相对于单纯比大小来说有违常理，但是存在规律。它和比较大小不同的是，比较大小先比较位数、再比较每一位大小；而这种比较大小的方式是可传递的。（为什么呢？因为是贪心，最好是证明哦～）

其次就是写程序的问题。众所周知大部分编程语言都可以给排序函数传入一个比较函数，比较任意两个元素的大小。由于这题的所有元素是完全可以排序的，我们只要比较两个字符串拼在一起的后数字大小就可以啦！

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from functools import cmp_to_key

def scmp(a, b):
    return int(b+a) - int(a+b)

class Solution:
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        nums = [*map(str, nums)]
        nums = sorted(nums, key=cmp_to_key(scmp))
        return str(int(''.join(nums)))

题目

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

1
2
3
4
5

Input:
    2
   / \
  1   3
Output: true

Example 2:

1
2
3
4
5
6
7
8

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

解题报告

这题主要考查的是二叉搜索树的性质，也就是对于每一个节点来说，它左子树的所有元素都小于它，而右子树的所有元素都大于它。也就是说二叉搜索树在本题中不允许出现两个节点值相同的情况。

方法一：前序遍历检查是否满足顺序

二叉搜索树的一个重要特征是，它的前序遍历是符合大小顺序的，因为前序遍历用的是左中右的顺序，这应该就很好理解啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.traverse = []
        self.dfs(root)
        return all(a < b for a, b in zip(self.traverse, self.traverse[1:]))
        
    def dfs(self, node):
        if not node:
            return
        self.dfs(node.left)
        self.traverse.append(node.val)
        self.dfs(node.right)

方法二：另一种利用性质的递归

另一种方法来自于 Leet Code 的讨论区。这种方法的中心思想利用的是节点大小的传递性：对于每个节点来说，它的左子节点的最大值是这个节点的值，而最小值维持和这个节点的最小值相同，右子节点同理。

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

def check_node(node, l, r):
        if not node:
            return True
        return l < node.val and node.val < r and check_node(node.left, l, node.val) and check_node(node.right, node.val, r)
    
class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        l, r = float("-inf"), float("inf")
        return check_node(root, l, r)

题目

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.

题目

LeetCode 链接

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

1
2
3
4

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

题目

TopCoder链接

Problem Statement

The holidays are near. Hero would like to buy some candies, so he went to the store. In the store he found some boxes. Each box has a label with three positive integers a[i], b[i], and cost[i]. Their meaning is as follows: Obviously, cost[i] is the amount Hero has to pay to buy this box. The other two numbers promise that the box will contain exactly a[i] red candies and exactly b[i] blue candies (and nothing else). Hero knows that the total number of candies always matches the label, but the colors sometimes don’t. Sometimes, exactly one candy in the box has the opposite color. Thus, for each box we have three possibilities: instead of (a[i] red, b[i] blue) we can also get (a[i]+1 red, b[i]-1 blue) or (a[i]-1 red, b[i]+1 blue). Hero is going to buy some of the boxes. Then, he will bring them home, he will unpack all boxes and pool all candies together. Hero will be happy if the final pile of candies will contain at least K candies of the same color. Find the cheapest set of boxes such that it is guaranteed that Hero will be happy if he buys these boxes. Return the cost of that set of boxes. If it is impossible to guarantee Hero’s happiness, return -1 instead.

题目

LeetCode链接

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.

题目

LeetCode链接

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题目

LeetCode链接

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

1
2
3
4
5
6

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]