首页 前端知识 TypeScript算法题实战——剑指 Offer篇(5)

TypeScript算法题实战——剑指 Offer篇(5)

2024-08-30 20:08:19 前端知识 前端哥 453 724 我要收藏

目录

  • 一、平衡二叉树
    • 1.1、题目描述
    • 1.2、题解
  • 二、数组中数字出现的次数
    • 2.1、题目描述
    • 2.2、题解
  • 三、数组中数字出现的次数 II
    • 3.1、题目描述
    • 3.2、题解
  • 四、和为s的两个数字
    • 4.1、题目描述
    • 4.2、题解
  • 五、和为s的连续正数序列
    • 5.1、题目描述
    • 5.2、题解
  • 六、翻转单词顺序
    • 6.1、题目描述
    • 6.2、题解
  • 七、滑动窗口的最大值
    • 7.1、题目描述
    • 7.2、题解
  • 八、队列的最大值
    • 8.1、题目描述
    • 8.2、题解
  • 九、n个骰子的点数
    • 9.1、题目描述
    • 9.2、题解
  • 十、扑克牌中的顺子
    • 10.1、题目描述
    • 10.2、题解

一支笔,一双手,一道力扣(Leetcode)做一宿!

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

题目全部来源于力扣题库:《剑指 Offer(第 2 版)》本章节包括的题目有(难度是我个人感受的难度,非官方标准):

题目难度
平衡二叉树简单
数组中数字出现的次数中等
数组中数字出现的次数 II中等
和为s的两个数字简单
和为s的连续正数序列简单
翻转单词顺序简单
滑动窗口的最大值中等
队列的最大值中等
n个骰子的点数困难
扑克牌中的顺子简单

一、平衡二叉树

1.1、题目描述

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

在这里插入图片描述

在这里插入图片描述

1.2、题解

在递归计算左子树和右子树深度时,加上判断Math.abs(left - right) > 1,若>1则说明此时二叉树已经不平衡了,将全局变量res置为false

function isBalanced(root: TreeNode | null): boolean {
    let res = true;
    if(root == null)
        return true;
    getHeight(root);
    function getHeight(root: TreeNode | null):number{
        if(root == null)
            return 0;
        let left = getHeight(root.left);
        let right = getHeight(root.right);
        if(Math.abs(left - right) > 1)
            res = false;
        return Math.max(left, right) + 1;
    }
    return res;
};

二、数组中数字出现的次数

2.1、题目描述

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:
输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

2.2、题解

首先想到的是哈希表法,维护一个哈希Mapkeynums[i]value为出现的次数:

function singleNumbers(nums: number[]): number[] {
    let myMap: Map<number, number> = new Map();
    for(let i = 0; i < nums.length; i++){
        myMap.set(nums[i], myMap.get(nums[i])? myMap.get(nums[i]) + 1 : 1)
    }
    let res = [];
    for(let i = 0; i < nums.length; i++) {
        if(myMap.get(nums[i]) == 1)
            res.push(nums[i]);
    }
    return res;
};

但是题目要求时间复杂度 O(N),空间复杂度 O(1),所以并不满足条件。
参考:https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solutions/572857/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/?envType=featured-list&envId=xb9nqhhg
的异或方法来解答。

首先异或运算满足交换律 a⊕b=b⊕a,且a⊕a=0,那么如果题目只存在一个仅出现一次的数字,那么a⊕b⊕c⊕d⊕a⊕c⊕d = a⊕a⊕c⊕c⊕d⊕d⊕c = c,就可以完全求出出现一次的c,代码如下:

function singleNumbers(nums: number[]): number[] {
    let x = 0;
    for(let i = 0; i < nums.length; i++){
        x ^= nums[i];
    }
    console.log(x);
    return [1,2];
};

然而题目要求的是有两个仅出现一次的数,即a⊕b⊕c⊕d⊕a⊕c⊕d⊕z = b⊕z,此时x求得的是b和z异或运算的值。此时得出的x如果为00100,说明b和z在二进制上面倒数第三位不同,如果为00110,说明b和z在二进制上面倒数第二、三位都不同。

由于数组中有两个数出现一次,那么我们可以把数组分成两个子数组,子数组内部出现一次的数仅有一个再进行异或,就可以得出答案,要将数组分成两个子数组(子数组内部出现一次的数仅有一个),可以按x的性质来分,可以按x的最高1位,也可以按x的最低1位:

function singleNumbers(nums: number[]): number[] {
    let x = 0;
    let res1 = 0, res2 = 0;
    for(let i = 0; i < nums.length; i++){
        x ^= nums[i];
    }
    let oneIndex = 1;
    while((x & oneIndex) == 0){
        oneIndex = oneIndex << 1; // m * 2
    }
    for(let i = 0; i < nums.length; i++){
        if(nums[i] & oneIndex)
            res1 = res1 ^ nums[i];
        else
            res2 = res2 ^ nums[i];
    }
    return [res1, res2];
};

三、数组中数字出现的次数 II

3.1、题目描述

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1:

