刷题保持头脑锋利

编程/技术 2019-04-11 @ 22:36:22 浏览数: 40 净访问: 33 By: skyrover

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议


很久都没有刷题了,现在感觉脑子有点粘。一直喜欢sharp这个词,让我感觉到无尽的能量,而刷题可以帮助头脑保持锋利!以前还坚持每天一题,后来工作太忙,停上几天,整个习惯就废掉了。今天重新拾起来,保持头脑锋利!

2019-04-11

933. 最近的请求次数

什么鬼题目,半天题没读懂,第一次提交超时。。

class RecentCounter:

    def __init__(self):
        self.counter = []


    def ping(self, t: int) -> int:
        if not t:
            return None
        self.counter.append(t)
        counter_len = len(self.counter)
        i = 0
        while i < counter_len:
            if self.counter[i] + 3000 < t:
                i += 1
            else:
                break
        return counter_len - i


# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

做了一个小优化,提交成功,不过性能还是不太好

class RecentCounter:

    def __init__(self):
        self.counter = []


    def ping(self, t: int) -> int:
        if not t:
            return None
        self.counter.append(t)
        counter_len = len(self.counter)
        i = 0
        while i < counter_len:
            if self.counter[i] + 3000 < t:
                i += 1
            else:
                break
        self.counter = self.counter[i:]
        return counter_len - i
  • 执行用时 : 788 ms, 在Number of Recent Calls的Python3提交中击败了20.31% 的用户
  • 内存消耗 : 17.8 MB, 在Number of Recent Calls的Python3提交中击败了26.36% 的用户

再根据CSAPP优化程序性能一节中提到的性能优化办法再做了点小优化,性能提高了一倍

class RecentCounter:

    def __init__(self):
        self.counter = []


    def ping(self, t: int) -> int:
        if not t:
            return None
        self.counter.append(t)
        counter_len = len(self.counter)
        i = 0
        threshold = t - 3000
        while i < counter_len:
            if self.counter[i] < threshold:
                i += 1
            else:
                break
        self.counter = self.counter[i:]
        return counter_len - i
  • 执行用时 : 440 ms, 在Number of Recent Calls的Python3提交中击败了36.55% 的用户
  • 内存消耗 : 17.8 MB, 在Number of Recent Calls的Python3提交中击败了38.76% 的用户

后面使用了python标准库collections中的deque,性能又提高了一倍

from collections import deque
class RecentCounter:

    def __init__(self):
        self.counter = deque()

    def put(self, ele):
        threshold = ele - 3000
        while self.counter and self.counter[0] < threshold:
            self.counter.popleft()
        self.counter.append(ele)

    def ping(self, t: int) -> int:
        if not t:
            return None
        self.put(t)
        return len(self.counter)

2019-04-10

977. 有序数组的平方

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        square = [a**2 for a in A]
        return sorted(square)
  • 执行用时 : 212 ms, 在Squares of a Sorted Array的Python3提交中击败了62.57% 的用户
  • 内存消耗 : 15.1 MB, 在Squares of a Sorted Array的Python3提交中击败了100.00% 的用户

2018-08-30

905. 按奇偶校验排序数组

双指针法

class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        i = 0
        j = len(A) - 1
        while i < j:
            while i < j and A[i] % 2 == 0:
                i += 1
            while i < j and A[j] % 2 != 0:
                j -= 1
            if i >= j:
                break
            A[i], A[j] = A[j], A[i]
        return A

2018-08-29

605. 种花问题

反向思考,即需要求解 0 0 0 这种的个数,并且在找到一个的时候,将中间的0替换为1,这样就不会重复了。下面判断虽然有点多,但是很直观.

class Solution:
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        i = 0
        count = 0
        while i < len(flowerbed):
            if flowerbed[i] == 0:
                if i - 1 < 0 and i + 1 >= len(flowerbed):
                    count += 1
                    break
                elif i - 1 < 0 and flowerbed[i + 1] == 0:
                    flowerbed[i] = 1
                    count += 1
                elif i - 1 < 0 and flowerbed[i + 1] != 0:
                    i += 1
                    continue
                elif i + 1 >= len(flowerbed) and flowerbed[i - 1] == 0:
                    flowerbed[i] = 1
                    count += 1
                elif i + 1 >= len(flowerbed) and flowerbed[i - 1] != 0:
                    i += 1
                    continue
                elif flowerbed[i - 1] == flowerbed[i + 1] == 0:
                    flowerbed[i] = 1
                    count += 1
            i += 1
        return count >= n

2018-08-28

897. 递增顺序查找树

人家要求最左边的节点是根,所以中序遍历,拿出数组后,组建一个bst。这里有个隐含的条件是中序遍历后的数组是默认有序的。。。因为如果要拿最左边的节点当作bst的根,那么这个最左边的节点一定是最小的。。。这题目有点问题。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def insert_bst(self, node, val):
        if node.val < val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self.insert_bst(node.left, val)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self.insert_bst(node.right, val)

    def traverse(self, root, values):
        if not root:
            return
        self.traverse(root.left, values)
        values.append(root.val)
        self.traverse(root.right, values)

    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        values = []
        self.traverse(root, values)        
        bst_root = TreeNode(values[0])
        node = bst_root
        for value in values[1:]:
            node.right = TreeNode(value)
            node = node.right
        return bst_root

2018-08-27

680. 验证回文字符串 Ⅱ

RecursionError: maximum recursion depth exceeded in comparison,这个。。。

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        deleted = False

        # 递归的处理,在删除的时候留下两种可能性,在第一种失败的情况下,回溯到该分叉
        def _validPalindrome(ss):
            nonlocal deleted
            if not ss:
                return True
            if ss[0] != ss[-1] and not deleted:
                deleted = True
                res = _validPalindrome(ss[1:])
                if not res:
                    res = _validPalindrome(ss[:-1])
            elif ss[0] != ss[-1]:
                return False
            else:
                res = _validPalindrome(ss[1:-1])
            return res

        return _validPalindrome(s)

改成迭代法,居然排名垫底

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        deleted = False
        stack = [s]
        another_ss = None
        while stack:
            ss = stack.pop()
            if not ss:
                return True
            if ss[0] != ss[-1] and not deleted:
                deleted = True
                stack.append(ss[1:])
                another_ss = ss[:-1]
            elif ss[0] != ss[-1]:
                if another_ss is not None:
                    stack.append(another_ss)
                    another_ss = None
                else:
                    return False
            else:
                stack.append(ss[1:-1])
        return True

一雪前耻,击败99%

class Solution(object):
    def validPalindrome(self, s):
        rs = s[::-1]
        if s == rs:
            return True
        # 回文其实判断的是 s == s[::-1]
        # 那么去掉第i个元素,判断剩下的字符串是否符合回文条件
        for i in range(len(s)):
            if s[i] != rs[i]:
                t1 = s[:i] + s[i+1:]
                # 因为去掉元素有两种可能,一种是去掉前面的,一种是去掉后面的
                t2 = rs[:i] + rs[i+1:]
                return t1 == t1[::-1] or t2 == t2[::-1]

2018-08-26

633. 平方数之和

击败90.48%

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        # 双指针法,左边从0开始,右边从sqrt(c)开始
        if c < 0:
            return False
        import math
        sqrt_c = int(math.sqrt(c))
        if sqrt_c ** 2 == c:
            return True
        i, j = 0, sqrt_c
        while i <= j:
            try_res = i ** 2 + j ** 2
            if try_res == c:
                return True
            elif try_res < c:
                i += 1
            else:
                j -= 1
        return False

2018-08-25

896. 单调数列

