350.The intersection of two array

2024-01-01

字数统计: 362字 | 阅读时长: 2min

350. The intersection of two array II
Simple
883
company
Amazon
company
Byte beating
company
Facebook
Give you two integer arrays nums1 and nums2 ，Please return the intersection of two arrays in the form of an array。The number of times each element in the return result，It should be consistent with the number of times the elements appear in both arrays（If the number of times is inconsistent，Then consider taking the smaller value）。You can consider the order of the output result。

 

Exemplary example 1：

enter：nums1 = [1,2,2,1], nums2 = [2,2]
Output：[2,2]
Exemplary example 2:

enter：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output：[4,9]
 

hint：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
 

Advance：

If the given array has been arranged, the order is good？How will you optimize your algorithm？
if nums1 Size ratio nums2 Small，Which method is better？
if nums2 The elements are stored on the disk，Memory is limited，And you can't load all elements at one time to memory，what should you do？

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hash_1 = {}
        hash_2 = {}
        for index, i in enumerate(nums):
            if i not in hash_1:
                hash_1[i] = 1
                hash_2[i] = [index]
            else:
                hash_1[i] += 1
                hash_2[i].append(index)
        for i in hash_1:
            if hash_1[i] >= 2:
                for j in range(len(hash_2[i])):
                    for m in range(j + 1, len(hash_2[i])):
                        if abs(hash_2[i][j] - hash_2[i][m]) <= k:
                            return True
        return False

# Sort out the meaning：Whether the existence does not exceed k+1k + 1k+1 window，window内有相同元素。
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        s = set()
        for i in range(n):
            if i > k:
                s.remove(nums[i - k - 1])
            if nums[i] in s:
                return True
            s.add(nums[i])
        return False

&&Operate

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num1 = collections.Counter(nums1)
        num2 = collections.Counter(nums2)
        num = num1 & num2
        return num.elements()

show all >>

445.Two numbersII

2024-01-01

字数统计: 316字 | 阅读时长: 1min

topic：

2023-07-03 (1).png
445.Two numbers

Thought：

I have been with yesterday’s question，Find by the way
What is deducted is a very strange oneprecompiled.listnode.ListNode，But mine is'__main__.ListNode'。
Because：Repeatedly defined$ListNode$
不反转Linkedof方法可能就是昨天of那种，转化为math做。
The code is still0x3fof
and昨天ofanswer法一样

Code：

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head  # Direct the next node to yourself
        head.next = None  # 断开指向下一个节点of连接，ensure最终Linkedof末尾节点of next Is an empty node
        return new_head

    # l1 and l2 为当前遍历of节点，carry Be in place
    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None:  # recursion边界：l1 and l2 都Is an empty node
            return ListNode(carry) if carry else None  # If you are in place，Just create an additional node
        if l1 is None:  # if l1 是空of，Then then l2 一定不Is an empty node
            l1, l2 = l2, l1  # exchange l1 and l2，ensure l1 non empty，从而简化Code
        carry += l1.val + (l2.val if l2 else 0)  # 节点值andcarry加在一起
        l1.val = carry % 10  # Each node saves a digital position
        l1.next = self.addTwo(l1.next, l2.next if l2 else None, carry // 10)  # carry
        return l1

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)  # l1 and l2 Reversal，Just become【2. Two numbers】Over
        l3 = self.addTwo(l1, l2)
        return self.reverseList(l3)

show all >>

538.Convert the binary search tree to cumulative tree

2024-01-01

字数统计: 1.2k字 | 阅读时长: 6min

topic：

“””

Give two forks search Root node，The node value of the tree is different，Please convert it to a cumulative tree（Greater Sum Tree），Make each node node The new value of the original tree is greater than or equal to the original tree node.val The sum of the value。

remind，二叉searchTree满足下列约束条件：

The left tree of the node contains only the key Less than Node node node。
The right tree of the node contains only the key more than the Node node node。
左右子Tree也必须是二叉searchTree。

Notice：This question 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ same

Exemplary example 1：

enter：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Exemplary example 2：

enter：root = [0,null,1]
Output：[1,null,1]

Exemplary example 3：

enter：root = [1,0,2]
Output：[3,3,2]

Exemplary example 4：

enter：root = [3,2,4,1]
Output：[7,9,4,10]

hint：

The number of nodes in the tree is in 0 and 10⁴between。
The value of each node -10⁴ and 10⁴ between。
All the values in the tree 互不same 。
给定的Tree为二叉searchTree。

Thought：

method one：Travel in the preface
Thinking and algorithm

本题中要求我们将每个节点的值修改为原来的节点值加上所有more than the它的节点值之and。这样我们只需要Travel in the preface该二叉searchTree，记录过程中的节点值之and，Not continuously update the node value of the nodes you currently traversed，即可得到topic要求的累加Tree。

