前言

本題解Go語言部分基于 LeetCode-Go
其他部分基于本人實踐學習
個人題解GitHub連接：LeetCode-Go-Python-Java-C
歡迎訂閱CSDN專欄，每日一題，和博主一起進步
LeetCode專欄
我搜集到了50道精選題，適合速成概覽大部分常用算法
突破算法迷宮：精選50道-算法刷題指南

本文部分內容來自網上搜集與個人實踐。如果任何信息存在錯誤,歡迎讀者批評指正。本文僅用于學習交流,不用作任何商業(yè)用途。

50. Pow(x, n)

題目

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [?2^31, 2^31? 1]

題目大意

實現 pow(x, n) ，即計算 x 的 n 次冪函數。

解題思路

• 要求計算 Pow(x, n)
• 這一題用遞歸的方式，不斷的將 n 2 分下去。注意 n 的正負數，n 的奇偶性。
  當然，讓我們分別介紹每個版本的解題思路：

Go 版本解題思路：

1. 基本情況處理：首先，檢查特殊情況。如果 n 等于 0，直接返回 1，因為任何數的 0 次冪都等于 1。如果 n 等于 1，直接返回 x，因為任何數的 1 次冪都等于它本身。

2. 處理負指數：如果 n 是負數，將 n 變?yōu)槠浣^對值，同時將 x 變?yōu)?1/x。這是因為 x 的負指數等于 1/x 的正指數。

3. 遞歸計算：接下來，采用遞歸的方式計算 x 的 n/2 次冪，將結果存儲在 tmp 變量中。這是因為 x^n 可以拆分為 x^(n/2) * x^(n/2)。

4. 處理奇數和偶數：根據 n 的奇偶性，如果 n 是偶數，返回 tmp 的平方；如果 n 是奇數，返回 tmp 的平方再乘以 x。

Python 版本解題思路：

1. 基本情況處理：同樣，首先檢查特殊情況。如果 n 等于 0，返回 1。如果 n 等于 1，返回 x。

2. 處理負指數：如果 n 是負數，將 n 變?yōu)槠浣^對值，同時將 x 變?yōu)?1/x。

3. 遞歸計算：使用遞歸計算 x 的 n/2 次冪，將結果存儲在 tmp 變量中。

4. 處理奇數和偶數：根據 n 的奇偶性，如果 n 是偶數，返回 tmp 的平方；如果 n 是奇數，返回 tmp 的平方再乘以 x。

Java 版本解題思路：

1. 基本情況處理：同樣，首先檢查特殊情況。如果 n 等于 0，返回 1。如果 n 等于 1，返回 x。

2. 處理負指數：如果 n 是負數，將 n 變?yōu)槠浣^對值，同時將 x 變?yōu)?1/x。

3. 遞歸計算：使用遞歸計算 x 的 n/2 次冪，將結果存儲在 tmp 變量中。

4. 處理奇數和偶數：根據 n 的奇偶性，如果 n 是偶數，返回 tmp 的平方；如果 n 是奇數，返回 tmp 的平方再乘以 x。

C++ 版本解題思路：

1. 基本情況處理：同樣，首先檢查特殊情況。如果 n 等于 0，返回 1。如果 n 等于 1，返回 x。

2. 處理負指數：如果 n 是負數，將 n 變?yōu)槠浣^對值，同時將 x 變?yōu)?1/x。

3. 數據類型轉換：將 n 轉換為 long long 類型，以避免整數溢出問題。

4. 遞歸計算：使用遞歸計算 x 的 n/2 次冪，將結果存儲在 tmp 變量中。

5. 處理奇數和偶數：根據 n 的奇偶性，如果 n 是偶數，返回 tmp 的平方；如果 n 是奇數，返回 tmp 的平方再乘以 x。

這些是每個版本中用于解決 Pow(x, n) 問題的主要思路。它們都利用了遞歸來拆分問題，同時考慮了指數的正負性和奇偶性，以獲得最終的結果。

代碼

Go

// 時間復雜度 O(log n), 空間復雜度 O(1)
func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return x
    }
    if n < 0 {
        n = -n
        x = 1 / x
    }
    // 遞歸計算 x 的 n/2 次冪
    tmp := myPow(x, n/2)
    if n%2 == 0 {
        // 如果 n 為偶數，則返回 tmp 的平方
        return tmp * tmp
    }
    // 如果 n 為奇數，則返回 tmp 的平方再乘以 x
    return tmp * tmp * x
}

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n == 1:
            return x
        if n < 0:
            n = -n
            x = 1 / x
        tmp = self.myPow(x, n // 2)
        if n % 2 == 0:
            return tmp * tmp
        return tmp * tmp * x

Java

class Solution {
    public double myPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n < 0) {
            n = -n;
            x = 1 / x;
        }
        double tmp = myPow(x, n / 2);
        if (n % 2 == 0) {
            return tmp * tmp;
        }
        return tmp * tmp * x;
    }
}

Cpp

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        long long absN = n; // 將 n 轉換為 long long 類型
…};

當然，讓我們逐個版本介紹并討論所需的基礎知識：

Go 版本：

1. 基本的 Go 語言知識: 在編寫 Go 代碼之前，你需要了解 Go 語言的基本語法、數據類型、變量聲明、函數定義等基礎知識。

2. 遞歸: 這個算法使用遞歸來計算冪函數。了解遞歸的概念和如何在 Go 中編寫遞歸函數是很重要的。

3. 條件語句: 代碼中使用了條件語句（if 和 if-else）來處理不同情況，例如 n 的正負性和奇偶性。

Python 版本：

1. Python 語言基礎: 你需要了解 Python 語言的基礎知識，包括變量、函數、條件語句、遞歸等。

2. 遞歸: 和 Go 版本一樣，Python 版本也使用遞歸來計算冪函數。了解遞歸的概念和如何在 Python 中編寫遞歸函數很重要。

Java 版本：

1. Java 語言基礎: 你需要熟悉 Java 語言的基礎，包括類的定義、方法的聲明、條件語句等。

2. 遞歸: 與前兩個版本一樣，Java 版本也使用遞歸來計算冪函數。了解遞歸的概念以及如何在 Java 中編寫遞歸函數是必要的。

3. 數據類型轉換: Java 版本中對 n 進行了數據類型轉換，將 int 轉換為 long。了解數據類型轉換的概念在處理數據時非常重要。

C++ 版本：

1. C++ 語言基礎: 你需要熟悉 C++ 語言的基礎知識，包括類的定義、函數的聲明、條件語句等。

2. 遞歸: 與其他版本一樣，C++ 版本也使用遞歸來計算冪函數。了解遞歸的概念以及如何在 C++ 中編寫遞歸函數是必要的。

3. 數據類型: C++ 版本中使用了 long long 數據類型來處理 n，這是為了避免整數溢出問題。了解 C++ 的數據類型和溢出問題是重要的。

這些是每個版本中需要掌握的基礎知識要點。如果你對其中任何一個版本有更具體的問題或需要進一步的解釋，請隨時提問。

51. N-Queens

題目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-queens’ placement, where'Q'and'.'both indicate a
queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

題目大意

給定一個整數 n，返回所有不同的 n 皇后問題的解決方案。每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 ‘Q’ 和 ‘.’
分別代表了皇后和空位。

解題思路

• 求解 n 皇后問題
• 利用 col 數組記錄列信息，col 有 n 列。用 dia1，dia2 記錄從左下到右上的對角線，從左上到右下的對角線的信息，dia1 和 dia2
  分別都有 2*n-1 個。
• dia1 對角線的規(guī)律是 i + j 是定值，例如[0,0]，為 0；[1,0]、[0,1] 為 1；[2,0]、[1,1]、[0,2] 為 2；
• dia2 對角線的規(guī)律是 i - j 是定值，例如[0,7]，為 -7；[0,6]、[1,7] 為 -6；[0,5]、[1,6]、[2,7] 為 -5；為了使他們從 0 開始，i -
  j + n - 1 偏移到 0 開始，所以 dia2 的規(guī)律是 i - j + n - 1 為定值。