class Solution(object):
    def isMonotonic(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        if A[0] == A[-1]:
            for a in A[1:-1]:
                if a != A[0]:
                    return False
            return True
        elif A[0] < A[-1]:
            increase = True
        else:
            increase = False
        i = 1
        while i < len(A):
            if A[i] < A[i-1] and increase:
                return False
            elif A[i] > A[i-1] and not increase:
                return False
            i += 1
        return True

2018-08-24

840. 矩阵中的幻方

坑爹的题目。。。

class Solution(object):
    def is_magic_squre(self, i, j, grid):
        for iter_i in range(i, i+3):
            for iter_j in range(j, j+3):
                if grid[iter_i][iter_j] > 9 or grid[iter_i][iter_j] < 1 :
                    return False
        res = grid[i][j] + grid[i][j+1] + grid[i][j+2]
        if grid[i+1][j] + grid[i+1][j+1] + grid[i+1][j+2] != res:
            return False
        if grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2] != res:
            return False
        if grid[i][j] + grid[i+1][j] + grid[i+2][j] != res:
            return False
        if grid[i][j+1] + grid[i+1][j+1] + grid[i+2][j+1] != res:
            return False
        if grid[i][j+2] + grid[i+1][j+2] + grid[i+2][j+2] != res:
            return False
        if grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2] != res:
            return False
        if grid[i+2][j] + grid[i+1][j+1] + grid[i][j+2] != res:
            return False
        return True

    def numMagicSquaresInside(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        count = 0
        for i in range(0, len(grid)-2):
            for j in range(0, len(grid[0])-2):
                if self.is_magic_squre(i, j, grid):
                    count += 1
        return count

2018-08-23

532. 数组中的K-diff数对

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums = sorted(nums)
        if len(nums) < 2:
            return 0
        i, j = 0, 1
        res = set()
        while i < len(nums) and j < len(nums):
            if i == j:
                j += 1
                continue
            while i < len(nums) and j < len(nums) and abs(nums[j] - nums[i]) < k:
                j += 1
            if j >= len(nums):
                break
            if abs(nums[j] - nums[i]) == k:
                res.add((nums[j], nums[i]))
            i += 1
        return len(res)

2018-08-22

168. Excel表列名称

击败87%的提交

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        # 26进制?
        col_map = {num: alpha for num, alpha in zip(range(1, 27), [chr(i) for i in range(65, 91)])}
        res = []
        while n > 26:
            n, remain = divmod(n, 26)
            if remain == 0:
                res.append('Z')
                n -= 1
            else:
                res.append(col_map[remain])
        res.append(col_map[n])
        return ''.join(reversed(res))

2018-08-21

219. 存在重复元素 II

其实不需要记录重复元素列表,只需要记录上一次的位置就好了,因为后面位置只有减去前一个位置才可能是最小的,记录以前的位置并没有什么用,反而增加了遍历次数。修改之后击败了99%的提交。

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        pos = {}
        for idx, num in enumerate(nums):
            if num in pos:
                if idx - pos[num] <= k:
                    return True
            pos[num] = idx
        return False

最大为k,这个着实迷惑了我。最后击败了27%的提交。

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        from collections import defaultdict
        pos = defaultdict(list)
        for idx, num in enumerate(nums):
            if num in pos:
                for ppos in pos[num]:
                    if abs(idx - ppos) <= k:
                        return True
            pos[num].append(idx)
        return False

2018-08-20

893. 特殊等价字符串组

class Solution(object):
    def numSpecialEquivGroups(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        from collections import defaultdict
        res = []
        for a in A:
            a_len = len(a)
            odd = defaultdict(int)
            even = defaultdict(int)
            for i in range(0, a_len, 2):
                odd[a[i]] += 1
            for i in range(1, a_len, 2):
                even[a[i]] += 1
            counter = {
                'odd': odd,
                'even': even
            }
            if counter not in res:
                res.append({
                    'odd': odd,
                    'even': even
                })
        return len(res)

2018-08-19

892. 三维形体的表面积

class Solution(object):
    def surfaceArea(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 卧槽,中间有洞没有cover
        res = 0
        rows = len(grid)
        cols = len(grid[0])
        for row in range(rows):
            for col in range(cols):
                # 上下表面
                if grid[row][col] > 0:
                    res += 2

                # 后表面
                # 后面有低于该正方体柱的
                if row - 1 >= 0 and grid[row-1][col] < grid[row][col]:
                    res += grid[row][col] - grid[row-1][col]
                elif row - 1 < 0:
                    res += grid[row][col]

                # 前表面
                if row + 1 < rows and grid[row+1][col] < grid[row][col]:
                    res += grid[row][col] - grid[row+1][col]
                elif row + 1 >= rows:
                    res += grid[row][col]

                # 左表面
                if col - 1 >= 0 and grid[row][col-1] < grid[row][col]:
                    res += grid[row][col] - grid[row][col-1]
                elif col - 1 < 0:
                    res += grid[row][col]

                # 右表面
                if col + 1 < cols and grid[row][col+1] < grid[row][col]:
                    res += grid[row][col] - grid[row][col+1]
                elif col + 1 >= cols:
                    res += grid[row][col]
        return res

2018-08-18

400. 第N个数字

击败100%的用户,感觉最近脑子变得不sharp了。

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 9 9*20 9*300
        if n < 10:
            return n
        digit_type = 1
        digit_num = 9
        while n > digit_num * digit_type:
            n -= digit_num * digit_type
            digit_type += 1
            digit_num *= 10
        # 第x个数字
        index_in_sub_range = (n - 1) // digit_type
        # 第x个数字第y位
        index_in_num = (n - 1) % digit_type
        # 因为x从0开始,所以从10**(digit_type-1)开始加
        return int(str(10 ** (digit_type - 1) + index_in_sub_range)[index_in_num])

2018-08-17

581. 最短无序连续子数组

这道题上最惨痛,错了6次,自己想偏了,搞得很麻烦。最后还不如这种方式简单,最多不超过nlgn的,难怪通过率只有27%

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sorted_nums = sorted(nums)
        i, j = 0, len(nums) - 1
        while i < len(nums):
            if nums[i] != sorted_nums[i]:
                break
            i += 1
        if i >= len(nums):
            return 0
        while j >= 0:
            if nums[j] != sorted_nums[j]:
                break
            j -= 1
        if i >= j:
            return 0
        return j - i + 1

2018-08-16

58. 最后一个单词的长度-

击败100%的提交

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        words = s.strip().split(' ')
        return len(words[-1]) if words else 0

2018-08-15

507. 完美数

可以得到一个数的一半的公约数都在[1, sqrt(num)]之中,所以直接遍历这个区间就可以了,可以减少很多元素,击败94%的提交

class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        import math
        if num <= 0:
            return False
        i = 1
        total = 0
        s_num = int(math.sqrt(num))
        if s_num == num:
            return False
        while i <= s_num:
            if num % i == 0:
                total += i + num / i
            i += 1
        if total != 2 * num:
            return False
        return True

不出意料,超时

class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num == 0:
            return False
        i = 1
        total = 0
        half_num = num // 2
        while i <= half_num:
            if num % i == 0:
                total += i
            i += 1
        if total == num:
            return True
        return False

2018-08-14

883. 三维形体投影面积

class Solution(object):
    def projectionArea(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 俯视图 应该是grid中元素大于1的个数
        # 主视图 应该是grid中纵列中的最大值
        # 侧视图 应该是grid中行的最大值
        res = 0
        rows = len(grid)
        cols = len(grid[0])
        res += sum(max(grid[row]) for row in range(rows))
        res += sum(max(grid[row][col] for row in range(rows)) for col in range(cols))
        res += sum(1 for row in range(rows) for col in range(cols) if grid[row][col])
        return res

2018-08-13

888. 公平的糖果交换

通过了,但是做题的人太少,没有排名。。

class Solution:
    def fairCandySwap(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: List[int]
        """
        # sumA - sumB = n
        # 找两个数组相差为n的两个数字
        diff = (sum(A) - sum(B)) / 2
        if diff > 0:
            res_a = sorted([a for a in A if (a - diff) > 0])
            res_b = sorted(B)
        else:
            res_a = sorted(A)
            res_b = sorted([b for b in B if (b + diff) > 0])
        i, j = 0, 0
        while i < len(res_a) and j < len(res_b):
            while res_a[i] - diff > res_b[j] and j < len(res_b):
                j += 1
            if res_a[i] - diff == res_b[j]:
                return [res_a[i], res_b[j]]
            i += 1

居然超出时间限制,嗯本来可以少点计算的。。改进中

class Solution:
    def fairCandySwap(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: List[int]
        """
        # sumA - sumB = n
        # 找两个数组相差为n的两个数字
        diff = (sum(A) - sum(B)) / 2
        for a in A:
            if a - diff in B:
                return [a, int(a-diff)]

2018-08-12

884. 两句话中的不常见单词

from collections import Counter
class Solution:
    def uncommonFromSentences(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: List[str]
        """
        count_a = Counter(A.split(' '))
        count_b = Counter(B.split(' '))
        a_eles = [ele for ele, count in count_a.items() if count == 1]
        b_eles = [ele for ele, count in count_b.items() if count == 1]
        res = []
        for a_ele in a_eles:
            if a_ele not in count_b:
                res.append(a_ele)
        for b_ele in b_eles:
            if b_ele not in count_a:
                res.append(b_ele)
        return res

2018-08-11

443. 压缩字符串

击败92.47%的提交

class Solution:
    def compress(self, chars):
        """
        :type chars: List[str]
        :rtype: int
        """
        res, i = 0, 0
        while i < len(chars):
            current_char = chars[i]
            count = 0
            while i < len(chars) and chars[i] == current_char:
                i += 1
                count += 1

            chars[res] = current_char
            res += 1
            if count > 1:
                for char in str(count):
                    chars[res] = char
                    res += 1
        return res

原地,击败16.13%的提交

class Solution:
    def compress(self, chars):
        """
        :type chars: List[str]
        :rtype: int
        """
        i = 1
        j = 0
        count = 1
        while i < len(chars) + 1:
            if i < len(chars) and chars[i] == chars[j]:
                count += 1
                i += 1
                continue
            data = [chars[j]]
            if count > 1:
                data.extend([ele for ele in str(count)])
            diff = len(chars[j:i]) - len(data)
            chars[j:i] = data
            i = i - diff
            count = 1
            j = i
            i += 1
        return len(chars)

只击败了2.15%的提交,而且不是原地进行的

class Solution:
    def compress(self, chars):
        """
        :type chars: List[str]
        :rtype: int
        """
        i = 1
        j = 0
        count = 1
        res = []
        while i < len(chars) + 1:
            if i < len(chars) and chars[i] == chars[j]:
                count += 1
                i += 1
                continue
            res.append(chars[j])
            if count > 1:
                res.extend([ele for ele in str(count)])
            count = 1
            j = i
            i += 1
        chars[:len(res)] = res
        return len(res)

2018-08-10

7. 反转整数

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        str_x = str(x)
        if str_x.startswith('-'):
            res = '-' + str_x[1:][::-1].lstrip('0')
        else:
            res = str_x[::-1].lstrip('0')
        res = int(res)
        if -2147483648 > res or res > 2147483647:
            return 0
        return res

2018-08-09

414. 第三大的数

为啥代码差不多一样,排名差了这么多,,,仅仅击败4%的提交

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return
        nums = sorted(set(nums), reverse=True)
        if len(nums) < 3:
            return nums[0]
        else:
            return nums[2]

14. 最长公共前缀

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        min_str = min(strs)
        max_str = max(strs)
        length = min(len(min_str), len(max_str))
        for i in range(length):
            if min_str[i] == max_str[i]:
                i += 1
            else:
                return min_str[:i]
        return min_str

击败74%的提交

class Solution(object):
    def same_prefix(self, a, b):
        length = min(len(a), len(b))
        for i in range(length):
            if a[i] == b[i]:
                i += 1
            else:
                return a[:i]
        return a[:length]

    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        res = strs[0]
        for i in range(1, len(strs)):
            res = self.same_prefix(res, strs[i])
            if not res:
                return res
        return res

190. 颠倒二进制位

击败90.38%的提交

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        bits = bin(n)[2:]
        bits = '0' * (32 - len(bits)) + bits
        return int(bits[::-1], 2)

击败15.9%的提交

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        bits = []
        while n != 0:
            n, bit = divmod(n, 2)
            bits.append(bit)
        bits = [0] * (32 - len(bits)) + bits[::-1]
        target_bits = ''.join(str(bit) for bit in bits[::-1])
        return int(target_bits, 2)

2018-08-08

645. 错误的集合

击败96.49%的提交

class Solution:
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # set一下,可以得到n为set的长度加一,这样就知道总和
        # 减去set的和,就知道少了什么元素,拿未set的数据和减set的和,就知道多了什么
        num_set = set(nums)
        set_sum = sum(num_set)
        n = len(num_set) + 1
        return [sum(nums) - set_sum, int(n * (n+1) / 2 - set_sum)]

卧槽,现在写代码效率越来越低了,只击败了13%的提交

class Solution:
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        min_num = min(nums)
        max_num = max(nums)
        num_map = {num: 0 for num in range(min_num, max_num+1)}
        res = [None, None]
        for num in nums:
            if num_map[num] == 1:
                res[0] = num
            else:
                num_map[num] = 1
        for num, value in num_map.items():
            if value == 0:
                res[1] = num
                break
        else:
            res[1] = 1 if min_num != 1 else max_num + 1
        return res

2018-08-07

687. 最长同值路径

已经遍历的元素不再进行查找,击败了50%的提交

class Solution1(object):

    def _dfs(self, node, value, seen):
        if not node:
            return 0
        if node.val == value:
            seen.add(node)
            count = 1
            left_count = self._dfs(node.left, value, seen)
            right_count = self._dfs(node.right, value, seen)
            count += max(left_count, right_count)
            return count
        return 0

    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        """
              5
             / \
            4   5
           / \   \
          1   1   5
        2
              1
             / \
            4   5
           / \   \
          4   4   5
        2
        """
        # 从根节点开始找,只要找到与根节点元素相等的值,就加一即可
        if not root:
            return 0
        max_count = 0
        stack = [root]
        seen = set()
        while stack:
            node = stack.pop()
            if node not in seen:
                count = self._dfs(node.left, node.val, seen)
                count += self._dfs(node.right, node.val, seen)
                max_count = max(max_count, count)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return max_count

这个题没说明白,就是最大路径上一个节点只能连两条线。下面这个提交只击败了2.81%的提交,肯定复杂度是比较高的。这只是确定能解出这个题目的第一种方法,后面会作出优化。

class Solution(object):

    def _dfs(self, node, value):
        if not node:
            return 0
        if node.val == value:
            count = 1
            left_count = self._dfs(node.left, value)
            right_count = self._dfs(node.right, value)
            count += max(left_count, right_count)
            return count
        return 0

    def longestUnivaluePath(self, root):
        # 从根节点开始找,只要找到与根节点元素相等的值,就加一即可
        if not root:
            return 0
        max_count = 0
        stack = [root]
        while stack:
            node = stack.pop()
            count = self._dfs(node.left, node.val)
            count += self._dfs(node.right, node.val)
            max_count = max(max_count, count)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return max_count

2018-08-06

160. 相交链表

实锤了,Leetcode服务器运行的太慢了,233333

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        # 双指针,同时开始遍历
        if not headA or not headB:
            return
        node_a, node_b = headA, headB
        while node_a and node_b and node_a != node_b:
            node_a = node_a.next
            node_b = node_b.next
            # 如果相等退出,包含None的情况
            if node_a == node_b:
                return node_a
            # 如果node_a完了,跳到b链表,
            # 两个链表如果相交的化,第二次遍历的时候肯定会重合
            if not node_a:
                node_a = headB
            if not node_b:
                node_b = headA
        return node_a

给链表上加标记,然后如果重复的话,说明有相交节点,感觉已经很高效了,但只是击败了25%的提交 = =!

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        """
        A:          a1 → a2

                             c1 → c2 → c3

        B:     b1 → b2 → b3
        c1相交
        """
        # 1. 给节点上加标记
        node_a = headA
        node_b = headB
        while node_a or node_b:
            if node_a:
                if not hasattr(node_a, 'visited'):
                    node_a.visited = True
                else:
                    return node_a
                node_a = node_a.next
            if node_b:
                if not hasattr(node_b, 'visited'):
                    node_b.visited = True
                else:
                    return node_b
                node_b = node_b.next

643. 子数组最大平均数 I

数组题把我做懵逼了都。不过遇到这种循环中要用sum函数的,还是慎重,如果能推出来,最好推导出来,这样极大提高效率。

class Solution:
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        i = k
        start_sum = sum(nums[:k])
        max_average = start_sum / k
        while i < len(nums):
            i = i + 1
            start_sum = start_sum - nums[i - k - 1] + nums[i - 1]
            max_average = max(start_sum / k, max_average)
        return max_average

2018-08-05

849. 到最近的人的最大距离

优化了下,击败了40%的提交

class Solution:
    def maxDistToClosest(self, seats):
        """
        :type seats: List[int]
        :rtype: int
        """
        seated = [idx for idx in range(len(seats)) if seats[idx] == 1]
        max_dis = 0
        for idx in range(len(seated) - 1):
            dis = (seated[idx + 1] - seated[idx]) // 2
            max_dis = max(dis, max_dis)
        if seats[0] != 1:
            max_dis = max(max_dis, seated[0])
        if seats[-1] != 1:
            max_dis = max(max_dis, len(seats) - seated[-1] - 1)
        return max_dis

脑子感觉锈住了,找不到好的算法,击败10%的提交。。

class Solution:
    def maxDistToClosest(self, seats):
        """
        :type seats: List[int]
        :rtype: int
        """
        i = 0
        max_dis = 0
        while i < len(seats):
            if seats[i] == 1:
                i += 1
                continue
            left = i
            while left >= 0 and seats[left] != 1:
                left -= 1
            right = i
            while right < len(seats) and seats[right] != 1:
                right += 1
            if left == -1:
                max_dis = max(max_dis, right-i)
            elif right == len(seats):
                max_dis = max(max_dis, i-left)
            else:
                max_dis = max(max_dis, min(i - left, right-i))
            i += 1
        return max_dis

724. 寻找数组的中心索引

击败73%的提交

class Solution:
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        total = sum(nums)
        left = 0
        for i in range(len(nums)):
            if (left << 1) + nums[i] == total:
                return i
            else:
                left += nums[i]
        return -1

另一种方法,就是记录下左边和右边目前的和,然后下一次就只需要在左边加上,和在右边减去对应的值就可以了,然后进行判断,击败30%的提交,还是有很大的改进余地。

其实这个加和减也可以优化掉,因为要使得题目成立,那么nums[i] + left + right = total, 并且 left = right,也就是nums[i] + 2 left = total,就只有一个未知数了。

class Solution:
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left_sum_cache = 0
        right_sum_cache = sum(nums)

        for i in range(len(nums)):
            left_sum_cache = left_sum_cache + (nums[i-1] if i != 0 else 0)
            right_sum_cache = right_sum_cache - nums[i]
            if left_sum_cache == right_sum_cache:
                return i
        return -1

第一种方法超时 = =!

class Solution:
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            if sum(nums[:i]) == sum(nums[i + 1:]):
                return i
        return -1

2018-08-04

189. 旋转数组

这种题,唉,一言难尽

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if k == 0:
            return
        nums_len = len(nums)
        nums[:nums_len-k] = nums[:nums_len-k][::-1]
        nums[nums_len-k:] = nums[nums_len-k:][::-1]
        nums[:] = nums[::-1]


class Solution1(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        nums[:] = nums[nums_len-k:] + nums[:nums_len-k]


class Solution3:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        new_nums = nums.copy()
        for i in range(len(nums)):
            new_nums[(i+k) % nums_len] = nums[i]
        nums[:] = new_nums

2018-08-03

700. 二叉搜索树中的搜索

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return
        queue = [root]
        while queue:
            node = queue.pop(0)
            if node.val == val:
                return node
            elif val < node.val and node.left:
                queue.append(node.left)
            elif val > node.val and node.right:
                queue.append(node.right)

2018-08-02

482. 密钥格式化

不优雅就不优雅了吧,脑子已经是一锅粥了。

class Solution(object):
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        S = ''.join(S.split('-')).upper()
        # 从后面往前遍历,每到一组就将结果放入结果集
        i = len(S) - 1
        j = len(S)
        count = 1
        res = []
        while i >= 0:
            if count % K == 0:
                res.append(S[i:j])
                j = i
                count = 1
            else:
                count += 1
            if i == 0 and S[i:j]:
                res.append(S[i:j])
            i -= 1
        return '-'.join(res[::-1])

234. 回文链表

O(n)时间复杂度和O(1)的空间复杂度,击败98%的吃瓜群众

class Solution1(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        """
        1->2->2->1->1
        输出: true
        """
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # slow 在中间位置(奇数) 或者 中间靠右(偶数)
        # 将slow右边的链表反转
        node = slow
        left = None
        while node:
            right = node.next
            node.next = left
            left = node
            node = right
        while left and head:
            if head.val != left.val:
                return False
            left = left.next
            head = head.next
        return True

O(n)时间复杂度和空间复杂度

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        """
        1->2->2->1
        输出: true
        """
        res = []
        node = head
        while node:
            res.append(node.val)
            node = node.next
        return res == res[::-1]

2018-08-01

20. 有效的括号

感觉脑子注意力无法集中了。。。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        s_map = {
            ']': '[',
            ')': '(',
            "}": '{'
        }
        # 栈 依次入栈 出栈
        stack = [s[0]]
        i = 1
        while i < len(s):
            if s[i] not in s_map:
                stack.append(s[i])
            else:
                if not stack or s_map[s[i]] != stack.pop(-1):
                    return False
            i += 1
        return True if len(stack) == 0 else False

674. 最长连续递增序列

注意细节啊

class Solution(object):
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        i = 1
        count = 1
        res = 0
        while i < len(nums):
            if nums[i] > nums[i-1]:
                count += 1
            else:
                res = max(res, count)
                count = 1
            i += 1
        else:
            res = max(res, count)
        return res

594. 最长和谐子序列

这道题换一种思路会非常简单,直接统计各个元素的数量,然后去找和该元素相差1的元素数量,两者之和就是结果。另外规定只按照向右找,即2找3,3找4.

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        from collections import Counter
        counter = Counter(nums)
        max_len = 0
        for key, value in counter.items():
            if key + 1 in counter:
                max_len = max(max_len, value + counter[key+1])
        return max_len

836. 矩形重叠

击败98.25%的提交

class Solution(object):
    def isRectangleOverlap(self, rec1, rec2):
        """
        :type rec1: List[int]
        :type rec2: List[int]
        :rtype: bool
        """
        # 重叠的可能有多种多样,不重叠的可能只有4种
        # 以第二个矩形为中心,进行判断
        if rec1[2] <= rec2[0] or rec1[1] >= rec2[3] or rec1[0] >= rec2[2] or rec1[3] <= rec2[1]:
            return False
        return True

111. 二叉树的最小深度

击败95.72%的提交

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        queue = [(root, 1)]
        while queue:
            node, level = queue.pop(0)
            if not node.left and not node.right:
                return level
            if node.left:
                queue.append((node.left, level+1))
            if node.right:
                queue.append((node.right, level+1))

125. 验证回文串

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        res = []
        for ele in s:
            if ele.isalnum():
                res.append(ele.lower())
        return res == res[::-1]

不知道为啥,很慌,做错了好几次

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        s = s.lower()
        i = 0
        j = len(s) - 1
        while i < j:
            while i < len(s) and not s[i].isalnum():   
                i += 1                                 
            while j > 0 and not s[j].isalnum():        
                j -= 1
            if i > j:
                return True
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

290. 单词模式

双向,完全匹配 233333

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        strings = str.split(' ')
        if len(strings) != len(pattern):
            return False
        word_map = {}
        used = set()
        for idx, ele in enumerate(pattern):
            if ele not in word_map and strings[idx] not in used:
                word_map[ele] = strings[idx]
                used.add(strings[idx])
            if word_map.get(ele) != strings[idx]:
                return False
        return True

2018-07-31

28. 实现strStr()

需要注意一些细节问题

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0
        if len(needle) > len(haystack):
            return -1
        i = j = 0
        while i < len(haystack) and len(needle) <= len(haystack) - i:
            if haystack[i] != needle[0]:
                i += 1
            else:
                inner_i = i
                while j < len(needle):
                    if haystack[inner_i] == needle[j]:
                        inner_i += 1
                        j += 1
                    else:
                        j = 0
                        i += 1
                        break
                else:
                    return i
        return -1

746. 使用最小花费爬楼梯

明显一看就是动态规划,那么动态规划要求解最后一个问题,就要找出前面问题之间的关系。这道题可以上一个台阶,也可以上两个台阶,那么dp[stop] = min(dp[stop-1]+cost[stop-1], dp[stop-2]+cost[stop-2])就是说,到达stop的时候可以通过前一个台阶上来,也可以通过前两个台阶上来,所以问题就转换成两个子问题的求解了,以此类推,那么一开始的时候只要知道第一个和第二个台阶的cost值就可以完成求解。

明显可以看出来dp[0]=0, dp[1]=0,因为一开始上台阶是没有cost的,所以开始动态规划的迭代,每个子问题都是最优解,那么最后的stop也是最优解了。

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        stop = len(cost)
        dp = {
            0: 0,
            1: 0
        }
        for i in range(2, stop+1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[stop]

2018-07-30

876. 链表的中间结点

双指针法

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 双指针
        i = j = head
        while i and j:
            if j.next and j.next.next:
                j = j.next.next
                i = i.next
            elif j.next:
                return i.next
            else:
                return i

2018-07-29

720. 词典中最长的单词

纳尼 ["yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"] 输出 ewqz 居然是错的,答案是yodn,什么鬼?原来是里面每个字不断的组成都得有

实现了个单词查找树,不过效率上只击败了15%的提交

另一种方法就是对每个单词进行迭代,然后对每个单词的前缀分别都进行遍历查找,看有没有在单词列表中

class Node:
    ENDOF = '#'

    def __init__(self, depth, parent, val=None):
        self.depth = depth
        self.val = val
        self.parent = parent
        self.children = {}


class Trie:
    def __init__(self):
        self.root = Node(depth=0, parent=None, val="root")
        self.size = 0
        self.count = None

    def add(self, key):
        self.size += 1
        node = self.root
        # 将单词key中的每一个字添加到树中
        for ele in key:
            if ele not in node.children:
                node.children[ele] = Node(node.depth + 1, node, ele)
            node = node.children[ele]
        else:
            node.children[Node.ENDOF] = Node(node.depth + 1, node, Node.ENDOF)
        return self.root

    def has_prefix(self, word):
        node = self.root

        for ele in word:
            node = node.children[ele]
            if Node.ENDOF not in node.children:
                return False
        else:
            return True


class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        trie = Trie()
        for word in words:
            trie.add(word)

        def _sort_func(x, y):
            if len(y) - len(x) == 0:
                if x < y:
                    return -1
                elif x > y:
                    return 1
                else:
                    return 0
            else:
                return len(y) - len(x)

        from functools import cmp_to_key
        words = sorted(words, key=cmp_to_key(_sort_func))
        for word in words:
            if trie.has_prefix(word):
                return word

2018-07-28

427. 建立四叉树

核心在于如何分割矩形以及递归截止条件

"""
# Definition for a QuadTree node.
class Node(object):
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution(object):

    def build_tree(self, rect):
        dup = set()
        row_len, col_len = len(rect), len(rect[0])
        row_mid, col_mid = row_len // 2, col_len // 2
        top_left_rect = []
        top_right_rect = []
        bottom_right_rect = []
        bottom_left_rect = []
        for row in range(row_mid):
            dup |= set(ele for ele in rect[row])
            top_left_rect.append(rect[row][0:col_mid])
            top_right_rect.append(rect[row][col_mid:])

        for row in range(row_mid, row_len):
            dup |= set(ele for ele in rect[row])
            bottom_left_rect.append(rect[row][0:col_mid])
            bottom_right_rect.append(rect[row][col_mid:])

        if len(dup) == 1:
            return Node(
                val=bool(dup.pop()), isLeaf=True, topLeft=None,
                topRight=None, bottomLeft=None, bottomRight=None
            )

        top_left = self.build_tree(top_left_rect)
        top_right = self.build_tree(top_right_rect)
        bottom_left = self.build_tree(bottom_left_rect)
        bottom_right = self.build_tree(bottom_right_rect)
        node = Node(
            val=True, isLeaf=False, topLeft=top_left,
            topRight=top_right, bottomLeft=bottom_left,
            bottomRight=bottom_right
        )
        return node

    def construct(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: Node
        """
        if not grid:
            return
        return self.build_tree(grid)

2018-07-27

205. 同构字符串

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        alphabet_map = {}
        used = set()
        for s_ele, t_ele in zip(s, t):
            if s_ele not in alphabet_map and t_ele not in used:
                alphabet_map[s_ele] = t_ele
                used.add(t_ele)
            if alphabet_map.get(s_ele) != t_ele:
                return False
        return True

830. 较大分组的位置

击败21.98%的提交,68ms,但是感觉效率应该挺高的啊,O(n)?看第一名也是O(n)算法啊,44ms

class Solution(object):
    def largeGroupPositions(self, S):
        """
        :type S: str
        :rtype: List[List[int]]
        """
        i = 0
        res = []
        while i < len(S):
            j = i + 1
            while j < len(S) and S[j] == S[i]:
                j += 1
            if j - i >= 3:
                res.append([i, j-1])
            i = j
        return res

203. 删除链表中的节点

一个优化后的迭代法,击败60%的提交

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        while head and head.val == val:
            head = head.next
        if not head:
            return
        node = head
        while node:
            if node.next and node.next.val == val:
                node.next = node.next.next
            else:
                node = node.next
        return head

迭代法击败40%的提交

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        while head and head.val == val:
            head = head.next
        if not head:
            return
        prev = head
        node = head.next
        while node:
            if node.val == val:
                prev.next = node.next
            else:
                prev = prev.next
            node = node.next
        return head

递归解法只击败了7%的提交。。。

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if not head:
            return
        if head.val == val:
            return self.removeElements(head.next, val)
        elif head.next and head.next.val == val:
            head.next = self.removeElements(head.next.next, val)
        else:
            head.next = self.removeElements(head.next, val)
        return head

796. 旋转字符串

感觉自己的算法功底提高了呢

class Solution(object):
    def rotateString(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: bool
        """
        if len(A) != len(B):
            return False
        if A == B:
            return True
        i = 0
        while i < len(B):
            if B[i] == A[0] and B[i:] + B[:i] == A:
                return True
            i += 1
        return False

697. 数组的度

另外一个版本,左右指针法,在遇到更大型数组的时候同样超出时间限制。。。那就是相同频次的数太多了。。。后来加了个判断,如果res == freq的话,直接返回结果即可,这样accepted了,而且击败了79%的提交。

class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        from collections import Counter, defaultdict
        freqs = defaultdict(list)
        counter = Counter(nums)
        for value, c in counter.items():
            freqs[c].append(value)
        freq = max(freqs)
        res = len(nums)
        for num in freqs[freq]:
            i, j = 0, len(nums) - 1
            while i < j:
                while nums[i] != num:
                    i += 1
                while nums[j] != num:
                    j -= 1
                res = min(res, j - i + 1)
                if res == freq:
                    return res
                break
        return res

这个版本的答案超出时间限制,n2算法是有很大优化余地的,2333333

class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        from collections import Counter
        counter = Counter(nums)
        freq = counter.most_common(1)[0][1]
        i = 0
        res = len(nums)
        while i < len(nums):
            j = i + 1
            inner_counter = Counter([nums[i]])
            while max(inner_counter.values()) != freq and j < len(nums):
                inner_counter.update([nums[j]])
                if max(inner_counter.values()) == freq:
                    res = min(res, j - i + 1)
                    if res == freq:
                        return res
                    break
                j += 1
            i += 1
        return res

872. 叶子相似的树

深度优先搜索

class Solution(object):
    def dfs(self, node):
        res = []
        leaf = True
        if node.left:
            leaf = False
            res.extend(self.dfs(node.left))
        if node.right:
            leaf = False
            res.extend(self.dfs(node.right))
        if leaf:
            res.append(node.val)
        return res

    def leafSimilar(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        leaf_nodes_1 = self.dfs(root1)
        leaf_nodes_2 = self.dfs(root2)
        return leaf_nodes_1 == leaf_nodes_2

2018-07-26

747. 至少是其他数字两倍的最大数

时间复杂度为O(n),看了其他答案,比如先max, 再index的,最后再遍历一遍nums,虽然总体是一个量级,但是常数项太大,所以我超过了98%的用户,233333333

class Solution(object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return 0
        max_num = second_max_num = None
        i = 0
        while i < len(nums):
            if max_num is None:
                max_num = nums[i], i
            elif nums[i] > max_num[0]:
                second_max_num = max_num
                max_num = nums[i], i
            elif second_max_num is None:
                second_max_num = nums[i], i
            elif nums[i] > second_max_num[0]:
                second_max_num = nums[i], i
            i += 1
        if second_max_num[0] == 0 or max_num[0] / second_max_num[0] >= 2:
            return max_num[1]
        else:
            return -1

589. N叉树的前序遍历

递归版,只击败了5%的用户,尴尬

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        # 前序遍历 递归版
        if not root:
            return []
        res = [root.val]
        for child in root.children:
            res.extend(self.preorder(child))
        return res

迭代版击败70%的用户

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        # 迭代版
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children[::-1]:
                stack.append(child)
        return res

2018-07-25

784. 字母大小写全排列

回溯,然后到结束的时候把结果记录下来,然后再返回上一层,这样就可以把所有可能的结果拿出来了。

回溯是一种穷举,但与brute force有一些区别,回溯带了两点脑子的,并不多,brute force一点也没带。

第一点脑子是回溯知道回头;相反如果是brute force,发现走不通立刻跳下山摔死,换第二条命从头换一条路走。

第二点脑子是回溯知道剪枝;如果有一条岔路上放了一坨屎,那这条路我们不走,就可以少走很多不必要走的路。

回溯是一种找路方法,搜索的时候走不通就回头换路接着走,直到走通了或者发现此山根本不通。

DFS是一种开路策略,就是一条道先走到头,再往回走一步换一条路走到头,这也是回溯用到的策略。在树和图上回溯时人们叫它DFS。

递归是一种行为,回溯和递归如出一辙,都是一言不合就回到来时的路,所以一般回溯用递归实现;当然也可以不用,用栈。

class Solution(object):

    def back_tracking(self, s, index, res):
        if index >= len(s):
            res.append(''.join(s))
            return
        if s[index].isalpha():
            s[index] = s[index].lower()
            self.back_tracking(s, index+1, res)
            s[index] = s[index].upper()
            self.back_tracking(s, index+1, res)
        else:
            self.back_tracking(s, index + 1, res)

    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        # 回溯
        """
            root
          a      A
          1      1
        b   B   b   B
        2   2   2   2
        """
        res = []
        self.back_tracking(list(S), 0, res)
        return res

2018-07-24

819. 最常见的单词

from collections import Counter

class Solution(object):
    def mostCommonWord(self, paragraph, banned):
        """
        :type paragraph: str
        :type banned: List[str]
        :rtype: str
        """
        symbol = "!?',;."
        counter = Counter()
        for word in paragraph.split(' '):
            word = word.strip(symbol).lower()
            if word not in banned:
                counter[word] += 1
        return counter.most_common(1)[0][0]

429. N叉树的层序遍历

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""

from collections import defaultdict
class Solution(object):

    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        """
        [
             [1],
             [3,2,4],
             [5,6]
        ]
        """
        if not root:
            return []
        queue = [(root, 0)]
        res = defaultdict(list)
        while queue:
            node, level = queue.pop(0)
            res[level].append(node.val)
            for child in node.children:
                queue.append((child, level+1))
        return [res[key] for key in sorted(res.keys())]

2018-07-23

717. 1比特与2比特字符

找到每一个比特字符的开始位置,然后往后加,毕竟1开始的就2位,0开始的就1位

class Solution(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        start = 0
        if len(bits) == 1:
            return True
        while start < len(bits):
            if bits[start] == 1:
                start += 2
            else:
                start += 1
            if start == len(bits) - 1:
                return True
        return False

458. 可怜的小猪

参考: https://www.zhihu.com/question/60227816

class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        import math
        return int(math.ceil(math.log(buckets, 1+minutesToTest / minutesToDie)))

2018-07-22

661. 图片平滑器

反正这道题不是什么好题。。。

import math
import copy
class Solution:

    def gen_inner_result(self, row, col, col_len, count, value):
        count += 1
        value += self.M[row][col]
        if col - 1 >= 0:
            count += 1
            value += self.M[row][col - 1]
        if col + 1 < col_len:
            count += 1
            value += self.M[row][col + 1]
        return count, value

    def gen_result(self, row, col, row_len, col_len):
        count = value = 0
        if row - 1 >= 0:
            count, value = self.gen_inner_result(row-1, col, col_len, count, value)
        if row + 1 < row_len:
            count, value = self.gen_inner_result(row+1, col, col_len, count, value)
        count, value = self.gen_inner_result(row, col, col_len, count, value)
        return int(math.floor(value / count))

    def imageSmoother(self, M):
        """
        :type M: List[List[int]]
        :rtype: List[List[int]]
        """
        if not M:
            return M
        self.M = M
        res_M = copy.deepcopy(M)
        for row in range(len(M)):
            for col in range(len(M[0])):
                res_M[row][col] = self.gen_result(row, col, len(M), len(M[0]))
        return res_M

2018-07-21

67. 二进制求和

class Solution:
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        a_stack = [int(ele) for ele in a]
        b_stack = [int(ele) for ele in b]
        res = []
        carry = 0
        while a_stack or b_stack or carry != 0:
            a_ele = a_stack.pop(-1) if a_stack else 0
            b_ele = b_stack.pop(-1) if b_stack else 0
            ele_sum = a_ele + b_ele + carry
            carry, res_ele = divmod(ele_sum, 2)
            res.append(str(res_ele))
        return ''.join(res[::-1])

2018-07-20

671. 二叉树中第二小的节点

传统方法,先把节点值都拿出来,然后判断,肯定比较慢,没有用到这个树的特性

class Solution:
    def traverse(self, node):
        if not node:
            return []
        res = [node.val]
        res += self.traverse(node.left)
        res += self.traverse(node.right)
        return res

    def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        """
            2
           / \
          2   5
             / \
            5   7
        5
        """
        values = set(self.traverse(root))
        if len(values) <= 1:
            return -1
        else:
            return sorted(values)[1]

另外一种方法,使用迭代法更加直观和简洁,通过记录first, second小的变量,不断迭代树中的节点并且进行更新即可

class Solution:
    def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return -1
        stack = [root]
        first, second = root.val, -1
        while stack:
            node = stack.pop()
            if node.val < first:
                first = node.val
            elif first < node.val and (node.val < second or second == -1):
                second = node.val
            if node.left:
                stack.append(node.left)
                stack.append(node.right)
        return second

590. N叉树的后序遍历

递归解法

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        # 左->右->中间
        if not root:
            return []
        res = []
        for child in root.children:
            res += self.postorder(child)
        res.append(root.val)
        return res

迭代法

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root:
            return []
        # 迭代法就是自己模拟栈
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            for child in node.children:
                stack.append(child)
            # res添加的顺序正好和后序遍历相反
            # 即先进入节点值,再进入的是右边子节点,所以后面直接逆序即可
            res.append(node.val)
        return res[::-1]

70. 爬楼梯

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        """
        1 
            1
        2 
            1 1
            2
        3
            2
                1 2
            1
                1 1 1
                2 1
        4
            1
                1 1 1 1
                1 2 1
                2 1 1
            2
                1 1 2
                2 2
        """
        dp = {
            1: 1,
            2: 2
        }
        for i in range(3, n+1):
            # 其实就是上第i-1个台阶的不同方法加上 上第i-2个台阶的方法次数只和
            # 因为如果上到i-2,差两个台阶上到i的可能次数
            # 如果上到i-1,就是差一个台阶上到i的可能次数
            # 比如n=4,差一个台阶上来的可能性为,也就是说末尾数字是1,则可能有 1111 121 211 即n=3的可能性
            # 差两个台阶上来的可能性为,就是末尾数字是2,可能有 22 112 即为n=2的可能性
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

559. N叉树的最大深度

传统的dfs

class Solution(object):
    def dfs(self, node, depth):
        max_depth = depth
        for child in node.children:
            max_depth = max(max_depth, self.dfs(child, depth+1))

        return max_depth

    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if not root:
            return 0
        depth = self.dfs(root, 1)
        return depth

另一种方法,和上面原理一样,只是更简洁

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root is None:
            return 0
        if not root.children:
            return 1
        return max(map(self.maxDepth, root.children)) + 1

844. 比较含退格的字符串

class Solution:

    def build_string(self, string):
        stack = []
        for s in string:
            if s != '#':
                stack.append(s)
            elif s == '#' and stack:
                stack.pop()
        return ''.join(stack)

    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        # 两个栈,入栈,并且遇到#出栈,最后比较字符串是否相等
        s = self.build_string(S)
        t = self.build_string(T)
        return s == t

733. 图像渲染

class Solution:

    def dfs(self, x, y, color, seen):
        # top
        if x - 1 >= 0 and not seen[x-1][y] and self.image[x-1][y] == self.image[x][y]:
            seen[x-1][y] = True
            self.dfs(x-1, y, color, seen)
            self.image[x - 1][y] = color
        if y + 1 < len(self.image[0]) and not seen[x][y+1] and self.image[x][y+1] == self.image[x][y]:
            seen[x][y+1] = True
            self.dfs(x, y+1, color, seen)
            self.image[x][y+1] = color
        if x + 1 < len(self.image) and not seen[x+1][y] and self.image[x+1][y] == self.image[x][y]:
            seen[x + 1][y] = True
            self.dfs(x+1, y, color, seen)
            self.image[x+1][y] = color
        if y - 1 >= 0 and not seen[x][y-1] and self.image[x][y-1] == self.image[x][y]:
            seen[x][y-1] = True
            self.dfs(x, y-1, color, seen)
            self.image[x][y-1] = color

    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        self.image = image
        seen = []
        for i in range(len(image)):
            inner = []
            for j in range(len(image[0])):
                inner.append(False)
            seen.append(inner)
        self.dfs(sr, sc, newColor, seen)
        self.image[sr][sc] = newColor
        return self.image

2018-07-19

155. 最小栈

使用最小堆

import heapq

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_heap = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        heapq.heappush(self.min_heap, x)
        self.stack.append(x)

    def pop(self):
        """
        :rtype: void
        """
        if self.stack:
            value = self.stack.pop(len(self.stack)-1)
            if value is not None:
                self.min_heap.remove(value)

    def top(self):
        """
        :rtype: int
        """
        if self.stack:
            return self.stack[len(self.stack)-1]

    def getMin(self):
        """
        :rtype: int
        """
        if self.min_heap:
            return heapq.nsmallest(1, self.min_heap)[0]

最小值判断

import sys

class MinStack1:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min = sys.maxsize
        self.stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if x <= self.min:
            # 在小于x的最小的值
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)

    def pop(self):
        """
        :rtype: void
        """
        peak = self.stack.pop()
        if peak == self.min:
            self.min = self.stack.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.min

2018-07-18

783. 二叉搜索树结点最小距离

常规方法,用到bst的特效

class Solution:
    def find_max(self, node):
        while node.right:
            node = node.right
        return node.val

    def find_min(self, node):
        while node.left:
            node = node.left
        return node.val

    def minDiffInBST(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return
        left_max = abs(root.val - self.find_max(root.left)) if root.left else None
        right_min = abs(root.val - self.find_min(root.right)) if root.right else None

        left = self.minDiffInBST(root.left)
        right = self.minDiffInBST(root.right)
        seq = [ele for ele in [left_max, right_min, left, right] if ele is not None]
        if seq:
            return min(seq)

先把数都拿出来,然后排序,然后逐一求差,找最小的

class Solution:
    def get_values(self, node):
        if not node:
            return []
        values = [node.val]
        values += self.get_values(node.left)
        values += self.get_values(node.right)
        return values

    def minDiffInBST(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        tree_vals = self.get_values(root)
        dp = []
        tree_vals.sort()
        for i in range(1, len(tree_vals)):
            dp.append(abs(tree_vals[i] - tree_vals[i-1]))
        return min(dp)

38. 报数

class Solution:
    def build(self, string):
        current = '#'
        count = 0
        res = ''
        for i in string:
            # 如果遍历字符和current记录中的不一样,则有可能是刚开始,也可能是一串相等数字的结束,
            # 如果是结束,则current就不等于#,这样将上一串数字结果加入到res
            # 然后将current置为当前数字,并且count置为1
            if i != current:
                if current != '#':
                    res += str(count) + current
                current = i
                count = 1
            else:
                count += 1
        res += str(count) + current
        return res

    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        string = '1'
        for i in range(2, n+1):
            string = self.build(string)
        return string

225. 用队列实现栈

这种题感觉比较无聊

from collections import deque


class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = deque([])

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.queue.appendleft(x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.queue.popleft()

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.queue[0]

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return len(self.queue) == 0

706. Design HashMap

class MyHashMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.map = [None] * 1000000

    def put(self, key, value):
        """
        value will always be positive.
        :type key: int
        :type value: int
        :rtype: void
        """
        self.map[key] = value

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        value = self.map[key]
        if value is None:
            return -1
        else:
            return value

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: void
        """
        self.map[key] = None

2018-07-17

653. 两数之和 IV - 输入 BST

哎,累了的时候就容易出小错误

class Solution:
    def traverse(self, node):
        if not node:
            return []
        res = [node]
        res += self.traverse(node.left)
        res += self.traverse(node.right)
        return res

    def search(self, node, target):
        if not node:
            return
        if node.val == target:
            return node
        elif node.val < target:
            return self.search(node.right, target)
        else:
            return self.search(node.left, target)

    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        # 遍历tree,随便拿一个元素,然后在bst中找另一个元素
        for ele in self.traverse(root):
            another = k - ele.val
            node = self.search(root, another)
            if node is None or node == ele:
                continue
            else:
                return True
        return False

二进制间距

class Solution:
    def binaryGap(self, N):
        """
        :type N: int
        :rtype: int
        """
        i = 0
        binary = bin(N)[2:]
        res = 0
        while i < len(binary):
            step = 1
            j = i + 1
            while j < len(binary) and binary[j] != '1':
                j += 1
                step += 1
            if j == len(binary):
                break
            i = j
            res = max(step, res)
        return res

Design HashSet

哈希表?

class MyHashSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.table = [None] * 1000000

    def add(self, key):
        """
        :type key: int
        :rtype: void
        """
        self.table[key] = key

    def remove(self, key):
        """
        :type key: int
        :rtype: void
        """
        self.table[key] = None

    def contains(self, key):
        """
        Returns true if this set did not already contain the specified element
        :type key: int
        :rtype: bool
        """
        return self.table[key] is not None



# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

690. 员工的重要性

递归处理

"""
# Employee info
class Employee:
    def __init__(self, id, importance, subordinates):
        # It's the unique id of each node.
        # unique id of this employee
        self.id = id
        # the importance value of this employee
        self.importance = importance
        # the id of direct subordinates
        self.subordinates = subordinates
"""


class Solution:
    def traverse(self, employee_id):
        employee = self.employees_dict[employee_id]
        importance = employee.importance
        for subordinate in employee.subordinates:
            importance += self.traverse(subordinate)
        return importance

    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        self.employees_dict = {e.id: e for e in employees}
        return self.traverse(id)

2018-07-16

704. Binary Search

确定边界条件的要点是,保证定义的区间规则和循环内部迭代的区间规则一致。比如下面的是左闭右闭区间,那么迭代的时候就可以使用right=mid-1,如果是左闭右开区间,那么right=mid,因为mid-1可能就是解,如果将right=mid-1那么就可能错过这个正解。循环结束条件也应该符合相同的区间规则。

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

2018-07-15

709. 转换成小写字母

直接调用python的方法

class Solution:
    def toLowerCase(self, str):
        """
        :type str: str
        :rtype: str
        """
        return str.lower()

或者通过ASC码来转换

class Solution:
    def toLowerCase(self, str):
        """
        :type str: str
        :rtype: str
        """
        res = []
        for s in str:
            ord_s = ord(s)
            if 65 <= ord_s <= 90:
                res.append(chr(ord_s + 32))
            else:
                res.append(s)
        return ''.join(res)

2018-07-14

860.柠檬水找零

贪心算法,优先拿大钞找零

class Solution:
    def lemonadeChange(self, bills):
        """
        :type bills: List[int]
        :rtype: bool
        """
        five, ten, twenty = 0, 0, 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else:
                if ten != 0 and five != 0:
                    ten -= 1
                    five -= 1
                    twenty += 1
                elif five >= 3:
                    five -= 3
                    twenty += 1
                else:
                    return False
        return True

2018-07-13

旋转数字

class Solution:
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        rotate_map = {
            '0': '0',
            '1': '1',
            '8': '8',
            '5': '2',
            '2': '5',
            '6': '9',
            '9': '6'
        }
        count = 0
        for n in range(N+1):
            n_list = []
            for d in str(n):
                if d not in rotate_map:
                    break
                n_list.append(rotate_map[d])
            else:
                if n != int(''.join(n_list)):
                    count += 1
        return count

2018-07-12

计数二进制子串

class Solution:
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 当前重复的数字种类的个数
        cur = 1
        # 上一种数字重复的次数
        pre = 0
        res = 0
        idx = 1
        # 遍历的时候如果和前一个数相等,则cur+1
        # 如果出现不等,则将cur赋值给pre
        # 只要pre大于等于cur的时候,count就自增1
        # 因为0011中的结果为2-> 01 和 0011
        while idx < len(s):
            if s[idx-1] == s[idx]:
                cur += 1
            else:
                pre = cur
                cur = 1
            if pre >= cur:
                res += 1
            idx += 1
        return res

2018-07-11

区域和检索 - 数组不可变

一道简单的题,却没想到动态规划可以如此高的效率

  • 普通方法(1416 ms)
class NumArray:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])
  • 动态规划(88 ms)
class NumArray:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self._dp = {}
        sums = 0
        for idx, num in enumerate(nums):
            sums += num
            self._dp[idx] = sums

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self._dp[j]
        return self._dp[j] - self._dp[i-1]

2018-07-10

山羊拉丁文

这是一道多么无聊的题啊!

class Solution:
    def toGoatLatin(self, S):
        """
        :type S: str
        :rtype: str
        """
        res = []
        d = {'A', 'E', 'I', 'O', 'U'}
        for idx, word in enumerate(S.split(' '), 1):
            if word[0].upper() in d:
                word += 'ma'
            else:
                first_alphabet = word[0]
                word = word[1:] + first_alphabet + 'ma'

            word += 'a' * idx
            res.append(word)
        return ' '.join(res)

2018-07-09

最大三角形面积

海伦公式:A = sqrt(s*(s-a)*(s-b)*(s-c)) 其中 s 为周长的一半 s = (a+b+c)/2

class Solution:
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        import math
        max_area = 0
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                for k in range(j+1, len(points)):
                    point_i, point_j, point_k = points[i], points[j], points[k]
                    distance_i_j = math.sqrt((point_i[0] - point_j[0]) ** 2 + (point_i[1] - point_j[1]) ** 2)
                    distance_i_k = math.sqrt((point_i[0] - point_k[0]) ** 2 + (point_i[1] - point_k[1]) ** 2)
                    distance_j_k = math.sqrt((point_k[0] - point_j[0]) ** 2 + (point_k[1] - point_j[1]) ** 2)
                    s = (distance_i_j + distance_i_k + distance_j_k) / 2
                    max_area = max(s * (s-distance_i_k) * (s-distance_i_j) * (s-distance_j_k), max_area)
        return math.sqrt(max_area)

2018-07-08

岛屿的最大面积

深度优先遍历,注意递归的结束条件

class Solution:
    def go_right(self, row, col):
        if col + 1 < self.cols:
            return row, col + 1
        return None, None

    def go_up(self, row, col):
        if row - 1 >= 0:
            return row - 1, col
        return None, None

    def go_down(self, row, col):
        if row + 1 < self.rows:
            return row + 1, col
        return None, None

    def go_left(self, row, col):
        if col - 1 >= 0:
            return row, col - 1
        return None, None

    def traverse_island(self, row, col):
        if row is None or col is None:
            return 0
        if self.grid[row][col] != 1:
            return 0
        self.grid[row][col] = 0
        result = 1
        result += self.traverse_island(*self.go_right(row, col))
        result += self.traverse_island(*self.go_down(row, col))
        result += self.traverse_island(*self.go_left(row, col))
        result += self.traverse_island(*self.go_up(row, col))
        return result

    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        self.grid = grid
        self.rows, self.cols = len(grid), len(grid[0])
        max_count = 0
        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] == 0:
                    continue
                else:
                    max_count = max(max_count, self.traverse_island(row, col))
        return max_count

2018-07-07

转置矩阵

对于方阵的话更简单,只需要考虑上半角矩阵,然后使用Python中的数字交换即可

class Solution:
    def transpose(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        if not A:
            return []
        rows, cols = len(A), len(A[0])
        B = [[0 for _ in range(rows)] for _ in range(cols)]
        for row in range(rows):
            for col in range(cols):
                if row != col:
                    B[col][row] = A[row][col]
                else:
                    B[row][col] = A[row][col]
        return B

2018-07-06

托普利茨矩阵

感觉不能再刷简单题了,要不废了。。。233333

class Solution:
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        if not matrix:
            return True
        rows, cols = len(matrix), len(matrix[0])
        for row in range(rows):
            for col in range(cols):
                if row + 1 < rows and col + 1 < cols:
                    if matrix[row][col] != matrix[row+1][col+1]:
                        return False
        return True

2018-07-05

二进制表示中质数个计算置位

最大的数不超过100万,直接把二进制中小于100万的位数弄出来,这样二进制中最多的1,就是这个最大值了。所以直接遍历下,然后判断其中1的个数是不是在质数列表中即可。

class Solution:
    def countPrimeSetBits(self, L, R):
        """
        :type L: int
        :type R: int
        :rtype: int
        """
        # 2^19 == 524288
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        res = 0
        for number in range(L, R+1):
            count = bin(number).count('1')
            if count in primes:
                res += 1
        return res

2018-07-04

棒球比赛

题目复杂,说了一大堆,解法简单

class Solution:
    def calPoints(self, ops):
        """
        :type ops: List[str]
        :rtype: int
        """
        res = []
        for op in ops:
            if op == '+':
                res.append(sum(res[-2:]))
            elif op == 'D':
                res.append(res[-1] * 2)
            elif op == 'C':
                res.pop(-1)
            else:
                res.append(int(op))
        return sum(res)

修剪二叉搜索树

递归递归递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        if not root:
            return
        if L <= root.val <= R:
            root.left = self.trimBST(root.left, L, R)
            root.right = self.trimBST(root.right, L, R)
        elif root.val < L:
            root = self.trimBST(root.right, L, R)
        elif root.val > R:
            root = self.trimBST(root.left, L, R)
        return root

2018-07-03

罗马数字转整数

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        converter = {
            'I': 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        s_list = list(s.upper())
        res = idx = 0
        s_list_len = len(s_list)
        while idx < s_list_len:
            ele = s_list[idx]
            if idx < s_list_len - 1:
                next_ele = s_list[idx+1]
                if converter[ele] < converter[next_ele]:
                    res += converter[next_ele] - converter[ele]
                    idx += 2
                    continue
            res += converter[ele]
            idx += 1
        return res

2018-07-02

写字符串需要的行数

class Solution:
    def numberOfLines(self, widths, S):
        """
        :type widths: List[int]
        :type S: str
        :rtype: List[int]
        """
        pos = {alphabet: idx for idx, alphabet in enumerate("abcdefghijklmnopqrstuvwxyz")}
        idx = row = col = 0
        while idx < len(S):
            expected = col + widths[pos[S[idx]]]
            if expected > 100:
                row += 1
                col = 0
            else:
                col += widths[pos[S[idx]]]
                idx += 1
        return [row+1, col]

2018-07-01

子域名访问计数

这道题没太多算法需要考虑,就是细节问题

class Solution:
    def subdomainVisits(self, cpdomains):
        """
        :type cpdomains: List[str]
        :rtype: List[str]
        """
        from collections import defaultdict
        counter = defaultdict(int)
        for cpdomain in cpdomains:
            times, domain = cpdomain.split(' ')
            elements = domain.split('.')
            idx = 0
            while idx < len(elements):
                subdomain = '.'.join(elements[idx:])
                counter[subdomain] += int(times)
                idx += 1
        return ["{} {}".format(value, key) for key, value in counter.items()]

2018-06-30

交替位二进制数

这道题比较简单,不过注意结束条件应该是n!=0

class Solution:
    def hasAlternatingBits(self, n):
        """
        :type n: int
        :rtype: bool
        """
        last = None
        while n != 0:
            n, remain = divmod(n, 2)
            if last is not None:
                if remain == last:
                    return False
            last = remain
        return True

2018-06-29

字符的最短距离

采用了左右边界指针法,pos为当前遍历指针,c_lft_posc_rgt_pos分别为在S中的c值左右指针,当pos遍历的时候,在lft指针左边,就是lft指针位置减去当前位置,在lft和rgt中间,则取最小值,等于rgt的时候需要调整左右指针位置,大于rgt则为pos减去rgt指针的位置。即可得解。

class Solution:
    def shortestToChar(self, S, C):
        """
        :type S: str
        :type C: str
        :rtype: List[int]
        """
        c_pos_in_S = []
        for idx, s in enumerate(S):
            if s == C:
                c_pos_in_S.append(idx)
        if not c_pos_in_S:
            return []
        c_lft_pos = c_pos_in_S.pop(0)
        c_rgt_pos = c_pos_in_S.pop(0) if c_pos_in_S else c_lft_pos
        pos = 0
        res = []
        while pos < len(S):
            if pos <= c_lft_pos:
                res.append(c_lft_pos - pos)
            elif c_lft_pos < pos < c_rgt_pos:
                res.append(min([c_rgt_pos - pos, pos - c_lft_pos]))
            elif pos == c_rgt_pos:
                # 在等于右边界的时候调整边界位置
                res.append(c_rgt_pos - pos)
                c_lft_pos = c_rgt_pos
                c_rgt_pos = c_pos_in_S.pop(0) if c_pos_in_S else c_lft_pos
            else:
                res.append(pos - c_rgt_pos)
            pos += 1
        return res

2018-06-28

唯一摩尔斯密码词

最朴素的解法

class Solution:
    def uniqueMorseRepresentations(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        alphabet_morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
                          "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
        alphabets = 'abcdefghijklmnopqrstuvwxyz'
        alphabet_morse_dict = {alphabet: morse for alphabet, morse in zip(alphabets, alphabet_morse)}
        res = set()
        for word in words:
            res.add(''.join(alphabet_morse_dict[w] for w in word))
        return len(res)

当然也可以这样,a的ascii码为97

class Solution:
    def uniqueMorseRepresentations(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        t = [".-","-...","-.-.","-..",".","..-.","--.","....","..",\
             ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        return len(set("".join(t[ord(a) - 97] for a in x) for x in words))

山脉数组的峰顶索引

二分法,主要确定循环条件,以及lo,hi值的确定

  • 慎重截止条件,根据指针移动条件来看,这里需要将数组判断到空为止,不能进入死循环。比如lo=0;hi=len(A)-1;lo<=hi,并且根据lo和hi指针的意义,比如判断数组等于key的位置,如果key存在于数组,lo==hi相等时已经得到解,所以是lo<hi
  • hi的确定一定在mid为止的左边,并且不包含当前位置
  • 一定在mid位置的右边,并且不包括当前mid位置

该题截止条件就是将数组判断为空为止,而且一般也不可能出现lo==hi这种情况,因为输入数组肯定是山峰数组,所以lo=0;hi=len(A);lo<hilo=0;hi=len(A)-1;lo<=hi都是可以的

lo的确定,一定在mid位置的右边,并且不包括当前mid位置,因为在第一个if已经判断了,所以mid不是正解

hi的确定,一定在mid为止的左边,并且不包含当前mid位置,因为在第一个if已经判断了,所以mid不是正解

class Solution:
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        lo = 0
        hi = len(A) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if A[mid - 1] < A[mid] > A[mid + 1]:
                return mid
            elif A[mid] >= A[mid - 1]:
                lo = mid + 1
            elif A[mid] >= A[mid + 1]:
                hi = mid - 1

翻转图像

比较简单,无须赘述。不过使用字典来取反,比使用异或运算ele ^ 1快点

class Solution:
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        reverse = {1: 0, 0: 1}
        res = []
        for element in A:
            processed_element = [reverse[ele] for ele in element[::-1]]
            res.append(processed_element)
        return res


点赞走一波😏


评论

提交评论