Typescript 是 Javascript 的超集。Typescript 为 Javascript 增加类型能力，主要为了避免 JS 弱类型下产生的各种有意无意的问题。Typescript 的出现大大改善了开发体验，增强了代码的可维护性和稳定性，如今已被越来越多的大型前端项目选用。
本系列将使用TypeScript实战算法，题目全部来源于力扣题库：《剑指 Offer（第 2 版）》，本章节包括的题目有：
题目 | 难度 |
|---|---|
I. 剪绳子 | 中等 |
二进制中1的个数 | 简单 |
数值的整数次方 | 简单 |
删除链表的节点 | 简单 |
正则表达式匹配 | 简单 |
调整数组顺序使奇数位于偶数前面 | 简单 |
反转链表 | 中等 |
合并两个排序的链表 | 简单 |
树的子结构 | 中等 |
二叉树的镜像 | 中等 |
一、I. 剪绳子
1.1、题目描述
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1： 输入: 2 输出: 1 解释: 2 = 1 1, 1 × 1 = 1 示例 2: 输入: 10 输出: 36 解释: 10 = 3 3 4, 3 × 3 × 4 = 36
1.2、题解
可以先演算一遍，n=2时输出1*1=1，n=3时输出1*2=2，n=4时输出2*2=4，n=5时输出2*3=6，n=6时输出2*2*2=8，n=7时输出2*2*3=12，n=8时输出2*3*3=18，n=8时输出3*3*3=27… ，可以由数学知识推得
- 大于4的值都要拆，拆出来的乘积会比本身要大；
- 拆成
3*3要比拆成2*2*2要好，也就是说尽量多拆成3； - 所有数都可以拆成若干3和若干2。
由如上性质，可得先把数尽量拆出3，如果拆到这个数小于等于4时，就不要拆了，因为4拆与不拆都相等，低于4拆了反而更小。
时间复杂度：O（n） 空间复杂度：O（1）
代码语言：javascript复制function cuttingRope(n: number): number {
let res = 1;
if(n == 0 || n ==1)
return 0;
else if(n == 2)
return 1;
else if(n == 3)
return 2;
else if(n == 4)
return 4;
else{
while(n > 4){
n = n -3;
res = res * 3;
}
res = res * n;
}
return res;
};在：II. 剪绳子 中原理相同，若2 <= n <= 1000，计算时取模 1e9 7（1000000007）就好：
function cuttingRope(n: number): number {
let res = 1;
if(n == 0 || n ==1)
return 0;
else if(n == 2)
return 1;
else if(n == 3)
return 2;
else if(n == 4)
return 4;
else{
while(n > 4){
n = n -3;
res = res * 3;
res = res % 1000000007
}
res = res * n ;
}
return res % 1000000007;
};二、二进制中1的个数
2.1、题目描述
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
2.2、题解
①、使用与运算遍历
使用n&(1<<i)将左移i位的1与n进行按位与，即为保留n的第i位，其余位置零。
时间复杂度：O（k），空间复杂度：O（1）
var hammingWeight = function(n) {
let res = 0;
for (let i = 0; i < 32; i ) {
if ((n & (1 << i)) !== 0) {
res ;
}
}
return res;
};②、巧用n &= n - 1
n-1和n的区别在于，n-1是在二进制n中将最右边的1变为0，此1右边的0全部变成1。
n &= n - 1计算后，n中最右边的1变为0，其余不变（此1右边全部为0）
这样就可以计一次，如此循环下去直到n &= n - 1为0,时间复杂度O（logn），空间复杂度O（1）：
代码语言：javascript复制var hammingWeight = function(n) {
let res = 0;
while (n) {
n &= n - 1;
res ;
}
return res;
};三、数值的整数次方
3.1、题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xnxn）。不得使用库函数，同时不需要考虑大数问题。
示例 1： 输入：x = 2.00000, n = 10 输出：1024.00000 示例 2： 输入：x = 2.10000, n = 3 输出：9.26100 示例 3： 输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
3.2、题解
单纯的用循环或者简单递归来做肯定会超时，这里需要拆解x 的 n 次幂函数，假设这里要求的是5959，首先可以拆解为54∗54∗5154∗54∗51，然后54=52∗52∗5054=52∗52∗50，然后52=51∗51∗5052=51∗51∗50,其实就是在递归中加入了位运算，将n拆为2的k次方×2的k次方×（剩下的2的1次方或者0次方），拆分我们可以使用位运算n >> 1即可以让n右移一位，n & 1可以分辨n为奇数还是偶数：
function myPow(x: number, n: number): number {
if (n == 0) return 1;
if (n == 1) return x;
if (n == -1) return 1 / x;
let half = myPow(x, n >> 1);
let mod = myPow(x, n & 1);
return half * half * mod;
};四、删除链表的节点
4.1、题目描述
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
4.2、题解
使用双指针方法，第一个指针指向当前节点，第二个指针指向当前节点的下一个节点。
首先判断第一个节点需不需要删除，如果需要删除则直接返回第二个指针就好了。
如果第一个节点不需要删除，则开始遍历链表，找到后执行 ptr1.next = ptr2.next，即可实现删除 ptr2节点。
时间复杂度：O（n）空间复杂度O（1）
代码语言：javascript复制function deleteNode(head: ListNode | null, val: number): ListNode | null {
let ptr1: ListNode = head;
let ptr2: ListNode = head.next;
if(ptr1.val == val)
return ptr2;
while(ptr1.next != null) {
if(ptr2.val == val){
ptr1.next = ptr2.next;
return head;
}
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return head;
};五、正则表达式匹配
5.1、题目描述
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
5.2、题解
本题采用的是动态规划分析，首先分别定义指针分析情况，s为待匹配字符串，p为匹配字符串。s使用dp状态来解，定义dp[i][j]为s前i个字符[0,i)是否能匹配p的前j个字符[0,j)。
首先dp[0][0] =true，然后开始判断s[i-1]和p[j-1],有如下情况：
s[i-1]==p[j-1]，说明当前指向的两个字符相同，不用考虑，dp[i][j] = dp[i-1][j-1];s[i-1]!=p[j-1]&&p[j-1]=='.'，此时p[j-1]中指向的是.，其是万能字符，直接相等就好，不用考虑，dp[i][j] = dp[i-1][j-1];s[i-1]!=p[j-1]&&p[j-1]=='*'，此时p[j-1]中指向的是*，可以匹配零个或多个前面的元素，而是否能取多个或1个字符要看j-2的字符是否和i-1的字符相同。因此首先要判断p[j-2]==s[i-1]3.1.p[j-2]==s[i-1]，p的j-2字符与s的i-1字符相同，可以让*进行匹配，这里有三种情况，即*取0个字符，取1个字符和取多个字符 3.2.p[j-2]=='.'，p的j-2字符为万能字符，可以让*进行匹配 3.3.p[j-2]!=s[i-1] 且也不是万能字符，无法匹配，dp[i][j] = false;
function isMatch(s: string, p: string): boolean {
if(s == null || p == null)
return false;
let dp = new Array(s.length 1);
for(let i = 0;i <= s.length;i ) {
dp[i] = new Array<boolean>(p.length 1).fill(false);
}
dp[0][0] = true;
for(let j = 1; j <= p.length; j ){
if(p[j-1] == '*'){
dp[0][j] = dp[0][j-2];
}
}
for(let i = 1; i <= s.length; i ){
for(let j = 1; j <= p.length; j ){
if(s[i-1] == p[j-1] || p[j-1] == '.'){
dp[i][j] = dp[i-1][j-1];
}
else if(p[j-1] == '*'){
if(s[i-1] != p[j-2] && p[j-2] != '.'){
dp[i][j] = dp[i][j-2];
}
else{
dp[i][j] = dp[i][j-2] || dp[i-1][j];
}
}
}
}
return dp[s.length][p.length];
};六、调整数组顺序使奇数位于偶数前面
6.1、题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例： 输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。
6.2、题解
比较简单，使用双指针不断向中部逼近就好了，nums[left]为奇数时，left ，nums[right]为偶数时，right --，若nums[left]为偶数，nums[right]为奇数时，则交换他们。
时间复杂度：O（n）空间复杂度：O（1）
代码语言：javascript复制function exchange(nums: number[]): number[] {
let left:number = 0;
let right:number = nums.length - 1;
while(left < right){
if(nums[left] % 2 == 1)
left ;
else if(nums[right] % 2 == 0)
right --;
else{
let tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left ;
right --;
}
}
return nums;
};七、反转链表
7.1、题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
7.2、题解
双指针法，先用tmp保存head结点的next，然后将head结点指向上一结点cur，然后两个结点（cur和head统一后移一位）。 时间复杂度：O（n）空间复杂度：O（1）
代码语言：javascript复制function reverseList(head: ListNode | null): ListNode | null {
if(head == null)
return null;
let cur: ListNode = null;
let temp: ListNode = null;
while(head){
temp = head.next;
head.next = cur;
cur = head;
head = temp;
}
return cur;
};八、合并两个排序的链表
8.1、题目描述
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
8.2、题解
使用递归法解决 时间复杂度：O（n）空间复杂度：O（1）
代码语言：javascript复制function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
if(l1 == null)
return l2;
if(l2 == null)
return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};九、树的子结构
9.1、题目描述
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
示例 1： 输入：A = [1,2,3], B = [3,1] 输出：false 示例 2： 输入：A = [3,4,5,1,2], B = [4,1] 输出：true
9.2、题解
使用深度优先搜索
代码语言：javascript复制function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
if(A == null || B == null)
return false;
function dfs(A:TreeNode, B:TreeNode):boolean {
if(B == null)
return true;
if(A == null)
return false;
return A.val===B.val && dfs(A.left, B.left)&&dfs(A.right, B.right);
}
return dfs(A, B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
};十、二叉树的镜像
10.1、题目描述
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
10.2、题解
从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转得到镜像。
代码语言：javascript复制function mirrorTree(root: TreeNode | null): TreeNode | null {
if(root == null)
return root;
let left:TreeNode|null = mirrorTree(root.left);
let right:TreeNode|null = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
};