還有一個位運算的方法，每行只能選一個位置放皇后，那么對每行遍歷可能放皇后的位置。如何高效判斷哪些點不能放皇后呢？這里的做法畢竟巧妙，把所有之前選過的點按照順序存下來，然后根據之前選的點到當前行的距離，就可以快速判斷是不是會有沖突。舉個例子:
假如在 4 皇后問題中，如果第一二行已經選擇了位置 [1, 3]，那么在第三行選擇時，首先不能再選 1, 3 列了，而對于第三行， 1
距離長度為2，所以它會影響到 -1, 3 兩個列。同理，3 在第二行，距離第三行為 1，所以 3 會影響到列 2, 4。由上面的結果，我們知道 -1,
4 超出邊界了不用去管，別的不能選的點是 1, 2, 3，所以第三行就只能選 0。在代碼實現中，可以在每次遍歷前根據之前選擇的情況生成一個
occupied 用來記錄當前這一行，已經被選了的和由于之前皇后攻擊范圍所以不能選的位置，然后只選擇合法的位置進入到下一層遞歸。另外就是預處理了一個皇后放不同位置的字符串，這樣這些字符串在返回結果的時候是可以在內存中復用的，省一點內存。
當然，讓我們分別介紹每個版本的解題思路：

Go 版本解題思路：

1. 遞歸回溯法：Go
   版本的解決方法采用了遞歸回溯法。從第一行開始，嘗試在每一行的每一列放置皇后，然后遞歸進入下一行。如果在某一行找到一個可行的皇后位置，就繼續(xù)下一行的放置。如果找不到合適的位置，就回溯到上一行，嘗試其他列的位置，直到找到所有可能的解。

2. 布爾數組：為了確?；屎蟛粫ハ喙?，使用了布爾數組 col、dia1 和 dia2
   來跟蹤哪些列和對角線已被占用。這些數組的索引表示列號和對角線編號，值為 true 表示已被占用，值為 false 表示可用。

3. 生成棋盤：在找到一個解之后，使用 generateBoard 函數生成棋盤，將皇后位置標記為 ‘Q’，并將棋盤添加到結果中。

Python 版本解題思路：

1. 遞歸回溯法：Python 版本的解決方法也采用了遞歸回溯法，與 Go
   版本相似。從第一行開始，嘗試在每一行的每一列放置皇后，然后遞歸進入下一行。如果在某一行找到一個可行的皇后位置，就繼續(xù)下一行的放置。如果找不到合適的位置，就回溯到上一行，嘗試其他列的位置，直到找到所有可能的解。

2. 布爾列表：為了確?；屎蟛粫ハ喙?，使用了布爾列表 col、dia1 和 dia2
   來跟蹤哪些列和對角線已被占用。這些列表的索引表示列號和對角線編號，值為 True 表示已被占用，值為 False 表示可用。

3. 生成棋盤：在找到一個解之后，使用 generateBoard 函數生成棋盤，將皇后位置標記為 ‘Q’，并將棋盤添加到結果中。

Java 版本解題思路：

1. 遞歸回溯法：Java
   版本的解決方法同樣采用了遞歸回溯法。從第一行開始，嘗試在每一行的每一列放置皇后，然后遞歸進入下一行。如果在某一行找到一個可行的皇后位置，就繼續(xù)下一行的放置。如果找不到合適的位置，就回溯到上一行，嘗試其他列的位置，直到找到所有可能的解。

2. 布爾數組：為了確?；屎蟛粫ハ喙?，使用了布爾數組 col、dia1 和 dia2
   來跟蹤哪些列和對角線已被占用。這些數組的索引表示列號和對角線編號，值為 true 表示已被占用，值為 false 表示可用。

3. 生成棋盤：在找到一個解之后，使用 generateBoard 函數生成棋盤，將皇后位置標記為 ‘Q’，并將棋盤添加到結果中。

C++ 版本解題思路：

1. 遞歸回溯法：C++
   版本的解決方法也采用了遞歸回溯法，與其他版本相似。從第一行開始，嘗試在每一行的每一列放置皇后，然后遞歸進入下一行。如果在某一行找到一個可行的皇后位置，就繼續(xù)下一行的放置。如果找不到合適的位置，就回溯到上一行，嘗試其他列的位置，直到找到所有可能的解。

2. 布爾向量：為了確?；屎蟛粫ハ喙?，使用了布爾向量 col、dia1 和 dia2
   來跟蹤哪些列和對角線已被占用。這些向量的索引表示列號和對角線編號，值為 true 表示已被占用，值為 false 表示可用。

3. 生成棋盤：在找到一個解之后，使用 generateBoard 函數生成棋盤，將皇后位置標記為 ‘Q’，并將棋盤添加到結果中。

這些解題思路的核心都是使用遞歸回溯法來嘗試不同的皇后放置方式，并使用布爾數組/列表/向量來跟蹤哪些位置已被占用，以確?；屎蟛换ハ喙?。同時，使用字符串處理來生成和表示棋盤。

代碼

Go

// 解法一 DFS
func solveNQueens(n int) [][]string {
    col, dia1, dia2, row, res := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1), []int{}, [][]string{}
    putQueen(n, 0, &col, &dia1, &dia2, &row, &res) // 調用putQueen函數來找到解
    return res
}

// 嘗試在一個n皇后問題中, 擺放第index行的皇后位置
func putQueen(n, index int, col, dia1, dia2 *[]bool, row *[]int, res *[][]string) {
    if index == n { // 所有皇后都已經成功擺放，得到一個解
        *res = append(*res, generateBoard(n, row)) // 生成棋盤并添加到結果集中
        return
    }
    for i := 0; i < n; i++ {
        // 嘗試將第index行的皇后擺放在第i列
        if !(*col)[i] && !(*dia1)[index+i] && !(*dia2)[index-i+n-1] {
            *row = append(*row, i)          // 在當前行的row中記錄皇后位置
            (*col)[i] = true                // 在列col中標記為占用
            (*dia1)[index+i] = true         // 在對角線dia1中標記為占用
            (*dia2)[index-i+n-1] = true     // 在對角線dia2中標記為占用
            putQueen(n, index+1, col, dia1, dia2, row, res) // 遞歸下一行
            (*col)[i] = false               // 回溯：取消占用
            (*dia1)[index+i] = false        // 回溯：取消占用
            (*dia2)[index-i+n-1] = false    // 回溯：取消占用
            *row = (*row)[:len(*row)-1]    // 回溯：移除上一行的皇后位置
        }
    }
    return
}

// 生成一個N皇后問題的棋盤
func generateBoard(n int, row *[]int) []string {
    board := []string{}
    res := ""
    for i := 0; i < n; i++ {
        res += "."
    }
    for i := 0; i < n; i++ {
        board = append(board, res) // 初始化棋盤為全"."
    }
    for i := 0; i < n; i++ {
        tmp := []byte(board[i])    // 將當前行轉換為字節(jié)切片以修改皇后位置
        tmp[(*row)[i]] = 'Q'        // 在皇后位置處添加"Q"表示皇后
        board[i] = string(tmp)
    }
    return board // 返回表示棋盤的字符串切片
}

Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        col = [False] * n
        dia1 = [False] * (2 * n - 1)
        dia2 = [False] * (2 * n - 1)
        row = [0] * n
        self.putQueen(n, 0, col, dia1, dia2, row, result)
        return result

    def putQueen(self, n, index, col, dia1, dia2, row, result):
        if index == n:
            result.append(self.generateBoard(n, row))
            return
        for i in range(n):
            if not col[i] and not dia1[index + i] and not dia2[index - i + n - 1]:
                row[index] = i
                col[i] = True
                dia1[index + i] = True
                dia2[index - i + n - 1] = True
                self.putQueen(n, index + 1, col, dia1, dia2, row, result)
                col[i] = False
                dia1[index + i] = False
                dia2[index - i + n - 1] = False

    def generateBoard(self, n, row):
        board = []
        for i in range(n):
            row_str = ['.' for _ in range(n)]
            row_str[row[i]] = 'Q'
            board.append(''.join(row_str))
        return board

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] col = new boolean[n];
        boolean[] dia1 = new boolean[2 * n - 1];
        boolean[] dia2 = new boolean[2 * n - 1];
        int[] row = new int[n];
        putQueen(n, 0, col, dia1, dia2, row, result);
        return result;
    }

    private void putQueen(int n, int index, boolean[] col, boolean[] dia1, boolean[] dia2, int[] row, List<List<String>> result) {
        if (index == n) {
            result.add(generateBoard(n, row));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                row[index] = i;
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n, index + 1, col, dia1, dia2, row, result);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
            }
        }
    }

    private List<String> generateBoard(int n, int[] row) {
        List<String> board = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append('.');
        }
        for (int i = 0; i < n; i++) {
            char[] chars = sb.toString().toCharArray();
            chars[row[i]] = 'Q';
            board.add(new String(chars));
        }
        return board;
    }
}

