TypeScript算法题实战——剑指 Offer篇（3）

2024-09-18 21:25:06 浏览数 (1)

随着TypeScript的流行，越来越多的开发者开始使用TypeScript来解决算法问题。

在本文中，我们将使用TypeScript来解决剑指offer的算法题。这些问题涵盖了各种各样的主题，包括数组、字符串、链表、树、排序和搜索等。我们将使用TypeScript的强类型和面向对象的特性来解决这些问题，并通过实际的代码示例来演示如何使用TypeScript来解决算法问题。

题目全部来源于力扣题库：《剑指 Offer（第 2 版）》，本章节包括的题目有：

题目

难度

从上到下打印二叉树

简单

二叉搜索树的后序遍历序列

简单

二叉树中和为某一值的路径

简单

字符串的排列

中等

数组中出现次数超过一半的数字

简单

最小的k个数

中等

连续子数组的最大和

中等

数字序列中某一位的数字

中等

把数组排成最小的数

中等

把数字翻译成字符串

中等

一、从上到下打印二叉树

1.1、题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 例如:

给定二叉树: [3,9,20,null,null,15,7],

在这里插入图片描述在这里插入图片描述

返回： [3,9,20,15,7]

1.2、题解

使用队列的方法进行层次遍历，首先将根节点压入队列，然后每从队首出一个元素，就将该元素的左右子节点压入队尾，这样就可以实现层序遍历。

代码语言：javascript复制
function levelOrder(root: TreeNode | null): number[] {
    let res:number[] = [];
    let que:TreeNode[] = [];

    if(!root)
        return res;
    que.push(root);
    while(que.length){
        let tmp: TreeNode = que.shift();
        if(tmp == null)
            continue;
        res.push(tmp.val);
        if(tmp.left)
            que.push(tmp.left);
        if(tmp.right)
            que.push(tmp.right);
    }
    return res;
};

二、 二叉搜索树的后序遍历序列

2.1、题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

示例 1： 输入: [1,6,3,2,5] 输出: false 示例 2： 输入: [1,3,2,6,5] 输出: true

2.2、题解

题目多读几遍就可以理解，二叉搜索树的后序遍历结果其实也是部分有序的，二叉搜索树的特点是左子树的值<根节点<右子树的值。而后续遍历的顺序是：左子节点→右子节点→根节点，后续遍历的最后一个数字一定是根节点，所以数组中最后一个数字就是根节点，我们从前（第0个）往后找到第一个比根节点大的数字，然后从这里分段，其左边的都是左子树，右边就是右子树

这里需要判断一下右子树的内部情况，如果其中有小于根节点的，那说明不是二叉搜索树，直接返回false。然后再以递归的方式判断左右子树。

代码语言：javascript复制
function verifyPostorder(postorder: number[]): boolean {
    if(postorder.length <= 1)
        return true;
    let root:number = postorder[postorder.length - 1];
    let index:number = 0;
    while(index < postorder.length - 1&&postorder[index] < root){
        index   ;
    }
    let leftChild:number[] = postorder.slice(0, index);
    let rightChild:number[] = postorder.slice(index, postorder.length - 1);
    for(let i = 0; i < rightChild.length; i  ){
        if(rightChild[i] < root)
            return false;
    }
    return verifyPostorder(leftChild) && verifyPostorder(rightChild);
};

三、二叉树中和为某一值的路径

3.1、题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

3.2、题解

使用深度优先搜索算法，val表示当前路径已经累计的和，list存储当前路径。 要注意的是： 1、不要根据路径和当前大小剪枝，因为题目里会有负数，只能全部遍历； 2、要是ans.push(list.slice())压入list的复制，如果是ans.push(list)压入list的引用的话，会影响res。

代码语言：javascript复制
function pathSum(root: TreeNode | null, target: number): number[][] {
    let ans:number[][] = [];
    let t:number = target;
    function dfs(root: TreeNode | null, val, list): void{
        if(root == null)
            return;
        list.push(root.val);
        if(root.val   val == t && root.left == null && root.right == null){
            ans.push(list.slice());
        }
        dfs(root.left, val   root.val, list);
        dfs(root.right, val   root.val, list);
        list.pop();
    }
    dfs(root, 0, []);
    return ans;
};

