2022-12-01

双指针

python
def maxProfit(prices):
    '''
    121. Best Time to Buy and Sell Stock
    Example 1:
    Input: prices = [7,1,5,3,6,4]
    Output: 5
    Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
	Example 2:
	Input: prices = [7,6,4,3,1]
	Output: 0
	Explanation: In this case, no transactions are done and the max profit = 0.
    先定义最大利润为0，最小价为列表第一位
    循环遍历价格
    定义当前利润等于循环的价格减去最小价
    如果当前利润大于最大利润，替换最大利润为当前利润
    如果当前循环价格小于最小价，替换最小价等于当前循环价格
    循环结束，返回最大利润
    '''
        maxProfit, minPrice= 0, prices[0]
        for price in prices:
            curProfit = price - minPrice
            if curProfit > maxProfit:
                maxProfit = curProfit
            elif price < minPrice:
                minPrice = price
        return maxProfit
    
    '''
    定义最大利润，最小价格，
    循环体内当前最大利润比较，当前最小价格比较
    '''
    minprice, maxprofit = float('inf'), 0
    for i in prices:
        maxprofit = max(maxprofit, i-minprice)
        minprice = min(i, minprice)
    return maxprofit
        

2022-12-02

88. 合并两个有序数组

python
'''
88. Merge Sorted Array
Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in num

'''