Cpp

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<bool> col(n, false);
        vector<bool> dia1(2 * n - 1, false);
        vector<bool> dia2(2 * n - 1, false);
        vector<int> row(n, 0);
        putQueen(n, 0, col, dia1, dia2, row, result);
        return result;
    }

    void putQueen(int n, int index, vector<bool>& col, vector<bool>& dia1, vector<bool>& dia2, vector<int>& row, vector<vector<string>>& result) {
        if (index == n) {
            result.push_back(generateBoard(n, row));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                row[index] = i;
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n, index + 1, col, dia1, dia2, row, result);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
            }
        }
    }

    vector<string> generateBoard(int n, vector<int>& row) {
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; i++) {
            board[i][row[i]] = 'Q';
        }
        return board;
    }
};

當然，讓我們分別介紹每個版本的代碼中所需要的基礎知識：

Go 版本：

1. 切片 (Slices)：Go 使用切片來處理動態(tài)數組。在代碼中，使用 []string 表示一個字符串切片，用于存儲每個皇后的位置。

2. 遞歸 (Recursion)：解決 N-Queens 問題的關鍵是遞歸。代碼中使用遞歸來嘗試在每一行中放置皇后，同時進行回溯，以尋找所有可能的解。

3. 布爾數組 (Boolean Arrays)：使用布爾數組來跟蹤哪些列和對角線已被占用，以確保皇后不互相攻擊。

Python 版本：

1. 列表 (Lists)：Python 使用列表來處理動態(tài)數組，類似于 Go 中的切片。在代碼中，使用 List[List[str]]
   表示一個字符串列表的列表，用于存儲棋盤的不同解。

2. 遞歸 (Recursion)：與 Go 版本類似，Python 版本也使用遞歸來嘗試在每一行中放置皇后，并進行回溯。

3. 布爾列表 (Boolean Lists)：Python 使用布爾列表來跟蹤哪些列和對角線已被占用，以確?；屎蟛换ハ喙簟?/p>

4. 列表推導式 (List Comprehension)：在生成棋盤時，使用列表推導式將字符串列表轉換為包含皇后位置的字符串。

Java 版本：

1. ArrayList：Java 中使用 ArrayList 來處理動態(tài)數組，類似于 Go 的切片和 Python
   的列表。在代碼中，使用 List<List<String>> 表示一個字符串列表的列表。

2. 遞歸 (Recursion)：與 Go 和 Python 版本類似，Java 版本也使用遞歸來嘗試在每一行中放置皇后，并進行回溯。

3. 布爾數組 (Boolean Arrays)：Java 使用布爾數組來跟蹤哪些列和對角線已被占用，以確保皇后不互相攻擊。

4. 字符串處理：Java 使用 StringBuilder 來處理字符串的可變性，以便在棋盤上放置皇后。

C++ 版本：

1. 向量 (Vectors)：C++ 使用向量來處理動態(tài)數組，類似于 Go 的切片、Python 的列表和 Java 的
   ArrayList。在代碼中，使用 vector<vector<string>> 表示一個字符串向量的向量。

2. 遞歸 (Recursion)：與其他版本類似，C++ 版本也使用遞歸來嘗試在每一行中放置皇后，并進行回溯。

3. 布爾向量 (Boolean Vectors)：C++ 使用布爾向量來跟蹤哪些列和對角線已被占用，以確?；屎蟛换ハ喙簟?/p>

4. 字符串處理：C++ 使用字符串向量和字符數組來表示和處理棋盤，將皇后位置添加到合適的位置。

這些基礎知識包括切片、列表、遞歸、布爾數組/列表、字符串處理等，是理解和編寫解決 N-Queens
問題的關鍵要素。如果您對其中的任何概念有更具體的疑問，或者需要更深入的解釋，請隨時提出。

52. N-Queens II

題目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

題目大意

給定一個整數 n，返回 n 皇后不同的解決方案的數量。

解題思路

• 這一題是第 51 題的加強版，在第 51 題的基礎上累加記錄解的個數即可。
• 這一題也可以暴力打表法，時間復雜度為 O(1)。

當然，讓我們分別介紹每個版本的解題思路：

Go 版本的解題思路

Go 版本的解決方案采用深度優(yōu)先搜索（DFS）和回溯法來解決 N 皇后問題。下面是解題思路的關鍵步驟：

1. 創(chuàng)建并初始化用于記錄列、兩個對角線是否被占用的布爾數組，以及記錄每行皇后位置的整數切片，還有結果的變量。

2. 從第一行開始，遞歸嘗試在每一行放置皇后，直到達到最后一行。每次放置皇后時，需要檢查當前列、兩個對角線是否被占用。

3. 如果某一行可以放置皇后，將皇后位置記錄在整數切片中，并更新列、對角線的占用情況。

4. 繼續(xù)遞歸到下一行，重復相同的過程。

5. 當放置完成所有行時，計數結果加1，表示找到了一種解法。

6. 回溯到上一行，撤銷當前行的皇后放置，繼續(xù)嘗試下一列。

7. 重復上述步驟，直到找到所有解法。

Python 版本的解題思路

Python 版本的解決方案也采用深度優(yōu)先搜索（DFS）和回溯法來解決 N 皇后問題。解題思路與 Go 版本基本相同：

1. 創(chuàng)建并初始化用于記錄列、兩個對角線是否被占用的布爾數組，以及記錄每行皇后位置的整數切片。

2. 從第一行開始，遞歸嘗試在每一行放置皇后，直到達到最后一行。每次放置皇后時，需要檢查當前列、兩個對角線是否被占用。

3. 如果某一行可以放置皇后，將皇后位置記錄在整數切片中，并更新列、對角線的占用情況。

4. 繼續(xù)遞歸到下一行，重復相同的過程。

5. 當放置完成所有行時，計數結果加1，表示找到了一種解法。

6. 回溯到上一行，撤銷當前行的皇后放置，繼續(xù)嘗試下一列。

7. 重復上述步驟，直到找到所有解法。

Java 版本的解題思路

Java 版本的解決方案同樣采用深度優(yōu)先搜索（DFS）和回溯法來解決 N 皇后問題。解題思路如下：

1. 創(chuàng)建并初始化用于記錄列、兩個對角線是否被占用的布爾數組，以及記錄每行皇后位置的整數數組。

2. 從第一行開始，遞歸嘗試在每一行放置皇后，直到達到最后一行。每次放置皇后時，需要檢查當前列、兩個對角線是否被占用。

3. 如果某一行可以放置皇后，將皇后位置記錄在整數數組中，并更新列、對角線的占用情況。

4. 繼續(xù)遞歸到下一行，重復相同的過程。

5. 當放置完成所有行時，計數結果加1，表示找到了一種解法。

6. 回溯到上一行，撤銷當前行的皇后放置，繼續(xù)嘗試下一列。

7. 重復上述步驟，直到找到所有解法。

C++ 版本的解題思路

C++ 版本的解決方案也使用深度優(yōu)先搜索（DFS）和回溯法來解決 N 皇后問題。以下是解題思路的關鍵步驟：

1. 使用位運算來高效地記錄列、兩個對角線是否被占用。其中，列使用一個整數表示，每一位表示一列是否被占用；兩個對角線也分別使用整數來表示。

