1460. 通過翻轉子數組使兩個數組相等 : 簡單計數模拟題

題目描述

這是 LeetCode 上的 ​​1460. 通過翻轉子數組使兩個數組相等​​ ，難度為 簡單。

Tag : 「模拟」、「計數」

給你兩個長度相同的整數數組 ​

​target​

​​ 和 ​

​arr​

​​ 。每一步中，你可以選擇 ​

​arr​

​ 的任意 非空子數組 并将它翻轉。你可以執行此過程任意次。

如果你能讓 ​

​arr​

​​ 變得與 ​

​target​

​​ 相同，傳回 ​

​True​

​​；否則，傳回 ​

​False​

​ 。

示例 1：

輸入：target = [1,2,3,4], arr = [2,4,1,3]

輸出：true

解釋：你可以按照如下步驟使 arr 變成 target：
1- 翻轉子數組 [2,4,1] ，arr 變成 [1,4,2,3]
2- 翻轉子數組 [4,2] ，arr 變成 [1,2,4,3]
3- 翻轉子數組 [4,3] ，arr 變成 [1,2,3,4]      

示例 2：

輸入：target = [7], arr = [7]      

示例 3：

輸入：target = [3,7,9], arr = [3,7,11]

輸出：false

解釋：arr 沒有數字 9      

提示：

模拟

當兩數組詞頻相同，且翻轉次數不受限制時，我們至少能通過「逐個調整」将一數組變為另一數組（以目前需要調整的位置作為待翻轉子數組的左端點，目标數值所在位置作為右端點）。

Java 代碼：

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        int n = arr.length, tot = 0;
        int[] cnt = new int[1010];
        for (int i = 0; i < n; i++) {
            if (++cnt[target[i]] == 1) tot++;
            if (--cnt[arr[i]] == 0) tot--;
        }
        return tot == 0;
    }
}      

TypeScript 代碼：

function canBeEqual(target: number[], arr: number[]): boolean {
    let n = target.length, tot = 0
    const cnt = new Array<number>(1010).fill(0)
    for (let i = 0; i < n; i++) {
        if (++cnt[target[i]] == 1) tot++
        if (--cnt[arr[i]] == 0) tot--
    }
    return tot == 0      

• 時間複雜度：
• 空間複雜度：，其中

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.1460​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。