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

这篇具有很好参考价值的文章主要介绍了TypeScript算法题实战——剑指 Offer篇(1)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Typescript 是 Javascript 的超集。Typescript 为 Javascript 增加类型能力,主要为了避免 JS 弱类型下产生的各种有意无意的问题。Typescript 的出现大大改善了开发体验,增强了代码的可维护性和稳定性,如今已被越来越多的大型前端项目选用。

【文末送书】:评论区抽一位朋友送出书籍《有趣的矩阵:看得懂又好看的线性代数》一本,包邮到家

本系列将使用TypeScript实战算法,题目全部来源于力扣题库:《剑指 Offer(第 2 版)》,本章节包括的题目有:

题目 难度
数组中重复的数字 简单
二维数组中的查找 中等
替换空格 简单
从尾到头打印链表 简单
重建二叉树 中等
用两个栈实现队列 简单
斐波拉契数列 简单
青蛙跳台阶问题 简单
旋转数组的最小数字 简单
矩阵中的路径 中等

一、数组中重复的数字

1.1、题目描述

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3

1.2、题解

①:哈希表解法
时间复杂度为O(n),空间复杂度为O(n)
本题可以采用哈希表来解很简单storeSet.has(nums[i])用于判断哈希表内是否有这个数。
不熟悉TypeScript哈希表的朋友可以看这一篇:TypeScript算法题实战——哈希表篇

function findRepeatNumber(nums: number[]): number {
    let storeSet: Set<number> = new Set();
    for(let i:number = 0; i < nums.length; i++){
        if(storeSet.has(nums[i])){
            return nums[i];
        }
        else{
            storeSet.add(nums[i]);
        }
    }
    return -1;
};

②:原地哈希解法(鸽巢原理/抽屉原理)
时间复杂度O(n),空间复杂度O(1)
这一步的原理简单来讲就是边做边交换让其排序到正确的位置,遍历数组,比如遍历第一个数为3,那么把第一个数和第个数进行交换,如果有重复的,在交换的时候你会发现要交换的数与本数相同,然后return出数字就好。

function findRepeatNumber(nums: number[]): number {
    for(let i:number = 0; i < nums.length; i++){
        while(nums[i] != i){
            if(nums[nums[i]] == nums[i])
                return nums[i];
            let tmp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = tmp;
        }
    }
    return -1;
};

二、二维数组中的查找

2.1、题目描述

在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

[ [1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30] ]
给定 target = 5,返回 true。
给定 target = 20,返回 false。

2.2、题解

站在右上角看。这个矩阵其实就像是一个Binary Search Tree(二叉搜索树),从右上开始算,target大于该数就向下,小于该数就向左。
时间复杂度O(n),空间复杂度O(1)

function findNumberIn2DArray(matrix: number[][], target: number): boolean {
    if(matrix.length == 0)
        return false;
    if(matrix[0].length == 0)
        return false;
    let x = 0;
    let y = matrix[0].length - 1;
    while(x < matrix.length && y > -1){
        if(matrix[x][y] == target)
            return true;
        if(matrix[x][y] < target){
            x++;
            continue;
        }
        if(matrix[x][y] > target){
            y--;
            continue;
        }
    }
    return false;
};

三、替换空格

3.1、题目描述

请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

示例 1:

输入:s = “We are happy.”
输出:“We%20are%20happy.”

3.2、题解

①、遍历
遇到“ ”在结尾加“%20”,遇到其他直接加
时间复杂度:O(n),空间复杂度O(n)

function replaceSpace(s: string): string {
    let res:string = "";
    for(let i of s){
        if(i===" ") 
            res+="%20";
        else 
            res+=i;
    }
    return res;
};

②、分割
首先使用split以空格为标识将s分割为数组,然后使用join把他们用“%20”连接起来。
时间复杂度:O(n) 空间复杂度O(n)

function replaceSpace(s: string): string {
    let arr: string[] = s.split(" ");
    return arr.join("%20");
};

四、 从尾到头打印链表

4.1、题目描述

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2] 输出:[2,3,1]

4.2、题解

①:迭代
遍历一次链表,使用数组记录值,然后再使用双指针倒转一次数组。

function reversePrint(head: ListNode | null): number[] {
    let res:number[] = [];
    let i = 0;
    while(head != null){
        res[i] = head.val;
        head = head.next;
        i++;
    }
    for (let i = 0, j = res.length - 1; i < j; i++, j--) {
        const c = res[i]
        res[i] = res[j]
        res[j] = c
    }
    return res;
};

②:递归
使用dfs,将最深层的最先放入数组中,每次先将当前节点的 next 指针进行递归处理,然后再将当前节点值加入数组,即可实现「从后往前」的顺序添加。