2. 從第一行開始，遞歸嘗試在每一行放置皇后，直到達到最后一行。在每一行，通過位運算來檢查當前列、兩個對角線是否被占用。

3. 如果某一行可以放置皇后，使用位運算將皇后位置標記為被占用，并繼續(xù)遞歸到下一行。

4. 當放置完成所有行時，計數結果加1，表示找到了一種解法。

5. 回溯到上一行，撤銷當前行的皇后放置，繼續(xù)嘗試下一列。

6. 重復上述步驟，直到找到所有解法。

總的來說，這些版本的解題思路都涉及深度優(yōu)先搜索和回溯，同時使用不同的數據結構和語言特性來實現相同的算法。理解遞歸、回溯以及位運算對于理解這些解決方案非常重要。

代碼

Go

// 解法二，DFS 回溯法
func totalNQueens(n int) int {
    // 創(chuàng)建并初始化用于記錄列、兩個對角線是否被占用的布爾數組，
    // 以及記錄每行皇后位置的數組，以及結果的變量
    col, dia1, dia2, row, res := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1), []int{}, 0
    // 調用遞歸函數放置皇后并計算結果
    putQueen52(n, 0, &col, &dia1, &dia2, &row, &res)
    // 返回結果
    return res
}

// 嘗試在一個n皇后問題中, 擺放第index行的皇后位置
func putQueen52(n, index int, col, dia1, dia2 *[]bool, row *[]int, res *int) {
    // 當擺放完成所有行時，計數結果加1
    if index == n {
        *res++
        return
    }

    // 遍歷當前行的每一列，嘗試放置皇后
    for i := 0; i < n; i++ {
        // 檢查當前列、兩個對角線是否被占用
        if !(*col)[i] && !(*dia1)[index+i] && !(*dia2)[index-i+n-1] {
            // 如果沒有被占用，將皇后放置在當前位置
            (*row) = append((*row), i)
            (*col)[i] = true
            (*dia1)[index+i] = true
            (*dia2)[index-i+n-1] = true
            // 遞歸放置下一行的皇后
            putQueen52(n, index+1, col, dia1, dia2, row, res)
            // 回溯，撤銷當前行的皇后放置，繼續(xù)嘗試下一列
            (*col)[i] = false
            (*dia1)[index+i] = false
            (*dia2)[index-i+n-1] = false
            (*row) = (*row)[:len(*row)-1]
        }
    }
    return
}

Python

class Solution:
    def totalNQueens(self, n: int) -> int:
        # 計算可以放置皇后的列的位掩碼，limit 為一個 n 位的二進制數，所有位都為 1
        limit = (1 << n) - 1
        # 調用 process 函數，初始時傳入全0的狀態(tài)，表示沒有皇后被放置
        return self.process(limit, 0, 0, 0)

    def process(self, limit, colLim, leftDiaLim, rightDiaLim):
        # 如果所有列都已經放置了皇后，表示找到了一種解法，返回 1
        if colLim == limit:
            return 1

        mostRight = 0
        # 計算當前行可以放置皇后的位置，pos 為一個二進制數，1 表示可以放置皇后的位置
        pos = limit & (~(colLim | leftDiaLim | rightDiaLim))
        res = 0
        while pos != 0:
            # 取出最右邊的 1，表示在該位置放置皇后
            mostRight = pos & (~pos + 1)
            pos = pos - mostRight
            # 遞歸調用 process 函數，放置下一行的皇后，并累加解的數量
            res += self.process(limit, colLim | mostRight, (leftDiaLim | mostRight) << 1, (rightDiaLim | mostRight) >> 1)
        # 返回總解的數量
        return res

Java

class Solution {
    public int totalNQueens(int n) {
        boolean[] col = new boolean[n];
        boolean[] dia1 = new boolean[2 * n - 1];
        boolean[] dia2 = new boolean[2 * n - 1];
        int[] row = new int[n];
        int[] res = new int[1];
        putQueen(n, 0, col, dia1, dia2, row, res);
        return res[0];
    }

    private void putQueen(int n, int index, boolean[] col, boolean[] dia1, boolean[] dia2, int[] row, int[] res) {
        if (index == n) {
            res[0]++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                row[index] = i;
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;
                putQueen(n, index + 1, col, dia1, dia2, row, res);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
            }
        }
    }
}

Cpp

class Solution {
public:
    int totalNQueens(int n) {
        // 調用 solve 函數，初始時傳入全0的狀態(tài)，表示沒有皇后被放置
        return solve(n, 0, 0, 0, 0);
    }

    int solve(int n, int row, int columns, int diagonals1, int diagonals2) {
        // 如果已經放置了 n 個皇后，表示找到了一種解法，返回 1
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            // 計算當前行可用的位置，通過位運算得到一個二進制數，1 表示可以放置皇后的位置
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            
            // 遍歷所有可用的位置
            while (availablePositions != 0) {
                // 取出最低位的 1，表示在該位置放置皇后
                int position = availablePositions & (-availablePositions);
                // 將該位置從可用位置中移除
                availablePositions = availablePositions & (availablePositions - 1);
                // 遞歸調用 solve 函數，放置下一行的皇后，并累加解的數量
                count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
            }
            // 返回總解的數量
            return count;
        }
    }
};

當然，讓我們分別介紹每個版本的代碼以及它們所需的基礎知識：

Go 版本

Go 版本的代碼是一個使用深度優(yōu)先搜索（DFS）和回溯法的解決方案，用于解決 N 皇后問題。以下是代碼中涉及的基礎知識：

1. 數組和切片：Go 中的數組和切片是重要的數據結構，用于存儲和處理數據。在這個問題中，使用了多個布爾數組來跟蹤已占用的列和對角線，以及一個整數切片來記錄每行的皇后位置。

2. 遞歸和回溯：該解決方案使用遞歸來嘗試放置皇后，并通過回溯來撤銷不可行的解決方案。遞歸是解決 N 皇后問題的關鍵。

3. 位運算：位運算用于快速檢查列、對角線是否被占用，以及在哪里放置皇后。這是該算法的關鍵部分。

Python 版本

Python 版本的代碼也是一個使用深度優(yōu)先搜索（DFS）和回溯法的解決方案。以下是代碼中涉及的基礎知識：

1. 遞歸和回溯：和 Go 版本一樣，Python 版本也使用遞歸來嘗試放置皇后，并通過回溯來撤銷不可行的解決方案。遞歸是解決 N 皇后問題的關鍵。

2. 位運算：位運算用于快速檢查列、對角線是否被占用，以及在哪里放置皇后。這是該算法的關鍵部分。

Java 版本

Java 版本的代碼也是一個使用深度優(yōu)先搜索（DFS）和回溯法的解決方案。以下是代碼中涉及的基礎知識：

1. 數組和列表：Java 中的數組和列表（ArrayList）用于存儲和處理數據。在這個問題中，使用了多個布爾數組來跟蹤已占用的列和對角線，以及一個整數數組來記錄每行的皇后位置。

2. 遞歸和回溯：該解決方案使用遞歸來嘗試放置皇后，并通過回溯來撤銷不可行的解決方案。遞歸是解決 N 皇后問題的關鍵。

C++ 版本

C++ 版本的代碼也是一個使用深度優(yōu)先搜索（DFS）和回溯法的解決方案。以下是代碼中涉及的基礎知識：

1. 位運算：C++ 版本中使用了位運算來快速檢查列、對角線是否被占用，以及在哪里放置皇后。這是該算法的關鍵部分。

2. 遞歸和回溯：該解決方案使用遞歸來嘗試放置皇后，并通過回溯來撤銷不可行的解決方案。遞歸是解決 N 皇后問題的關鍵。

總的來說，無論使用哪種編程語言，解決 N 皇后問題的關鍵概念包括遞歸、回溯和位運算。理解這些概念將有助于理解和實現這些代碼。

53. Maximum Subarray

題目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

題目大意

給定一個整數數組 nums ，找到一個具有最大和的連續(xù)子數組（子數組最少包含一個元素），返回其最大和。

解題思路

