一支筆，一雙手，一道力扣（Leetcode）做一宿！

在本文中，我們將使用TypeScript來解決劍指offer的算法題。這些問題涵蓋了各種各樣的主題，包括數(shù)組、字符串、鏈表、樹、排序和搜索等。我們將使用TypeScript的強類型和面向?qū)ο蟮奶匦詠斫鉀Q這些問題，并通過實際的代碼示例來演示如何使用TypeScript來解決算法問題。
題目全部來源于力扣題庫：《劍指 Offer（第 2 版）》本章節(jié)包括的題目有（難度是我個人感受的難度，非官方標準）：

一、圓圈中最后剩下的數(shù)字

1.1、題目描述

0,1,···,n-1這n個數(shù)字排成一個圓圈，從數(shù)字0開始，每次從這個圓圈里刪除第m個數(shù)字（刪除后從下一個數(shù)字開始計數(shù)）。求出這個圓圈里剩下的最后一個數(shù)字。

例如，0、1、2、3、4這5個數(shù)字組成一個圓圈，從數(shù)字0開始每次刪除第3個數(shù)字，則刪除的前4個數(shù)字依次是2、0、4、1，因此最后剩下的數(shù)字是3。

示例 1：

輸入: n = 5, m = 3
輸出: 3

示例 2：

輸入: n = 10, m = 17
輸出: 2

1.2、題解

本題是著名的 “約瑟夫環(huán)” 問題，數(shù)字環(huán)是首尾相接的。

首先使用模擬法來想，首先建立一個長度為n的鏈表，每輪刪除第m個節(jié)點，直至鏈表長度為1時結(jié)束，返回最后剩余的節(jié)點。但是模擬法要刪除n-1輪，每輪要在鏈表中尋找需要m次，時間復(fù)雜度達到了O（n*m），明顯會超時。

所以使用動態(tài)規(guī)劃，全文最重要的點是只關(guān)心最終活著那個人的下標變化，設(shè)解為dp[i],dp[i]表示最后剩下來的數(shù)的當(dāng)前下標
舉個例子：

    假設(shè)有一圈數(shù)字[0,1,2,3,4,5],m=3
    我們令刪除后的元素的后一個元素放在最前面方便計數(shù)
    1.刪除2->[3,4,5,0,1]
    2.刪除5->[0,1,3,4]
    3.刪除3->[4,0,1]
    4.刪除1->[4,0]
    5.刪除4->[0]
    嘗試反推:
    如何從最后剩下的元素的索引0反推至第一輪元素索引呢?
    注意到:2->1的過程是將刪除的的元素5補在尾巴上變成[0,1,3,4,5],然后再總體向右移動m位
    變成:[3,4,5,0,1];同樣地,此時的最終活下來的元素0的索引由0->3
    顯然這是(idx+m)%len的結(jié)果,idx為刪除5后的索引,len為補上刪除元素后數(shù)組的長度

這里引一張想吃火鍋的木易大佬的圖，畫的很清楚：

轉(zhuǎn)移方程為：dp[i] = (dp[i - 1] + m)%i,代碼其實很簡單：

function lastRemaining(n: number, m: number): number {
    let x = 0;
    for(let i = 2; i <= n; i++)
        x = (x + m) % i;
    return x;
};

二、股票的最大利潤

2.1、題目描述

假設(shè)把某股票的價格按照時間先后順序存儲在數(shù)組中，請問買賣該股票一次可能獲得的最大利潤是多少？

示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。

示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

2.2、題解

1??:雙指針算法

第一個指針保存當(dāng)前遇見的最小投資點，第二個指針保存當(dāng)前遇見的投資點，因為題目要求只能買賣一次，所以可邊遍歷邊計算并保存當(dāng)前最大期望收益。

一個指針記錄訪問過的最小值（注意這里是訪問過的最小值），一個指針一直往后走，然后計算他們的差值，保存最大的即可，代碼如下：

function maxProfit(prices: number[]): number {
    if(prices.length == 0)
        return 0;
    let res = 0;
    let min = prices[0];
    for(let i = 1; i < prices.length; i++){
        min = Math.min(min, prices[i]);
        res = Math.max(prices[i] - min, res);
    }
    return res;
};

2??:單調(diào)棧

單調(diào)棧解決的原理很簡單，我們要始終保持棧頂元素是所訪問過的元素中最小的，如果當(dāng)前元素小于棧頂元素，就讓棧頂元素出棧，讓當(dāng)前元素入棧。如果訪問的元素大于棧頂元素，就要計算他和棧頂元素的差值，并記錄這個差值的最大值。

其實這種方法與雙指針法的原理相似，只不過保存時使用的棧來保存。

