Eazow

Stay kind and positive

0%

Posted on Reading time ≈ 2 mins.

题目

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

Posted on Reading time ≈ 1 mins.

题目

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

Posted on Reading time ≈ 1 mins.

题目

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"

Posted on Reading time ≈ 1 mins.

题目

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"

Posted on Reading time ≈ 1 mins.

题目

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

Posted on Reading time ≈ 1 mins.

题目

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"

Posted on Reading time ≈ 1 mins.

题目

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

Posted on Reading time ≈ 1 mins.

题目

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"

Posted on Reading time ≈ 1 mins.

题目

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:

1
2
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
  • The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

难度

Easy

方法

遍历所有可能的时间，如果其中1的个数等于n，则将该时间加入返回的结果列表中

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        result = []
        for i in range(12):
            for j in range(60):
                if bin(i).count("1") + bin(j).count("1") == num:
                    result.append("%d:%02d" % (i, j))
        return result

assert Solution().readBinaryWatch(1) == ["0:01", "0:02", "0:04", "0:08", "0:16", "0:32", "1:00", "2:00", "4:00", "8:00"]

Posted on Reading time ≈ 1 mins.

题目

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

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

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

难度

Easy

方法

对于每个point，用一个map统计各个距离d下对应的其他point的个数n，即map的key为距离d，value为距离该point为d的其他point的个数n。然后An取2，即n*(n-1)。最后将各个point对应的n*(n-1)累加即可

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        result = 0
        for point_i in points:
            distance_map = {}
            for point_j in points:
                distance = (point_i[0] - point_j[0]) * (point_i[0] - point_j[0]) + \
                           (point_i[1] - point_j[1]) * (point_i[1] - point_j[1])
                distance_map[distance] = distance_map.get(distance, 0) + 1

            for distance in distance_map:
                count = distance_map[distance]
                result += count * (count - 1)

        return result

assert Solution().numberOfBoomerangs([[0,0], [1,0], [2,0]]) == 2