Method Two：Morris Traversal
Thinking and algorithm

There is a clever way to be online，只占用常数空间来实现中序Traversal。This method is caused by J. H. Morris exist 1979 Annual thesis「Traversing Binary Trees Simply and Cheaply」Proposed for the first time，Because it is called Morris Traversal。

我们以一个简单的Binary tree为例进行说明。假设我们要进行中序Traversal的 Morris Traversal。

Initialization The current node is the root node（current = 1）。
When the current node is not empty，Execute the following steps：
1. The left node of the current node is not empty。We find the front -drive node of the current node，也就是左子Tree中的最右节点。exist这个例子中，The front -drive node is the node5。
2. The right node of the front -drive node is empty，Point your right node to the current node（5 -> 1）。
3. Move the current node to its left child node（current = 2）。
1
2
3
4
5
1
\
2
/ \
4 5
1. The left node of the current node is not empty。We find the front -drive node of the current node，也就是左子Tree中的最右节点。exist这个例子中，The front -drive node is the node4。
2. The right node of the front -drive node is empty，Point your right node to the current node（4 -> 2）。
3. Move the current node to its left child node（current = 4）。
1
2
3
4
5
6
7
8
1
\
2
\
4
\
5
1. The left node of the current node is empty。Output当前节点的值（4）。
2. Move the current node to its right node（current = 5）。
3. The left node of the current node is empty。Output当前节点的值（5）。
4. Move the current node to its right node（current = 2）。
1
2
3
4
5
1
\
2
\
4
1. The left node of the current node is empty。Output当前节点的值（2）。
2. Move the current node to its right node（current = 1）。
1
2
3
1
\
2
1. The left node of the current node is empty。Output当前节点的值（1）。
2. Move the current node to its right node（current = 3）。
1
2
3
1
\
2
1. The left node of the current node is empty。Output当前节点的值（3）。
2. Move the current node to its right node（current = null）。
The current node is empty，Traversal结束。

According to the above steps，通过修改节点between的指针关系，我们完成了对Binary tree的中序Traversal。

Code：

中序Traversal

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def dfs(root: TreeNode):
            nonlocal total
            if root:
                dfs(root.right)
                total += root.val
                root.val = total
                dfs(root.left)
        
        total = 0
        dfs(root)
        return root

MorrisTraversal

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        # Get the successor node of the given node（中序Traversal中的下一个节点）
        def getSuccessor(node: TreeNode) -> TreeNode:
            succ = node.right
            while succ.left and succ.left != node:
                succ = succ.left
            return succ
        
        total = 0  # 记录累加的节点值之and
        node = root  # The current node initialization is the root node

        while node:
            if not node.right:  # If the right node of the current node is empty
                total += node.val  # Add the value of the current node to the cumulative value
                node.val = total  # Update the value of the current node to accumulate value
                node = node.left  # Move the current node to its left child node
            else:  # If the right node of the current node is not empty
                succ = getSuccessor(node)  # Get the successor node of the current node
                if not succ.left:  # If the left node of the successor node is empty
                    succ.left = node  # Point the left -node of the successor node to the current node，Establish a clue
                    node = node.right  # Move the current node to its right node
                else:  # If the left node of the successor node is not empty
                    succ.left = None  # Set the left node of the successor node to empty，Remove clues
                    total += node.val  # Add the value of the current node to the cumulative value
                    node.val = total  # Update the value of the current node to accumulate value
                    node = node.left  # Move the current node to its left child node

        return root  # Return to the root node

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def convert(node: TreeNode, total: int) -> int:
            if not node:
                return total

            # 递归Traversal右子Tree
            total = convert(node.right, total)

            # Update the node value to accumulate and add value
            total += node.val
            node.val = total

            # 递归Traversal左子Tree
            total = convert(node.left, total)

            return total

        convert(root, 0)
        return root

show all >>

6275. Make all the minimum operations of all elements in the array II

2024-01-01

字数统计: 202字 | 阅读时长: 1min

2023-01-22 (1).png
6275. Make all the minimum operations of all elements in the array II

Thought:

Weekly Two Questions！！！

·First use the list derivative to calculate the difference between each element。
·Then，Initialize a counter to track the required operations required。
·The difference between traversing，And check whether each difference can be removed。
·if not，Then return -1，Because the array cannot be equal to the given operation。
·If it is eliminated，It removes the absolute value of the difference to add to the counter。
·at last，It returns the required number of operations。

for example：[3,0,-6,3]It is every positive number divided by3In harmony，Tested many times，是因为at last一种特殊情况（When two list items, etc.）No consideration。