function maxProfit(prices: number[]): number {
    if(prices.length == 0)
        return 0;
    let myStack = [];
    myStack.push(prices[0]);
    let max = 0;
    for(let i = 1; i < prices.length; i++){
        // 當(dāng)前投資點小于之前的最佳投資點
        // 即棧頂元素大于prices[i]，那么棧頂元素出棧，
        if(myStack[myStack.length - 1] > prices[i]){
            myStack.pop();
            myStack.push(prices[i]);
        }else{
            //棧頂元素不大于prices[i]，計算prices[i]和棧頂元素的差值
            max = Math.max(max, prices[i] - myStack[myStack.length - 1]);
        }
    }
    return max;
};

3??:動態(tài)規(guī)劃
設(shè)動態(tài)規(guī)劃列表 dp ，dp[i]代表以 prices[i]為結(jié)尾的子數(shù)組的最大利潤，由于題目限定為“買賣股票一次”因此，前i日的最大利潤dp[i] 等于Max（前i-1日的最大利潤，第i日賣出的最大利潤）

原理與前兩個方法類似，只不過使用dp來保存之前的最大收益期望。

function maxProfit(prices: number[]): number {
    if(prices.length < 2)
        return 0;
    let min = prices[0];
    let dp:number[] = [0];
    for(let i = 1; i < prices.length; i++){
        min = Math.min(prices[i], min);
        dp[i] = Math.max(dp[i - 1], prices[i] - min);
    }
    return dp[prices.length - 1]
};

三、求1+2+…+n

3.1、題目描述

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字及條件判斷語句（A?B:C）。

示例 1：
輸入: n = 3 輸出: 6

示例 2：
輸入: n = 9 輸出: 45

3.2、題解

最簡單就是使用遞歸解題：

function sumNums(n: number): number {
    if(n == 0)
        return 0;
    return n + sumNums(n - 1);
};

