Eazow

Stay kind and positive

0%

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

Posted on Reading time ≈ 1 mins.

题目

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

1
2
Input: [1,2,3]
Output: 6

Example 2:

1
2
Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

难度

Easy

方法

注意有负数的情况。对nums排序，取max(nums[-3] * nums[-2] * nums[-1], nums[0] * nums[1] * nums[-1])

python代码

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = sorted(nums)
        return max(nums[-3] * nums[-2] * nums[-1], nums[0] * nums[1] * nums[-1])

assert Solution().maximumProduct([1,2,3,4]) == 24
assert Solution().maximumProduct([-4,-3,-2,-1,60]) == 720

Posted on Reading time ≈ 1 mins.

题目

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

1
2
3
4
5
6
7
8
Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

难度

Easy

方法

先统计每个字符出现的次数，对于出现偶数次的字符，能全部用于组成回文。对于出现基数次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
22
23
24
25
26
27
28
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        counter = {}
        for c in s:
            if counter.has_key(c):
                counter[c] += 1
            else:
                counter[c] = 1

        palindrome_length = 0
        single = False
        for key in counter:
            if counter[key] % 2 == 0:
                palindrome_length += counter[key]
            else:
                palindrome_length += counter[key] - 1
                single = True

        if single:
            palindrome_length += 1

        return palindrome_length

assert Solution().longestPalindrome("abccccdd") == 7

Posted on Reading time ≈ 1 mins.

题目

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

难度

Easy

方法

先用一个dict统计每个单词出现的次数，然后从头开始检查s的字符，如果字符出现次数为1，则返回该字符的位置; 如果所有字符出现字数都不为1，则返回-1

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        counter = {}
        for c in s:
            if counter.has_key(c):
                counter[c] += 1
            else:
                counter[c] = 1

        for i in range(len(s)):
            if counter[s[i]] == 1:
                return i
        return -1

assert Solution().firstUniqChar("leetcode") == 0
assert Solution().firstUniqChar("leveleetcode") == 2

Posted on Reading time ≈ 2 mins.

题目

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

1
2
3
4
5
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", 
"Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

  1. N is a positive integer and won’t exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

难度

Easy

方法

对数组排序，同时对其索引也排序，即排序后元素之前的索引被记录。排序后的元素对应的rank位置分别为Gold Medal, Silver Medal, Bronze Medal, 4, 5...，然后将该rank赋值给排序前索引对应的位置即可

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 findRelativeRanks(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        numsStrs = []
        for i in range(len(nums)):
            numsStrs.append(str(nums[i])+'-'+str(i))

        numsStrs = sorted(numsStrs, lambda x,y: cmp(int(x.split("-")[0]), int(y.split("-")[0])))[::-1]
        ranks = [''] * len(nums)
        for i in range(len(numsStrs)):
            index = int(numsStrs[i].split("-")[1])
            if i == 0:
                ranks[index] = "Gold Medal"
            elif i == 1:
                ranks[index] = "Silver Medal"
            elif i == 2:
                ranks[index] = "Bronze Medal"
            else:
                ranks[index] = str(i+1)
        return ranks

assert Solution().findRelativeRanks([1, 2, 3, 4, 5]) == ["5", "4", "Bronze Medal", "Silver Medal", "Gold Medal"]
assert Solution().findRelativeRanks([10, 3, 8, 9, 4]) == ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

Posted on Reading time ≈ 1 mins.

题目

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Example:

1
2
3
4
5
6
7
8
9
10
Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

  1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.
  2. All the tilt values won’t exceed the range of 32-bit integer.

难度

Easy

方法

对该二叉树进行后续遍历，算出每个节点的左右子树之和的差的绝对值，累加到最后的result中。然后将节点值替换为左右子树节点值之和。

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
36
37
38
39
40
41
42
43
44
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.result = 0
        self.traverse(root)
        return self.result

    def traverse(self, node):
        if node:
            self.traverse(node.left)
            self.traverse(node.right)

            if node.left and node.right:
                self.result += abs(node.right.val - node.left.val)
                node.val += node.right.val + node.left.val
            elif node.left:
                self.result += abs(node.left.val)
                node.val += node.left.val
            elif node.right:
                self.result += abs(node.right.val)
                node.val += node.right.val

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
assert Solution().findTilt(root) == 7

root = TreeNode(-8)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.left.left = TreeNode(-8)
root.left.left.right = TreeNode(-1)
root.left.left.right.right = TreeNode(8)
assert Solution().findTilt(root) == 18

Posted on Reading time ≈ 1 mins.

题目

Find the sum of all left leaves in a given binary tree.

Example:

1
2
3
4
5
6
7
    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

方法

递归遍历，如果为左节点，则打上标记isLeft，如果该节点没有左右子节点，则将该节点值累加到最后的结果中

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 sumOfLeftLeaves(self, root):
        self.result = 0
        self.traverse(root)
        return self.result

    def traverse(self, node, isLeft=False):
        if node and node.left == None and node.right == None and isLeft:
            self.result += node.val
        if node:
            self.traverse(node.left, True)
            self.traverse(node.right)


root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

assert Solution().sumOfLeftLeaves(root) == 24