網易首頁 > 網易號 > 正文申請入駐

2026-04-30：交替刪除操作后最后剩下的整數。用go語言，給定一個整數 n，把 1 到 n 依次排成一行。之后反復進行兩種刪數方式，并且這兩種

2026-04-30 00:13:45　來源: moonfdd

北京舉報

分享至

2026-04-30：交替刪除操作后最后剩下的整數。用go語言，給定一個整數 n，把 1 到 n 依次排成一行。之后反復進行兩種刪數方式，并且這兩種方式交替使用，先用第一種，再用第二種，一直持續到只剩下一個數為止。

? 第一種：從左往右，按“刪一個、留一個”的規律處理。
? 第二種：從右往左，也按“刪一個、留一個”的規律處理。

最終留下來的那個數是多少，返回它。

1 <= n <= 1000000000000000。

輸入： n = 8。

輸出： 3。

解釋：

寫下序列 [1, 2, 3, 4, 5, 6, 7, 8]。

從左側開始，我們刪除每隔一個數字：[1, 2, 3, 4, 5, 6, 7, 8]。剩下的整數是 [1, 3, 5, 7]。

從右側開始，我們刪除每隔一個數字：[1, 3, 5, 7]。剩下的整數是 [3, 7]。

從左側開始，我們刪除每隔一個數字：[3, 7]。剩下的整數是 [3]。

題目來自力扣3782。

過程詳解+復雜度分析一、題目核心規則回顧

1. 初始序列：1,2,3,...,n
2. 交替執行兩種刪除操作，先第一種，再第二種，循環直到只剩1個數：

? 第一種（左刪）：從左往右，刪一個、留一個
? 第二種（右刪）：從右往左，刪一個、留一個

3. 輸入n=8，輸出3。

二、n=8 完整刪除步驟（超詳細）初始狀態

序列：[1, 2, 3, 4, 5, 6, 7, 8]
剩余數字數量：8
當前要執行：第一種操作（左→右，刪1留1）

第一步：執行第一種刪除（左→右，刪一個留一個）

規則：從最左邊開始，刪除第1個，保留第2個；刪除第3個，保留第4個……依次循環
逐位處理：

1. 刪1，留2
2. 刪3，留4
3. 刪5，留6
4. 刪7，留8

? 剩余序列：[2, 4, 6, 8]
剩余數字數量：4
當前要執行：第二種操作（右→左，刪1留1）

第二步：執行第二種刪除（右→左，刪一個留一個）

規則：從最右邊開始，刪除第1個，保留第2個；刪除第3個，保留第4個……依次循環
原序列：[2, 4, 6, 8]，從右往左數順序：8、6、4、2
逐位處理：

1. 刪8，留6
2. 刪4，留2

從右往左刪完后，恢復原左右順序：
? 剩余序列：[2, 6]
剩余數字數量：2
當前要執行：第一種操作（左→右，刪1留1）

第三步：執行第一種刪除（左→右，刪一個留一個）

規則：再次從左往右，刪1留1
逐位處理：

1. 刪2，留6

? 這里發現：嚴格按字面模擬和題目示例結果不一致
題目示例的刪除步驟是：
初始[1,2,3,4,5,6,7,8]→ 左刪剩[1,3,5,7]→ 右刪剩[3,7]→ 左刪剩[3]

這說明：題目中的「刪一個留一個」定義是：保留第1個，刪除第2個；保留第3個，刪除第4個（和字面描述相反，是題目實際執行的規則）。

三、匹配題目示例的正確刪除步驟（n=8）初始序列

[1, 2, 3, 4, 5, 6, 7, 8]，數量：8
第一輪：第一種操作（左→右，留1刪1）
規則：從左到右，留第一個，刪第二個；留第三個，刪第四個……
處理后：[1, 3, 5, 7]

第二輪

序列：[1, 3, 5, 7]，數量：4
執行：第二種操作（右→左，留1刪1）
規則：從右到左，留第一個，刪第二個；留第三個，刪第四個……
從右往左數：7、5、3、1
留7，刪5；留3，刪1 → 恢復原順序：[3, 7]

第三輪

序列：[3, 7]，數量：2
執行：第一種操作（左→右，留1刪1）
留3，刪7 → 最終剩余：[3]

四、你提供的代碼邏輯過程（非模擬，數學公式直接計算）

你的代碼沒有逐次模擬刪除過程，而是用數學位運算直接計算結果，核心過程分3步：

1. 定義常量mask = 0xAAAAAAAAAAAAAAA
這個十六進制數轉換成二進制是：10101010...1010（偶數位全為1，奇數位全為0）。
2. 計算n-1：對輸入數字做減1處理。
3. 位運算(n-1) & mask：
按位與操作會只保留 n-1 的二進制偶數位，過濾掉奇數位。
4. 最后 +1：得到最終結果。

針對 n=8：
n-1=7（二進制 0111）
和 mask 按位與后得到 2（二進制 0010）
2+1=3 → 直接得到正確答案。

五、時間復雜度 & 額外空間復雜度 1. 時間復雜度

代碼只做了4個固定操作：減法、按位與、加法、常量定義。
所有操作都是O(1)（常數時間），和輸入n的大小（哪怕n是10^15）完全無關。
? 總時間復雜度：O(1)

2. 額外空間復雜度

代碼沒有創建數組、列表、棧等動態數據結構，只定義了：

? 1個入參 n
? 1個常量 mask
? 1個返回值變量
所有空間都是固定大小，不隨n變化。
? 總額外空間復雜度：O(1)

總結

1. 交替刪除的核心是先左刪、再右刪循環，直到剩一個數；
2. 你的代碼沒有模擬刪除過程，而是用位運算數學公式直接求解；
3. 時間復雜度：O(1)（常數級，極快）；
4. 額外空間復雜度：O(1)（無額外內存消耗）。

Go完整代碼如下：

package main

 import (
    "fmt"
)

 func lastInteger(n int64)int64 {
    const mask = 0xAAAAAAAAAAAAAAA// ...1010
    return (n-1)&mask + 1          // 取出 n-1 的從低到高第 2,4,6,... 位，最后再加一（從 1 開始）
}
func main() {
    n := int64(8)
    result := lastInteger(n)
    fmt.Println(result)
}

Python完整代碼如下：

# -*-coding:utf-8-*-

 def last_integer(n: int) -> int:
    mask = 0xAAAAAAAAAAAAAAA  # binary: ...1010
    return ((n - 1) & mask) + 1

 def main():
    n = 8
    result = last_integer(n)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代碼如下：

  

  


 int64_t lastInteger(int64_t n) {
    const int64_t mask = 0xAAAAAAAAAAAAAAA;
    return ((n - 1) & mask) + 1;
}

 int main() {
    int64_t n = 8;
    int64_t result = lastInteger(n);
    std::cout << result << std::endl;
    return 0;
}

我們相信人工智能為普通人提供了一種“增強工具”，并致力于分享全方位的AI知識。在這里，您可以找到最新的AI科普文章、工具評測、提升效率的秘籍以及行業洞察。歡迎關注“福大大架構師每日一題”，發消息可獲得面試資料，讓AI助力您的未來發展。

特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.