输入:nums = [3,4,3,3]
输出:4

示例 2:
输入:nums = [9,1,7,9,7,9,7]
输出:1

3.2、题解

哈希表方法同样能解,上一题的哈希方法直接拿过来套用。力扣上面有大神提供的位运算方法,使用到了模三计数器(数电的知识)的设计,没有很看懂。

这里提供一种排序方法:
首先将数组使用sort()进行排序,排序后的数组应当满足相同的数会以 3 的倍排序好,重新遍历排序好的数组,以 3 倍的“距离”跳跃式遍历,判断nums[i] == nums[i + 2]是否成立即可:

function singleNumber(nums: number[]): number {
    if(nums.length == 1)
        return nums[0];
    nums.sort();
    for(let i = 0; i < nums.length; i += 3){
        if(nums[i] != nums[i + 2])
            return nums[i];
    }
    return 1;
};

四、和为s的两个数字

4.1、题目描述

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

示例 2:
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

4.2、题解

使用双指针法,由于数组已经是排序好的数组,左指针指向最小值,右指针指向最大值,若当前最小值+最大值大于target,则右指针左移一位,若当前最小值+最大值小于target,则左指针右移一位:

function twoSum(nums: number[], target: number): number[] {
    let left = 0;
    let right = nums.length;
    while(nums[left] + nums[right] != target){
        if(nums[left] + nums[right] < target)
            left++;
        else{
            right--;
        }
    }
    return [nums[left], nums[right]];
};

五、和为s的连续正数序列

5.1、题目描述

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

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

示例 2:
输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

5.2、题解

使用滑动窗口法,并维护一个当前滑动窗口里的值的和,若和大于target则将左边界右移,若和小于target则将右边界右移,若当前窗口的和等于target则记录窗口内的值并压入结果集中,再将右边界右移。

function findContinuousSequence(target: number): number[][] {
    let left = 1;
    let right = 1;
    let sum = 0;
    let res: number[][] = [];
    while(left <= target / 2){
        if(sum < target){
            sum = sum + right;
            right++
        }
        else if(sum > target){
            sum = sum - left;
            left++;
        }
        else{
            let tmpRes: number[] = [];
            for(let i = left; i < right; i++){
                tmpRes.push(i);
            }
            res.push(tmpRes);
            sum = sum - left;
            left ++;
        }
    }
    return res;
};

六、翻转单词顺序

6.1、题目描述

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. “,则输出"student. a am I”。

示例 1:
输入: “the sky is blue”
输出: “blue is sky the”

示例 2:
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

6.2、题解

使用js自带的split函数,可以将字符串以" "为

function reverseWords(s: string): string {
    let arr = s.split(' ');
    let res = "";
    for(let i = arr.length - 1; i > -1; i--){
        if(arr[i]!='')
            res = res + arr[i] + ' ';
    }
    return res.substring(0, res.length - 1);
};

七、滑动窗口的最大值

7.1、题目描述

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 73
1 [3 -1 -3] 5 3 6 73
1 3 [-1 -3 5] 3 6 75
1 3 -1 [-3 5 3] 6 75
1 3 -1 -3 [5 3 6] 76
1 3 -1 -3 5 [3 6 7]7

7.2、题解

由于滑动窗口的性质其实很像一个队列,我们可以维护一个单调递减队列作为判断最大值的辅助,队列长度为k,当队列为空时将数压入队列,当后续的数要进来时,判断想要入队列的数与队尾的当前元素的大小,维护单调队列:

  • 队尾元素小于新增元素,则弹出队尾元素直至队尾元素大于新增元素
  • 队尾元素大于新增元素,则正常入队

形成窗口后,left变动时要判断当前边界值是否是队列的队首元素,如果是的话,下次滑动窗口后,队首元素不在窗口内了,得出队。

function maxSlidingWindow(nums: number[], k: number): number[] {
    if(k === 1)
        return nums;
    let tmpQue = [];
    let res = [];
    let right = 0;
    for(right = 0; right < nums.length; right++){
        // 维护单调递减队列
        while(tmpQue.length != 0 && tmpQue[tmpQue.length - 1] <  nums[right]){
            tmpQue.pop();
        }
        tmpQue.push(nums[right]);

        let left = right - k + 1;
        if(left < 0)  // 窗口尚未形成
            continue;
        else{  // 窗口已经形成
            res.push(tmpQue[0]);
            // 如果左边界是当前最大值
            if(nums[left] == tmpQue[0]){
                tmpQue.shift();
            }
        }
    }
    return res;
};

八、队列的最大值

8.1、题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空,pop_front 和 max_value 需要返回 -1

输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

输入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
输出: [null,-1,-1]

8.2、题解

根据示例,题目的意思如下:

  • “MaxQueue” :生成队列,无需输入
  • “push_back” :向队列传入元素,需要输入一个数,输出null
  • “max_value” :求队列中的最大值,无需输入,输出当前队列中的最大值
  • “pop_front” : 删除队列头部元素,输出一个数

