TypeScript算法题实战——剑指 Offer篇（4）
原创
TypeScript算法题实战——剑指 Offer篇（4）
原创
在本文中，我们将使用TypeScript来解决剑指offer的算法题。这些问题涵盖了各种各样的主题，包括数组、字符串、链表、树、排序和搜索等。我们将使用TypeScript的强类型和面向对象的特性来解决这些问题，并通过实际的代码示例来演示如何使用TypeScript来解决算法问题。本章节包括的题目有：
题目 | 难度 |
|---|---|
礼物的最大价值 | 简单 |
最长不含重复字符的子字符串 | 简单 |
丑数 | 中等 |
第一个只出现一次的字符 | 简单 |
数组中的逆序对 | 困难 |
两个链表的第一个公共节点 | 简单 |
在排序数组中查找数字 I | 中等 |
0～n-1中缺失的数字 | 简单 |
二叉搜索树的第k大节点 | 简单 |
二叉树的深度 | 简单 |
一、礼物的最大价值
1.1、题目描述
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
1.2、题解
使用动态规划方法，原地更改grid数组，更改后的grid数组中，grid[i][j]表示当前走到第i行第j列作为终点最多可以获得的价值
可以得知第一行的数只可从左边到达，如grid[0][3]，只可能是从grid[0][0]、grid[0][1]、grid[0][2]依次走过来，不可能有其他方案，故grid[0][3]时最多获取的价值只有grid[0][0]+grid[0][1]+grid[0][2]+grid[0][3]
同理得知第一列的数只可从上边到达。如此即可初始化所有 grid[i][0]和grid[0][j]的状态
非第一行和第一列的状态方程为grid[i][j] = Math.max(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];，即选择左边和上边的较大的价值，与自身相加，即为到自身处时能够获取的最大价值：
function maxValue(grid: number[][]): number {
const m:number = grid.length;
const n:number = grid[0].length;
for(let i = 1 ; i < m; i++){
grid[i][0] = grid[i][0] + grid[i - 1][0];
}
for(let j = 1; j < n; j++){
grid[0][j] = grid[0][j] + grid[0][j - 1];
}
for(let i = 1; i < m; i++){
for(let j = 1; j < n; j++){
grid[i][j] = Math.max(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
}
}
return grid[m - 1][n - 1];
};二、最长不含重复字符的子字符串
2.1、题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
2.2、题解
方法一：队列+哈希表 使用队列，挨个存数字，如遇到重复，则从队首弹出元素直至弹出到不重复为止（使用哈希表来判断重复）
function lengthOfLongestSubstring(s: string): number {
let myQue:string[] = [];
let storeSet: Set<string> = new Set();
let maxLength: number = 0;
for(let i = 0; i < s.length; i++){
if(!storeSet.has(s[i]))
storeSet.add(s[i]);
else{
while(1){
let tmpStr = myQue.shift();
if(tmpStr == s[i])
break;
storeSet.delete(tmpStr);
}
}
myQue.push(s[i]);
if(myQue.length> maxLength)
maxLength = myQue.length;
}
return maxLength;
};方法二：动态规划+哈希map
遍历字符串，使用哈希map统计各个字符最后一次出现时的索引位置
使用动态规划，dp[j]表示以s[j]为结尾的“最长不重复子字符串”长度，设s[i]为与s[j]相同的上一个重复字符;
状态转移方程可以列为：
- 当i<0时，即没有找到，dp[j] = dp[j-1] + 1;
- 当dp[j - 1] < j - i，说明字符s[i]在子字符串dp[j - 1] 区间之外，也就是dp[j - 1]的状态不会影响本次计算，即dp[j] = dp[j - 1] + 1
- 当dp[j - 1] >= j - i，说明字符s[i]在子字符串dp[j - 1] 区间之内，也就是dp[j - 1]的状态会影响本次计算，他包含了本字符，强行加进来会导致字符重复，故dp[j] = j - i;
时间复杂度为O（N）空间复杂度为O（1）
function lengthOfLongestSubstring(s: string): number {
let myMap: Map<string, number> = new Map();
let maxLength:number = 0;
let tmp = 0;
let j = -1
for(let i = 0; i < s.length; i++){
if(myMap.has(s[i])){
j = myMap.get(s[i]);
}
myMap.set(s[i], i);
tmp = tmp < i - j ? (tmp + 1) : (i - j);
if(tmp > maxLength)
maxLength = tmp;
}
return maxLength;
};三、丑数
3.1、题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
3.2、题解
除了dp[0] = 1,所有丑数均是前面的丑数乘以2或者3或者5得到的,由此性质来做动态规划：
- 将前面求得的丑数记录下来，后面的丑数就是前面的某个丑数*2，*3，*5
- 但是问题来了，我怎么确定已知前面k-1个丑数，我怎么确定第k个丑数呢
- 采取用三个指针的方法，p2,p3,p5
index2指向的数字number2下一次永远*2，index2指向的数字number3下一次永远*3，index2指向的数字number5永远*5- 我们从
2*number2 3*number3 5*number5选取最小的一个数字，作为第k个丑数 - 如果
第K个丑数==2*number2，也就是说前面0-index2个丑数*2不可能产生比第K个丑数更大的丑数了，所以index2++ - index3,index5同理
- 返回第n个丑数
function nthUglyNumber(n: number): number {
let dp: number[] = [1];
let [index2, index3, index5] = [0, 0, 0];
let number2: number, number3:number, number5:number;
for(let i = 1; i < n; i++){
number2 = 2 * dp[index2];
number3 = 3 * dp[index3];
number5 = 5 * dp[index5];
dp[i] = Math.min(number2, number3, number5);
console.log(index2,index3,index5);
if(dp[i] == number2) index2++;
if(dp[i] == number3) index3++;
if(dp[i] == number5) index5++;
}
return dp[n - 1];
};四、第一个只出现一次的字符
4.1、题目描述
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1: 输入：s = “abaccdeff” 输出：‘b’
示例 2: 输入：s = “” 输出：’ ’
4.2、题解
使用哈希map存储数字出现的频次，遍历第二遍时找到第一个频次为1的字符
function firstUniqChar(s: string): string {
let storeMap:Map<string, number> = new Map();
for(let i = 0; i < s.length; i++){
if(storeMap.has(s[i])){
storeMap.set(s[i], storeMap.get(s[i] + 1));
}
else
storeMap.set(s[i], 1);
}
for(let i = 0; i < s.length; i++){
if(storeMap.get(s[i]) == 1)
return s[i];
}
return ' ';
};五、数组中的逆序对
5.1、题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1: 输入: [7,5,6,4] 输出: 5
解释：75,76,74,54,64
5.2、题解
使用归并排序来做，每次在右指针移动时计算贡献度，贡献度为左数组里左指针以后的元素个数（leftLength - i）。
如7,5,6,4，归并排序首先将其转成[7],[5],[6],[4]这四个小数组，然后分析[7]和[5]，7比5大，归并排序后为[5,7]，7对于逆序的贡献为1，分析[6]和[4]，6比4大，归并排序后为[4,6]，6对于逆序的贡献为1，
然后再分析[5,7]和[4,6]，排序的过程如下：首先变为[4,]，无贡献，然后变为[4,5]，5对于逆序的贡献为2 - 0 = 2，然后变为[4,5,6]，6对于逆序的贡献度为2 - 1 =1，最后变为[4,5,6,7]，贡献度总和为5。
function reversePairs(nums: number[]): number {
let cal = 0;
mergeSort(nums);
return cal;
function mergeSort(arr: number[]): number[] {
if(arr.length < 2){
return arr;
}
let mid = Math.floor(arr.length/2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left:number[], right:number[]):number[]{
let res = [];
let leftLength = left.length;
let rightLength = right.length;
let len = leftLength + rightLength;
for(let index = 0, i = 0, j = 0; index < len; index++){
// 左数组已经遍历完
if(i >= leftLength){
res[index] = right[j++];
}
// 右数组已经遍历完
else if(j >= rightLength){
res[index] = left[i++];
}
// 左数组当前指针指向的元素正常小于或者等于右数组当前指针指向的元素
else if(left[i] <= right[j]){
res[index] = left[i++];
}
// 左数组当前指针指向的元素大于右数组当前指针指向的元素
else{
res[index] = right[j++];
cal += leftLength - i;
}
}
return res;
}
};六、两个链表的第一个公共节点
6.1、题目描述
输入两个链表，找出它们的第一个公共节点。如：
6.2、题解
很经典的一道题目，可以使用哈希表法，先遍历一遍A链表，将结点存入哈希表当中，然后再遍历B链表，如果哈希表中存在该结点，则该结点就是第一个公共节点。
也可以使用双指针的解法，让A和B两个指针遍历一次自己的赛道后，交换赛道再跑一次即可，判断是否相交。
var getIntersectionNode = function(headA, headB) {
if(headA === null || headB === null)
return null;
let pA = headA, pB = headB;
while(pA != pB){
if(pA != null){
pA = pA.next;
}else{
pA = headB;
}
if(pB != null){
pB = pB.next;
}else{
pB = headA;
}
}
return pA;
};七、在排序数组中查找数字 I
7.1、题目描述
统计一个数字在排序数组中出现的次数。
示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
7.2、题解
使用两次二分法，先找到第一次出现target的数，再找到最后一次出现target的数，然后两者下标相减+1，即为等于target的数的个数。
function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
let first = -1;
let last = -1;
while(left <= right){
let middle = left + right >> 1;
if(nums[middle] == target){
first = middle;
right = middle - 1; // 核心
}else if(nums[middle] > target){
right = middle - 1;
}
else{
left = middle + 1;
}
}
left = 0, right = nums.length - 1;
while(left <= right){
let middle = left + right >> 1;
if(nums[middle] == target){
last = middle;
left = middle + 1; // 核心
}else if(nums[middle] > target){
right = middle - 1;
}
else{
left = middle + 1;
}
}
if(first == -1)
return 0;
else
return last - first + 1;
};八、0～n-1中缺失的数字
8.1、题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1: 输入: [0,1,3] 输出: 2
示例 2: 输入: [0,1,2,3,4,5,6,7,9] 输出: 8
8.2、题解
同样使用二分法，由于题目是一个从0到n-1的长度为n-1的递增排序数组，所以只需要判断nums[middle] == middle如果为True，说明左边的那一半没有问题，再看右边的这一半，如果为False，说明左边这一半有问题，看左边这一半。
function missingNumber(nums: number[]): number {
let left = 0;
let right = nums.length - 1;
let middle = 0;
while(left <= right){
middle = left + right >> 1;
if(nums[middle] == middle){
left = middle + 1;
}
else{
right = middle - 1;
}
}
// console.log(left, middle, right);
return left;
};九、二叉搜索树的第k大节点
9.1、题目描述
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
9.2、题解
这题利用二叉搜索树的性质，二叉搜索树的先序遍历即为从小到大的排序，那么要求第k大节点，即可以先先序遍历，然后输出倒数第k个结点（valArray.length - k）即可。
function kthLargest(root: TreeNode | null, k: number): number {
let valArray: number[] = [];
function traverse(root: TreeNode, valArray:number[]){
if(root == null)
return;
traverse(root.left,valArray);
valArray.push(root.val);
traverse(root.right,valArray);
}
traverse(root, valArray);
return valArray[valArray.length - k];
};十、二叉树的深度
10.1、题目描述
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度 3 。
10.2、题解
第一种方法，直接递归判断，当前树的最大深度= 1 + max（左子树的深度，右子树的深度）
function maxDepth(root: TreeNode | null): number {
if(root == null)
return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};第二种方法，层序遍历算总层数即可，关于层序遍历可以看：TypeScript算法题实战——二叉树篇
function maxDepth(root: TreeNode | null): number {
let res: number[][] = [];
let tmpList: TreeNode[] = [];
if(root !== null)
tmpList.push(root);
while(tmpList.length > 0){
let tmpArray:number[] = [];
for(let i = 0, length = tmpList.length; i < length; i++){
let tmpNode: TreeNode = tmpList.shift();
tmpArray.push(tmpNode.val);
if(tmpNode.left)
tmpList.push(tmpNode.left);
if(tmpNode.right)
tmpList.push(tmpNode.right);
}
res.push(tmpArray);
}
// console.log(res);
return res.length;
};🎉 支持我：点赞👍+收藏⭐️+留言📝
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