• 這一題可以用 DP 求解也可以不用 DP。
• 題目要求輸出數組中某個區(qū)間內數字之和最大的那個值。dp[i] 表示 [0,i] 區(qū)間內各個子區(qū)間和的最大值，狀態(tài)轉移方程是 dp[i] = nums[i] + dp[i-1] (dp[i-1] > 0)，dp[i] = nums[i] (dp[i-1] ≤ 0)。
  Go版本:

1. 定義maxSubArray函數,參數為nums切片。
2. 定義tmp和m變量,分別表示當前子數組之和和最大子數組之和。m初始化為nums[0]。
3. 遍歷nums,用tmp累加當前元素。
4. 比較m和tmp,通過max函數取較大值賦給m。
5. 如果tmp<0,通過max函數將tmp賦為0。
6. 循環(huán)結束后返回m。

Python版本:

1. 定義maxSubArray函數,參數為nums列表。
2. 定義tmp和m變量,分別表示當前子數組之和和最大子數組之和。m初始化為nums[0]。
3. 遍歷nums,用tmp累加當前元素。
4. 比較m和tmp,通過內置max函數取較大值賦給m。
5. 如果tmp<0,通過max函數將tmp賦為0。
6. 循環(huán)結束后返回m。

Java版本:

1. 定義maxSubArray方法,參數為nums數組。
2. 定義tmp和m變量,分別表示當前子數組之和和最大子數組之和。m初始化為nums[0]。
3. 遍歷nums,用tmp累加當前元素。
4. 比較m和tmp,通過Math.max取較大值賦給m。
5. 如果tmp<0,通過Math.max將tmp賦為0。
6. 循環(huán)結束后返回m。

C++版本:

1. 定義maxSubArray方法,參數為nums向量。
2. 定義tmp和m變量,分別表示當前子數組之和和最大子數組之和。m初始化為nums[0]。
3. 遍歷nums,用tmp累加當前元素。
4. 比較m和tmp,通過max方法取較大值賦給m。
5. 如果tmp<0,通過max方法將tmp賦為0。
6. 循環(huán)結束后返回m。

核心思路都是一樣的,主要區(qū)別在語法細節(jié)上,利用本地語言特性進行優(yōu)化。

代碼

Go

// 定義一個名為 maxSubArray 的函數，接受一個整數數組 nums 作為參數，返回最大子數組和。
func maxSubArray(nums []int) int {
    // 如果數組為空，直接返回 0。
    if len(nums) == 0 {
        return 0
    }
    // 初始化一個臨時變量 tmp 和最大子數組和 m，初始值為數組的第一個元素。
    var tmp = 0
    var m = nums[0]
    // 遍歷整個數組。
    for i := 0; i < len(nums); i++ {
        // 更新臨時變量 tmp，將當前元素加入其中。
        tmp += nums[i]
        // 更新最大子數組和 m，取當前的 m 和 tmp 的較大值。
        m = max(m, tmp)
        // 如果 tmp 小于 0，將 tmp 重置為 0，因為負數不會對最大子數組和產生正面影響。
        tmp = max(tmp, 0)
    }
    // 返回最大子數組和 m。
    return m
}

// 定義一個名為 max 的輔助函數，接受兩個整數參數 a 和 b，返回較大的整數。
func max(a, b int) int {
    // 如果 a 大于 b，返回 a，否則返回 b。
    if a > b {
        return a
    }
    return b
}

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 如果數組為空，直接返回0。
        if not nums:
            return 0
        # 初始化一個臨時變量 tmp 和最大子數組和 m，初始值為數組的第一個元素。
        tmp = 0
        m = nums[0]
        # 遍歷整個數組。
        for num in nums:
            # 更新臨時變量 tmp，將當前元素加入其中。
            tmp += num
            # 更新最大子數組和 m，取當前的 m 和 tmp 的較大值。
            m = max(m, tmp)
            # 如果 tmp 小于 0，將 tmp 重置為 0，因為負數不會對最大子數組和產生正面影響。
            tmp = max(tmp, 0)
        # 返回最大子數組和 m。
        return m

Java

class Solution {
    public int maxSubArray(int[] nums) {
        // 如果數組為空，直接返回0。
        if (nums.length == 0) {
            return 0;
        }
        // 初始化一個臨時變量 tmp 和最大子數組和 m，初始值為數組的第一個元素。
        int tmp = 0;
        int m = nums[0];
        // 遍歷整個數組。
        for (int i = 0; i < nums.length; i++) {
            // 更新臨時變量 tmp，將當前元素加入其中。
            tmp += nums[i];
            // 更新最大子數組和 m，取當前的 m 和 tmp 的較大值。
            m = Math.max(m, tmp);
            // 如果 tmp 小于 0，將 tmp 重置為 0，因為負數不會對最大子數組和產生正面影響。
            tmp = Math.max(tmp, 0);
        }
        // 返回最大子數組和 m。
        return m;
    }
}

Cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 如果數組為空，直接返回0。
        if (nums.empty()) {
            return 0;
        }
        // 初始化一個臨時變量 tmp 和最大子數組和 m，初始值為數組的第一個元素。
        int tmp = 0;
        int m = nums[0];
        // 遍歷整個數組。
        for (int num : nums) {
            // 更新臨時變量 tmp，將當前元素加入其中。
            tmp += num;
            // 更新最大子數組和 m，取當前的 m 和 tmp 的較大值。
            m = max(m, tmp);
            // 如果 tmp 小于 0，將 tmp 重置為 0，因為負數不會對最大子數組和產生正面影響。
            tmp = max(tmp, 0);
        }
        // 返回最大子數組和 m。
        return m;
    }
};

基礎知識

對于Go版本:

• 函數定義:Go語言中使用func關鍵字定義函數,括號內參數列表,大括號內函數體。
• 返回值:Go函數可以只返回一個值,使用return語句。
• 切片操作:nums []int定義一個int切片,len(nums)獲取切片長度,nums[i]訪問切片元素。
• if條件判斷:if a > b {} else {}。
• for循環(huán):for i := 0; i < len(nums); i++ {}。
• 變量定義:var tmp int 定義臨時變量。
• 取最大值:調用max函數比較a,b大小返回較大值。

對于Python版本:

• 函數定義:使用def定義函數,參數列表中的self代表類內方法。
• 返回值:使用 return 語句返回值。
• 列表操作:nums作為列表參數,len(nums)獲取長度,num遍歷列表元素。
• if條件判斷:if not nums: 判斷空列表。
• 取最大值:調用內置max函數比較兩個值。

對于Java版本:

• 方法定義:public類型說明方法訪問權限,int返回值類型。
• 數組操作:nums.length獲取數組長度,nums[i]訪問元素。
• if條件判斷:if(nums.length == 0)。
• for循環(huán):for(初始化;條件;迭代)。
• 取最大值:Math.max(a, b)調用工具類方法。

對于C++版本:

• 方法定義:class內定義,int返回類型。
• 向量操作:nums作為向量參數,empty()判斷空,num遍歷。
• if條件判斷:if(nums.empty())。
• for循環(huán):for(元素類型 元素:容器)。
• 取最大值:調用max方法比較兩個值。
  主要就是函數/方法定義,基礎數據結構的操作,流程控制語言(if/for)的使用,數值比較取最大值。掌握了這些基礎語法,就可以編寫出算法代碼。

54. Spiral Matrix

題目

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

題目大意

給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，返回矩陣中的所有元素。

解題思路

• 給出一個二維數組，按照螺旋的方式輸出
• 解法一：需要注意的是特殊情況，比如二維數組退化成一維或者一列或者一個元素。注意了這些情況，基本就可以一次通過了。
• 解法二：提前算出一共多少個元素，一圈一圈地遍歷矩陣，停止條件就是遍歷了所有元素（count == sum）
  Go版本:

1. 定義方向向量數組spDir,表示向右、下、左、上的方向
2. 使用visit矩陣標記已訪問位置
3. 根據round變量判斷方向,初始化為向右
4. 遍歷矩陣,每次根據方向向量更新坐標
5. 判斷是否到達轉角,是則round自增變換方向
6. 判斷坐標是否出界
7. 判斷該位置是否已訪問,未訪問則標記并添加到結果
8. 根據當前方向判斷周圍是否訪問過,是則改變方向