四、字符串的排列

4.1、题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例: 输入：s = “abc” 输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

4.2、题解

使用哈希表 DFS方法，pos代表当前的深度位置，让当前位置与之后所有位置进行交换，catSet是一个哈希集合，用于排除重复的方案，char记录当前的的排列，当pos == s.length时，当次递归结束，将char处理后压入res中即可。

代码语言：javascript复制
function permutation(s: string): string[] {
    let char = s.split('');
    let res:string[] = [];
    function dfs(pos){
        if(pos == s.length){
            res.push(char.join(""));
            return;
        }
        let catSet = new Set();
        for(let i = pos; i < s.length; i  ){
            if(catSet.has(char[i])){
                continue;
            }
            catSet.add(char[i]);
            {
                const tmp = char[pos];
                char[pos] = char[i];
                char[i] = tmp; 
            }
            dfs(pos   1);
             {
                const tmp = char[pos];
                char[pos] = char[i];
                char[i] = tmp; 
            }
        }
    }
    dfs(0);
    return  res;
};

五、数组中出现次数超过一半的数字

5.1、题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

5.2、题解

使用Boyer-Moore 投票算法也叫摩尔投票法，维护一个候选众数 candidate 和它出现的次数 count：

  1. 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
  2. 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
  3. . 如果 x 与 candidate 不等，且计数器再减1后小于0了，那么说明当前疑似的众数被减光了，换candidate，count置1。
代码语言：javascript复制
function majorityElement(nums: number[]): number {
    let count:number = 0;
    let candidate: number = -1;
    for(let i = 0; i < nums.length; i  ){
        if(nums[i] == candidate)
               count;
        else{
            if(-- count < 0){
                count = 1;
                candidate = nums[i];
            }
        }
    }
    return candidate;
};

六、最小的k个数

6.1、题目描述

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0]

6.2、题解

解法一：调用sort排序后返回前k个元素，使用sort((a, b) =>{ return a - b})将数组从小到大排序，然后使用slice返回前k个。

代码语言：javascript复制
function getLeastNumbers(arr: number[], k: number): number[] {
    return arr.sort((a, b) =>{ return a - b}).slice(0, k);
};

解法二：部分快排分治法

参考：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solution/chao-quan-3chong-jie-fa-zhi-jie-pai-xu-zui-da-dui-/ 单次快排后，返回的index之前的所有元素均比arr[index]小，index之后的所有元素均比arr[index]大，那么

  1. 如果index等于k，即index之前的结果就是题解；
  2. 如果index小于k，即index之前的结果还不够k个，所以需要将index之后的结果继续快排；
  3. 如果index大于k，即index之前的结果多于k个，需要将index之前的结果再次快排。
代码语言：javascript复制
function getLeastNumbers(arr: number[], k: number): number[] {
    if(k >= arr.length)
        return arr;
    let left:number = 0;
    let right:number = arr.length - 1; 
    // 快排的单次分治
    function partition(arr:number[], start:number, end:number):number {
        const k:number = arr[start];
        let left:number = start   1;
        let right:number = end;

        while(1){
            while(left <= end && arr[left] <= k)   left;
            while(right >= start   1 && arr[right] >= k) --right;
            if(left >= right)
                break;

        [arr[left], arr[right]] = [arr[right], arr[left]];
          left;
        --right;
        }
        [arr[right], arr[start]] = [arr[start], arr[right]];
        return right;
    }
    //index为当前分治点，若点位小于k，则往右边继续分治，若点位大于k则往左边继续分治
    let index:number = partition(arr, left, right);
    while(index !== k){
        if(index < k){
            left = index   1;
            index = partition(arr, left, right);
        }
        else if(index > k){
            right = index - 1;
            index = partition(arr, left, right);
        }
    }
    return arr.slice(0, k);
};

七、连续子数组的最大和

7.1、题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为6。

7.2、题解

使用动态规划，维护一个dp数组，dp[i]表示以元素nums[i]为结尾的连续子数组最大和，其中dp[i]=max((dp[i-1] nums[i]), nums[i])，res用于保存dp中的最大值，可以边算状态数组时边记录最大值，也可以最后再遍历一次状态数组。