由于題目不允許使用if關(guān)鍵字，所以我們使用&&運算符替換，當(dāng)n大于0時都會運行后面(n += sumNums(n - 1)，達到與上述代碼同樣的效果。

function sumNums(n: number): number {
    return n && (n += sumNums(n - 1));
};

四、不用加減乘除做加法

4.1、題目描述

寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用 “+”、“-”、“*”、“/” 四則運算符號。

示例:

輸入: a = 1, b = 1 輸出: 2

4.2、題解

題目要求了不能使用運算符 +，-，*，/
所以我們考慮使用位運算來解決加法問題。
先從十進制來考慮加法原理，舉個例子，15+17：

1. 首先計算個位相加：5 + 7 = 12，個位為2，先不考慮進位問題
2. 再計算十位相加：1 + 1 = 2， 十位為2
3. 數(shù)字個十位相加，22
4. 計算進位的數(shù)字：5 + 7 = 12，進位1，得到進位的數(shù)字有10
5. 進位數(shù)與數(shù)字相加：10 + 22 = 32

從二進制的角度來講，15的二進制為01111,17的二進制為10001

1. 首先計算機各個位置上的數(shù)字分別相加: 01111 + 10001 = 1 1110
2. 然后計算進位的數(shù)字，1 + 1 = 10
3. 然后再計算11110 和 10 的相加，依次類推，直至后面這個數(shù)即b為0；

在位運算中，第一步可以用異或來做，即^
而計算進位的數(shù)字可以用與和左移來算，如01 & 01 = 01，然后左移即可得到進位10

function add(a: number, b: number): number {
    if(b == 0)
        return a;
    let currN = a ^ b;
    let upN = (a & b) << 1;
    return add(currN, upN);
};

五、構(gòu)建乘積數(shù)組

5.1、題目描述

給定一個數(shù)組 A[0,1,…,n-1]，請構(gòu)建一個數(shù)組 B[0,1,…,n-1]，其中 B[i] 的值是數(shù)組 A 中除了下標 i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，不能使用除法。

示例:
輸入: [1,2,3,4,5]
輸出: [120,60,40,30,24]

5.2、題解

首先想到的是用總乘積除以當(dāng)前數(shù)，但是不能用除法，而且數(shù)組中間存在0，如果除0會出現(xiàn)問題。

而如果用暴力來模擬：

function constructArr(a: number[]): number[] {
    let res: number[] = [];
    for(let i = 0; i < a.length; i++){
        let temp = 1;
        for(let j = 0; j < a.length; j++){
            if(j == i)
                continue;
            temp = temp * a[j];
        }
        res.push(temp);
    }
    return res;
};

時間復(fù)雜度$O(N^2)$，會超時：

這里采用左右乘積列表方法，即構(gòu)建一個左列表存儲索引左側(cè)所有數(shù)字的乘積，構(gòu)建一個右列表存儲索引左側(cè)所有數(shù)字的乘積，對于給定索引 i，我們將使用它左邊所有數(shù)字的乘積乘以右邊所有數(shù)字的乘積。

function constructArr(a: number[]): number[] {
    let left = [1];
    let right = [];
    let res = [];
    for(let i = 1; i < a.length; i++){
        left[i] = a[i - 1] * left[i - 1];
    }
    right[a.length - 1] = 1;
    for(let i = a.length - 2; i >= 0; i--){
        right[i] = a[i + 1] * right[i + 1];
    }
    for(let i = 0; i < a.length; i++){
        res[i] = left[i] * right[i];
    }
    return res;
};

六、把字符串轉(zhuǎn)換成整數(shù)

6.1、題目描述

寫一個函數(shù) StrToInt，實現(xiàn)把字符串轉(zhuǎn)換成整數(shù)這個功能。不能使用 atoi 或者其他類似的庫函數(shù)。

首先，該函數(shù)會根據(jù)需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止。

當(dāng)我們尋找到的第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續(xù)數(shù)字組合起來，作為該整數(shù)的正負號；假如第一個非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成整數(shù)。

該字符串除了有效的整數(shù)部分之后也可能會存在多余的字符，這些字符可以被忽略，它們對于函數(shù)不應(yīng)該造成影響。

注意：假如該字符串中的第一個非空格字符不是一個有效整數(shù)字符、字符串為空或字符串僅包含空白字符時，則你的函數(shù)不需要進行轉(zhuǎn)換。

在任何情況下，若函數(shù)不能進行有效的轉(zhuǎn)換時，請返回 0。

示例 1:

輸入: “42” 輸出: 42

示例 2:

輸入: " -42" 輸出: -42
解釋: 第一個非空白字符為 ‘-’, 它是一個負號。

示例 3:

輸入: “4193 with words” 輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 ‘3’ ，因為它的下一個字符不為數(shù)字。

示例 4:

輸入: “words and 987” 輸出: 0
解釋: 第一個非空字符是 ‘w’, 但它不是數(shù)字或正、負號。因此無法執(zhí)行有效的轉(zhuǎn)換。

示例 5:

輸入: “-91283472332” 輸出: -2147483648
解釋: 數(shù)字 “-91283472332” 超過 32位有符號整數(shù)范圍。 因此返回 INT_MIN (?231) 。

6.2、題解

這里補充正則表達式用到的RegExp對象的match方法：match()方法是RegExp對象的一個方法，用來檢索字符串中符合正則表達式規(guī)則的字符串，并將匹配到的字符串以數(shù)組形式返回，用法如下：

let regExp = new RegExp('/^[-+]?(\d+)/');
let res = str.match(regExp);

這里我們使用：正則表達式處理，提取后比較范圍然后判斷：

function strToInt(str: string): number {
    str = str.trim(); // 去掉前后空格
    let INT_MIN = -Math.pow(2,31), INT_MAX = Math.pow(2,31) - 1;
    let regExp = new RegExp(/^[\+\-]?\d+/);
    let res = str.match(regExp);
    console.log(res);
    if(res == null)
        return 0;
    if(res[0][0] == '-' && Number(res[0]) < INT_MIN){
        return INT_MIN;
    }
    if(Number(res[0]) > INT_MAX){
        return INT_MAX;
    }
    return Number(res[0]);
};

圖簡單的方法，這里可以使用parseInt() 函數(shù)，parseInt() 函數(shù)可解析一個字符串，并返回一個整數(shù)，parseInt() 函數(shù)可以處理以下情況：

1. 解析正整數(shù)：當(dāng)字符串以數(shù)字開頭時，parseInt() 將從字符串的開頭開始解析直到遇到非數(shù)字字符。它會忽略字符串開頭的空白字符，并返回解析后的整數(shù)。
2. 解析負整數(shù)：當(dāng)字符串以負號（-）開頭時，parseInt() 會將其視為一個負整數(shù)。
3. 處理非數(shù)字字符：當(dāng)字符串中包含非數(shù)字字符時，parseInt() 將停止解析，并返回已解析的部分。例如，parseInt(“123abc”) 將返回 123。
4. 處理基數(shù)（進制）：通過提供第二個參數(shù) radix，可以指定解析時所使用的基數(shù)。例如，parseInt(“10”, 2) 將按二進制解析字符串 “10”，返回 2。
5. 忽略浮點數(shù)部分：parseInt() 函數(shù)將忽略字符串中的小數(shù)點和小數(shù)部分。例如，parseInt(“3.14”) 將返回 3。
6. parseInt() 函數(shù)還有一些特殊情況，例如在解析以 0x 開頭的字符串時會將其視為十六進制數(shù)

這里可以直接調(diào)用函數(shù)，然后判斷一下最大和最小范圍：

function strToInt(str: string): number {
    let m = Math.pow(2, 31);
    return Math.min(Math.max(parseInt(str) || 0, -m), m - 1);
};

七、 二叉搜索樹的最近公共祖先

7.1、題目描述

給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>

例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。

示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋:節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身

7.2、題解

使用遞歸法，從根節(jié)點找起，顯然可得最近公共祖先的值肯定是大于其中一個數(shù)，小于另外一個數(shù)，使用遞歸法，如果當(dāng)前節(jié)點同時大于這兩個數(shù)，則他兩肯定在左子樹當(dāng)中，如果當(dāng)前節(jié)點同時小于這兩個數(shù)，則他兩肯定在右子樹當(dāng)中，如此查找，直到第一次出現(xiàn)一個在左子樹，一個在右子樹則滿足條件：

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if(root.val > p.val && root.val > q.val){
        return lowestCommonAncestor(root.left, p, q);
    }
    if(root.val < p.val && root.val < q.val){
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
};

八、二叉樹的最近公共祖先

8.1、題目描述

這一題題干跟前一題類似，唯一的不同是這里的二叉樹是普通二叉樹，不再是二叉搜索樹

8.2、題解

同樣采用遞歸的方法，但此時需要判斷左子樹是否存在p或q中的一個，判斷右子樹是否存在p或q中的一個，如果左子樹存在一個，右子樹存在一個則返回當(dāng)前節(jié)點，若只有左子樹存在（右邊找的為空），則訪問左子樹，若只有右子樹存在（左邊找的為空），則訪問右子樹。

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
	if(root == null)
        return null;
    if(root == p || root == q)
        return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    // 即在第一次該節(jié)點的左子樹和右子樹上分別找到了p 和 q
    if(left !== null && right !== null){
        return root;
    }
    // 暫時只找到一個
    else if(left == null){
        return right;
    }
    else if(right == null){
        return left;
    }
};

