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 中表示数组的状态，需要对数组进行离散化编码。• 先将 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 中，通过位运算来提取区间和拼接新状态，避免手动构造数组，提高效率。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;}
·股票配资平台查询系统
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
·
道正网提示：文章来自网络，不代表本站观点。
相关文章
热点资讯