Python版本:

1. 定義左右上下邊界,表示當前遍歷的范圍
2. 通過不斷改變邊界坐標實現螺旋遍歷
3. 從左到右遍歷上邊界,然后上邊界下移
4. 從上到下遍歷右邊界,然后右邊界左移
5. 判斷邊界是否相遇,相遇則結束
6. 從右到左遍歷下邊界,然后下邊界上移
7. 從下到上遍歷左邊界,然后左邊界右移

Java版本:

1. 定義dr、dc數組表示四個方向
2. 使用visited數組標記已訪問位置
3. di變量控制方向,每次遍歷后自增改變方向
4. 根據方向數組計算下一個遍歷位置
5. 如果下個位置合法且未訪問過,則移動坐標
6. 否則改變di繼續(xù)遍歷

C++版本:

1. 定義方向數組dr、dc
2. 使用visited向量標記已訪問位置
3. di變量控制方向,轉角時自增di改變方向
4. 根據dr、dc計算下個遍歷位置
5. 如果合法且未訪問,移動坐標
6. 否則改變方向繼續(xù)遍歷

代碼

Go

// 定義一個螺旋遍歷二維矩陣的函數
func spiralOrder(matrix [][]int) []int {
    // 如果矩陣為空,直接返回空切片
    if len(matrix) == 0 { 
       return []int{}
    }
    // 定義一個結果切片
    res := []int{}
    // 如果矩陣只有一行,直接遍歷添加到結果切片
    if len(matrix) == 1 {
       for i := 0; i < len(matrix[0]); i++ {
          res = append(res, matrix[0][i])
       }
       return res
    }
    // 如果矩陣只有一列,直接遍歷添加到結果切片   
    if len(matrix[0]) == 1 {
       for i := 0; i < len(matrix); i++ {
          res = append(res, matrix[i][0])
       }
       return res
    }
    // 定義一個訪問矩陣,標記已訪問過的元素
    visit, m, n, round, x, y, spDir := make([][]int, len(matrix)), len(matrix), len(matrix[0]), 0, 0, 0, [][]int{
       []int{0, 1},  // 向右的方向向量
       []int{1, 0},  // 向下的方向向量
       []int{0, -1}, // 向左的方向向量
       []int{-1, 0}, // 向上的方向向量
    }
    // 初始化訪問矩陣
    for i := 0; i < m; i++ {
       visit[i] = make([]int, n)
    }
    // 標記當前位置為已訪問
    visit[x][y] = 1
    // 將當前位置元素添加到結果切片
    res = append(res, matrix[x][y])
    // 開始遍歷矩陣
    for i := 0; i < m*n; i++ {
       // 根據當前方向向量更新x、y坐標 
       x += spDir[round%4][0] 
       y += spDir[round%4][1]
       // 如果遍歷到轉角,改變方向
       if (x == 0 && y == n-1) || (x == m-1 && y == n-1) || (y == 0 && x == m-1) {
          round++
       }
       // 檢查坐標是否出界
       if x > m-1 || y > n-1 || x < 0 || y < 0 {
          return res
       }
       // 如果當前位置未訪問過
       if visit[x][y] == 0 {
          // 標記為已訪問
          visit[x][y] = 1
          // 添加到結果切片 
          res = append(res, matrix[x][y])
       }
       // 根據當前方向判斷是否需要改變方向
       switch round % 4 {
       case 0: // 向右
          if y+1 <= n-1 && visit[x][y+1] == 1 { // 右側已訪問過
             round++ // 改變方向
             continue
          }
       case 1: // 向下
          if x+1 <= m-1 && visit[x+1][y] == 1 { // 下方已訪問過
             round++
             continue
          } 
       case 2: // 向左
          if y-1 >= 0 && visit[x][y-1] == 1 { // 左側已訪問過
             round++
             continue
          }
       case 3: // 向上
          if x-1 >= 0 && visit[x-1][y] == 1 { // 上方已訪問過
             round++
             continue
          }
       }
    }
    // 返回結果切片
    return res
}

Python

python
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 定義左、上邊界
        left, top = 0, 0 
        # 定義右、下邊界  
        bottom, right = len(matrix), len(matrix[0])

        # 結果列表
        ans = []

        # 當左右邊界未相遇,上下邊界未相遇時
        while left < right and top < bottom:
            
            # 從左到右遍歷上邊界  
            for i in range(left, right):
                ans.append(matrix[top][i])
            # 上邊界下移
            top += 1

            # 從上到下遍歷右邊界
            for i in range(top, bottom):
                ans.append(matrix[i][right - 1])
            # 右邊界左移
            right -= 1

            # 如果邊界相遇,結束循環(huán)
            if left >= right or top >= bottom:
                break

            # 從右到左遍歷下邊界
            for i in range(right - 1, left - 1, -1):
                ans.append(matrix[bottom - 1][i])
            # 下邊界上移
            bottom -= 1

            # 從下到上遍歷左邊界
            for i in range(bottom - 1, top - 1, -1):
                ans.append(matrix[i][left])
            # 左邊界右移
            left += 1

        return ans

Java

import java.util.ArrayList; 
import java.util.List;

class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    
    List<Integer> res = new ArrayList<>();
    
    if(matrix.length == 0) return res;
    
    int m = matrix.length;
    int n = matrix[0].length;
    
    boolean[][] visited = new boolean[m][n];
    
    int[] dr = {0, 1, 0, -1}; // 右、下、左、上 
    int[] dc = {1, 0, -1, 0};
    
    int r = 0, c = 0, di = 0;
    
    for(int i = 0; i < m * n; i++) {
      
      res.add(matrix[r][c]);
      visited[r][c] = true;
      
      int cr = r + dr[di];
      int cc = c + dc[di];
      
      if(0 <= cr && cr < m && 0 <= cc && cc < n && !visited[cr][cc]) {
        r = cr;
        c = cc; 
      }
      else {
        di = (di + 1) % 4; // 改變方向
        r += dr[di]; 
        c += dc[di];
      }
    }
    
    return res;

  }
}

Cpp

#include <vector>

using namespace std;

class Solution {
public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {

    vector<int> res;
    if (matrix.empty()) return res;

    int m = matrix.size(), n = matrix[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n));

    int dr[4] = {0, 1, 0, -1}; // 右、下、左、上
    int dc[4] = {1, 0, -1, 0};  

    int r = 0, c = 0, di = 0;

    for (int i = 0; i < m * n; i++) {

      res.push_back(matrix[r][c]);
      visited[r][c] = true;

      int cr = r + dr[di], cc = c + dc[di];

      if (0 <= cr && cr < m && 0 <= cc && cc < n && !visited[cr][cc]) {
        r = cr; c = cc;
      }  
      else {
        di = (di + 1) % 4; // 改變方向
        r += dr[di]; c += dc[di]; 
      }
    }

    return res;

  }
};

基礎知識

1. Go版本

• 使用方向向量控制遍歷順序,根據round變量控制方向
• 使用visit矩陣記錄已訪問位置,避免重復訪問
• 注意處理邊界條件,如矩陣只有一行或一列的情況

2. Python版本

• 使用左右上下邊界控制遍歷范圍
• 通過改變邊界坐標實現螺旋遍歷
• 注意處理邊界相遇的情況

3. Java版本

• 使用方向數組dr、dc控制遍歷方向
• visited數組記錄已訪問位置
• 改變di控制方向,轉角時di自增實現方向改變

4. C++版本

• 與Java版本類似,使用方向數組dr、dc
• visited向量記錄已訪問位置
• 改變di改變方向,轉角時自增di

綜合來說,螺旋遍歷矩陣需要注意邊界處理,并通過控制方向實現螺旋遍歷順序。記錄已訪問位置很重要,避免重復訪問。

55. Jump Game

題目

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

題目大意

給定一個非負整數數組，最初位于數組的第一個位置。數組中的每個元素代表在該位置可以跳躍的最大長度。判斷是否能夠到達最后一個位置。

解題思路

