题目

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]

十字路口的红绿灯，每分钟交替一次的话，你在红灯的时候到达的平均等待时间是多久？

公交车平均五分钟来一次的话你等公交车要多久？

错啦！这就是经典的等车悖论，因为公交车平均每五分钟来一辆，那么你的平均等待时间将是五分钟。

均匀分布和指数分布

红绿灯和公交车有什么不同的地方呢？

什么是TLDR？

TLDR 它本身

tl;dr 是一个网络词汇，和十动然拒这类差不多，是个缩写。它的全称是「Too Long; Don’t Read」，翻译成中文的话就叫「太长不看」。它兴起于一些论坛，为了说明「楼主你的破文章又臭又长」，不过后来有许多文章的开头也用

这个东西为啥叫太长不看？

一个叫「太长不看」的命令行工具显然是解决一些令程序员一个脑袋两个大的太长的东西，而这个东西就是 Linux man pages。它到底有多长呢，man pages的官方压缩包是 2M 多的大小，解压后是 16M。 16M 确实不算大了，然而这 16M 可是纯文本啊。用来做类比的话，一本50万字的中文小说变成纯文本文件之后也就那么 1M 多，可想而知这甚至是全英文 man pages 有多长了。

我们却需要它

作为程序员有时又十分需要 man pages。 虽然它长，你又不得不去读它：比如说，你知道 ssh 的基本用法是

1

ssh username@remote_host

然而当你想换个端口或是利用私钥登入服务器的时候就傻眼了，不得不打开 man pages：

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

SH(1)                    BSD General Commands Manual                   SSH(1)

NAME
     ssh -- OpenSSH SSH client (remote login program)

SYNOPSIS
     ssh [-1246AaCfGgKkMNnqsTtVvXxYy] [-b bind_address] [-c cipher_spec]
         [-D [bind_address:]port] [-E log_file] [-e escape_char]
         [-F configfile] [-I pkcs11] [-i identity_file]
         [-J [user@]host[:port]] [-L address] [-l login_name] [-m mac_spec]
         [-O ctl_cmd] [-o option] [-p port] [-Q query_option] [-R address]
         [-S ctl_path] [-W host:port] [-w local_tun[:remote_tun]]
         [user@]hostname [command]

DESCRIPTION

以下省略一万字……

尽管机器学习从分类上而言只是人工智能（也就是常说的AI）的分支之一，但其本身也是一个相当巨大的命题。在未来的一段时间里，我将花时间在专栏写一些我比较熟悉的机器学习相关的概念和算法，最主要的目的是为了梳理自己的知识体系，也是希望和大家分享学习的历程和感悟，以达到交流的目的。

这两年大数据火了，机器学习、神经网络、数据挖掘、强化学习等等这些名词都火了，然而我常常在想，把这些名词挂在嘴边的我们，究竟能否在这个领域飞速发展的情况下，清楚地了解到自己说的每一个名词——谁是谁的分支，哪个和哪个又是同等关系或是没有关系的——在名词爆炸的状态下，想学什么，了解其基础概念是必不可少的。

与数据相关的概念

假如我们有一组天气数据，是来自全世界不同国家和地区的每日天气，内容包括最高温度、最低温度、平均湿度、风速之类的相关数据，例如数据的一部分是这样的：

在这组数据中，我们将称A市、B市、C市等市以及其情况的总和称为数据集（data set）。表格中的每一行，也就是某城市和它的情况被称为一个样例（sample/instance）。表格中的每一列（不包括城市），例如最高温度、最低温度，被称为特征（feature/attribute），而每一列中的具体数值，例如36℃ 、28℃，被称为属性值（attribute value）。数据中也可能会有缺失数据（missing data），例如B市的某时刻风速，我们会将它视作缺失数据。