Code：

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        if k <= 0:
            if nums1 != nums2:
                return -1
            else:
                return 0
        diff = [nums1[i] - nums2[i] for i in range(len(nums1))]
        if sum(diff) != 0:
            return -1
        if sum(diff) % k != 0:
            return -1
        operations = 0
        for index, d in enumerate(diff):
            if d % k != 0:
                return -1
            if d > 0:
                operations += d // k
        return operations

show all >>

6293. Count the number of good array

2024-01-01

字数统计: 187字 | 阅读时长: 1min

At first glance, this question is a double pointer，But I am not familiar with the double pointer，Most of the time was wasted when you set up the framework。

This question is the third question of Zhou Sai，The first two questions were killed quickly，But because I slept，It’s only half an hour left when the computer is turned on。

always theredebug，Watch this afternoon0x3fSolution。There is a set of explanations of his sliding window algorithm and double pointer。

from collections import Counter
from itertools import count
from typing import List


class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        start = 0
        tail = 0
        flag = 0
        if len(set(nums)) == 1:
            if k > len(nums) * (len(nums)-1) // 2:
                return 0
        while start < len(nums) - 1:
            x = Counter(nums[start:tail])
            if len(x) >= k:
                flag2 = 0
                for j in x:
                    if x[j] >= k:
                        flag2 += 1
                if flag2 >= k:
                    flag += 1
            else:
                for i in x:
                    if x[i] * (x[i] - 1) // 2 >= k:
                        flag += 1
            if tail != len(nums):
                tail += 1
            else:
                start += 1

        return flag

show all >>

6323. Child that divides money the most

2024-01-01

字数统计: 510字 | 阅读时长: 3min

topic：

I met for the first time：’2023/3/19-16:51’
screenshot2023-09-22 afternoon11.42.18.png
6323. Child that divides money the most.md

Thought：

“————–”

This question is the first half of the year3月份的时候的周赛topic，topic链接：6323

“————–”

I found that this is a mathematical problem at the beginning，I wrote for a long time, I don’t know how to deal with the last money left。
So I wrote a list，One child and one child gives money。
math：
If the remaining 0 people，and money>0，Then you must be divided into one that has been divided 8 Dollar的people，
ans minus one。
If the remaining 1 people，and money=3，To avoid allocation 4 Dollar，
Then you must be divided into one that has been divided 8 Dollar的people，ans minus one。
其它情况全部给一个people，if这个people分配到 4 Dollar，
他再给另一个people 1 Dollar，so ans constant。

The following isylbExplanation of big guys：（2023-9-22renew）
if money<children，Then there must be children who do not share money，return −1。

if money>8×children，So children−1 A child obtained 8 Dollar，剩下的一A child obtained money−8×(children−1) Dollar，return children−1。

if money=8×children−4，So children−2 A child obtained 8 Dollar，The remaining two children sharing the rest 12 Dollar（As long as not 4, 8 Dollar就行），return children−2。

if，We assumed that there are x A child obtained 8 Dollar，Then the rest of the money is money−8×x，As long as it is guaranteed to be greater than equal to the remaining number of children children−x，You can satisfy the meaning。therefore，We just need to ask x Maximum value，That is the answer。

Code：