def merge(nums1, m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        重新定义nums1等于排序后的num1和nums2切片且合并后的列表
        """
        nums1[:] = sorted(nums1[:m] + nums2[:n])
        # 这里不能用nums1，如果用则创建一个新对象也叫nums1,
        # 用切片则在原始列表内存地址中修改
        print(num1)
nums1=[1,2,3,0,0,0]
m=3
nums2 = [2,5,6]
n = 3
merge(nums1,m,nums2,n)

2022-12-03

415.Add Strings

不能直接str转int，需要内部实现一个str转int

Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

python
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        '''
        内部定义一个str转int的方法
        用字典接收str：0-9对应int：0-9
        输出初始化为0
        循环输入的字符串，
        输出=输出初始化*10 + 当前循环的值
        循环结束得到int型的数字返回
        最后主函数返回两数int相加后转字符串
        '''
        def str2int(num):
            numDict = {'0' : 0, '1' : 1, '2' : 2, '3' : 3, '4' : 4, '5' : 5,
                  '6' : 6, '7' : 7, '8' : 8, '9' : 9}
            output = 0
            for d in num:
                output = output * 10 + numDict[d]
            return output
        
        return str(str2int(num1) + str2int(num2)) 

2022-12-04

动态规划

Dynamic Programming

如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的

解题思路：

1. 确定dp数组（dp table）以及下标的含义
   1. 下标代表推导这个问题次数，值代表推导结果
2. 确定递推公式
   1. fn=f(n-1)+f(n-2)
3. dp数组如何初始化
   1. f0=0, f1=1
4. 确定遍历顺序
   1. 从前向后，从左往右
5. 举例推导dp数组
   1. 验证第6轮的斐波那契数为13

斐波那契数列

python
'''
70. Climbing Stairs
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:
    1 <= n <= 45
'''
class Solution:
    def climbStairs(self, n: int) -> int:
        '''
        a, b = b, a+b
        斐波那契额数列
        '''
        a, b = 1, 1
        for i in range(n):
            a, b = b, a+b
        return a

2022-12-06

Best Time to Buy and Sell Stock II

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        '''
        初始化最大利润为0，
        从列表的第2个成员开始循环，如果第二个大于第一个，
        最大利润等于第2个减去第一个【加上上一轮的最大利润】
        '''
        maxProfit = 0
        for i in range(1, len(prices)):
            if prices[i]>prices[i-1]:
                maxProfit += prices[i]-prices[i-1]
        return maxProfit 

2022-12-07

Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

python
class Solution:
    def reverse(self, x: int) -> int:
        if 2**31-1 > x > 0:
            if int(str(x)[::-1]) > 2**31-1:
                return 0
            else:
                return int(str(x)[::-1])
        elif -2**31 < x < 0:
            if -(int(str(abs(x))[::-1])) < -2**31:
                return 0
            else:
                return -(int(str(abs(x))[::-1]))
        else:
            return 0

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

python
# %%取模是取余数，//取掉余数，向上取整
def oddnumFirst(nums):
    head, tail = 0, len(nums)-1
    while head < tail:
        if nums[head] % 2 == 1:
            head += 1
        elif nums[tail] % 2 == 1:
            nums[tail], nums[head] = nums[head], nums[tail]
        tail -= 1
    print(nums)
    return nums

nums = [1,2,3,4]
oddnumFirst(nums)

2022-12-08

Valid Palindrome

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        '''
        定义首尾双指针，
        循环首小于尾，循环左边不是字母数字，左边则加1
        循环左边不是字母数字，右边减1，
        如果左边不等于右边返回false，左边加，1右边减1
        循环结束左边等于右边返回true
        '''
        left, right = 0, len(s)-1
        while left < right:
            while left < right and not s[left].isalnum():
                # 这里左边小于右边为了退出循环
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True

Palindrome Number

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

python
class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x)[::-1] == str(x)

349.Intersection of Two Arrays

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

python
def intersection(nums1, nums2):
    return list(set([i for i in nums1 if i in nums2]))

剑指 Offer 61. 扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5

数组的数取值为 [0, 13] .

python

Remove All Adjacent Duplicates In String

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

python
def removeDuplicates(self, s: str) -> str:
        '''
        如果遇到空字符串返回空串，
        定义一个空栈列表用于比较跟循环的元素是否相同，
        循环字符串，如果列表为空或者栈顶不等于本次循环元素，那么该元素入栈
        否则出栈，
        用字符串连接方法将列表剩余字符串连接并返回
        '''
        if s == '':
            return ''
        stack = []
        for element in range(len(s)):
            if stack == [] or stack[-1] != s[element]:
                stack.append(s[element])
            else:
                stack.pop()
        result = ''.join(stack)
        return result

Reverse Words in a String III

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "God Ding"
Output: "doG gniD"

python
class Solution:
    def reverseWords(self, s: str) -> str:
        record = s.split(' ')
        for element in range(len(record)):
            record[element] = record[element][::-1]
        result = ' '.join(record)
        return result

Number of 1 Bits

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

python
class Solution:
    def hammingWeight(self, n: int) -> int:
        return str(bin(n)).count('1')

2022-12-09

Two Sum II - Input Array Is Sorted

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        '''
        需要定义数组中成员出现的具体值和索引, 用哈希字典表记录
        循环numbers的key, value
        如果目标值减去循环值为x在字典key中, 则返回字典中的x和当前循环索引位
        由于题目说索引从1开始，所以返回列表中x+1和当前循环索引位+1
        上述条件不成立则添加进字典，列表的值作为字典的key，列表的索引作为
        字典的value
        循环完毕，未发现目标值减去循环值为x在字典中，返回空列表
        '''        
        record = {}
        for k, v in enumerate(numbers):
            if target - v in record:
                return [record[target - v]+1, k+1]
            record[v] = k
        return []

Missing Number

268. Missing Number

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

python
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        '''
        快慢指针
        排好序后（列表的索引和值应该相等，遇到不等的就是需要返回的值）
        定义慢指针，循环快指针在列表中，
        如果快指针不等于慢指针，返回慢指针
        不成立慢指针加1，
        循环结束返回慢指针表示在列表末尾添加
        '''
        nums.sort()# [0, 1, 3]
        slow = 0
        for fast in nums:
            if fast != slow:
                return slow
            slow += 1
        return slow

Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

python
class MyHashMap:

    def __init__(self):
        self.hashmap = {}

    def put(self, key: int, value: int) -> None:
        self.hashmap[key] = value

    def get(self, key: int) -> int:
        if key in self.hashmap:
            return self.hashmap[key]
        else:
            return -1

    def remove(self, key: int) -> None:
        self.temp = self.get(key)
        if self.temp != -1:
            self.hashmap.pop(key)


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

2022-12-10

Middle of the Linked List

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''
        定义快慢指针，循环快的链表和快指针不为空
        快链表步长2向前走，慢链表步长1向前走，
        最终快的到达空，慢的才走一半正是中间节点
        '''
        fast = slow = head
        while fast and fast.next:
            # 用不为空判断快指针到终点，
            # 如果奇数链表成员个数，fast.next指向空
            # 如果偶数链表成员个数，fast为空
            fast = fast.next.next
            slow = slow.next
        return slow

2022-12-12

Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

python
class Solution:
    def validPalindrome(self, s: str) -> bool:
        '''
        定义双指针，左指针0，右指针字符串长度-1
        
        循环退出条件左指针小于等于右指针
        如果左右不相等，返回左右值和左右值的反转值是否相等的bool，或者左右索引+1和其反转值是否相等的bool
        如果左右值相等，左指针右指针各自向中心移动一位
        循环退出返回True
        '''
        left, right = 0, len(s)-1
        while left <= right:
            if s[left] != s[right]:
                return s[left:right] == s[left:right][::-1] or s[left +1:right+1] == s[left+1:right+1][::-1]
            else:
                left += 1
                right -= 1
        return True

Longest Continuous Increasing Subsequence

674. Longest Continuous Increasing Subsequence

Example 1:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

Example 2:

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.

python
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        '''
        使用计数器记住连续子数组出现的最大长度，用列表记住最后的长度
        如果长度大于等于2，循环nums，如果第二个大于第一个，计数器+1，
        否则计数器还是等于1，最后追加计数器的值到列表，返回列表中
        最大的数就是连续子数组的最大长度。
        如果nums长度等于1返回1，否则返回0
        '''
        counter =1
        record = []
        if len(nums) >=2:
            for i in range(len(nums)-1):
                if nums[i+1] > nums[i]:
                    counter +=1
                else:
                    counter =1
                record.append(counter)
            return max(record)
        elif len(nums) ==1:
            return 1
        else:
            return 0

Find the Index of the First Occurrence in a String

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

python
# a.find('e')# find()方法返回找到e的最低索引，没找到返回-1
# str.find(str, beg=0, end=len(string))
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

Factorial Trailing Zeroes

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0
Output: 0

python
class Solution:
    def trailingZeroes(self, n: int) -> int:
        import math
        value = str(math.factorial(n))[::-1]
        counter = 0
        for i in value:
            if i != '0':break
            else:counter += 1
        return counter

2022-12-13

Maximum Product of Three Numbers

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

628. Maximum Product of Three Numbers

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

python
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        '''
        升序后，返回最后三位相乘和头两位和最后一位相乘的最大值
        '''
        nums.sort()
        return max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1])

252. Meeting Rooms

Problem: Given an array of meeting time intervals consisting of start and end times[[s1,e1],[s2,e2],…](si< ei), determine if a person could attend all meetings.

Example(s):

Input: [[0,30],[5,10],[15,20]] Output: false

python
'''
上一次会议的结束时间点大于下一场会议的开始时间点返回False，反之等于小于返回True
'''
def meetingRoom(nums):
    nums.sort()
    for i in range(len(nums)-1):
        if nums[i][1] > nums[i+1][0]:
            return False
    return True


# nums = [[7,10], [2,4]]
nums = [[0,30],[5,10],[15,20]]
if __name__ == '__main__':
    print(meetingRoom(nums))

231.Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

python
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        while n %2 ==0:
            n = n/2
        return n == 1

2022-12-14

581.Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

python
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        '''
        升序数组，在原数组上定义左右指针，同时向中心移动，
        与升序后的数组对比如果相等说明该位置不需要操作
        向中心移动一位，如果不等跳出循环，当前索引即需要排序的子数组边界
        最后原数组长度减去左右边界索引就是结果
        '''
        sorted_nums = sorted(nums)
        if sorted_nums == nums:
            return 0
        left_sorted = 0
        right_sorted = 0
        for i in range(len(nums)):
            if nums[i] == sorted_nums[i]:
                left_sorted += 1
            else:
                break
        for i in range(len(nums)):
            if nums[-i-1] == sorted_nums[-i-1]:
                right_sorted += 1
            else:
                break
        return len(nums) - left_sorted - right_sorted
        '''
        升序数组，定义左右指针，当左指针小于等于右指针时，
        如果原数组左指针等于升序后数组的左指针，
        即左边以左都不需要排序，左指针加1
        右边同理
        左边和右边都没找到相等的值，说明左边以左和右边以右都不需要排序，
        中间的需要排序，返回列表切片+1（由于切片左闭右开所以加1）
        最后左边大于右边循环退出，返回0，说明源列表不需要排序他已经是升序
        '''
        sortNums = sorted(nums)
        left, right = 0, len(nums)-1
        while left <= right:
            if nums[left] == sortNums[left]:
                left += 1
            elif nums[right] == sortNums[right]:
                right -= 1
            else:
                return len(nums[left:right])+1
        return 0

2022-12-15

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.

• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

python
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.nums = nums
        heapq.heapify(self.nums)
        
    def add(self, val: int) -> int:
        heapq.heappush(self.nums, val)
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)
        return self.nums[0]



# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

119.Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

python
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        return [[math.comb(i, j) for j in range(i+1)] for i in range(rowIndex+1)][rowIndex]

852.Peak Index in a Mountain Array

An array arr a mountain if the following properties hold:

• arr.length >= 3

• There exists some

  i
  

  with

  0 < i < arr.length - 1
  

  such that:

  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

python
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        # return arr.index(max(arr)) # 1
        # left, right = 0, len(arr)-1 # 2
        # while left != right:         
        #     if arr[left] > arr[right]:
        #         right -= 1
        #     elif arr[left] < arr[right]:
        #         left += 1
        #     elif arr[left] == arr[right] and left == right:
        #         return left
        #     else:
        #         right -= 1
        #         left += 1
        # return left
        left, right = 0, len(arr)-1 # 3
        while left < right:
            mid = (left+right) // 2
            if arr[mid] > arr[mid+1]:
                right = mid
            else:
                left = mid + 1
        return right

237.Delete Node in a Linked List

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        '''
        拷贝节点1赋值给节点5
        将拷贝的节点1的指针指向下下个节点9
        '''
        node.val = node.next.val
        node.next = node.next.next
        

922.Sort Array By Parity II

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

Example 1:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3]
Output: [2,3]

python
'''
定义偶奇双指针，
循环条件：偶奇同时小于列表长度，否则退出
如果列表的偶数索引值除以2等于1（代表此处索引不是偶数），和奇数的值做交换
再将奇数的指针向前移动2位
条件不成立说明此处是偶数，故将偶数指针向前移动2位
循环完毕返回列表
'''
class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        even, odd = 0, 1
        while even < len(nums) and odd < len(nums):
            if nums[even] % 2 == 1: # 偶数
                nums[even], nums[odd] = nums[odd], nums[even]
                odd += 2
            else:
                even += 2
        return nums

2022-12-16

387.First Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

python
class Solution:
    def firstUniqChar(self, s: str) -> int:
        '''
        用字典存储每个子串出现的次数(get()取字典中的键，keys()取字典中
        所有键的列表，values()取字典中所有值的列表，items()取字典中所有键值对的元组列表)，
        循环字符串，如果当前循环的值在字典中等于1，返回当前值
        循环完毕上述未返回则返回-1
        '''
        record = {}
        for i in s:
            if record.get(i) == None:
                record[i] = 1
            else:
                record[i] += 1
        for _ in range(len(s)):
            if record[s[_]] == 1:
                return _
        return -1

796.Rotate String

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

• For example, if s = "abcde", then it will be "bcdea" after one shift.

Example 1:

Input: s = "abcde", goal = "cdeab"
Output: true

Example 2:

Input: s = "abcde", goal = "abced"
Output: false

python
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        '''
        在长度相等的情况下，
        任何一方的2倍字符串，
        另一方都存在于这个2倍串
        '''
        return s in goal+goal and  len(s) == len(goal)

205.Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

python
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
		'''
        判断子串索引出现的列表是否相等即可
        '''
        return [s.index(i) for i in s] == [t.index(i) for i in t]

2022-12-18

350.Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

python
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        record = []
        pairdict = {}
        for i in nums1:
            pairdict[i] = pairdict.get(i, 0) + 1
        for j in nums2:
            if j in pairdict and pairdict[j] > 0:
                record.append(j)
                pairdict[j] -= 1
        return record

905.Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]
Output: [0]

python
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        counter = 0
        for i in range(len(nums)):
            if nums[counter] % 2 != 0:# 奇数
                nums.append(nums.pop(counter))
            else:
                counter += 1
        return nums

303.Range Sum Query - Immutable

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

python
class NumArray:

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

    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left:right+1])

2022-12-19

Example 1:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

python
class Solution:
    def reverseBits(self, n: int) -> int:
        '''
        先转换二进制，再转换字符串反转，再转换十进制
        '''
        as_bin = '{:032b}'.format(n)
        reversed_bin = ''.join(reversed(as_bin))
        return int(reversed_bin, base=2)

705.Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.

• bool contains(key) Returns whether the value key exists in the HashSet or not.

• void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

python
class MyHashSet:

    def __init__(self):
        self.HashSet = set()

    def add(self, key: int) -> None:
        self.HashSet.add(key)

    def remove(self, key: int) -> None:
        self.HashSet.discard(key)

    def contains(self, key: int) -> bool:
        return key in self.HashSet


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

1089.Duplicate Zeros

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

python
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        originLen, i = len(arr), 0
        while i < originLen:
            if arr[i] == 0:
                arr.insert(i+1, 0)
                arr.pop()
                i += 2
            else:
                i += 1

414.Third Maximum Number

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example 1:

Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2:

Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

python
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        if len(set(nums)) < 3:
            return max(nums)
        else:
            return sorted(set(nums))[-3]

2022-12-20

482.License Key Formatting

Example 1:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: s = "2-5g-3-J", k = 2
Output: "2-5G-3J"
Explanation: The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

python
class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        '''
        
        '''
        s = s.upper().replace('-', '')
        lenS = len(s)
        dash = k if lenS%k==0 else lenS%k
        result = s[:dash]
        while dash < lenS:
            result += '-' + s[dash:dash+k]
            dash += k
        return result

485.Max Consecutive Ones

Given a binary array nums, return the maximum number of consecutive 1's in the array.

Example 1:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 2

python
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        newstr = ''.join([str(i) for i in nums])
        newlist = newstr.split('0')
        return len(max(newlist))

345.Reverse Vowels of a String

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

python
class Solution:
    def reverseVowels(self, s: str) -> str:
        '''
        定义元音字母大小写列表，定义左右双指针，s转换成列表
        循环左边小于右边时，当左右指针值在元音列表中时
        左右指针值互换，左边加1，右边减1，
        当左边不在元音表里，加1
        当右边不在元音表，减1
        返回将列表转换成字符串
        '''
        vowels = list('aeiouAEIOU')
        left, right = 0, len(s)-1
        s = list(s)
        while left < right:
            if s[left] in vowels and s[right] in vowels:
                s[left], s[right] = s[right], s[left]
                left +=1
                right -=1
            if s[left] not in vowels:
                left +=1
            if s[right] not in vowels:
                right -=1
        return ''.join(s)

541.Reverse String II

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer 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 leave the other as original.

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"

python
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        '''
        将s转换成列表，循环列表从0到列表长度，步长为2k，
        将s切片从开头到i+k等于反转的它
        返回字符串连在一起
        '''
        s = list(s)
        for i in range(0, len(s), k*2):
            s[i:i+k] = s[i:i+k][::-1]
        return ''.join(s)

58.Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal

substring

consisting of non-space characters only.

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

python
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s1 = s.rstrip()
        for i in range(len(s1), 0, -1):
            if s1[i-1] == ' ':
                return len(s1[-1:i-1:-1])
        return len(s1)

989.Add to Array-Form of Integer

The array-form of an integer num is an array representing its digits in left to right order.

• For example, for num = 1321, the array form is [1,3,2,1].

Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.

Example 1:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: num = [2,7,4], k = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

python
class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        return [int(i) for i in list(str(int(''.join([str(i) for i in num]))+k))]

2022-12-21

326.Power of Three

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3x.

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 33

Example 2:

Input: n = 0
Output: false
Explanation: There is no x where 3x = 0.

Example 3:

Input: n = -1
Output: false
Explanation: There is no x where 3x = (-1).

python
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        while n % 3 == 0:
            n = n/3
        return n == 1

342.Power of Four

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

python
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        while n % 4 == 0:
            n = n / 4
        return n == 1
        # return n in set([4**0, 4**1, 4**2, 4**3, 4**4, 4**5,4**6, 4**7, 4**8, 4**9, 4**10, 4**11, 4**12, 4**13, 4**14, 4**15])

976.Largest Perimeter Triangle

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

python
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        sortnums = sorted(nums)[::-1]
        for i in range(len(nums)-2):
            if sortnums[i+2]+sortnums[i+1] > sortnums[i]:
                return sortnums[i+2]+sortnums[i+1]+sortnums[i]
        return 0

724.Find Pivot Index

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

python
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        '''
        定义左右双指针，使用枚举方法循环第一个值，
        中间索引是第一个值，那么右边的值和减去当前值
        如果左边等于右边，返回索引位，左边之和等于左边加当前循环值
        循环完毕，代表没有中间索引。返回-1
        '''
        left, right = 0, sum(nums)
        for index, value in enumerate(nums):
            right -= value# 因为已经开启循环，需要首先更新左边之和
            if left == right:
                return index
            left += value
        return -1

As we iterate through the array of numbers, we need to keep track of the sum of the values on the current number's left and its right. The following debugger trace demonstrates the values of the variables in each loop before the left == right line

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

1. index: 0, num: 1, left: 0, right: 27
2. index: 1, num: 7, left: 1, right: 20
3. index: 2, num: 3, left: 8, right: 17
4. index: 3, num: 6, left: 11, right: 11 <-- Found!!!

867.Transpose Matrix

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

Example 2:

Input: matrix = [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

python
class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        # return zip(*matrix)
        """
        先从列遍历，再嵌套行遍历，交换行列为列行到新数组（m行n列）
        m是3行，列表中3个子列表对应3行，n是3列一个子列表中3个子元素对应列数
        """
        m, n = len(matrix), len(matrix[0])
        result = [[0]*m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                result[j][i] = matrix[i][j]
        return result

1356.Sort Integers by The Number of 1 Bits

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

python
class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x: (bin(x).count('1'), x))

2022-12-22

1005.Maximize Sum Of Array After K Negations

Given an integer array nums and an integer k, modify the array in the following way:

• choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        '''
        对列表正序，循环k次，将列表第一个元素取反，
        再次对列表正序(对负数转正，对正数取最小的取反，最后求和才是最大化的值)
        '''
        nums.sort()
        for i in range(k):
            nums[0] = -nums[0]
            nums.sort()
        return sum(nums)

860.Lemonade Change

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: bills = [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

python
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        '''
        初始化十块五块有0张，循环账单，
        如果5，五块加1
        如果10且五块不为空，五块减1
        如果20且十块五块不为空，十块减1五块减1
        如果20且五块大于等于3，五块减3
        上述不服，返回false
        循环结束返回true
        '''
        five=ten=0
        for i in bills:
            if i == 5:
                five+=1
            elif i == 10 and five:
                ten+=1
                five-=1
            elif i == 20 and ten and five:
                ten-=1
                five-=1
            elif i == 20 and five >=3:
                five-=3
            else:
                return False
        return True

2022-12-23

917. Reverse Only Letters

Given a string s, reverse the string according to the following rules:

• All the characters that are not English letters remain in the same position.
• All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

python
class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        '''
        定义左右双指针，将s列表化，
        循环退出条件left < right
        如果左边的不是字母，左边加1，
        如果右边不是字母，右边加1
        否则交换左右指针值，左右往中间移动一位
        用join方法将新列表组合成字符串返回
        '''
        s, left, right = list(s), 0, len(s)-1
        while left < right:
            if not s[left].isalpha():
                left +=1
            elif not s[right].isalpha():
                right -=1
            else:
                s[left], s[right] = s[right], s[left]
                left +=1
                right -=1
        return ''.join(s)

507.Perfect Number

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer n, return true if n is a perfect number, otherwise return false.

Example 1:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

Example 2:

Input: num = 7
Output: false

python
class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        return num in [6,28,496,8128,33550336]

1287.Element Appearing More Than 25% In Sorted Array

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Example 2:

Input: arr = [1,1]
Output: 1

python
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        '''
        循环数组，当前循环值如果等于（当前索引+列表长度除以4）的值。
        返回当前值
        '''
        for i in range(len(arr)):
            if arr[i] == arr[i+len(arr)//4]:
                return arr[i]

1290.Convert Binary Number in a Linked List to Integer

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

The most significant bit is at the head of the linked list.

Example 1:

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

Example 2:

Input: head = [0]
Output: 0

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        s = ''
        while head:
            s += str(head.val)
            head = head.next
        return int(s.encode('ascii'), 2)

1480.Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

python
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        return [sum(nums[:i+1]) for i in range(len(nums))]

2022-12-24

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"
Output: 3

python
class Solution:
    def maxDepth(self, s: str) -> int:
        '''
        用栈的后进先出来，遇到左括号入栈，遇到右括号出栈，用变量
        记录过程中最大栈深度就是题解
        '''
        result, depth = 0, 0
        for i in s:
            if i == '(':
                depth +=1
                result = max(depth, result)
            elif i == ')':
                depth -=1
        return result

2022-12-26

1365. How Many Numbers Are Smaller Than the Current Number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

python
class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        '''
        将列表正序枚举每个数，小于当前数的个数等于当前数的索引，
        '''
        record = {}
        for k, v in enumerate(sorted(nums)):
            if v not in record:
                record[v]=k
        return [record[i] for i in nums]

1446.Consecutive Characters

The power of the string is the maximum length of a non-empty substring that contains only one unique character.

Given a string s, return the power of s.

Example 1:

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Example 2:

Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

python
class Solution:
    def maxPower(self, s: str) -> int:
        ''' 
        用count=1=result计数，循环列表，如果第二个字符串等于
        第一个字符串，count加1，否则count还是等于1，
        选出result和count中最大的数，返回result
        '''
        count=result=1
        for i in range(len(s)-1):
            if s[i+1] == s[i]:
                count +=1
            else:
                count = 1
            result = max(count, result)
        return result

2022-12-27

941.Valid Mountain Array

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

python
class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        '''
        排除列表长度小于3的数组不是山峰数组。
        定义左右双指针，循环从1到索引结束，
        两边向中间靠近，如果左边小于等于左边加1，那么进一步，
        如果右边小于等于右边减1，那么进一步，
        最后是山峰左右相等，不是则不等
        '''
        if len(arr) < 3:
            return False
        left, right = 0, len(arr)-1
        for i in range(1, len(arr)-1):
            if arr[left] < arr[left+1]:
                left +=1
            if arr[right] < arr[right-1]:
                right -=1
        return left == right

844.Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

python
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        result1 = ''
        result2 = ''

        for fast1 in range(len(s)):
            if s[fast1] != '#':
                result1 += s[fast1]
            else:
                result1 = result1[:-1]

        for fast2 in range(len(t)):
            if t[fast2] != '#':
                result2 += t[fast2]
            else:
                result2 = result2[:-1]
        return result1 == result2

367.Valid Perfect Square

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Example 1:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

python
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        return int(num**0.5)**2 == num

2022-12-28

1464.Maximum Product of Two Elements in an Array

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        '''
        循环nums，找出第一个最大值，然后pop在找出最大值，如果res
        长度等于2，退出循环，返回res两值减1相乘
        '''
        res=[]
        for i in range(2):
            res.append(nums.pop(nums.index(max(nums))))
        return (res[0]-1) * (res[1]-1)
    
    	
        nums.sort()
        return (nums[-1]-1) * (nums[-2]-1)