国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【算法學習】1486. 數組異或操作（java / c / c++ / python / go /

ztyzz / 2134人閱讀

摘要：數組定義為下標從開始且。請返回中所有元素按位異或后得到的結果。樣例輸入輸出解釋數組為，其中。為按位異或運算符。也就是只有是奇數并且是奇數的時候，最終結果的最低位才會是。

非常感謝你閱讀本文~
歡迎【?點贊】【?收藏】【?評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~

1486. 數組異或操作：

給你兩個整數，n 和 start 。

數組 nums 定義為：nums[i] = start + 2 * i（下標從 0 開始）且 n == nums.length 。

請返回 nums 中所有元素按位異或（XOR）后得到的結果。

樣例 1

輸入：	n = 5, start = 0輸出：	8解釋：	數組 nums 為 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。     "^" 為按位異或 XOR 運算符。

樣例 2

輸入：	n = 4, start = 3輸出：	8解釋：	數組 nums 為 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

樣例 3

輸入：	n = 1, start = 7輸出：	7

樣例 4

輸入：	n = 10, start = 5輸出：	2

提示

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

分析

我們可以直接按照題意，暴力循環，那么時間復雜度就是O(n)，是否有時間復雜度為O(1)的算法呢？

記x為變量，^是異或操作，則異或運算滿足以下性質：

  1. x ^ x = 0；
  2. x ^ 0 = x；
  3. x ^ y = y ^ x（交換律）；
  4. (x ^ y) ^ z = x ^ (y ^ z)（結合律）；
  5. x ^ y ^ y = x（自反性）；
  6. 如果x是4的倍數，x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0；
  • 本題要計算的 結果公式 為：start ^ (start + 2) ^ (start + 4) ^ ? ^(start + 2 * (n ? 1))。
  • 如果有一個函數 sumXor(x) 可以計算 0 ^ 1 ^ 2 ^ ? ^ x 。
  • 對于某變量x和n，計算sumXor(s - 1) ^ sumXor(s + n - 1)的結果，根據上面的 性質1 可以將 0 ^ 1 ^ 2 ^ … ^ (s - 1) 的值抵消為0，就變成 0 ^ s ^ (s + 1) ^ (s + 2) ^ ? ^ (s + n - 1) ，根據 性質2 可知與0做異或操作還是自己，最后結果就變成 s ^ (s + 1) ^ (s + 2) ^ ? ^ (s + n - 1) ，這個結果很接近我們要計算的內容。
  • 如果我們令 s = start / 2 ，把 結果公式 轉換成 (s ^ (s + 1) ^ (s + 2) ^ ? ^ (s + n - 1)) * 2，這樣并不成立，因為在做除以2的操作時，最低位丟失了，但是我們可以多帶帶處理最低位。
  • 觀察 結果公式 可知 (start + 2)，(start + 4) ，… ，(start + 2 * (n ? 1)) 的奇偶性質相同，而且和start一致，也就是最低位要么都是0，要么都是1，只有基數個1做異或操作時才會是1。也就是只有start是奇數并且n是奇數的時候，最終結果的最低位 e 才會是1。
  • 這時 結果公式 可以轉化為： ((sumXor(s - 1) ^ sumXor(s + n - 1)) * 2) | e 。

只要我們可以實現函數sumXor(x)，那么題目計算就可以做到O(1)的時間復雜度，根據 性質6 和 性質2 我們只需要考慮x除以4的余數，也就是最低2位，可以得到如下推導：

x % 4 = 0 的二進制位：xx…x00
x % 4 = 1 的二進制位：xx…x01
x % 4 = 2 的二進制位：xx…x10
x % 4 = 3 的二進制位：xx…x11

  • x % 4 = 0，sumXor(x) = x；
  • x % 4 = 1，sumXor(x) = (x - 1) ^ x，簡化可得 sumXor(x) = 1；
  • x % 4 = 2，sumXor(x) = (x - 2) ^ (x - 1) ^ x，簡化可得 sumXor(x) = x | 1；
  • x % 4 = 3，sumXor(x) = 0；
  • x % 4 等同于 x & 3 的操作，而且理論上 & 操作要比 % 操作更快；

題解

java