代码语言：javascript复制
function maxSubArray(nums: number[]): number {
    let res:number = nums[0];
    let dp:number[] = [];
    dp[0] = res;
    for(let i = 1; i < nums.length; i  ){
        dp[i] = Math.max(nums[i], dp[i - 1]   nums[i]);
        res = Math.max(res, dp[i]);
    }
    return res;
};

八、数字序列中某一位的数字

8.1、题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1： 输入：n = 3 输出：3

示例 2： 输入：n = 11 输出：0

8.2、题解

参考https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/js-5xing-dai-ma-ji-shi-xing-zhu-shi-by-o-2skd/

题目最后仅需要返回第n位对应的单个数字，但是每个数字的长度不同，会影响逻辑判断，那么我们可以扩充每个数字到相同的长度来计算位置。

例如要找到第15位置（应该返回12的2），我们扩充为 00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24 ....

跟原数列相比，第15位置其实前面增加了10个0位，此时其在第25位置。如何在这个新的序列中计算呢？首先找到是第几个隔间：Math.floor(25/2)=12,然后再找是该隔间的第几个元素，25%2=1，即为第12个隔间的第1个元素：2（下标从0开始）

而要找到第205位置，扩充为001|002|003|004|005|006|007|008|009|010|011|012|013|...

此时第205位置前面新增的位数为10 100，此时其在第315位置。然后以同样方法找到第几个隔间：Math.floor(315/3)=105，然后再找是该隔间的第几个元素，315%3=0，即为第105个隔间的第0个元素：1

以这种思路，代码如下：

代码语言：javascript复制
function findNthDigit(n: number): number {
    let i = 1;
    while( i * (10 ** i) < n){
        n = n   10 ** i;
        i   ;
    }
    return Number((Math.floor(n / i)   "")[n % i]);
};

九、把数组排成最小的数

9.1、题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1: 输入: [10,2] 输出: “102”

示例 2: 输入: [3,30,34,5,9] 输出: “3033459”

9.2、题解

从两个数开始讲，比如3和30，可以排成3 30 => 330和 30 3 => 303，题目要求最小，那么采用30 3的方案，而在数组中，就可以把30排在3前面，以保证这两数的部分满足最小方案。

从三个数来看，3,30,15，首先可以看3和30，先排成30,3,15的模式，然后再继续往后看3,15，3和15可以排成3 15 => 315和 15 3 => 153，153更小，故可以排成15,3的模式，此时数组变成30,15,3，再来一遍，以此类推，最后数组变成了15,30,3，为最小情况。

推广到多个数，其实可以发现上述步骤在做一种冒泡排序操作，只是这种排序的条件是判断两数交换后的组合数是否更小，由于js和ts原生sort函数支持回调函数，我们直接修改回调函数，最后将排序好的数组内部元素转成字符串并连接起来即可。

代码语言：javascript复制
function minNumber(nums: number[]): string {
    nums.sort((a, b) => Number(String(a)   String(b)) < Number(String(b)   String(a)) ? -1 : 1)
    return nums.map(e => String(e)).join('');
};

十、把数字翻译成字符串

10.1、题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1: 输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi” 。

10.2、题解

分析本题，从12258开始分析，首先从头开始12258可以分为1/2258和12/258，这个问题就变成计算2258和258有多少种情况，然后将他们相加。

分析1/2258，其可以分为1/2/258和1/22/58，分析12/258，其可以分为12/2/58和12/25/8，依此类推，这个就很像做过的跳台阶问题，一次可以选择跳一级或者跳两级，只不过这里跳两级的条件要加上不能大于25。

基于这种思想，使用递归法，代码如下：

代码语言：javascript复制
function translateNum(num: number): number {
    let str:string = num.toString();
    function dfs(str, point){
        if(point >= str.length - 1)
            return 1;
        const temp = Number(str[point]   str[point   1]);
        if(temp >= 10 && temp <= 25){
            return dfs(str, point   1)   dfs(str, point   2);
        }else{
            return dfs(str, point   1);
        }
    }

    return dfs(str, 0);
};
腾讯技术创作特训营S9

0 人点赞