function reversePrint(head: ListNode | null): number[] {
    const ans: number[] = new Array<number>()
    function dfs(head: ListNode | null){
        if(head == null)
            return;
        dfs(head.next);
        ans.push(head.val);
    }
    dfs(head)
    return ans
};

五、重建二叉树

5.1、题目描述

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

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

5.2、题解

本题是经典已知前序和中序,重建二叉树:

  • 二叉树前序遍历的顺序为,先遍历根节点,随后递归地遍历左子树,最后递归遍历右子树。
  • 二叉树中序遍历的顺序为:先递归地遍历左子树,随后遍历根节点,最后递归遍历右子树。

前序遍历的第一个节点定然是当前树的根节点,构建树节点,拿 root 把中序遍历的数组劈开,左边为左子树,右边为右子树,递归操作就可以了。

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if(preorder.length == 0|| inorder.length ==0 )
        return null;
    let root: TreeNode = new TreeNode(preorder[0]);
    const currIndex = inorder.indexOf(preorder[0]);
    preorder.shift();

    root.left = buildTree(preorder, inorder.slice(0, currIndex));
    root.right = buildTree(preorder, inorder.slice(currIndex + 1));
    return root;
};

六、用两个栈实现队列

6.1、题目描述

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入: [“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”]
[[],[3],[],[],[]] 输出:[null,null,3,-1,-1]

示例 2:

输入:
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]] 输出:[null,-1,null,null,5,2]

6.2、题解

这题的题目已经在题目告诉我们,也就是要用两个栈构造一个队列,栈是先进后出,队列先进先出。那么构造两个栈,一个是输入栈一个是输出栈,在输入时,直接往输入栈中压栈就好了,在输出的时候,首先判断输出栈中有无元素,有则直接弹出,没有的话将输入栈的元素挨个弹出再压入输出栈中,做完这一步后,再弹出输出栈的元素就好。

class CQueue {
    instack: number[];
    outstack: number[];
    constructor() {
        this.instack = [];
        this.outstack = [];
    }

    appendTail(value: number): void {
        this.instack.push(value);
    }

    deleteHead(): number {
        if(this.outstack.length != 0)
            return this.outstack.pop();
        while(this.instack.length != 0){
            this.outstack.push(this.instack.pop());
        }
        if(this.outstack.length != 0)
            return this.outstack.pop();
        return -1;
    }
}

七、I. 斐波那契数列

7.1、题目描述

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

7.2、题解

这题若直接用简单递归肯定会超时,下面使用动态规划或者记忆递归来做。

①、动态规划
时间复杂度:O(n),空间复杂度:O(n)

function fib(n: number): number {
    let fidArray = [];
    fidArray[0] = 0;
    fidArray[1] = 1;
    for(let i = 2; i < n + 1; i++){
        fidArray[i] = (fidArray[i - 1] + fidArray[i -2]) % 1000000007; 
    }
    return fidArray[n];
};

②、记忆递归法
时间复杂度:O(n) 空间复杂度O(n)
使用一个Map<number, number>()记录已经算过的值,一key:value的方式存储,memory.has(n)用于判断是否算过key为n的值,memory.get(n)用于返回key为n的值。

function fib(n: number): number {
    let memory = new Map<number, number>();

    function fibMemory(n:number, memory:Map<number, number>){
        if(n == 1) return 1;
        if(n == 0) return 0;
        if(memory.has(n)){
        return memory.get(n);
        }
        let res = (fibMemory(n - 1, memory) + fibMemory(n - 2, memory)) %1000000007;
        memory.set(n, res);
        return res;
    }
    return fibMemory(n, memory)
};

八、II. 青蛙跳台阶问题

8.1、题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

8.2、题解

同斐波拉契数列,只不过初始fidArray[0] = 1;fidArray[1] = 1;,这样fidArray[2] = fidArray[0] + fidArray[1] = 2;

①、动态规划
时间复杂度O(n) 空间复杂度O(n)

function numWays(n: number): number {
    let fidArray = [];
    fidArray[0] = 1;
    fidArray[1] = 1;
    for(let i = 2; i < n + 1; i++){
        fidArray[i] = (fidArray[i - 1] + fidArray[i -2]) % 1000000007; 
    }
    return fidArray[n];
};

②、记忆递归
时间复杂度O(n) 空间复杂度O(n)

function numWays(n: number): number {
    let memory = new Map<number, number>();

    function fibMemory(n:number, memory:Map<number, number>){
        if(n == 1) return 1;
        if(n == 0) return 0;
        if(memory.has(n)){
        return memory.get(n);
        }
        let res = (fibMemory(n - 1, memory) + fibMemory(n - 2, memory)) %1000000007;
        memory.set(n, res);
        return res;
    }
    return fibMemory(n, memory)
};

