目录
- 一、平衡二叉树
- 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、题解
首先想到的是哈希表法，维护一个哈希Map，key为nums[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 7 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 6 |
| 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是大小王，且可以五张都是。
要打出顺子，有两个特点：
- 除了0可以重复，其他数不能重复（不然顺子里面会出现对，如3,4,4,5,6、0,3,4,5,5不符合要求）
- 最大值减去最小值应该小于5，比如2,3,4,5,6、2,0,0,4,5
- 数字最大为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; };
