Eazow

Stay kind and positive

0%

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

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