剑指Offer

没做的题目 x <= 6, 11, 12

API

Math对象

字符串

  1. 'a '.trim() // 'a' 去除字符串前后两端的空白，包括换行符

题型技巧

找序列中某两个符合条件的值(重复，相反，和为x)

暴力两重循环

Map

在找重复出现的值的时候不一定要采用两重循环，可以考虑使用Map对象以及一次迭代遍历。这样可以将时间复杂度降低为O(n)。
在此基础上，map其实是插入和删除更占优势。读取速度上不如对象和数组。因此也可以将Map对象更换成对象或者类数组。

类型转换

字符串转数字

  1. +'00025'  // 25
  2. parseInt('00025') // 25
  3. Number('00025') // 25

反转

反转数字

  • 转变成字符串反转再转成数字
  • 通过对原数进行循环除以10，结果数从0开始累加原数对10的余数，以及积累乘10
  1.     // 回文数判断
  2.         ... // 省略一些开头的判断
  3.         var x = 12321;    
  4.     var reverseNum = 0;
  5.     while(x > reverseNum){
  6.         reverseNum = reverseNum * 10 + x % 10;
  7.         x = parseInt(x / 10);
  8.     }
  9.     return (reverseNum == x) || (parseInt(reverseNum / 10) == x);

反转字符串

  • 直接循环倒序输出
  • String.split()方法转成数组然后使用数组方法Array.reverse()将数组倒序，再使用Array.join()转换成字符串。更麻烦，比上一种方法差很多。

字符串出现的第一个位置

一个字符串在另一个字符串出现的第一个位置

  1. 'asss'.indexOf('ss') // 1

一个栈中的所有元素出栈

注意点：条件,for (let n = 0; n < array.length; n++)如果这样写，实际上array.length是一直在变化的，这样子的循环无法全部出栈

二分查找

版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++ 代码模板：

  1. int bsearch_1(int l, int r)
  2. {
  3.    while (l < r)
  4.    {
  5.        int mid = l + r >> 1;
  6.        if (check(mid)) r = mid;
  7.        else l = mid + 1;
  8.    }
  9.    return l;
  10. }

版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

C++ 代码模板：

  1. int bsearch_2(int l, int r)
  2. {
  3.    while (l < r)
  4.    {
  5.        int mid = l + r + 1 >> 1;
  6.        if (check(mid)) l = mid;
  7.        else r = mid - 1;
  8.    }
  9.    return l;
  10. }

这里用了最经典的两种取点的方法，注意第二种之所以要+1，是为了取到第二个中点，并且防止死循环。