题目

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.

题目

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]

如何登录新浪微博是令许多数据新手（包括我）头疼的大问题。由于新浪的反爬虫策略，网上的教程往往撑不过几个月，查阅到的资料在半年前或是一年前——而它们早就无法使用了，在你想开始爬虫的时候被活生生卡在了第一步。

简单而言，我使用的方法是通过 Selenium 模拟浏览器的行为，直接在浏览器中输入用户名和密码并登录，然后直接从浏览器中获取 Cookies。虽然听起来十分简单（实际上也十分简单），但是确实是十分有效的方式。只要一个网站能通过浏览器登陆，我们就可以简单改造这个程序来登录并获得想要的资料。

什么是Selenium？如何使用？

Selenium 是一个项目的名称，都与浏览器和网页测试相关。主要的工具也就是今天我们所要使用的，是WebDriver，是一个浏览器自动化工具。它为很多不同的语言提供了库，包括 Python、Java、Ruby 等。本文中我选择使用 Python 来进行操作，当然你也可以使用你熟悉的语言来进行操作。

在 Python中使用 Selenium 只需要通过pip安装 Selenium 提供的 Python 库。

1

pip3 install selenium  # 如果你使用 Python 2 ，请使用 pip install selenium

仅仅安装 Selenium 本身是不够的，你同时还需要安装 Driver 。你可以将 Driver 理解为浏览器本身的『驱动』，在程序中使用 Driver 就相当于你打开了一个浏览器做了些什么事情。

由于使用网页版微信，机器人往往不能够永远地在线。如果无法一直在线，也就失去了自动回复程序的意义。在此，我们使用两种方式来监控机器人程序：

1. 自动定时发送消息
2. 使用supervisor进行监控

自动发送消息

准备

如果需要定时发送消息，使用sleep方式来等待计时会阻塞线程，因此我们会使用threading来进行多线程的操作。把一个线程分配给自动给特定人发送微信消息。

定义自动发送消息的方法

在进行多线程操作之前，我们先定义一个自动发送消息的方法以备调用：

1
2
3
4
5

def send_online_notification(name):
    my_friend = ensure_one(bot.search(name))
    while True:
        my_friend.send('Hello!') # 你想发送的消息
        time.sleep(3600) # 一小时后在进行发送

wxpy的ensure_one()方法会确认返回的内容仅有一个值，如果返回的列表超过一个值（或是没有返回），它会进行报错。我们在这里寻找name相关的好友，并且保证只有一个这样的好友。如果你需要给多个好友发送消息，我建议再使用一个循环来遍历好友列表。

本篇的诞生来自于一朋友制作的表情机器人。当时觉得十分有趣，也希望加入到群聊机器人中，因此就向他讨要了源代码并制作了表情功能。在此我也再次感谢吴毅凡同学的协助！

准备工作

由于需要读取网页内容，本文中由于我个人偏好使用xpath来选择网页中元素，使用了lxml包，安装的话需要：

1

pip install lxml

如果你想要使用BeautifulSoup来处理网页，请安装：

1

pip install beautifulsoup4