2026-02-18：拆分归拢数组。用go话语，给定两个长度均为 n 的整数数组 nums1 和 nums2。你不错对 nums1 进行若干次如下“剪切-粘贴”操作：• 采取一个连络区间 nums1[L..R]（含端点）。• 将该区间从数组中摘出，数组剩下前半段 nums1[0..L-1]（若 L=0 则为空）和后半段 nums1[R+1..n-1]（若 R=n-1 则为空）。• 把摘出的那段（保握原有司法）插入到剩尾数组的狂妄位置，不错放在职意两个元素之间，也不错放到开头或末尾。问：要把 nums1 变为 nums2，至少需要进行若干次这么的剪切-粘贴操作？2 <= n == nums1.length == nums2.length <= 6。-100000 <= nums1[i]， nums2[i] <= 100000。nums2 是 nums1 的一个 排列。输入: nums1 = [1，1，2，3，4，5]， nums2 = [5，4，3，2，1，1]。输出: 3。评释:移除下标 0 - 2 处的 [1，1，2]；剩余 [3，4，5]；将 [1，1，2] 插入到位置 2，得到 [3，4，1，1，2，5]。移除下标 1 - 3 处的 [4，1，1]；剩余 [3，2，5]；将 [4，1，1] 插入到位置 3，得到 [3，2，5，4，1，1]。移除下标 0 - 1 处的 [3，2]；剩余 [5，4，1，1]；将 [3，2] 插入到位置 2，得到 [5，4，3，2，1，1]。题目来独力扣3690。解题念念路与形势1. 问题转动• 给定两个长度换取的数组 nums1 和 nums2，nums2 是 nums1 的一个排列。• 允许对 nums1 进行操作：遴荐一个连络区间，将其切出，然后插入到剩尾数组的狂妄位置（包括开头、中间、末尾）。• 决议：用最少的操作次数将 nums1 造成 nums2。2. 情状暗示• 由于数组长度 n ≤ 6，最多有 6! 种排列，但因为有类似元素，现实情状数更少。• 为了在 BFS 中暗示数组的情状，开云app下载需要对数组进行碎裂化编码。• 先将 nums1 排序得到 sorted，然后用每个元素在 sorted 中的索引暗示该元素。• 每个元素用 3 位二进制暗示（因为 n ≤ 6，索引 0~5，3 位迷漫）。• 将所有这个词这个词数组编码成一个整数，举例 nums = [1，1，2，3，4，5]，sorted = [1，1，2，3，4，5]，编码后每个元素用它在 sorted 中的索引暗示，然后拼接成一个整数。3. BFS 搜索• 从运奇迹态 val1（nums1 的编码）源流，决议情状是 val2（nums2 的编码）。• 使用队伍进行 BFS，每一层代表一次操作。• 关于现时情状 a，摆设所有这个词可能的剪切区间 [l， r]（0 ≤ l ≤ r < n）：• 从 a 中索要出区间 sub。• 将 a 分红三部分：左边（l 之前）、区间、右边（r 之后）。• 将区间 sub 插入到剩尾数组（左边+右边）的狂妄位置（0 到 n - (r - l + 1) 个位置）。• 生成新的情状 c。• 要是 c 等于 val2，则复返现时步数 ans。• 不然，要是 c 未被走访过，则加入队伍，陆续搜索。4. 编码与解码• encode 函数：将数组 nums 中每个元素替换为它在 sorted 中的索引，然后按 3 位一组拼接成整数。• 在 BFS 中，华体会体育app通过位运算来索要区间和拼接新情状，幸免手动构造数组，提高成果。5. 搜索拆开• BFS 第一次到达决议情状时，对应的步数即是最少操作次数。• 由于情状空间有限，BFS 一定能找到解。时期复杂度分析• 情状数：最多有 n! 种排列，n ≤ 6，是以情状数 ≤ 720。• 关于每个情状，摆设所有这个词可能的剪切区间：区间数目为 O(n²) = 36。• 关于每个区间，摆设插入位置：最多 O(n) = 6。• 是以每个情状推广出的新情状数 ≤ 36 × 6 = 216。• BFS 遍历所有这个词情状，总操作次数 ≤ 720 × 216 ≈ 15 万次，现实更少。• 每次操作王人是位运算，常数很小。• 总时期复杂度：O(n! × n³)，但现实运行很快，因为 n 很小。迥殊空间复杂度分析• 需要存储所有这个词走访过的情状：最多 720 个情状，每个情状用一个整数暗示，map 支拨稍大，但一经 O(情状数)。• 队伍中最多同期存储一层情状，最坏情况下可能存储所有这个词情状，但亦然 O(情状数)。• 总数外空间复杂度：O(n!)，即 O(720) 级别，相等小。追思• 使用 BFS + 情状压缩（编码）求解最少剪切-粘贴次数。• 时期复杂度：O(n! × n³)• 空间复杂度：O(n!)Go好意思满代码如下：.package mainimport ("fmt""slices""sort")funcencode(nums， sorted []int) (res int) {for i， x := range nums { res |= sort.SearchInts(sorted， x) << (i * 3) }return}funcminSplitMerge(nums1， nums2 []int)int {if slices.Equal(nums1， nums2) {return } n := len(nums1) sorted := slices.Clone(nums1) // 用于碎裂化 slices.Sort(sorted) val1 := encode(nums1， sorted) val2 := encode(nums2， sorted) vis := map[int]bool{val1: true} q := []int{val1}for ans := 1; ; ans++ { tmp := q q = nilfor _， a := range tmp {for r := 1; r <= n; r++ { // 为便捷已毕，先摆设 r，再摆设 l t := a & (1<<(r*3) - 1)for l := range r { sub := t >> (l * 3) b := a&(1<<(l*3)-1) | a>>(r*3)<<(l*3) // 从 a 中移除 subfor i := range n - r + l + 1 { c := b&(1<<(i*3)-1) | sub<<(i*3) | b>>(i*3)<<((i+r-l)*3)if c == val2 {return ans }if !vis[c] { vis[c] = true q = append(q， c) } } } } } }}funcmain() { nums1 := []int{1， 1， 2， 3， 4， 5} nums2 := []int{5， 4， 3， 2， 1， 1} result := minSplitMerge(nums1， nums2) fmt.Println(result)}Python好意思满代码如下：.# -*-coding:utf-8-*-import sysfrom typing import Listimport bisectdef encode(nums: List[int]， sorted_vals: List[int]) -> int:"""将数组编码为整数，每3位存储一个元素的索引""" res = for i， x in enumerate(nums): # bisect_left 尽头于 Go 的 sort.SearchInts idx = bisect.bisect_left(sorted_vals， x) res |= idx << (i * 3)return resdef min_split_merge(nums1: List[int]， nums2: List[int]) -> int:"""联想通过分割和归拢操作将 nums1 调度为 nums2 的最小步数"""if nums1 == nums2:return n = len(nums1) # 用于碎裂化 sorted_vals = nums1.copy() sorted_vals.sort() val1 = encode(nums1， sorted_vals) val2 = encode(nums2， sorted_vals) visited = {val1: True} queue = [val1] ans = 1 while queue: tmp = queue queue = []for a in tmp: # 摆设 r (子数组右鸿沟，1-based)for r in range(1， n + 1): # 索要低 r*3 位四肢 t t = a & ((1 << (r * 3)) - 1) # 摆设 l (子数组左鸿沟，-based)for l in range(r): sub = (t >> (l * 3)) & ((1 << ((r - l) * 3)) - 1) # 从 a 中移除子数组 [l， r) # 低 l*3 位保握不变 low_mask = (1 << (l * 3)) - 1 low_part = a & low_mask # 高位部分右移 high_part = a >> (r * 3) b = low_part | (high_part << (l * 3)) # 将子数组插入到各个可能的位置for i in range(n - r + l + 1): # 构建新数组 c # 低 i*3 位来自 b 的低位 c_low = b & ((1 << (i * 3)) - 1) # 中间插入子数组 c_mid = sub << (i * 3) # 高位来自 b 的剩余部分 c_high = (b >> (i * 3)) << ((i + r - l) * 3) c = c_low | c_mid | c_highif c == val2:return ansif c not in visited: visited[c] = True queue.append(c) ans += 1return-1 # 表面上不会引申到这里def main(): nums1 = [1， 1， 2， 3， 4， 5] nums2 = [5， 4， 3， 2， 1， 1] result = min_split_merge(nums1， nums2)print(result)if __name__ == "__main__": main()C++好意思满代码如下：.#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <unordered_map>using namespace std;int encode(const vector<int>& nums， const vector<int>& sorted) {int res = ;for (int i = ; i < nums.size(); i++) {// lower_bound 尽头于 Go 的 sort.SearchIntsint idx = lower_bound(sorted.begin()， sorted.end()， nums[i]) - sorted.begin(); res |= idx << (i * 3); }return res;}int minSplitMerge(vector<int>& nums1， vector<int>& nums2) {if (nums1 == nums2) {return; }int n = nums1.size(); vector<int> sorted = nums1; // 用于碎裂化 sort(sorted.begin()， sorted.end());int val1 = encode(nums1， sorted);int val2 = encode(nums2， sorted); unordered_map<int， bool> vis; vis[val1] = true; vector<int> q; q.push_back(val1);for (int ans = 1; ; ans++) { vector<int> tmp = q; q.clear();for (int a : tmp) {for (int r = 1; r <= n; r++) { // 为便捷已毕，先摆设 r，再摆设 lint t = a & ((1 << (r * 3)) - 1);for (int l = ; l < r; l++) {int sub = (t >> (l * 3)) & ((1 << ((r - l) * 3)) - 1);// 从 a 中移除 subint low_mask = (1 << (l * 3)) - 1;int low_part = a & low_mask;int high_part = a >> (r * 3);int b = low_part | (high_part << (l * 3));// 将子数组插入到各个可能的位置for (int i = ; i < n - r + l + 1; i++) {int c_low = b & ((1 << (i * 3)) - 1);int c_mid = sub << (i * 3);int c_high = (b >> (i * 3)) << ((i + r - l) * 3);int c = c_low | c_mid | c_high;if (c == val2) {return ans; }if (vis.find(c) == vis.end()) { vis[c] = true; q.push_back(c); } } } } } }}int main() { vector<int> nums1 = {1， 1， 2， 3， 4， 5}; vector<int> nums2 = {5， 4， 3， 2， 1， 1};int result = minSplitMerge(nums1， nums2); cout << result << endl;return;}
{jz:field.toptypename/}·
咱们坚信东谈主工智能为平庸东谈主提供了一种“增强用具”，并努力于共享全观念的AI学问。在这里，您不错找到最新的AI科普著述、用具评测、普及成果的隐讳以及行业瞻念察。迎接体恤“福大大架构师逐日一题”，发音讯可取得口试而已，让AI助力您的改日发展。
·
备案号: