Eazow

晚上11点前睡，你能做到吗？

1

前几天，北京大学法学院2017迎新典礼上，白建军教授给新生的建议火遍全网：“早睡早起+把微信朋友圈控制在10人以内+拒绝以陪读为目的的表白。这个办法能不能把你弄成精英中的精英，我不知道。但试过的，都说好。”

这3条建议中，我试过“早睡早起”这一条。抓住早睡这个突破点后，早起也能轻松上手，投资小，回报大，性价比高。

但我观察周围，这大约是个年轻人全民熬夜的年代。有人工作分工没办法，有人夜晚干活效率高，有人单纯性晚睡拖延症。许多人在睡觉方面缺乏自制力，晚上不想睡，手机像长在手上似的；早上起不来，醒来就跟闹钟置气，一天到晚觉得困。

原来在我们这个时代，早睡早起，真的变成了最知易行难的自律。

虽然网上不时会曝出因为熬夜导致健康受损甚至猝死的案例，不管当事人如何苦口婆心地劝诫一定要规律作息，千万不要熬夜，可还是有许多人会说，道理我们都知道的，可就是忍不住熬夜啊。

2

以前我在深圳工作时，有段时间早上五点多就起床，去附近的荔香公园快走。我发现这个时段公园里老年人的密度极高，他们神采奕奕地进行着做操、跑步、挥鞭等各种锻炼。

而我看到年轻人密度最高的时段是晚上。我有时加班到晚上十点多，在赶回家睡觉的路上，看到写字楼里还有大片灯光，商场周围还有K歌聚会，便利店里还有人进人出。

这好像一幕滑稽戏，早睡早起的老年人和晚睡晚起的年轻人，处于不同的时区。结果，老年人状态越来越燃，年轻人却越活越没精神。

其实，早睡早起，是性价比最高的自律。

前东家大领导30多岁那年，大病一场之后，作息习惯大换血，他把工作模式从没日没夜改为早睡早起，工作绩效不减反增；

我婶婶婚后越长越好看，随着年纪增长，她的皮肤却比初见时细腻白嫩了很多，她说因为自己单身时熬的夜，结婚后都戒了；

我早上五点多去公园的事迹被同事们听说后，都叉着腰笑我过着老年人的生活，可我那时的工作效率和身体状态都处于巅峰级别。

题目

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R(Right), L(Left), U(Up) and D(down). The output should be true or false representing whether the robot makes a circle.

Example 1:

1
2

Input: "UD"
Output: true

Example 2:

1
2

Input: "LL"
Output: false

难度

Easy

方法

对每个方向计数，如果L出现的次数==R出现的次数，并且U出现的次数==D出现的次数，则robot会回到初始位置，返回True；否则返回False

python代码

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

class Solution(object):
    def judgeCircle(self, moves):
        """
        :type moves: str
        :rtype: bool
        """
        counter = {}
        for c in moves:
            counter[c] = counter.get(c, 0) + 1

        return counter.get("L") == counter.get("R") and counter.get("U") == counter.get("D")

assert Solution().judgeCircle("UD") == True
assert Solution().judgeCircle("LL") == False

题目

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

1
2
3
4
5
6
7
8
9

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

1
2
3
4
5
6
7

Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

难度

Easy

方法

首先将最小值minimum和第二小值second_minimum置为maxint，递归遍历二叉树，如果节点值比最小值小，则将最小值赋给第二小值，然后将最小值更新为节点值；如果节点值比最小值大，并且节点值小于第二小值，则将第二小值更新为节点值。节点遍历后如果第二小值==maxint，即没有第二小值，则返回-1

python代码

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

import sys

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

class Solution(object):
    def findSecondMinimumValue(self, root):
        self.min = sys.maxint
        self.second_min = sys.maxint
        def traverse(node):
            if node:
                if node.val < self.min:
                    self.second_min = self.min
                    self.min = node.val
                elif node.val < self.second_min and node.val != self.min:
                    self.second_min = node.val

                traverse(node.left)
                traverse(node.right)

        traverse(root)
        if self.second_min != sys.maxint:
            return self.second_min
        return -1

root = TreeNode(2)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)

assert Solution().findSecondMinimumValue(root) == 5

题目

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
Example 1:

1
2
3

**Input:** [1,3,2,2,5,2,3,7]
**Output:** 5**
Explanation:** The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

难度

Easy

方法

用一个map存放所有值出现的次数，对于map中的每个num，求出num和num+1出现的次数之和，找出最大值即可

python代码

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

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_count = {}
        for num in nums:
            nums_count[num] = nums_count.get(num, 0) + 1

        result = 0
        for num in nums_count:
            count = nums_count[num]
            if nums_count.get(num+1):
                result = max(result, count + nums_count[num+1])
        return result