class Solution {    public int xorOperation(int n, int start) {        int s = start >> 1, e = n & start & 1;        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);        return ret << 1 | e;    }    public int sumXor(int x) {        switch (x & 3) {            case 0:                return x;            case 1:                return 1;            case 2:                return x | 1;            default:                // x & 3 == 3                return 0;        }    }}

c

int xorOperation(int n, int start) {    int s = start >> 1, e = n & start & 1;    int ret = sumXor(s - 1) ^ sumXor(s + n - 1);    return ret << 1 | e;}int sumXor(int x) {    switch (x & 3) {        case 0:            return x;        case 1:            return 1;        case 2:            return x | 1;        default:            // x & 3 == 3            return 0;    }}

c++

class Solution {public:    int xorOperation(int n, int start) {        int s = start >> 1, e = n & start & 1;        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);        return ret << 1 | e;    }    int sumXor(int x) {        switch (x & 3) {            case 0:                return x;            case 1:                return 1;            case 2:                return x | 1;            default:                // x & 3 == 3                return 0;        }    }};

python

class Solution:    def xorOperation(self, n: int, start: int) -> int:        def sumXor(x):            if x % 4 == 0:                return x            if x % 4 == 1:                return 1            if x % 4 == 2:                return x | 1            return 0        s = start >> 1        e = n & start & 1        ans = sumXor(s - 1) ^ sumXor(s + n - 1)        return ans << 1 | e

go

func xorOperation(n, start int) (ans int) {    s, e := start>>1, n&start&1    ret := sumXor(s-1) ^ sumXor(s+n-1)    return ret<<1 | e}func sumXor(x int) int {    switch x & 3 {        case 0:            return x        case 1:            return 1        case 2:            return x | 1        default:            return 0    }}

rust

impl Solution {   pub fn xor_operation(n: i32, start: i32) -> i32 {    let s = start >> 1;    let e = n & start & 1;    let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1);    return ret << 1 | e  }  fn sum_xor(x: i32) -> i32 {    match x & 3 {      0 => x,      1 => 1,      2 => x | 1,      _ => 0    }  }}

原題傳送門

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/122565.html

相關文章

  • 【算法學習】1920. 基于排列構建數組（java / c / c++ / python / go

    摘要：請你構建一個同樣長度的數組，其中，對于每個，都滿足。返回構建好的數組。從開始的排列是一個由到和也包含在內的不同整數組成的數組。 非常感謝你閱讀本文，歡迎【?點贊...

    aisuhua 評論0 收藏0

  • SegmentFault 技術周刊 Vol.40 - 2018，來學習一門新的編程語言吧！

    摘要：入門，第一個這是一門很新的語言，年前后正式公布，算起來是比較年輕的編程語言了，更重要的是它是面向程序員的函數式編程語言，它的代碼運行在之上。它通過編輯類工具，帶來了先進的編輯體驗，增強了語言服務。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不覺已經到來了，總結過去的 2017，相信小伙們一定有很多收獲...

    caspar 評論0 收藏0

  • SegmentFault 技術周刊 Vol.40 - 2018，來學習一門新的編程語言吧！

    摘要：入門，第一個這是一門很新的語言，年前后正式公布，算起來是比較年輕的編程語言了，更重要的是它是面向程序員的函數式編程語言，它的代碼運行在之上。它通過編輯類工具，帶來了先進的編輯體驗，增強了語言服務。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不覺已經到來了，總結過去的 2017，相信小伙們一定有很多收獲...

    nihao 評論0 收藏0

  • SegmentFault 技術周刊 Vol.40 - 2018，來學習一門新的編程語言吧！

    摘要：入門，第一個這是一門很新的語言，年前后正式公布，算起來是比較年輕的編程語言了，更重要的是它是面向程序員的函數式編程語言，它的代碼運行在之上。它通過編輯類工具，帶來了先進的編輯體驗，增強了語言服務。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不覺已經到來了，總結過去的 2017，相信小伙們一定有很多收獲...

    Drummor 評論0 收藏0

  • 【算法日積月累】1-選擇排序

    摘要：選擇排序算法實現實現選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實現前面我們說到了，我們為了突出排序算法的思想，將所有的例子僅限在數組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

    neuSnail 評論0 收藏0

發表評論

0條評論

ztyzz

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<