List

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        money -= children
        children_list = [1] * children
        if money < 0:
            return -1
        counts = min(money // 7, children)
        for i in range(counts):
            children_list[i] = 8
        children_list[-1] += money - counts * 7
        counts = children_list.count(8)
        if children_list[-1] == 4:
            if children_list[-2] != 8:
                pass
            else:
                counts -= 1
        return counts

math

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        money -= children  # 每people至少 1 Dollar
        if money < 0: return -1
        ans = min(money // 7, children)  # Preliminary allocation，让尽量多的people分到 8 Dollar
        money -= ans * 7
        children -= ans
        # children == 0 and money：Must find a previous division 8 Dollar的people，After allocating the remaining money
        # children == 1 and money == 3：不能有people恰好分到 4 Dollar
        if children == 0 and money or \
           children == 1 and money == 3:
            ans -= 1
        return ans

ylb

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        if money < children:
            return -1
        if money > 8 * children:
            return children - 1
        if money == 8 * children - 4:
            return children - 2
        return (money-children) // 7

show all >>

6300. Minimum public value

2024-01-01

字数统计: 56字 | 阅读时长: 1min

2023-01-22 (2).png
6300. Minimum public value

Thought：

Originally intending to use the meta group one by one to find one by one，But timeout。
Then useintersectionFunction inO(1)Solution at time complexity

Code：

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        common = set(nums1).intersection(nums2)
        if common:
            return min(common)
        return -1

show all >>

6324. Maximize the great value of the array

2024-01-01

字数统计: 394字 | 阅读时长: 2min

topic：

6324. Maximize the great value of the array.md
Give you a bidding 0 Started integer array nums 。You need to nums Re -arrange into a new array perm 。

definition nums of Great value To satisfy 0 <= i < nums.length and perm[i] > nums[i] of下标数目。

Please return to re -arrangement nums 后of maximum Great value。

Exemplary example 1：

enter：nums = [1,3,5,2,1,3,1]
Output：4
explain：A optimal arrangement scheme is perm = [2,5,1,3,3,1,1] 。
The bidding is 0, 1, 3 and 4 Place，All perm[i] > nums[i] 。So we return 4 。

Thought：

Three ways to think about this question：
The first is Tian Ji horse racing（I am）： InumsContinuously reappear，Advance numbers，Then compare（time out）
Then there is a double pointer-Hash table：
每个元素只能被bigof元素指向一次（for example5Compare3big，3Can’t follow4对Compare了）
Two pointers point to the tail element at the same time，whenleft not less than rightof时候，left–。
else left– right– Counter– count ++
Last returncount
灵神ofTian Ji horse racing：
sort后直接在原数组上面找Comparewhen前元素bigof元素

Code：

I am

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        nums_source.sort()
        max_count = 0
        
        # when新数组与旧数组相同时，Stop loop
        for _ in range(len(nums)):
             nums_source = nums_source[1:] + [nums_source[0]]
             print(nums_source, nums)
             count = 0
             for i in range(len(nums)):
                 if nums_source[i] > nums[i]:
                     count += 1
                     print(count)
             max_count = max(max_count, count)
        return max_count

Double pointer+Hash table

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        #print(nums)
        left = len(nums) - 1
        dicts = Counter(nums)
        count = 0
        right = left
        while right >= left >= 0:
            if nums[right] <= nums[left]:
                left -= 1
            if nums[right] > nums[left]:
                if dicts[nums[left]] > 0:
                    dicts[nums[left]] -= 1
                    left -= 1
                    right -= 1
                    count += 1
                    #print(dicts, nums, count)
                else:
                    left -= 1
            elif right == 0 or left == 0:
                break

        return count

Tian Ji horse racing

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            if x > nums[i]:
                i += 1
        return i

show all >>

6338. Number of methods of monkey collision Weekly

2024-01-01

字数统计: 148字 | 阅读时长: 1min

2023-01-29 (1).png
6338. Number of methods of monkey collision

Thought：

纯math问题，that is$2^n - 2$。butnAt most$10^9$So big，Return directly to timeout。
所以用了Fast power算法，

使用Fast power算法来降低计算 2^n Time complexity。
it’s here，We use variables x To store 2^n，And in each cycle x square。when n When you are a miracle，We will take the result to take the result x。This can be calculated in each cycle2^n。
Before returning the result，We need to use(res-2)%mod Remove the border situation

Code：

class Solution:
    def monkeyMove(self, n: int) -> int:
        mod = 10**9 + 7
        res = 1
        x = 2
        while n > 0:
            if n % 2 == 1:
                res = (res * x) % mod
            x = (x * x) % mod
            n = n // 2
        return (res-2) % mod

show all >>

6331The most prizes won in the two lines make()usage

2024-01-01

字数统计: 328字 | 阅读时长: 1min

topic

2023-02-05 (1).png
6331. The most prizes won in the two lines

Thought

make
make() yes Go Built -in function of language memory distribution，There are three parameters default。

1	make(Type, len, cap)

Type：type of data，Necessary parameters，Type 的值只能yes slice、 map、 channel 这三种type of data。
len：type of data实际占用的内存空间长度，map、 channel yesOptional parameter，slice yesNecessary parameters。
cap：为type of data提前预留的内存空间长度，Optional parameter。
所谓的提前预留yes当前为type of data申请内存空间的时候，Apply for additional memory space in advance，This can avoid the overhead brought by the second allocation of memory，Greatly improve the performance of the program。
You have such doubts when you see here，Since the size of the data has been specified at the time of initialization，Then why do you still specify the reserved size?？
这yes因为 make() 使用的yes一种动态数组算法，At first apply to the operating system for a small piece of memory，
这个就yes cap，wait cap quilt len After the occupation is full, you need to expand the capacity，
扩容就yes动态数组再去向操作系统申请当前长度的两倍的内存，Then copy the old data to the new memory space。

func maximizeWin(prizePositions []int, k int) (ans int) {
	n := len(prizePositions)
	pre := make([]int, n+1)
	left := 0
	for right, v := range prizePositions {
		for v-prizePositions[left] > k {
			left++
		}
		ans = max(ans, right-left+1+pre[left])
		pre[right+1] = max(pre[right],right-left+1)
	}
	return ans
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

show all >>