• 給出一個非負數組，要求判斷從數組 0 下標開始，能否到達數組最后一個位置。
• 這一題比較簡單。如果某一個作為 起跳點 的格子可以跳躍的距離是 n，那么表示后面 n 個格子都可以作為 起跳點?？梢詫γ恳粋€能作為 起跳點 的格子都嘗試跳一次，把 能跳到最遠的距離maxJump 不斷更新。如果可以一直跳到最后，就成功了。如果中間有一個點比 maxJump 還要大，說明在這個點和 maxJump 中間連不上了，有些點不能到達最后一個位置。
  當然，我來分別介紹每個版本的解題思路：

Go 版本解題思路：

• 題目要求判斷是否能夠從第一個位置跳躍到最后一個位置。
• 使用一個變量 maxj 來表示當前能夠跳到的最遠位置，初始值為0。
• 遍歷數組中的每個元素，對于每個元素，檢查是否能夠跳到當前位置（i > maxj 表示無法跳到當前位置，返回false），然后更新 maxj 為當前位置和當前位置能跳躍的最大距離之間的較大值。
• 如果成功遍歷完整個數組，說明可以跳到最后一個位置，返回true。

Python 版本解題思路：

• 同樣，題目要求判斷是否能夠從第一個位置跳躍到最后一個位置。
• 使用變量 max_i 來表示當前能夠跳到的最遠位置，初始值為0。
• 使用 enumerate 函數遍歷列表，i 表示當前位置，jump 表示當前位置的跳數。
• 如果 max_i 大于等于 i 并且 i + jump 大于 max_i，則更新 max_i 為 i + jump。
• 最后，判斷 max_i 是否大于等于最后一個位置 i，如果是，則返回True，否則返回False。

Java 版本解題思路：

• 題目要求判斷是否能夠從第一個位置跳躍到最后一個位置。
• 使用變量 max_i 來表示當前能夠跳到的最遠位置，初始值為0。
• 使用 for 循環(huán)遍歷數組，i 表示當前位置。
• 如果 max_i 大于等于 i 并且 i + nums[i] 大于 max_i，則更新 max_i 為 i + nums[i]。
• 最后，判斷 max_i 是否大于等于數組的最后一個位置，如果是，則返回True，否則返回False。

C++ 版本解題思路：

• 同樣，題目要求判斷是否能夠從第一個位置跳躍到最后一個位置。
• 使用變量 max_i 來表示當前能夠跳到的最遠位置，初始值為0。
• 使用 for 循環(huán)遍歷向量，i 表示當前位置。
• 如果 max_i 大于等于 i 并且 i + nums[i] 大于 max_i，則更新 max_i 為 i + nums[i]。
• 最后，判斷 max_i 是否大于等于向量的最后一個位置，如果是，則返回True，否則返回False。

這些解題思路都是基于貪心算法的思想，即不斷更新能夠跳到的最遠位置，最終判斷是否能夠跳到最后一個位置。希望這些解題思路能夠幫助您理解每個版本的解決方案。如果您有更多問題，請隨時提出。

代碼

func canJump(nums []int) bool {
  maxj := 0 // 初始化一個變量 maxj，表示當前能夠跳到的最遠的位置
  for i := 0; i < len(nums); i++ { // 遍歷數組中的每個元素
    if i > maxj { // 如果當前索引 i 大于 maxj，說明無法跳到當前位置
      return false // 返回 false，表示無法跳到末尾
    }
    maxj = max(maxj, nums[i]+i) // 更新 maxj，取當前 maxj 和當前位置能跳到的最遠位置的較大值
  }
  return true // 如果成功遍歷完數組，說明可以跳到末尾，返回 true
}

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

Python

class Solution:
    def canJump(self, nums) :
        max_i = 0       # 初始化當前能到達最遠的位置，開始時為0
        for i, jump in enumerate(nums):   # 使用enumerate函數遍歷列表，i為當前位置，jump是當前位置的跳數
            if max_i >= i and i + jump > max_i:  # 如果當前位置能到達，并且當前位置+跳數>最遠位置
                max_i = i + jump  # 更新最遠能到達位置
        return max_i >= i  # 判斷最遠能到達位置是否大于等于最后一個位置i，返回True或False

Java

class Solution {
    public boolean canJump(int[] nums) {
        int max_i = 0;  // 初始化當前能到達最遠的位置，開始時為0
        for (int i = 0; i < nums.length; i++) {
            if (max_i >= i && i + nums[i] > max_i) {
                max_i = i + nums[i];  // 更新最遠能到達位置
            }
        }
        return max_i >= nums.length - 1;  // 判斷最遠能到達位置是否大于等于最后一個位置
    }
}

Cpp

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_i = 0;  // 初始化當前能到達最遠的位置，開始時為0
        for (int i = 0; i < nums.size(); i++) {
            if (max_i >= i && i + nums[i] > max_i) {
                max_i = i + nums[i];  // 更新最遠能到達位置
            }
        }
        return max_i >= nums.size() - 1;  // 判斷最遠能到達位置是否大于等于最后一個位置
    }
};

當然，我可以使用中文來詳細介紹每個版本的所需基礎知識。

Go 版本：

1. 數組和切片：了解如何聲明和使用數組和切片。在Go中，數組是固定長度的，而切片是動態(tài)數組。

2. 循環(huán)和迭代：理解for循環(huán)和如何遍歷切片或數組。

3. 函數：熟悉如何定義和調用函數。在這個示例中，有兩個函數，canJump 和 max。

Python 版本：

1. 列表和迭代：了解如何聲明和操作Python的列表（List）數據結構。列表可以包含不同類型的元素。

2. enumerate函數：了解enumerate函數，它用于同時遍歷列表的索引和值。

3. 條件語句：理解if條件語句的使用，以及如何根據條件執(zhí)行不同的操作。

Java 版本：

1. 數組和循環(huán)：了解如何聲明和操作Java數組。Java中數組的大小是固定的。

2. for循環(huán)：理解for循環(huán)的使用，以及如何遍歷數組。

3. 條件語句：熟悉if條件語句的使用，以根據條件執(zhí)行不同的操作。

C++ 版本：

1. 向量（Vector）：了解如何使用C++的向量容器，它類似于動態(tài)數組。向量可以自動調整大小。

2. for循環(huán)：理解for循環(huán)的使用，以及如何遍歷向量。

3. 條件語句：熟悉if條件語句的使用，以根據條件執(zhí)行不同的操作。

這些基礎知識是理解和編寫這些版本中的解決方案所必需的。如果您需要更詳細的解釋或有其他問題，請隨時提出。

56. Merge Intervals

題目

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

題目大意

合并給的多個區(qū)間，區(qū)間有重疊的要進行區(qū)間合并。

解題思路

Go 版本:

1. 首先，通過遍歷所有區(qū)間，找到它們的最大起點和最小終點，以便后續(xù)數組的初始化。

2. 創(chuàng)建兩個數組 start 和 end，用于統(tǒng)計每個起始點和結束點的出現次數。

3. 第二次遍歷區(qū)間列表，將每個區(qū)間的起始點和結束點在相應的數組中加一。

4. 使用 prefix 變量來記錄當前活躍的區(qū)間數，通過 prefix 的值可以確定是否開始一個新的合并區(qū)間。

5. 最后，根據 prefix 的值，將合并后的區(qū)間加入到答案中。

Python 版本:

1. 首先，通過遍歷所有區(qū)間，找到它們的最大起點和最小終點，以便后續(xù)列表的初始化。

2. 創(chuàng)建兩個列表 start 和 end，用于統(tǒng)計每個起始點和結束點的出現次數。

3. 第二次遍歷區(qū)間列表，將每個區(qū)間的起始點和結束點在相應的列表中加一。

4. 使用 prefix 變量來記錄當前活躍的區(qū)間數，通過 prefix 的值可以確定是否開始一個新的合并區(qū)間。

5. 最后，根據 prefix 的值，將合并后的區(qū)間加入到答案中。

Java 版本:

1. 首先，通過遍歷所有區(qū)間，找到它們的最大起點和最小終點，以便后續(xù)數組的初始化。

2. 創(chuàng)建兩個數組 start 和 end，用于統(tǒng)計每個起始點和結束點的出現次數。