九、 旋转数组的最小数字

9.1、题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一次旋转,该数组的最小值为 1。

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

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

9.2、题解

无论数组旋转过多少次,他们内部的链条是不会变的,依然还是一个环形,只是说这个环的开头变了,我们可以使用双指针进行二分法来解

function minArray(numbers: number[]): number {
    let left = 0;
    let right = numbers.length - 1;
    while(left != right){
        let mid = left +Math.floor((right - left) / 2);
        if(numbers[mid] > numbers[right]){
            left = mid + 1;
        }
        else if(numbers[mid] < numbers[right]){
            right = mid;
        }
        else{
            right = right - 1;
        }
    }
    return numbers[left];
};

十、矩阵中的路径

10.1、题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
TypeScript算法题实战——剑指 Offer篇(1)

示例 1:

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],
word = “ABCCED” 输出:true
示例 2:

输入:board = [[“a”,“b”],[“c”,“d”]], word = “abcd” 输出:false

10.2、题解

深度优先搜索算法,首先判断是否溢出边界,然后判断是否访问过(这里设置已访问过的元素置为空),然后判断是否等于当前所需字母,最后判断是否满足所需字符串长度。

在判断的时候,同时判断四个方向的情况,并用逻辑或连接他们的结果。

function exist(board: string[][], word: string): boolean {
    function dfs(i: number, j: number, index:number): boolean{
        if(i < 0 || i >= board.length)
            return false;
        if(j < 0 || j >= board[i].length)
            return false;
        if(board[i][j] == ' ')
            return false;
        if(board[i][j] != word[index])
            return false;
        if(index == word.length - 1)
            return true;
        
        let tempValue = board[i][j];
        board[i][j] = ' ';
        let res = dfs(i + 1, j, index + 1) || dfs(i -1, j, index + 1) || dfs(i, j + 1, index + 1) || dfs(i, j - 1, index + 1) ;
        board[i][j] = tempValue;
        return res;
    }

    for(let i = 0; i < board.length; i++){
        for(let j = 0; j < board[i].length; j++){
            if(dfs(i, j, 0)) return true;
        }
    }
    return false;
};

书籍推荐

TypeScript算法题实战——剑指 Offer篇(1)
京东购买链接:https://item.jd.com/13640773.html

【内容简介】

本书分别从中国古代数学思想益智游戏企业管理计算机科学博弈论等角度出发,介绍了线性代数和矩阵理论中的相关概念和理论在上述领域的应用。通过阅读本书,读者对线性代数在实际问题中的应用会有更加直观的了解,有助于激发读者对线性代数的学习兴趣和学习热情。

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

本书分为8章,涵盖的主要内容有线性方程组的计算益智数字游戏中的矩阵经营管理中的矩阵矩阵与图片美化计算机绘画中的矩阵矩阵与密码设计互联网中的矩阵矩阵与博弈论

本书内容通俗易懂、生动有趣,特别适合中学生、大学生及各年龄层的数学爱好者作为线性代数入门读物使用。另外,本书也适合作为各类大中专院校的教学参考书使用。

【适合人群】

多次迭代的线性代数硬核教程:理工生自学佳选,线性代数学习好帮手,内容千锤百炼,反复反馈、打磨、迭代,示例来源于生活,激发读者兴趣,降低理解难度。

  • 多图:数缺形时少直观,形少数时难入微,数形结合百般好。
  • 经典:内容千锤百炼,在使用中反复反馈、打磨、迭代。
  • 实战:示例来源于生活,激发读者兴趣,降低理解难度。
  • 硬核:多次迭代的硬核教程,线性代数学习好帮手。

【作者简介】

马婧瑛,博士,宁夏大学副教授,硕士生导师。发表高质量学术论文十余篇,获得宁夏自然科学优秀学术论文一等奖一项(排名第一)、二等奖一项(排名第二)。多年担任宁夏大学线性代数课程讲授工作。

汪文帅,博士,宁夏大学教授,博士生导师。兼任中国数学会理事、第二届中国智能物联系统建模与仿真专业委员会委员。发表高质量学术论文三十余篇,出版专著一部,曾获宁夏回族自治区科技进步二等奖、宁夏哲学社会科学优秀成果二等奖、宁夏回族自治区教学成果二等奖、宝钢优秀教师奖。

【活动介绍】

