LeetCode

Posted on

这是我的力扣刷题记录，每天N题！

Easy

1 Two Sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

1
2
Given nums = [2, 7, 11, 15], target = 9. 
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        // 存储已经遇到过的可能的解
        // Key存解的数字，value存另一半解的index
        bufferDict = {}
        // O(n)复杂度
        for i in range(length):
            if nums[i] in bufferDict:
                // 发现已经存储过了，就返回结果
                return [bufferDict[nums[i]], i]
            else:
                // 将当前数字对应的解存下来
                bufferDict[target - nums[i]] = i

771 Jewels and Stones

Description

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Examples

1
2
3
4
5
Input: J = "aA", S = "aAAbbbb"
Output: 3

Input: J = "z", S = "ZZ"
Output: 0

Note

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

Solution

我的第一反应: 40ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        ## do a map
        Jlist = list(J)
        Jdict = {}
        for j in Jlist:
            Jdict[j] = 1
        ## judge whether i have these jewels
        for s in list(S):
            if s in Jdict:
                Jdict[s] += 1
        ## count all the jewels I have
        answer = 0
        for j in Jdict:
            answer += Jdict[j] - 1
        return answer

我觉得好的答案: 36ms

1
2
3
class Solution:
	def numJewelsInStones(self, J: str, S: str) -> int:
		return sum([1 for s in S if s in J])

938 Range Sum of BST

Description

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Examples

1
2
3
4
5
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note

  • The number of nodes in the tree is at most 10000.
  • The final answer is guaranteed to be less than 2^31.

Solution

我的第一反应：232ms

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


离开J？“举行的吃饭v会尽快，。/
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.result = 0
    ## 二叉搜索树遍历一遍逐个判断
    ## 先序遍历
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        # 首先需要左边节点非空，
        # 且如果当前的节点值已经比L还小了，那么左子树都不用搜索了
        if root.left is not None and root.val >= L:
            self.rangeSumBST(root.left, L, R)
        # 判断当前节点是否符合条件
        if (root.val >= L) and (root.val <= R):
            self.result += root.val
        # 首先需要右边节点非空，
        # 且如果当前的节点值已经比R还大了，那么右子树都不用搜索了
        if root.right is not None and root.val <= R:
            self.rangeSumBST(root.right, L, R)
        # 所有子树搜索完毕，返回子树结果
        return self.result

我觉得比较好的答案：