九、機器人的運動范圍

9.1、題目描述

地上有一個m行n列的方格，從坐標 [0,0] 到坐標 [m-1,n-1] 。一個機器人從坐標 [0, 0] 的格子開始移動，它每次可以向左、右、上、下移動一格（不能移動到方格外），也不能進入行坐標和列坐標的數(shù)位之和大于k的格子。例如，當(dāng)k為18時，機器人能夠進入方格 [35, 37] ，因為3+5+3+7=18。但它不能進入方格 [35, 38]，因為3+5+3+8=19。請問該機器人能夠到達多少個格子？

示例 1：

輸入：m = 2, n = 3, k = 1
輸出：3

示例 2：

輸入：m = 3, n = 1, k = 0
輸出：1

9.2、題解

首要要理解一下題目，題目說的是數(shù)位之和不大于k，即比如[13,12],數(shù)位之和為1+3+1+2=7，所以m = 2, n = 3, k = 1時，滿足條件的有[0,0],[0,1],[1,0]三個結(jié)果
m = 3, n = 1, k = 0時，滿足條件的有[0,0]一個結(jié)果。

設(shè)立res作為全局結(jié)果數(shù)量，visited數(shù)組記錄是否已經(jīng)被訪問過，然后使用采用dfs方法遍歷所有情況：

function movingCount(m: number, n: number, k: number): number {
    let res = 0;
    let visited = new Array(m).fill(0).map(()=> new Array(n).fill(false));
    function dfs(i:number, j:number){
        if(sum(i, j) > k || i < 0 || j < 0 || i >= m || j >= n || visited[i][j])
            return;
        res ++;
        visited[i][j] = true; 
        dfs(i, j + 1);
        dfs(i, j - 1);
        dfs(i - 1, j);
        dfs(i + 1, j);
    }
    function sum(i:number, j:number):number{
        return Math.floor(i / 10) + i % 10 + Math.floor(j / 10) + j % 10
    }
    dfs(0, 0);
    return res;
};

十、H 指數(shù)

10.1、題目描述

給你一個整數(shù)數(shù)組 citations ，其中 citations[i] 表示研究者的第 i 篇論文被引用的次數(shù)。計算并返回該研究者的 h 指數(shù)。

根據(jù)維基百科上 h 指數(shù)的定義：h 代表“高引用次數(shù)” ，一名科研人員的 h 指數(shù) 是指他（她）至少發(fā)表了 h 篇論文，并且每篇論文 至少 被引用 h 次。如果 h 有多種可能的值，h 指數(shù) 是其中最大的那個。

10.2、題解

先從小到大排序，然后從后往前遍歷，將h因子置為0，從影響因子最大的文章開始，當(dāng)citations[i] > h時，h++：文章來源地址http://www.zghlxwxcb.cn/news/detail-683438.html

function hIndex(citations: number[]): number {
    citations.sort(function(a,b){return a-b});
    let h = 0;
    for(let i = citations.length - 1; i >= 0; i--){
        if(citations[i] > h){
            h++;
        }
    }
    return h;
};

到了這里，關(guān)于TypeScript算法題實戰(zhàn)——劍指 Offer篇（6）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！