共计 12210 个字符,预计需要花费 31 分钟才能阅读完成。
首发于微信公众号《前端成长记》,写于 2019.11.21
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
- 题目分析设想
- 编写代码验证
- 查阅他人解法
- 思考总结
目录
- 67. 二进制求和
- 69.x 的平方根
- 70. 爬楼梯
- 83. 删除排序链表中的重复元素
- 88. 合并两个有序数组
Easy
67. 二进制求和
题目地址
题目描述
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1
和 0
。
示例:
输入: a = "11", b = "1"
输出: "100"
输入: a = "1010", b = "1011"
输出: "10101"
题目分析设想
这道题又是一道加法题,所以记住下,直接转数字进行加法可能会溢出,所以不可取。所以我们需要遍历每一位来做解答。我这有两个大方向:补 0 后遍历,和不补 0 遍历。但是基本的依据都是本位相加,逢 2 进 1 即可,类似手写 10 进制加法。
- 补 0 后遍历,可以采用先算出的位数推入数组最后反转,也可以采用先算出的位数填到对应位置后直接输出
- 不补 0 遍历,根据短数组的长度进行遍历,长数组剩下的数字与短数组生成的进位进行计算
查阅他人解法
Ⅰ. 补 0 后遍历,先算先推
代码:
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {let times = Math.max(a.length, b.length) // 需要遍历次数
// 补 0
while(a.length < times) {a = '0' + a}
while(b.length < times) {b = '0' + b}
let res = []
let carry = 0 // 是否进位
for(let i = times - 1; i >= 0; i--) {const num = carry + (a.charAt(i) | 0) + (b.charAt(i) | 0)
carry = num >= 2 ? 1 : 0
res.push(num % 2)
}
if (carry === 1) {res.push(1)
}
return res.reverse().join('')
};
结果:
- 294/294 cases passed (68 ms)
- Your runtime beats 95.13 % of javascript submissions
- Your memory usage beats 72.58 % of javascript submissions (35.4 MB)
- 时间复杂度
O(n)
Ⅱ. 补 0 后遍历,按位运算
代码:
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {let times = Math.max(a.length, b.length) // 需要遍历次数
// 补 0
while(a.length < times) {a = '0' + a}
while(b.length < times) {b = '0' + b}
let res = []
let carry = 0 // 是否进位
for(let i = times - 1; i >= 0; i--) {res[i] = carry + (a.charAt(i) | 0) + (b.charAt(i) | 0)
carry = res[i] >= 2 ? 1 : 0
res[i] %= 2
}
if (carry === 1) {res.unshift(1)
}
return res.join('')
};
结果:
- 294/294 cases passed (60 ms)
- Your runtime beats 99.65 % of javascript submissions
- Your memory usage beats 65.82 % of javascript submissions (35.5 MB)
- 时间复杂度
O(n)
Ⅲ. 不补 0 遍历
当然处理方式还是可以选择上面两种,我这就采用先算先推来处理了。
代码:
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {let max = Math.max(a.length, b.length) // 最大长度
let min = Math.min(a.length, b.length) // 最大公共长度
// 将长字符串拆成两部分
let left = a.length > b.length ? a.substr(0, a.length - b.length) : b.substr(0, b.length - a.length)
let right = a.length > b.length ? a.substr(a.length - b.length) : b.substr(b.length - a.length)
// 公共长度部分遍历
let rightRes = []
let carry = 0
for(let i = min - 1; i >= 0; i--) {const num = carry + (right.charAt(i) | 0) + (((a.length > b.length ? b : a)).charAt(i) | 0)
carry = num >= 2 ? 1 : 0
rightRes.push(num % 2)
}
let leftRes = []
for(let j = max - min - 1; j >= 0; j--) {const num = carry + (left.charAt(j) | 0)
carry = num >= 2 ? 1 : 0
leftRes.push(num % 2)
}
if (carry === 1) {leftRes.push(1)
}
return leftRes.reverse().join('') + rightRes.reverse().join('')
};
结果:
- 294/294 cases passed (76 ms)
- Your runtime beats 80.74 % of javascript submissions
- Your memory usage beats 24.48 % of javascript submissions (36.2 MB)
- 时间复杂度
O(n)
查阅他人解法
看到一些细节上的区别,我这使用 '1' | 0
来转数字,有的使用 ''1' - '0''
。另外还有就是初始化结果数组长度为最大长度加 1 后,最后判断首位是否为 0 需要剔除的,我这使用的是判断最后是否还要进位补 1。
这里还看到用一个提案中的 BigInt
类型来解决的
Ⅰ.BigInt
代码:
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {return (BigInt("0b"+a) + BigInt("0b"+b)).toString(2);
};
结果:
- 294/294 cases passed (52 ms)
- Your runtime beats 100 % of javascript submissions
- Your memory usage beats 97.05 % of javascript submissions (34.1 MB)
- 时间复杂度
O(1)
思考总结
通过 BigInt
的方案我们能看到,使用原生方法确实性能更优。简单说一下这个类型,目前还在提案阶段,看下面的等式基本就能知道实现原理自己写对应 Hack
来实现了:
BigInt(10) = '10n'
BigInt(20) = '20n'
BigInt(10) + BigInt(20) = '30n'
虽然这种方式很友好,但是还是希望看到加法题的时候,能考虑到遍历按位处理。
69.x 的平方根
题目地址
题目描述
实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例:
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
题目分析设想
同样,这里类库提供的方法 Math.sqrt(x)
就不说了,这也不是本题想考察的意义。所以这里有几种方式:
- 暴力法,这里不用考虑溢出是因为 x 没溢出,所以即使加到平方根加 1,也会终止循环
- 二分法,直接取中位数运算,可以快速排除当前区域一半的区间
编写代码验证
Ⅰ. 暴力法
代码:
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {if (x === 0) return 0
let i = 1
while(i * i < x) {i++}
return i * i === x ? i : i - 1
};
结果:
- 1017/1017 cases passed (120 ms)
- Your runtime beats 23 % of javascript submissions
- Your memory usage beats 34.23 % of javascript submissions (35.7 MB)
- 时间复杂度
O(n)
Ⅱ. 二分法
代码:
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {if (x === 0) return 0
let l = 1
let r = x >>> 1
while(l < r) {
// 这里要用大于判断,所以取右中位数
const mid = (l + r + 1) >>> 1
if (mid * mid > x) {r = mid - 1} else {l = mid}
}
return l
};
结果:
- 1017/1017 cases passed (76 ms)
- Your runtime beats 96.08 % of javascript submissions
- Your memory usage beats 59.17 % of javascript submissions (35.5 MB)
- 时间复杂度
O(log2(n))
查阅他人解法
这里看见了两个有意思的解法:
- 2 的幂次底层优化
- 牛顿法
Ⅰ. 幂次优化
稍微解释一下,二分法需要做乘法运算,他这里改用加减法
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let l = 0
let r = 1 << 16 // 2 的 16 次方,这里我猜是因为上限 2^32 所以取一半
while (l < r - 1) {const mid = (l + r) >>> 1
if (mid * mid <= x) {l = mid} else {r = mid}
}
return l
};
结果:
1017/1017 cases passed (72 ms)
Your runtime beats 98.46 % of javascript submissions
Your memory usage beats 70.66 % of javascript submissions (35.4 MB)
- 时间复杂度
O(log2(n))
Ⅱ. 牛顿法
算法说明:
在迭代过程中,以直线代替曲线,用一阶泰勒展式(即在当前点的切线)代替原曲线,求直线与 xx 轴的交点,重复这个过程直到收敛。
首先随便猜一个近似值 x
,然后不断令 x
等于 x
和 a/x
的平均数,迭代个六七次后 x
的值就已经相当精确了。
公式可以写为 X[n+1]=(X[n]+a/X[n])/2
代码:
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {if (x === 0 || x === 1) return x
let a = x >>> 1
while(true) {
let cur = a
a = (a + x / a) / 2
// 这里是为了消除浮点运算的误差,1e- 5 是我试出来的
if (Math.abs(a - cur) < 1e-5) {return parseInt(cur)
}
}
};
结果:
- 1017/1017 cases passed (68 ms)
- Your runtime beats 99.23 % of javascript submissions
- Your memory usage beats 9.05 % of javascript submissions (36.1 MB)
- 时间复杂度
O(log2(n))
思考总结
这里就提一下新接触的牛顿法吧,实际上是牛顿迭代法,主要是迭代操作。由于在单根附近具有平方收敛,所以可以转换成线性问题去求平方根的近似值。主要应用场景有这两个方向:
- 求方程的根
- 求解最优化问题
70. 爬楼梯
题目地址
题目描述
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n
是一个正整数。
示例:
输入:2
输出:2
解释:有两种方法可以爬到楼顶。1. 1 阶 + 1 阶
2. 2 阶
输入:3
输出:3
解释:有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
题目分析设想
这道题很明显可以用动态规划和斐波那契数列来求解。然后我们来看看其他正常思路,如果使用暴力法的话,那么复杂度将会是 2^n
,很容易溢出,但是如果能够优化成 n
的话,其实还可以求解的。所以这道题我就从以下三个方向来作答:
- 哈希递归,也就是暴力运算的改进版,通过存下算过的值降低复杂度
- 动态规划
- 斐波那契数列
编写代码验证
Ⅰ. 哈希递归
代码:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {let hash = {}
return count(0)
function count (i) {if (i > n) return 0
if (i === n) return 1
// 这步节省运算
if(hash[i] > 0) {return hash[i]
}
hash[i] = count(i + 1) + count(i + 2)
return hash[i]
}
};
结果:
- 45/45 cases passed (52 ms)
- Your runtime beats 98.67 % of javascript submissions
- Your memory usage beats 48.29 % of javascript submissions (33.7 MB)
- 时间复杂度
O(n)
Ⅱ. 动态规划
代码:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {if (n === 1) return 1
if (n === 2) return 2
// dp[0] 多一位空间,省的后面做减法
let dp = new Array(n + 1).fill(0)
dp[1] = 1
dp[2] = 2
for(let i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
};
结果:
- 45/45 cases passed (48 ms)
- Your runtime beats 99.48 % of javascript submissions
- Your memory usage beats 21.49 % of javascript submissions (33.8 MB)
- 时间复杂度
O(n)
Ⅲ. 斐波那契数列
其实斐波那契数列就可以用动态规划来实现,所以下面的代码思路很相似。
代码:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {if (n === 1) return 1
if (n === 2) return 2
let num1 = 1
let num2 = 2
for(let i = 3; i <= n; i++) {
let count = num1 + num2
num1 = num2
num2 = count
}
// 相当于 fib(n)
return num2
};
结果:
- 45/45 cases passed (56 ms)
- Your runtime beats 95.49 % of javascript submissions
- Your memory usage beats 46.1 % of javascript submissions (33.7 MB)
- 时间复杂度
O(n)
查阅他人解法
查看题解发现这么几种解法:
- 斐波那契公式(原来有计算公式可以直接用,尴尬)
- Binets 方法
- 排列组合
Ⅰ. 斐波那契公式
代码:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {const sqrt_5 = Math.sqrt(5)
// 由于 F0 = 1,所以相当于需要求 n+1 的值
const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2, n + 1)
return Math.round(fib_n / sqrt_5)
};
结果:
- 45/45 cases passed (52 ms)
- Your runtime beats 98.67 % of javascript submissions
- Your memory usage beats 54.98 % of javascript submissions (33.6 MB)
- 时间复杂度
O(log(n))
Ⅱ.Binets 方法
算法说明:
使用矩阵乘法来得到第 n 个斐波那契数。注意需要将初始项从 fib(2)=2,fib(1)=1
改成 fib(2)=1,fib(1)=0
,来达到矩阵等式的左右相等。
解法参考官方题解
代码:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {function pow(a, n) {let ret = [[1,0],[0,1]] // 矩阵
while(n > 0) {if ((n & 1) === 1) {ret = multiply(ret, a)
}
n >> 1
a = multiply(a, a)
}
return ret;
}
function multiply(a, b) {let c = [[0,0], [0,0]]
for (let i = 0; i < 2; i++) {for(let j = 0; j < 2; j++) {c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
}
}
return c
}
let q = [[1,1], [1, 0]]
let res = pow(q, n)
return res[0][0]
};
结果:
测试用例可以输出,提交发现超时。
这个笔者还没完全理解,所以很抱歉,暂时没有 js 相应代码分析,后续会补上。也欢迎您补充给我,感谢!
Ⅲ. 排列组合
代码:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
// n 个台阶走 i 次 1 阶和 j 次 2 阶走到,推导出 i + 2*j = n
function combine(m, n) {if (m < n) [m, n] = [n, m];
let count = 1;
for (let i = m + n, j = 1; i > m; i--) {
count *= i;
if (j <= n) count /= j++;
}
return count;
}
let total = 0;
// 取出所有满足条件的解
for (let i = 0,j = n; j >= 0; j -= 2, i++) {total += combine(i, j);
}
return total;
};
结果:
- 45/45 cases passed (60 ms)
- Your runtime beats 87.94 % of javascript submissions
- Your memory usage beats 20.72 % of javascript submissions (33.8 MB)
- 时间复杂度
O(n^2)
思考总结
这种叠加的问题,首先就会想到动态规划的解法,刚好这里又满足斐波那契数列,所以我是推荐首选这两种解法。另外通过查看他人解法学到了斐波那契公式,以及站在排列组合的角度去解,开拓了思路。
83. 删除排序链表中的重复元素
题目地址
题目描述
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例:
输入: 1->1->2
输出: 1->2
输入: 1->1->2->3->3
输出: 1->2->3
题目分析设想
注意一下,给定的是一个排序链表,所以只需要依次更改指针就可以直接得出结果。当然,也可以使用双指针来跳过重复项即可。所以这里有两个方向:
- 直接运算,通过改变指针指向
- 双指针,通过跳过重复项
如果是无序链表,我会建议先得到所有值然后去重后(比如通过 Set)生成新链表作答。
编写代码验证
Ⅰ. 直接运算
代码:
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
// 复制一个用做操作,由于对象是传址,所以改指针指向即可
let cur = head
while(cur !== null && cur.next !== null) {if (cur.val === cur.next.val) { // 值相等
cur.next = cur.next.next
} else {cur = cur.next}
}
return head
};
结果:
- 165/165 cases passed (76 ms)
- Your runtime beats 87.47 % of javascript submissions
- Your memory usage beats 81.21 % of javascript submissions (35.5 MB)
- 时间复杂度
O(n)
Ⅱ. 双指针法
代码:
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
// 新建哨兵指针和当前遍历指针
if (head === null || head.next === null) return head
let pre = head
let cur = head
while(cur !== null) {
debugger
if (cur.val === pre.val) {
// 当前指针移动
cur = cur.next
} else {
pre.next = cur
pre = cur
}
}
// 最后一项如果重复需要把 head.next 指向 null
pre.next = null
return head
};
结果:
- 165/165 cases passed (80 ms)
- Your runtime beats 77.31 % of javascript submissions
- Your memory usage beats 65.1 % of javascript submissions (35.7 MB)
- 时间复杂度
O(n)
查阅他人解法
忘记了,这里确实还可以使用递归来作答。
Ⅰ. 递归法
代码:
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {if(head === null || head.next === null) return head
if (head.val === head.next.val) { // 值相等
return deleteDuplicates(head.next)
} else {head.next = deleteDuplicates(head.next)
}
return head
};
结果:
- 165/165 cases passed (80 ms)
- Your runtime beats 77.31 % of javascript submissions
- Your memory usage beats 81.21 % of javascript submissions (35.5 MB)
- 时间复杂度
O(n)
思考总结
关于链表的题目一般都是通过修改指针指向来作答,区分单指针和双指针法。另外,遍历也是可以实现的。
88. 合并两个有序数组
题目地址
题目描述
给定两个有序整数数组 nums1
和 nums2
,将 nums2
合并到 nums1
中,使得 num1
成为一个有序数组。
说明:
- 初始化
nums1
和nums2
的元素数量分别为m
和n
。 - 你可以假设
nums1
有足够的空间(空间大小大于或等于m + n
)来保存nums2
中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
题目分析设想
之前我们做过删除排序数组中的重复项,其实这里也类似。可以从这几个方向作答:
- 数组合并后排序
- 遍历数组并进行插入
- 双指针法,轮流比较
但是由于题目有限定空间都在 nums1
,并且不要写 return
,直接在 nums1
上修改,所以我这里主要的思路就是遍历,通过 splice
来修改数组。区别就在于遍历的方式方法。
- 从前往后
- 从后往前
- 合并后排序再赋值
编写代码验证
Ⅰ. 从前往后
代码:
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
// 两个数组对应指针
let p1 = 0
let p2 = 0
// 这里需要提前把 nums1 的元素拷贝出来,要不然比较赋值后就丢失了
let cpArr = nums1.splice(0, m)
// 数组指针
let p = 0
while(p1 < m && p2 < n) {
// 先赋值,再进行 + 1 操作
nums1[p++] = cpArr[p1] < nums2[p2] ? cpArr[p1++] : nums2[p2++]
}
// 已经有 p 个元素了,多余的元素要删除,剩余的要加上
if (p1 < m) {// 剩余元素,p1 + m + n - p = m + n - (p - p1) = m + n - p2
nums1.splice(p, m + n - p, ...cpArr.slice(p1, m + n - p2))
}
if (p2 < n) {// 剩余元素,p2 + m + n - p = m + n - (p - p2) = m + n - p1
nums1.splice(p, m + n - p, ...nums2.slice(p2, m + n - p1))
}
};
结果:
- 59/59 cases passed (48 ms)
- Your runtime beats 100 % of javascript submissions
- Your memory usage beats 64.97 % of javascript submissions (33.8 MB)
- 时间复杂度
O(m + n)
Ⅱ. 从后往前
代码:
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {// 避免 nums1 = [0,0,0,0], nums2 = [1,2] 这种 nums1.length > nums2.length 并且 m = 0
nums1.splice(m, nums1.length - m)
// 两个数组对应指针
let p1 = m - 1
let p2 = n - 1
// 数组指针
let p = m + n - 1
while(p1 >= 0 && p2 >= 0) {
// 先赋值,再进行 - 1 操作
nums1[p--] = nums1[p1] < nums2[p2] ? nums2[p2--] : nums1[p1--]
}
// 可能 nums2 有剩余,由于指针是下标,所以截取数量需要加 1
nums1.splice(0, p2 + 1, ...nums2.slice(0, p2 + 1))
};
结果:
- 59/59 cases passed (52 ms)
- Your runtime beats 99.76 % of javascript submissions
- Your memory usage beats 78.3 % of javascript submissions (33.6 MB)
- 时间复杂度
O(m + n)
Ⅲ. 合并后排序再赋值
代码:
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {arr = [].concat(nums1.splice(0, m), nums2.splice(0, n))
arr.sort((a, b) => a - b)
for(let i = 0; i < arr.length; i++) {nums1[i] = arr[i]
}
};
结果:
- 59/59 cases passed (64 ms)
- Your runtime beats 90.11 % of javascript submissions
- Your memory usage beats 31.21 % of javascript submissions (34.8 MB)
- 时间复杂度
O(m + n)
查阅他人解法
这里看到一个直接用两次 while
,然后直接用 m/n
来计算下标的,没有额外空间,但是本质上也是从后往前遍历。
Ⅰ. 两次 while
代码:
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {// 避免 nums1 = [0,0,0,0], nums2 = [1,2] 这种 nums1.length > nums2.length 并且 m = 0
// nums1.splice(m, nums1.length - m)
// 从后开始赋值
while(m !== 0 && n !== 0) {nums1[m + n - 1] = nums1[m - 1] > nums2[n - 1] ? nums1[--m] : nums2[--n]
}
// nums2 有剩余
while(n !== 0) {nums1[m + n - 1] = nums2[--n]
}
};
结果:
- 59/59 cases passed (56 ms)
- Your runtime beats 99.16 % of javascript submissions
- Your memory usage beats 64.26 % of javascript submissions (33.8 MB)
- 时间复杂度
O(m + n)
思考总结
碰到数组操作,会优先考虑双指针法,具体指针方向可以由题目逻辑来决定。
(完)
本文为原创文章,可能会更新知识点及修正错误,因此转载请保留原出处,方便溯源,避免陈旧错误知识的误导,同时有更好的阅读体验
如果能给您带去些许帮助,欢迎 ⭐️star 或 ✏️ fork
(转载请注明出处:https://chenjiahao.xyz)