Eazow

Stay kind and positive

0%

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

Posted on Reading time ≈ 1 mins.

题目

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

1
2
3
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

难度

Easy

方法

遍历2个字符串，索引分别为i, j，如果ransomNote[i] == magazine[j]，则i++, j++，否则j++。如果i == len(ransomNote)，则表示能够用magazine的字符组成ransomNote，否则则不能

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 canConstruct(self, ransomNote, magazine):
        ransomNote = sorted(ransomNote)
        magazine = sorted(magazine)

        i = 0
        j = 0
        while i < len(ransomNote) and j < len(magazine):
            if ransomNote[i] == magazine[j]:
                j += 1
                i += 1
            else:
                j += 1
   
        if i == len(ransomNote):
            return True
        return False

assert Solution().canConstruct("a", "b") == False
assert Solution().canConstruct("aa", "ab") == False
assert Solution().canConstruct("aa", "aab") == True
assert Solution().canConstruct("djfjfhjf", "aaigcbiafifghhdihcfdjjej") == True

Posted on Reading time ≈ 1 mins.

题目

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

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

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, 
you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

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

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

难度

Easy

方法

首先对s和g排序，如果s~j~=gi，则content_count++,j++,i++；否则j++，直到s~j~>=g~i~。注意i和j边界的处理

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 findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g = sorted(g)
        s = sorted(s)
        i = 0
        content_count = 0
        for greed in g:
            while i < len(s):
                if s[i] >= greed:
                    content_count += 1
                    i += 1
                    break
                i += 1
            else:
                break

        return content_count

assert Solution().findContentChildren([1, 2 ,3], [1, 1]) == 1
assert Solution().findContentChildren([1, 2], [1, 2, 3]) == 2
assert Solution().findContentChildren([1, 2, 3], []) == 0
assert Solution().findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]) == 2
assert Solution().findContentChildren([1, 2, 3], [3]) == 1

Posted on Reading time ≈ 1 mins.

题目

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

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

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

难度

Easy

方法

这是一个数学题，假设数组中最小的数为min，需要移动x次，最后数组中的数都为m，则其实是一个求x的方法

1
2
3
4
5
6
(n - 1) * x + sum = n * m
min + x = m
nx - x + sum = n * (min + x)
nx - x + sum = n * min + nx
sum - x = n * min
x = sum - n * min

python代码

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

assert Solution().minMoves([1,2,3]) == 3
assert Solution().minMoves([1,1,3]) == 2

Posted on Reading time ≈ 1 mins.
题目

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. 
Hence return [3, 14.5, 11].

Note:

  1. The range of node’s value is in the range of 32-bit signed integer.
难度

Easy

方法

对二叉树进行深度遍历，将深度level作为参数传递，记录每一级的sum和个数n，最后将sum/n保存到结果列表中即可

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
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        sums = []
        nums = []
        def dfs(node, level):
            if node:
                if len(sums) <= level:
                    sums.append(0)
                    nums.append(0)

                sums[level] += node.val
                nums[level] += 1

                dfs(node.left, level+1)
                dfs(node.right, level+1)

        dfs(root, 0)

        result = []
        for i in range(len(sums)):
            result.append(sums[i]/float(nums[i]))

        return result


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

assert Solution().averageOfLevels(root) == [3, 14.5, 11]