一支笔，一双手，一道力扣（Leetcode）做一宿！
在本文中，我们将使用TypeScript来解决剑指offer的算法题。这些问题涵盖了各种各样的主题，包括数组、字符串、链表、树、排序和搜索等。我们将使用TypeScript的强类型和面向对象的特性来解决这些问题，并通过实际的代码示例来演示如何使用TypeScript来解决算法问题。
本章节包括的题目有（难度是我个人感受的难度，非官方标准）：
题目 | 难度 |
|---|---|
平衡二叉树 | 简单 |
数组中数字出现的次数 | 中等 |
数组中数字出现的次数 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位：
代码语言：javascript复制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函数，可以将字符串以" "为
代码语言：javascript复制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变动时要判断当前边界值是否是队列的队首元素，如果是的话，下次滑动窗口后，队首元素不在窗口内了，得出队。
代码语言：javascript复制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” ： 删除队列头部元素，输出一个数
其本质类似求滑动窗口最大值的问题。这个队列可以看成是一个滑动窗口，入队就是将窗口的右边界右移，出队就是将窗口的左边界右移。维护一个单调递减队列，从而帮助存储队列的最大值。
代码语言：javascript复制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的情况之和。
故可以由此编码：
代码语言：javascript复制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;
};