assert Solution().findLHS([1,3,2,2,5,2,3,7]) == 5

题目

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
Note:

1. All letters in hexadecimal (a-f) must be in lowercase.
2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

1
2
3
4

Input:
26
Output:
"1a"

Example 2:

1
2
3
4

Input:
-1
Output:
"ffffffff"

难度

Easy

方法

对于num，每次num&15便可取到最右的4个bit位，然后num>>4循环处理即可将num转换为16进制。因为num范围为32bit位，因此最多右移8次，每次右移4个bit位。当num不为0时，转换为16进制后，前面有0需去除。

python代码

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

class Solution(object):
    def toHex(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num == 0:
            return "0"
        map = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"]
        hex = ""
        for i in range(8):
            hex = map[num & 0xf] + hex
            num = num >> 4

        return hex.lstrip("0")

assert Solution().toHex(-1) == "ffffffff"
assert Solution().toHex(26) == "1a"

题目

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

难度

Easy

方法

从低位到高位相加，每一位的结果为除10取余，如果有进位1，则在下一位求和的时候需要+1，循环处理即可。注意最高位相加后如果有进位，需要在结果的最前面补1

python代码

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

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        i = len(num1) - 1
        j = len(num2) - 1
        num = ""
        carry = 0
        while i >= 0 or j >= 0:
            result = carry
            if i >= 0:
                result += int(num1[i])
            if j >= 0:
                result += int(num2[j])
            if result >= 10:
                carry = 1
            else:
                carry = 0
            num = str(result % 10) + num
            i -= 1
            j -= 1
        if carry == 1:
            num = "1" + num
        return num

assert Solution().addStrings("111", "234965") == "235076"
assert Solution().addStrings("999", "1") == "1000"

题目

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

1
2
3
4
5

    1
   / \
  2   3
 / \     
4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

难度

Easy

方法

求出每个节点左右子树的深度，相加即为该节点对应的diameter，最后取最大的diameter即可

python代码

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

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

class Solution(object):
    def diameterOfBinaryTree(self, root):
        self.diameter = 0
        def depth(node):
            if node:
                l_depth = depth(node.left)
                r_depth = depth(node.right)
                self.diameter = max(self.diameter, l_depth + r_depth)
                return max(l_depth, r_depth) + 1
            return 0

        depth(root)
        return self.diameter


root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
assert Solution().diameterOfBinaryTree(root) == 3

题目

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:

1
2

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

1. The string consists of lower English letters only.
2. Length of the given string and k will in the range [1, 10000]

难度

Easy

方法

每次处理s[0:2k]，将s[0:k]逆序后拼接s[k:2k]，然后将s[2k:]赋值给s，循环处理直至s为空即可

python代码

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

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        result = ""
        while s:
            temp = s[0:k]
            result += temp[::-1] + s[k:2*k]
            s = s[2*k:]
        return result

assert Solution().reverseStr("abcdefg", 2) == "bacdfeg"

题目

You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. ‘A’ : Absent.
2. ‘L’ : Late.
3. ‘P’ : Present.

A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

1
2

Input: "PPALLP"
Output: True

Example 2:

1
2

Input: "PPALLL"
Output: False

难度

Easy

方法

对'A'和'L'计数，如果'A'出现的次数>1，返回False；如果'L'连续出现的次数>2，则返回False；其他情况返回True

python代码

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

class Solution(object):
    def checkRecord(self, s):
        """
        :type s: str
        :rtype: bool
        """
        a_count = 0
        l_count = 0
        for c in s:
            if c == "A":
                a_count += 1
                l_count = 0
                if a_count > 1:
                    return False
            elif c == "L":
                l_count += 1
                if l_count > 2:
                    return False
            else:
                l_count = 0

        return True

assert Solution().checkRecord("PPALLP") == True
assert Solution().checkRecord("PPALLL") == False
assert Solution().checkRecord("ALPP") == True

题目

Given an integer, return its base 7 string representation.

Example 1:

1
2

Input: 100
Output: "202"

Example 2:

1
2

Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

难度

Easy

方法

对num取除以7的余数，即为最低位的数，然后将num/7赋值给num，继续取num除以7的余数即为倒数第二位的数，依次类推。注意num为0时需要返回"0"

python代码

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

class Solution(object):
    def convertToBase7(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num == 0:
            return "0"
        symbol = ""
        if num < 0:
            num = 0 - num
            symbol = "-"

        result = ""
        while num > 0:
            result += str(num % 7)
            num = num / 7

        return symbol + result[::-1]

assert Solution().convertToBase7(100) == "202"
assert Solution().convertToBase7(-7) == "-10"