非常感謝你閱讀本文~
歡迎【👍點贊】【?收藏】【📝評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~
文章目錄
- 1720. 解碼異或后的陣列：
- 樣例 1
- 樣例 2
- 提示
- 分析
- 題解
- java
- c
- c++
- python
- go
- rust
- 原題傳送門
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 <= 104
- encoded.length == n - 1
- 0 <= encoded[i] <= 105
- 0 <= first <= 105
分析
這道題是道考察基礎的題目，
- 我們先從位的角度考慮，異或運算只會影響對應的位，不同的位之間不產生影響，那么如果X是未知數，Y是已知的，Z是表示X和Y是相同的還是不同的，這種情況下，我們是不是一下子就知道X是什么了呢？（因為一個位不是0就是1，如果X和Y相同，那不用說，X的值就是Y；如果X和Y不同，那Y如果是0，X就是1，反之如果Y是1，X就是0）
- 異或的一個特性是，X和Y異或得到結果Z，那么知道其中任意2個數，做異或運算就可以得到剩下的那個數，
題解
java
class Solution {
public int[] decode(int[] encoded, int first) {
final int n = encoded.length;
int[] ans = new int[n + 1];
ans[0] = first;
for (int i = 0; i < n; ++i) {
ans[i + 1] = ans[i] ^ encoded[i];
}
return ans;
}
}
c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* decode(int* encoded, int encodedSize, int first, int* returnSize){
*returnSize = encodedSize + 1;
int* ans = malloc(sizeof(int) * (*returnSize));
ans[0] = first;
for (int i = 0; i < encodedSize; ++i) {
ans[i + 1] = ans[i] ^ encoded[i];
}
return ans;
}
c++
class Solution {
public:
vector<int> decode(vector<int>& encoded, int first) {
const int n = encoded.size();
vector<int> ans(n + 1);
ans[0] = first;
for (int i = 0; i < n; ++i) {
ans[i + 1] = ans[i] ^ encoded[i];
}
return ans;
}
};
python
class Solution:
def decode(self, encoded: List[int], first: int) -> List[int]:
ans = [first]
for num in encoded:
ans.append(ans[-1] ^ num)
return ans
go
func decode(encoded []int, first int) []int {
ans := make([]int, len(encoded) + 1)
ans[0] = first
for i, e := range encoded {
ans[i + 1] = ans[i] ^ e
}
return ans
}
rust
impl Solution {
pub fn decode(encoded: Vec<i32>, first: i32) -> Vec<i32> {
let mut ans = vec![first];
encoded.iter().enumerate().for_each(|(i, v)| {ans.push(ans[i] ^ v);});
ans
}
}
原題傳送門
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/302275.html
標籤：其他