Re: [閒聊] 每日leetcode
看板Marginalman作者sustainer123 (caster)時間1年前 (2024/08/03 09:07)推噓1(1推 0噓 0→)留言1則, 1人參與討論串624/1554 (看更多)
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
推
08/03 11:21,
1年前
, 1F
08/03 11:21, 1F
討論串 (同標題文章)
完整討論串 (本文為第 624 之 1554 篇)：