LeetCode 训练场:1720. 解码异或后的数组

简介: LeetCode 训练场:1720. 解码异或后的数组

题目

1720. 解码异或后的数组

难度:简单

描述

未知 整数数组 arr 由 n 个非负整数组成。


经编码后变为长度为 n - 1 的另一个整数数组 encoded ,其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如,arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。


给你编码后的数组 encoded 和原数组 arr 的第一个元素 first(arr[0])。


请解码返回原数组 arr 。可以证明答案存在并且是唯一的。


示例 1:


输入: encoded = [1,2,3], first = 1

输出: [1,0,2,1]

解释: 若 arr = [1,0,2,1] ,那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]


示例 2:


输入: encoded = [6,2,7,3], first = 4

输出: [4,2,0,7,4]


提示:


2 < = n < = 1 0 4 2 <= n <= 10^42<=n<=10

4

encoded.length == n - 1

0 <= encoded[i] <= 105

0 <= first <= 105

方法

思路

因为 a ^ b = c,a ^ b ^ b = a,所以得知 c ^ b = a


观察题目,可以发现 arr[0] ^ arr[1] = encode[0]、arr[1] ^ arr[2] = encode[1]……,已知 encode 数组和 arr[0],运用上面的式子可以知道 arr[1] = arr[0] ^ encode[0]、arr[2] = arr[1] ^ encode[1]……


因为主要是遍历了一趟数组,所以时间复杂度为 O(n);


实现


class Solution {
    public int[] decode(int[] encoded, int first) {
        // 编码前的数组
        int[] arr = new int[encoded.length + 1];
        // 编码前数组的第一个元素
        arr[0] = first;
        // arr[i] ^ arr[i + 1] = encode[i],反过来 arr[i + 1] = encode[i] ^ arr[i]
        for(int i = 0; i < arr.length - 1; i++){
            arr[i + 1] = arr[i] ^ encoded[i];
        }
        return arr;
    }
}
目录
相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
131 1
|
5月前
|
Go 索引
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
144 6
|
6月前
|
存储 机器学习/深度学习 缓存
🚀 力扣热题 394:字符串解码(详细解析)(Go语言版)
文章提供了两种解法:栈结构和递归解法。栈解法通过维护数字栈与字符串栈,依次处理 `[` 和 `]`,构造解码结果;递归解法则利用函数调用逐层解析嵌套结构。两者时间复杂度均为 $O(n)$,空间复杂度也为 $O(n)$。栈解法直观易懂,适合初学者;递归解法优雅简洁,适合处理深度嵌套规则。掌握这两种方法,可灵活应对类似问题,提升解题能力。
195 11
|
11月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
108 0
|
11月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
81 4
|
11月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
93 0
Leetcode第三十三题(搜索旋转排序数组)
|
11月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
179 0
|
11月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
76 0
|
12月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
184 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
302 2