Re: [閒聊] 每日leetcode

[sustainer123 (caster)]

https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays

1460. Make Two Arrays Equal by Reversing Subarrays

給定arr跟target兩個等長array 你可以任意反轉arr的非空子陣列

反轉不限次數

假設能讓arr變成target 回傳True 反之False


Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]
2- Reverse subarray [4,2], arr becomes [1,2,4,3]
3- Reverse subarray [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to
do so.
Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.
Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to
target.


Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000


思路:

時間O(N) 空間O(N)

確認arr所有元素是否在target 然後確認數量是否相等

Python Code:

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        record1 = defaultdict(int)
        record2 = defaultdict(int)

        for i in range(len(arr)):
            if arr[i] not in target:
                return False
            record1[arr[i]] += 1
            record2[target[i]] += 1

        for k in record1.keys():
            if record1[k] != record2[k]:
                return False

        return True


思路2:

時間O(nlogn) 空間O(1)

排序

Python Code:
class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return sorted(target) == sorted(arr)




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722647254.A.3A2.html
※ 編輯: sustainer123 (123.194.160.111 臺灣), 08/03/2024 09:27:05
推 dont: 大師