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

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

• ? 第一種：從左往右，按“刪一個(gè)、留一個(gè)”的規(guī)律處理。

• ? 第二種：從右往左，也按“刪一個(gè)、留一個(gè)”的規(guī)律處理。

最終留下來的那個(gè)數(shù)是多少，返回它。

1 <= n <= 1000000000000000。

輸入： n = 8。

輸出： 3。

解釋：

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

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

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

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

題目來自力扣3782。

過程詳解+復(fù)雜度分析 一、題目核心規(guī)則回顧

1. 1. 初始序列：1,2,3,...,n

2. 2. 交替執(zhí)行兩種刪除操作，先第一種，再第二種，循環(huán)直到只剩1個(gè)數(shù)：

• ? 第一種（左刪）：從左往右，刪一個(gè)、留一個(gè)

• ? 第二種（右刪）：從右往左，刪一個(gè)、留一個(gè)

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

二、n=8 完整刪除步驟（超詳細(xì)） 初始狀態(tài)

序列：[1, 2, 3, 4, 5, 6, 7, 8]
剩余數(shù)字?jǐn)?shù)量：8
當(dāng)前要執(zhí)行：第一種操作（左→右，刪1留1）

第一步：執(zhí)行第一種刪除（左→右，刪一個(gè)留一個(gè)）

規(guī)則：從最左邊開始，刪除第1個(gè)，保留第2個(gè)；刪除第3個(gè)，保留第4個(gè)……依次循環(huán)
逐位處理：

1. 1. 刪1，留2

2. 2. 刪3，留4

3. 3. 刪5，留6

4. 4. 刪7，留8

? 剩余序列：[2, 4, 6, 8]
剩余數(shù)字?jǐn)?shù)量：4
當(dāng)前要執(zhí)行：第二種操作（右→左，刪1留1）

第二步：執(zhí)行第二種刪除（右→左，刪一個(gè)留一個(gè)）

規(guī)則：從最右邊開始，刪除第1個(gè)，保留第2個(gè)；刪除第3個(gè)，保留第4個(gè)……依次循環(huán)
原序列：[2, 4, 6, 8]，從右往左數(shù)順序：8、6、4、2
逐位處理：

1. 1. 刪8，留6

2. 2. 刪4，留2

從右往左刪完后，恢復(fù)原左右順序：
? 剩余序列：[2, 6]
剩余數(shù)字?jǐn)?shù)量：2
當(dāng)前要執(zhí)行：第一種操作（左→右，刪1留1）

第三步：執(zhí)行第一種刪除（左→右，刪一個(gè)留一個(gè)）

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

1. 1. 刪2，留6

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

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

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

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

第二輪

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

第三輪

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

四、你提供的代碼邏輯過程（非模擬，數(shù)學(xué)公式直接計(jì)算）

你的代碼沒有逐次模擬刪除過程，而是用數(shù)學(xué)位運(yùn)算直接計(jì)算結(jié)果，核心過程分3步：

1. 1. 定義常量mask = 0xAAAAAAAAAAAAAAA
   這個(gè)十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制是：10101010...1010（偶數(shù)位全為1，奇數(shù)位全為0）。

2. 2. 計(jì)算n-1：對(duì)輸入數(shù)字做減1處理。

3. 3. 位運(yùn)算(n-1) & mask：
   按位與操作會(huì)只保留 n-1 的二進(jìn)制偶數(shù)位，過濾掉奇數(shù)位。

4. 4. 最后 +1：得到最終結(jié)果。

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

五、時(shí)間復(fù)雜度 & 額外空間復(fù)雜度 1. 時(shí)間復(fù)雜度

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

2. 額外空間復(fù)雜度

代碼沒有創(chuàng)建數(shù)組、列表、棧等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，只定義了：

• ? 1個(gè)入?yún)?n

• ? 1個(gè)常量 mask

• ? 1個(gè)返回值變量
  所有空間都是固定大小，不隨n變化。
  ? 總額外空間復(fù)雜度：O(1)

1. 1. 交替刪除的核心是先左刪、再右刪循環(huán)，直到剩一個(gè)數(shù)；

2. 2. 你的代碼沒有模擬刪除過程，而是用位運(yùn)算數(shù)學(xué)公式直接求解；

3. 3. 時(shí)間復(fù)雜度：O(1)（常數(shù)級(jí)，極快）；

4. 4. 額外空間復(fù)雜度：O(1)（無額外內(nèi)存消耗）。

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;
}

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