北京大学出版社,4月“423世界读书日”促销活动安排:
当当活动日期:4.6-4.11,4.18-4.23
京东活动日期: 4.6 一天, 4.17-4.23
活动期间满100减50或者半价5折销售
欢迎大家关注参与423读书日北大社促销活动文章来源地址https://www.toymoban.com/news/detail-413290.html

到了这里,关于TypeScript算法题实战——剑指 Offer篇(1)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • React框架:TypeScript支持的JavaScript库

    React 框架是一个功能强大的 JavaScript 库,让用户可以轻松地构建高度动态的用户界面。它借助虚拟 DOM 的思想实现高效的性能,并具有易于使用和灵活的编程接口。随着越来越多的人开始使用 React ,在不断的发展和变化中, React 框架现在加入了 TypeScript 的支持,使其成为一个

    2024年02月11日
    浏览(66)
  • TypeScript是什么?它与JavaScript有什么区别?

    面试题-TS(1):TypeScript是什么?它与JavaScript有什么区别? TypeScript是一种编程语言,它是JavaScript的超集。它通过添加静态类型、类、接口和模块等功能来扩展JavaScript。 JavaScript是一种广泛应用于Web开发的脚本语言,它的灵活性和易用性使得它成为了开发者们的首选。然而,JavaS

    2024年02月16日
    浏览(48)
  • TypeScript:为什么JavaScript需要类型检查?

    JavaScript是当今最为流行的编程语言之一。它是一种高级的、解释性的编程语言,用于Web应用程序的开发。然而,JavaScript的灵活性也是它的弱点之一。JavaScript中的变量、函数、类等都是动态类型,这意味着它们的类型可以在运行时发生变化。虽然这种灵活性为JavaScript开发人员

    2024年02月04日
    浏览(56)
  • typeof 在TypeScript中和JavaScript中的区别

            在TypeScript中和JavaScript中都有typeOf,但是作用用法却大有不同。 一、typeof用来判断数据类型返回结果: 基本数据类型:string,number,boolean,undefined 引用数据类型:object (不管是什么引用类型就返回object),function 二、typeof判断变量是否存在         ts中的typeof可

    2024年02月09日
    浏览(50)
  • Vue框架:适用于TypeScript的JavaScript框架

    Vue 是一个高效、灵活、易于学习的 JavaScript 框架,它采用了 MVVM 架构,能够快速构建交互式的用户界面。作为一种现代化的框架,Vue已经成为了许多开发者的首选,其中也包括了很多使用 TypeScript 的开发者。 Vue 框架的最大特点是轻量级、易于上手、灵活和高效,这一点也是

    2024年02月11日
    浏览(41)
  • TypeScript 从入门到精通:打造可靠、高效的现代 JavaScript

    TypeScript作为一种静态类型的编程语言,可以显著改善JavaScript项目的可维护性、可读性和开发效率。本篇博客将带你从入门到精通TypeScript,探索其强大的特性和用法。我们将深入了解基本类型和变量声明、函数和类、模块和命名空间等核心概念,并通过更多的案例代码帮助你

    2024年02月13日
    浏览(57)
  • 《剑指offer》(3)排序算法篇

    class Solution:     def duplicate(self , numbers: List[int]) - int:         if len(numbers) = 1:             return -1         import collections         num_dict = collections.Counter(numbers)         res = [key for (key,value) in num_dict.items() if value 1]         return res[0] class Solution:     def sort(self,num): #快排

    2024年02月13日
    浏览(38)
  • TypeScript:赋予JavaScript数据类型新的力量,提升编程效率!

    🎬 岸边的 风: 个人主页  🔥  个人专栏  : 《 VUE 》 《 javaScript 》 ⛺️  生活的理想,就是为了理想的生活 ! ​ TypeScript: 扩展 JavaScript 数据类型,赋予编程更强大的表达能力! 在现代Web开发中, TypeScript 已经成为了一种备受欢迎的编程语言。它不仅继承了 JavaScript 的

    2024年02月09日
    浏览(47)
  • TypeScript的魔法:如何轻松提升JavaScript项目的稳定性

    JavaScript,作为Web开发的核心语言,因其灵活性和广泛的应用受到开发者的喜爱。然而,这种灵活性也带来了挑战,尤其是在大型项目中,代码的维护和错误的追踪变得越来越困难。 TypeScript,起初被许多开发者视为“带类型的JavaScript”,但实际上,它远不止于此。确实,Ty

    2024年02月10日
    浏览(49)
  • 剑指 offer 动态规划算法题:丑数

    题目描述 :我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。 分析:         枚举法, 从 1 开始判断遍历,判断是否丑数(只有 2, 3, 5 作为因子),若是丑数 n 自减,直到 n 等于 1,返回即可。         动态规划法,

    2024年02月16日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包