其本质类似求滑动窗口最大值的问题。这个队列可以看成是一个滑动窗口,入队就是将窗口的右边界右移,出队就是将窗口的左边界右移。维护一个单调递减队列,从而帮助存储队列的最大值。

class MaxQueue {
    myQueue:number[];
    maxQueue:number[];
    constructor() {
        this.myQueue = [];
        this.maxQueue = [];
    }

    max_value(): number {
        if(this.myQueue.length == 0)
            return -1;
        return this.maxQueue[0];
    }

    push_back(value: number): void {
        this.myQueue.push(value);
        while(this.maxQueue.length != 0 && this.maxQueue[this.maxQueue.length - 1] < value){
            this.maxQueue.pop();
        }
        this.maxQueue.push(value);
    }

    pop_front(): number {
        if(this.myQueue.length == 0)
            return -1;
        let res = this.myQueue.shift();
        if(res == this.maxQueue[0])
            this.maxQueue.shift();
        return res;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * var obj = new MaxQueue()
 * var param_1 = obj.max_value()
 * obj.push_back(value)
 * var param_3 = obj.pop_front()
 */

九、n个骰子的点数

9.1、题目描述

把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

9.2、题解

这题题目的意思是,输入1,也就是1个骰子,投出各个数值(1~6)的概率,也就是1/6 = 0.16667
输入2,也就是2个骰子,此时2个骰子的和范围为2~12,为2的概率为(两个骰子都为1),也就是1/6*1/6 = 1/36 = 0.02778。以此类推。

如果使用暴力法,2个骰子有6 × 6 = 36种情况,36种情况再汇聚成11种结果,但是如果题目n=11,那11个骰子有6的11次方情况,汇聚成61种结果,如此的话,时间复杂度会非常高。

这里选择动态规划方法:
设置dp[n][j]表示投掷完第n枚骰子后,点数和为j的次数那么

  • dp[1][1] = 1,dp[1][2] = 1 ... ... dp[1][6] = 1;
  • dp[2][1] = dp[1][1](在第一次投出1的情况下,此次投出1) = 1; dp[2][3] = dp[1][1](在第一次投出1的情况下,此次投出2) + dp[1][2](在第一次投出2的情况下,此次投出1) = 2; dp[2][4] = dp[1][1] + dp[1][2] + dp[1][3] = 3 ....
  • 推理可以得出状态转移方程:d[n][j] = dp[n - 1][j - 1] + dp[n - 1][j - 2] + dp[n - 1][j - 3] + … + dp[n - 1][j - 6] ,即第n个骰子投完后,出现和为j的概率,由第n-1个骰子投完后,第n个骰子投出1,2,3,4,5,6的情况之和。

故可以由此编码:

function dicesProbability(n: number): number[] {
     let dp = new Array(n + 1).fill(0).map(i => new Array(6 * n + 1).fill(0));
     for(let j = 1; j <= 6; j++){
         dp[1][j] = 1;
     }
     for(let i = 2; i <= n; i++){
        //  最小值到最大值
         for(let j = i; j<=6*i; j++){
            //  第i个骰子从1到6的情况
             for(let k = 1; k <= 6; k++){
                //  不要算dp[k - 1][j - k]为负的情况,不可能存在
                if(j - k <= 0){
                    break;
                 }
                dp[i][j] = dp[i - 1][j - k] + dp [i][j];
             }
         }
     }
    let all = Math.pow(6, n);
    let res:number[] = [];
    // 收集n到6*n的结果集次数
    for(let i = n; i <= 6 *n; i++){
        res.push(dp[n][i]/all);
    }
    return res;
};

十、扑克牌中的顺子

10.1、题目描述

从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

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

输入: [0,0,1,2,5]
输出: True

10.2、题解

这题要注意的是A为1,故10 J Q K A不能算顺子,而0是大小王,且可以五张都是。
要打出顺子,有两个特点:

  1. 除了0可以重复,其他数不能重复(不然顺子里面会出现对,如3,4,4,5,6、0,3,4,5,5不符合要求)
  2. 最大值减去最小值应该小于5,比如2,3,4,5,6、2,0,0,4,5
  3. 数字最大为14,最小为0
function isStraight(nums: number[]): boolean {
    let storeSet: Set<number> = new Set();
    let max = 1, min = 14;
    for(let i = 0 ; i < nums.length; i++){
        if(nums[i] !=0){
            // 判断是否出现其他不在扑克牌的数字
            if(nums[i] > 14 || nums[i] < 1){
                return false;
            }
            // 判断是否有重复数字(除0之外)
            if(storeSet.has(nums[i]))
                return false;
            storeSet.add(nums[i]);
            max = Math.max(max, nums[i]);
            min = Math.min(min,nums[i])
        }
    }
    return max - min < 5;
};
转载请注明出处或者链接地址:https://www.qianduange.cn//article/17246.html
评论
发布的文章

JWT(JSON WEB TOKEN)详解

2024-09-10 23:09:36

NPM 常用命令(十二)

2024-09-10 23:09:24

大家推荐的文章
会员中心 联系我 留言建议 回顶部
复制成功!