Skip to content

RQsky/sword-refer-to-offer

Repository files navigation

剑指offer刷题笔记(JavaScript)

大厂SP冲!

题目都是leetcode->剑指offer的原题,文件命名规则是题号-简短的题目描述。 代码头部会写解法,但只是写了我认为常用的解法,不一定全面。 解法大都来源于leetcode的评论区。 本项目特色:

1. 会从python社区吸收优秀的解法,不只是JS社区。
2. 会尽可能多的使用JS特色的方法,比如尽量使用 *for...in...* 而不是用C语言那种模式。
3. 会标明易错点

位运算

56-1, 56-2

js 所有位运算符 左移 << 右移 >> 无符号右移 >>> 按位与 & 按位或 | 按位异或 ^ 按位取反 ~ 规律:

1. 右移不会移动符号位。左移可能覆盖符号位。无符号右移会移动符号位(这样符号位空了,会补0,所以操作结果必为正数,我觉得这是它叫做这个名字的原因)
2. 三种移位符号都是给空位补0,溢出的则删除。
3. 与,或,异或,取反都会操作符号位。
4. js 整数用32位表示,-1并不是把1的符号位变为1构成的,而是把最大的正整数(32位)的符号位变为1.同理-2是把第二大的正整数的符号位变为1.
5. 移位运算符优先级大于 &。

二分查找

53-1, 53-2

要点:

  1. 一般指针移动写:r = mid - 1l = mid + 1。这样不会陷入死循环。
  2. 循环条件写:l<=rl<r。一般来说,如果要找的target不一定在nums中,条件就是l<=r。当然53-1有点例外,他是非严格递增的。
  3. 不要怕排除正确答案,有可能有时候右指针指向了target左边,但是再往下循环都一直会移动左指针,最后左指针会指向右指针后面一位,依然会得正确解。
  4. 只需要考虑最后一层循环的两种情况[target-1, target], [target, target],考虑这两种情况下算法是否正确就行了。

数组解构赋值的使用

[a, b] = [b, a]

  1. 在数组中,如果a, b的索引必然不同,则可以使用。如果可能相同,即和自己互换,会出问题。—— 21, 38, 40, 45 题。
  2. 在链表中,使用应该没问题,24, 25 题。
  3. 在树中使用,有问题,别用。27 题。

TODO

  1. 41-50差2个困难1个中等。
  2. 19
  3. 61-70

Author

  • RQsky - 中科院退学边缘硕士,懒狗

About

coding notes

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published