3. 第二次遍歷區(qū)間列表，將每個區(qū)間的起始點和結束點在相應的數組中加一。

4. 使用 prefix 變量來記錄當前活躍的區(qū)間數，通過 prefix 的值可以確定是否開始一個新的合并區(qū)間。

5. 最后，將合并后的區(qū)間加入到答案數組中。

C++ 版本:

1. 首先，通過遍歷所有區(qū)間，找到它們的最大起點和最小終點，以便后續(xù)向量的初始化。

2. 創(chuàng)建兩個向量 start 和 end，用于統(tǒng)計每個起始點和結束點的出現次數。

3. 第二次遍歷區(qū)間列表，將每個區(qū)間的起始點和結束點在相應的向量中加一。

4. 使用 prefix 變量來記錄當前活躍的區(qū)間數，通過 prefix 的值可以確定是否開始一個新的合并區(qū)間。

5. 最后，將合并后的區(qū)間加入到答案向量中。

總的來說，這些版本的解決方案都采用了相似的核心思想：先找到區(qū)間的最大起點和最小終點，然后統(tǒng)計每個起始點和結束點的出現次數，最后根據這些信息進行合并操作。

代碼

Go

func merge(intervals [][]int) [][]int {
    MAX := math.MinInt
    MIN := math.MaxInt
    left := -1
    prefix := 0
    for _, temp := range intervals {
        x := temp[0]
        y := temp[1]
        if x < MIN {
            MIN = x
        }
        if y > MAX {
            MAX = y
        }
    }

    start := make([]int, MAX+1)
    end := make([]int, MAX+1)

    for i := 0; i < len(intervals); i++ {
        x := intervals[i][0]
        y := intervals[i][1]
        start[x]++
        end[y]++
    }

    var ans [][]int
    size := 0
    for i := MIN; i <= MAX; i++ {
        if start[i] > 0 {
            prefix += start[i]
            if prefix == start[i] {
                left = i
            }
        }
        if end[i] > 0 {
            prefix -= end[i]
            if prefix == 0 {
                ans = append(ans, []int{left, i})
                size++
            }
        }
    }
    return ans
}

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        MAX = float('-inf')
        MIN = float('inf')
        left = -1
        prefix = 0
        for temp in intervals:
            x = temp[0]
            y = temp[1]
            if x < MIN:
                MIN = x
            if y > MAX:
                MAX = y

        start = [0] * (MAX + 1)
        end = [0] * (MAX + 1)
        
        for i in range(len(intervals)):
            x = intervals[i][0]
            y = intervals[i][1]
            start[x] += 1
            end[y] += 1

        ans = []
        size = 0
        for i in range(MIN, MAX + 1):
            if start[i] > 0:
                prefix += start[i]
                if prefix == start[i]:
                    left = i
            if end[i] > 0:
                prefix -= end[i]
                if prefix == 0:
                    ans.append([left, i])
                    size += 1
        
        return ans

Java

class Solution {
    static int[][] ans = new int[10001][2]; // 創(chuàng)建一個靜態(tài)二維數組用于存儲合并后的區(qū)間
    public int[][] merge(int[][] intervals) {
        int MAX = Integer.MIN_VALUE, MIN = Integer.MAX_VALUE, left = -1, prefix = 0;
        for (int[] temp : intervals) {
            int x = temp[0];
            int y = temp[1];
            if (x < MIN) MIN = x;
            if (y > MAX) MAX = y;
        }
        int[] start = new int[MAX+1], end = new int[MAX+1];
        
        // 統(tǒng)計每個起始點和結束點出現的次數
        for (int i = 0; i < intervals.length; i++) {
            int x = intervals[i][0];
            int y = intervals[i][1];
            start[x]++;
            end[y]++;
        }

        int size = 0;
        for (int i = MIN; i <= MAX; i++) {
            if (start[i] > 0) {
                prefix += start[i];
                if (prefix == start[i]) {
                    left = i;
                }
            }
            if (end[i] > 0) {
                prefix -= end[i];
                if (prefix == 0) {
                    ans[size++] = new int[]{left, i}; // 找到一個合并后的區(qū)間
                }
            }
        }
        return Arrays.copyOfRange(ans, 0, size); // 返回合并后的結果數組
    }
}

Cpp

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int MAX = INT_MIN;
        int MIN = INT_MAX;
        int left = -1;
        int prefix = 0;
        for (const vector<int>& temp : intervals) {
            int x = temp[0];
            int y = temp[1];
            if (x < MIN) MIN = x;
            if (y > MAX) MAX = y;
        }

        vector<int> start(MAX + 1, 0);
        vector<int> end(MAX + 1, 0);

        for (int i = 0; i < intervals.size(); i++) {
            int x = intervals[i][0];
            int y = intervals[i][1];
            start[x]++;
            end[y]++;
        }

        vector<vector<int>> ans;
        int size = 0;
        for (int i = MIN; i <= MAX; i++) {
            if (start[i] > 0) {
                prefix += start[i];
                if (prefix == start[i]) {
                    left = i;
                }
            }
            if (end[i] > 0) {
                prefix -= end[i];
                if (prefix == 0) {
                    ans.push_back({left, i});
                    size++;
                }
            }
        }
        return ans;
    }
};

每個版本的解決方案以及所需的基礎知識。

Go 版本：

這個 Go 版本的解決方案使用了以下重要的基礎知識：

1. 切片（Slices）和數組（Arrays）： Go 中的切片和數組是用來存儲多個相同類型的數據的數據結構。在這個解決方案中，切片用于存儲合并后的區(qū)間。

2. 循環(huán)（Loop）： 使用 for 循環(huán)遍歷區(qū)間列表和其他數據結構。

3. 條件語句（Conditional Statements）： 使用條件語句來處理不同的情況，例如合并區(qū)間。文章來源地址http://www.zghlxwxcb.cn/news/detail-727832.html

4. 切片追加（Slice Append）： 使用 append 函數來動態(tài)擴展切片以添加合并后的區(qū)間。

Python 版本：

這個 Python 版本的解決方案使用了以下基礎知識：

1. 列表（Lists）： 列表是 Python 中的一種數據結構，用于存儲多個對象。在這個解決方案中，列表被用于存儲合并后的區(qū)間。

2. 循環(huán)（Loop）： 使用 for 循環(huán)來遍歷區(qū)間列表和其他數據結構。

3. 條件語句（Conditional Statements）： 使用條件語句來處理不同的情況，例如合并區(qū)間。

4. 列表追加（List Append）： 使用 append 方法來動態(tài)擴展列表以添加合并后的區(qū)間。

Java 版本：

這個 Java 版本的解決方案使用了以下基礎知識：

1. 類和對象（Classes and Objects）： Java 是面向對象的編程語言，這個解決方案中創(chuàng)建了一個名為 Solution 的類來解決問題。

2. 數組（Arrays）： 使用數組來存儲合并后的區(qū)間。

3. 循環(huán)（Loop）： 使用 for 循環(huán)來遍歷區(qū)間列表和其他數據結構。

4. 條件語句（Conditional Statements）： 使用條件語句來處理不同的情況，例如合并區(qū)間。

5. 靜態(tài)數組和動態(tài)數組（Static and Dynamic Arrays）： 靜態(tài)數組是提前定義大小的數組，而動態(tài)數組可以根據需要動態(tài)分配大小。

C++ 版本：

這個 C++ 版本的解決方案使用了以下基礎知識：

1. 類和對象（Classes and Objects）： C++ 是面向對象的編程語言，這個解決方案中創(chuàng)建了一個名為 Solution 的類來解決問題。

2. 向量（Vectors）： 使用向量來存儲合并后的區(qū)間。向量是 C++ 標準庫提供的動態(tài)數組數據結構。

3. 循環(huán)（Loop）： 使用 for 循環(huán)來遍歷區(qū)間列表和其他數據結構。

4. 條件語句（Conditional Statements）： 使用條件語句來處理不同的情況，例如合并區(qū)間。

到了這里，關于Go-Python-Java-C-LeetCode高分解法-第八周合集的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！