剑指offer

offer刷题分类汇总

数学运算

位运算的总结

image-20200607190632492

  • 非（NOT）操作。NOT a 结果为 a 的反转（即反码）

  • << (左移):类似于进位,抛弃高位向左,低位补0

  • >> (有符号右移)

  • >>> (无符号右移)

注意:

  • 左移相当于在乘以2倍,右移====除以2

不用加减乘除做加法

题目:

  • 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

思路:

  • 将加法拆解成三步：
    • 1.不进位相加
    • 2.计算进位
    • 3.进位与不进位结果进行相加
    • 重复这三步，直到进位值为0

使用位运算来计算二进制：

  • 二进制异或操作和不进位相加得到的结果相同(1^1=0 0^1=1 0^0=0)
  • 二进制与操作后左移和进位结果相同（1&1=1 1&0=0 0&0=0）

数组

，用于按顺序存储元素的集合。但是元素可以随机存取，因为数组中的每个元素都可以通过数组索引来识别。插入和删除时要移动后续元素，还要考虑扩容问题，插入慢。

1 双指针

  • 上面链表中提到的一类题目，主要是利用两个或多个不同位置的指针，通过速度和方向的变换解决问题。注意这种技巧经常在排序数组中使用。

1.1 和为S的两个数字

题目

  • 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路

  • 设置两个索引标志left,right,分别从左和右开始靠近,
  • 如果s>sum right–
  • s<sum left++
  • 返回当前的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function FindNumbersWithSum(array, sum)
{
    // write code here
  if(array&&array.length>0){
    var left = 0;
    var right = array.length-1;
    while(left<right){
      var s = array[left]+array[right]
      if(s>sum){
        right--;
      }else if(s<sum){
        left++
      }else{
        return [array[left],array[right]]
      }
    }
  }
  return []
}

1.2 调整数组的顺序时奇数在前面,偶数在后面

题目

  • 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分

思路

  • 分别保存起来
  • 在拼接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function reOrderArray(array)
{
    // write code here
 var odd = [];
  var even = [];
  for (var item of array){
    if(item%2==0){
      even.push(item)
    }else{
      odd.push(item)
    }
  }
  return [...odd,...even]
}

1.3 和为s的连续正整数序列

题目

输入一个正数S，打印出所有和为S的连续正数序列。

例如：输入15，有序1+2+3+4+5 = 4+5+6 = 7+8 = 15 所以打印出3个连续序列1-5，5-6和7-8

思路

  • 双指针法
  • 先定义两个指针,start = 1,end=2(有序的数组)
  • 判断条件start<end
  • curSum>sum->start++,反之end++
  • 相等的情况下,将start到end的值保存到输出数组序列中,

image-20200617094114690

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function FindContinuousSequence(sum)
{
    // write code here
  //定义数组保存输出序列
  var result = [];
  var end=2,start=1,curSum=3;
  while(start<end){
    if(curSum>sum){
      //先减去原先的start,
      curSum-=start;
      //start移动
      start++
    }else if(curSum<sum){
      end++;
      curSum+=end;
    }else{
      //相等的情况下,将start-end的值保存在当前的子数组中,保存在result中,
      var child =[]
      for(var i=start;i<=end;i++){
        child.push(i)
      }
      result.push(child)
      //start移动
      curSum-=start;
      start++;
      end++;
      curSum+=end;
    }
  }
  return result
}

2 数组之和

2.1 两数之和

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

思路

  • 使用一个map将遍历过的数字存起来，值作为key，下标作为值。

    对于每一次遍历：

    • 取map中查找是否有key为target-nums[i]的值
    • 如果取到了，则条件成立，返回。
    • 如果没有取到，将当前值作为key，下标作为值存入map

    时间复杂度：O(n)

    空间复杂度O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function twoSum(nums, target) {
  //借助map来存储
  const map = {}
  if (Array.isArray(nums)) {
    for (var i = 0; i < nums.length; i++) {
      //map可以直接进行存储
      if (map[target - nums[i]] !== undefined) {
        return [map[target - nums[i]], i]
      } else {
        map[nums[i]] = i;
      }
    }
  }
  return []
}

2.2 三数之和(leetcode)

题目

给定一个包含 n 个整数的数组nums，判断 nums 中是否存在三个元素a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意

答案中不可以包含重复的三元组。

思路

  • 1.为了方便去重，我们首先将数组排序
  • 2.对数组进行遍历，取当前遍历的数nums[i]为一个基准数，遍历数后面的数组为寻找数组
  • 3.在寻找数组中设定两个起点，最左侧的left(i+1)和最右侧的right(length-1)
  • 4.判断nums[i] + nums[left] + nums[right]是否等于0，如果等于0，加入结果，并分别将left和right移动一位
  • 5.如果结果大于0，将right向左移动一位，向结果逼近
  • 5.如果结果小于0，将left向右移动一位，向结果逼近
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function threeSum(numbers) {
  //定义变量来存储当前满足条件的数组
  var result = [];
  //排序方便去重
  numbers.sort((a, b) => a - b);

  //遍历
  for (var i = 0; i < numbers.length; i++) {
    //跳过重复的数字
    if (i && numbers[i] == numbers[i - 1]) {
      continue;
    }
    var left = i + 1;
    var right = numbers.length - 1;
    //双指针来查找
    while (left < right) {
      var sum = numbers[i] + numbers[left] + numbers[right];
      if (sum > 0) {
        right--
      } else if (sum < 0) {
        left++;
      } else {
        //相等的情况下,保存,left和right都要移动指针
        result.push([numbers[i], numbers[left++], numbers[right--]]);
        //left和right去重
        while (numbers[left] == numbers[left - 1]) {
          left++;
        }
        while (numbers[right] == numbers[right + 1]) {
          right--;
        }
      }
    }
  }
  return result
}

2.3 四数之和

题目

给定一个包含 n 个整数的数组nums，判断 nums 中是否存在四个元素a，b，c，d ，使得 a + b + c + d = 0 ？找出所有满足条件且不重复的四元组。

答案中不可以包含重复的四元组。

思路

  • 和三数之和的思路是一样的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function fourSum(nums, target) {
  if (nums.length < 4) return [];
  var result = [];
  //1.排序便于去重
  nums.sort((a, b) => a - b);
  //2.循环
  for (var i = 0; i < nums.length - 3; i++) {
    //去重
    if (i && nums[i] == nums[i - 1]) {
      continue;
    }
    //如果从左侧起连续的四个数大于了target,后面的都不会等于target(已经排序了)
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
      // 直接结束循环
      break
    }
    //第二个数去重
    for (var j = i + 1; j < nums.length - 2; j++) {
      if (j && nums[j] == nums[j - 1]) {
        continue;
      };
      //设置亮哥哥指针开始同侧探索
      var left = j + 1, right = nums.length - 1;
      while (left < right) {
        var sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum == target) {
          result.push([nums[i], nums[j], nums[left], nums[right]])
        }
        //left和right去重,并移动指针
        if (sum <= target) {
          while (nums[left] == nums[++left]);
        } else {
          while (nums[right] == nums[--right]);
        }

      }
    }
  }
  return result
}

var nums = [1, 0, -1, 0, -2, 2], target = 0;
console.log(fourSum(nums, target));

3 数据统计

如何对数组进行更高效额统计计算

3.1数组中出现次数超过数组一半的数字

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路

  • 目标值的个数比其他所有值加起来的数多

    记录两个变量 1.数组中的某个值 2.次数

    1.当前遍历值和上一次遍历值相等？次数+1 ： 次数-1。

    2.次数变为0后保存新的值。

    3.遍历结束后保存的值,判断其是否复合条件

    事件复杂度O(n) 不需要开辟额外空间 , 逻辑稍微复杂

image-20200617132313777

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function MoreThanHalfNum_Solution(numbers)
{
    // write code here
  //定义两个变量来用来记录target(目标值)和count的个数
  if(!numbers||numbers.length<0) return 0;
  var target = numbers[0];
  var count=0;
  //第一次循环找出target
  for(var i=0;i<numbers.length;i++){
    //相等的情况下
    if(numbers[i]==target){
      count++;
    }else{
      count--
    }
    //如果count==0表示当前数字不是最长数字被抵消了,重新复值向后遍历
    if(count==0){
      target=numbers[i];
      count=1
    }
  }
  //第二次循环找出target的count
  count=0
  for(var j=0;j<numbers.length;j++){
    if(numbers[j]==target){
      count++
    }
  }
  //符合条件长度的判断
  return count> Math.floor(numbers.length/2)?target:0
}

3.2连续子数组的最大值

题目

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为O(n)

例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)

思路

  • 记录一个当前连续子数组最大值 max 默认值为数组第一项

    记录一个当前连续子数组累加值 sum 默认值为数组第一项

    1.从数组第二个数开始，若 sum<0 则当前的sum不再对后面的累加有贡献，sum = 当前数

    2.若 sum>0 则sum = sum + 当前数

    3.比较 sum 和 max ，max = 两者最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function FindGreatestSumOfSubArray(array)
{
  if(Array.isArray(array)&&array.length>0){
    //定义当前和和最大值
    var sum = array[0];
    var max = array[0];
    for(var i=1;i<array.length;i++){
      if(sum<0){
        //和小于0时,前面的值都不会对后面的有﹢影响
        sum = array[i]
      }else{
        sum+=array[i]
      }
      if(sum>max){
        max=sum;
      }  
  }
    return max
  }
  return 0
}

3.3 第一个只出现一次的字符9

  • 遍历字符串，比较每个字符第一次和最后一次出现的位置是否相同。

    1
    indexOf`的时间复杂度为`O(n)`，所以整体的时间复杂度为O(n2)，空间复杂度为`0
1
2
3
4
5
6
7
8
9
10
11
12
function PrintMinNumber(numbers)
{
    // write code here
  if(!numbers || numbers.length==0) return ''
  
 return numbers.sort(compare).join('')
}
 function compare(a, b) {
      const front = "" + a + b;
      const behind = "" + b + a;
      return front - behind;
    }

3.4 扑克牌顺子

题目

扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。

2-10为数字本身，A为1，J为11...大小王可以看成任何数字，可以把它当作0处理。

思路

  • 1.数组排序
  • 2.遍历数组
  • 3.若为0，记录0的个数加1
  • 4.若不为0，记录和下一个元素的间隔
  • 5.最后比较0的个数和间隔数，间隔数>0的个数则不能构成顺子
  • 6.注意中间如果有两个元素相等则不能构成顺子

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function IsContinuous(numbers)
{
    // write code here
  if(numbers&&numbers.length>0){
    //排序
    numbers.sort();
    //记录0的个数
    var numOfZero=0;
    //记录间隔数的和
    var numOfInterval=0
    //循环计算,0的个数大于等于所有间隔数的和,返回true
    for(var i=0;i<numbers.length-1;i++){
      if(numbers[i]==0){
        numOfZero ++
      }else{
        //计算间隔数
        var space = numbers[i+1]-numbers[i];
        //排除对子的出现
        if(space==0){
          return false;
        }else{
          numOfInterval += space-1;
        }
      }
    }
    if(numOfZero>=numOfInterval)
      return true
  }
}

4 二维数组

建立一定的抽象建模能力，将实际中的很多问题进行抽象

4.1 构建乘积数组

题目

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法

思路

  • 可以先计算下面的值,在循环乘以上三角的值

image-20200617085505793

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function multiply(array)
{
    // write code here
  //定义一个数组保存B
  var result = [];
  //判断是不是数组以及数组是不是为空
  if(Array.isArray(array)&& array.length>0){
    //计算下三角
    result [0] =1;
    for(var i=1;i<array.length;i++){
      result[i] = result[i-1]*array[i-1];
    }
    //将上三角的元素乘进去
    var temp = 1;
    for(j = array.length-2;j>=0;j--){
    //暂存当前的要乘以的元素
      temp = temp*array[j+1];
      result[j] = result[j]*temp;
    }
  }
  return result;
}

4.2 顺时针打印矩阵

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

image-20200617135655513

思路

打印拆分四部

  • 第一步：从左到右打印一行
  • 第二步：从上到下打印一列
  • 第三步：从右到左打印一行
  • 第四步：从下到上打印一列

最后一圈很有可能出现几种异常情况,打印矩阵最里面一圈可能只需三步、两步、甚至一步

所以在每一行打印时要做好条件判断:

  • 能走到最后一圈，从左到右必定会打印

  • 结束行号大于开始行号，需要从上到下打印

  • 结束列号大于开始列号，需要从右到左打印

  • 结束行号大于开始行号+1，需要从下到上打印

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function printMatrix(matrix)
{
    // write code here
  var start = 0;
  //获取函数和列数 
  var rows = matrix.length;
  var columns = matrix[0].length;
  //保存数组
  var result = []
  
  if(!rows&&!columns){
    return false
  }
  //循环条件
  while(rows>start*2&&columns>start*2){
    //转一圈
    runCircle(matrix,start,rows,columns,result)
    //注意这里的起点都是(start,start),上面的函数只是转了一圈,转完进行下一圈
    start++;
  }
  return result
}

//
function runCircle(matrix,start,rows,columns,result){
  //获取当下遍历一圈的x和y的值
  var endX = columns-start-1;
  var endY = rows-start-1;
  for(var i=start;i<=endX;i++){
    result.push(matrix[start][i])
  }
  if(endY>start){
    for(var j = start+1;j<=endY;j++){
      result.push(matrix[j][endX])
    }
    if(endX>start){
      for(var m=endX-1;m>=start;m--){
        result.push(matrix[endY][m])
      }
      if(endY>start+1){
        for(var n = endY-1;n>start;n--){
          result.push(matrix[n][start])
        }
      }
    }
  }
}

5 其他

5.1 把数组排成最小的数

题目

  • 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

    例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323

思路

通过sort函数,

1
2
3
4
5
6
7
8
9
10
11
12
13
function PrintMinNumber(numbers)
{
    // write code here
  if(!numbers || numbers.length==0) return ''
  
 return numbers.sort(compare).join('')
}
//自定义排序规则
 function compare(a, b) {
      const front = "" + a + b;
      const behind = "" + b + a;
      return front - behind;
    }

5.2 在排序数组中查找数字

题目

统计一个数字在排序数组中出现的次数

思路

  • 1.直接遍历数组，判断前后的值是否相同，找到元素开始位置和结束位置，时间复杂度O(n)
  • 2.使用二分查找找到目标值，在向前向后遍历，找到所有的数，比上面略优，时间复杂度也是O(n)
  • 3.使用二分查找分别找到第一个目标值出现的位置和最后一个位置，时间复杂度O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
function binaryTree(data, arr, start, end) { 
  if (start > end) { 
    return -1
  }
  var mid = Math.floor((end + start) / 2);
  if (data == arr[mid]) {
    return mid
  } else if (data > arr[mid]) {
    return binaryTree(data, arr, mid + 1, end)
  } else { 
    return binaryTree(data,arr,start,mid-1)
  }
}

5.3 数组中的逆序对

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

思路

  • 使用暴力法：从第一个数开始，依次和后面每一个数字进行比较记录逆序对的个数，时间复杂度O(n2)

  • 使用分治的细想：

若没了解过归并排序，建议先熟悉归并排序算法再来看本题。

直接将归并排序进行改进，把数据分成N个小数组。

合并数组 left - mid , mid+1 - right，合并时， 若array[leftIndex] > array[rightIndex] ,则比右边 rightIndex-mid个数大

1
count += rightIndex-mid

注意和归并排序的区别： 归并排序是合并数组数从小数开始，而本题是从大数开始。

时间复杂度O(nlogn)

空间复杂度O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function InversePairs(data) {
  return mergeSort(data, 0, data.length - 1, [])%1000000007;
}
/*
arr:需要遍历的数组
start:合并的开始位置
end:合并的结束位置
temp:保存归并排序的结果(从大数到小数排序的)
*/
function mergeSort(arr, left, right, temp) {
  //拆分
  if (left < right) {
  //这里取中位数
    var mid = left + right >> 1;
    var l = mergeSort(arr, left, mid, temp)
    var r = mergeSort(arr, mid + 1, right, temp)

    //合并操作
    var leftIndex = mid;
    var rightIndex = right;
    //合并的时候是两个数组合并,每次合并都把最大的值归并到temp数组中,temp数组长度时数组arr的长度tempIndex
    var tempIndex = right;
    var count = 0

    //遍历数组计算count和保存两侧的最大值到temp
    while (leftIndex >= left && rightIndex > mid) {
      //依次从后后往前比较
      if (arr[leftIndex] > arr[rightIndex]) {
        // 左边的大, 保存左边的值,同时count+=插值(已经递归排序了差值就是逆序对数)
        count += (rightIndex - mid);
        temp[tempIndex--] = arr[leftIndex--];
      } else {
        //右边的大保存右边的值
        temp[tempIndex--] = arr[rightIndex--];
      }
    }
    //如果跳出循环,左边的数值大,将左边的直接添加到temp中
    while (leftIndex >= left) {
      temp[tempIndex--] = arr[leftIndex--]
    }
    //右边还有数组则右边直接添加到temp中
    while (rightIndex > mid) {
      temp[tempIndex--] = arr[rightIndex--];
    }
    //将暂存在temp中的归并排序的值修改arr
    for (var i = left; i <= right; i++) {
      arr[i] = temp[i]
    }
    //返回排序好的count,同时数组arr的改变也是
    return count + l + r;
  }
  return 0
}
module.exports = {
    InversePairs : InversePairs
};

堆

  • 堆的顶层是一棵完全二叉树,可以用数组实现
  • 最大堆:每一个元素的节点值不小于其子节点
  • 最小堆:每个元素的节点值不大于其子节点
image-20200618153941577
  • 应用:堆在处理某些特殊场景时可以大大降低代码的时间复杂度，例如在庞大的数据中找到最大的几个数或者最小的几个数，可以借助堆来完成这个过程。

1 堆的基本操作

1.1 堆的基本结构

image-20200618154319630

  • 堆的底层实际上是一棵完全二叉树。
  • 可以用数组实现
  • 每个的节点元素值不小于其子节点 - 最大堆
  • 每个的节点元素值不大于其子节点 - 最小堆

1.2 堆的构建

堆存储在下标为0开始的数组中，因此在堆中给定下标为i的结点时：
（1） 如果i=0，结点i是根节点，没有双亲节点；否则结点i的双亲结点为 结点(i-1)/2

（2） 如果2 * i + 1 <= n - 1，则结点i的左孩子为结点2 * i + 1，否则结 点i无左孩子

（3）如果2 * i + 2 <= n - 1，则结点i的右孩子为结点2 * i + 2，否则结 点i无右孩

image-20200618160822673

1.2.1 大顶堆

对于第一个非叶子节点开始依次对数组中的元素进行下沉操作

  • 和孩子节点的最大值max比较
  • 大于max的—不需要在下沉
  • 小于max—和max交换位置继续下一层孩子节点的比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//1.大顶堆的创建
function createMaxHeap(arr, length) { 
  // 寻找根节点
  for (var i = Math.floor(length / 2) - 1; i >= 0; i--) { 
    // 调整大顶堆
    ajustMaxHeap(arr, i, length);
  }
  return arr;
}
function ajustMaxHeap(arr, index, length) { 
  //调整左右子树,这里的i*2+1是跳转到下一层的子节点
  for (var i = index * 2 + 1; i < length; i = i * 2 + 1) { 
    //调整i+1<length表明是有子节点的
    if (i + 1 < length && arr[i + 1] > arr[i]) { 
      i++;
    }
    //判断子节点是不是大于节点的最大值index
    if (arr[index] >= arr[i]) { 
      //根节点大于子节点
      break
    } else {
      //最大值的给根节点
      [arr[index],arr[i]]=[arr[i],arr[index]]
      index = i;
    }
  }
}

1.2.2 小顶堆

从第一个非叶子节点开始依次对数组中的元素进行下沉操作

  • 和孩子节点的最小值min比较
  • 小于min — 不需要在下沉
  • 大于min — 和min交换位置（下沉） - 继续和下一层孩子节点比较，直到队列末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//小顶堆的创建
function createMinHeap(arr, length) {
  for (var i = Math.floor(length / 2) - 1; i >= 0; i--) {
    ajustMinHeap(arr, i, length)
  }
  return arr
}
function ajustMinHeap(arr, index, length) {
  for (var i = index * 2 + 1; i < length; i * 2 + 1) {
    if (i + 1 > length && arr[i + 1] < arr[i]) {
      i++
    }
    if (arr[index] < arr[i]) {
      break
    } else {
    //小的始终在最前面
      [arr[index], arr[i]] = [arr[i], arr[index]]
      index = i
    }
  }
}

1.3 堆的插入(先进先出)

  • 由于堆属于优先队列，只能从末尾添加
  • 添加后有可能破坏堆的结构，需要从下到上进行调整
  • 如果元素小于父元素，上浮

小顶堆为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//堆的插入(小顶堆)(优先队列只能从末尾插入元素)
function addEleHeap(arr = [], element) {
  //插入元素到队列中
  arr.push(element);
  //获取最后插入的元素得所用
  var index = arr.length - 1;
  //获取父元素的索引
  var target = Math.floor((index - 1) / 2);
  // 父元素的索引非0
  while (target >= 0) {
    arr[target];
    //判断父元素和插入元素的大小
    if (arr[index] < arr[target]) {
      //新插入的元素小于,调整树的结构
      [arr[index], arr[target]] = [arr[target], arr[index]];
      index = target;
      target = Math.floor((index - 1) / 2);
    } else {
      break;
    }
  }
  return arr
}

1.4 堆的移出

  • 由于堆属于优先队列，只能从头部移除
  • 移除头部后，使用末尾元素填充头部，开始头部下沉操作(调用小顶堆的调整)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//小顶堆(堆的移出只能从头部移出,用最后一位填充,在调整)
function removeEleHeap(arr = []) {
  var result = null
  if (arr.length > 1) {
    //取出第一个待删除元素
    result = arr[0];
    //用最后一个元素填充
    arr[0] = arr.pop();
    ajustMinHeap(arr, 0, arr.length)
  } else if (arr.length == 1) {
    return arr.pop()
  }
  return result
}

1.5 堆的封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
function Heap(type = 'min') {
      this.type = type;
      this.value = [];
    }

    Heap.prototype.create = function () {
      const length = this.value.length;
      for (let i = Math.floor((length / 2) - 1); i >= 0; i--) {
        this.ajust(i, length);
      }
    }

    Heap.prototype.ajust = function (index, length) {
      const array = this.value;
      for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
        if (i + 1 < length) {
          if ((this.type === 'max' && array[i + 1] > array[i]) ||
            (this.type === 'min' && array[i + 1] < array[i])) {
            i++;
          }
        }
        if ((this.type === 'max' && array[index] < [array[i]]) ||
          (this.type === 'min' && array[index] > [array[i]])) {
          [array[index], array[i]] = [array[i], array[index]];
          index = i;
        } else {
          break;
        }
      }
    }

    Heap.prototype.add = function (element) {
      const array = this.value;
      array.push(element);
      if (array.length > 1) {
        let index = array.length - 1;
        let target = Math.floor((index - 1) / 2);
        while (target >= 0) {
          if ((this.type === 'min' && array[index] < array[target]) ||
            (this.type === 'max' && array[index] > array[target])) {
            [array[index], array[target]] = [array[target], array[index]]
            index = target;
            target = Math.floor((index - 1) / 2);
          } else {
            break;
          }
        }
      }
    }

    Heap.prototype.pop = function () {
      const array = this.value;
      let result = null;
      if (array.length > 1) {
        result = array[0];
        array[0] = array.pop();
        this.ajust(0, array.length);
      } else if (array.length === 1) {
        return array.pop();
      }
      return result;
    }

    var heap = new Heap('max');
    heap.add(6)
    heap.add(10)
    console.log(heap.value);
    console.log(heap.pop());
    console.log(heap.value);

2 练习题

2.1最小的k个数

题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4

思路

思路1:

先排序，再取前k个数，最小时间复杂度nlogn。

思路2:

1.把前k个数构建一个大顶堆

2.从第k个数开始，和大顶堆的最大值进行比较，若比最大值小，交换两个数的位置，重新构建大顶堆

3.一次遍历之后大顶堆里的数就是整个数据里最小的k个数。

时间复杂度nlogk，优于思路1。

2.2 数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数

分析

  • 这种题目可以通过对来解决太复杂了
  • 直接插入排序后通过计算奇偶性来解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var arr = []
function Insert(num)
{
    // write code here
  //将num放进数组arr,在排序
  arr.push(num);
  arr.sort();
}
function GetMedian(){
	// write code here
  var len = arr.length
  if(len==0) return 0
  //判断奇数还是偶数
  if(len%2==1){
    return arr[Math.floor(len/2)]
  }
  if(len%2==0){
    //偶数是中间两位数相加除以/2
    return (arr[arr.length/2]+arr[arr.length/2-1])/2
  }
}

链表

1 链表的基础

  • 用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。

  • 需要遍历才能查询到元素，查询慢。

  • 插入元素只需断开连接重新赋值，插入快。

2 基本应用

2.1 从尾到头打印链表

题目

  • 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

分析

image-20200612122301666

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    // write code here
   //通过循环头插法插入到数组
   var arr = [];
  while(head){
    arr.unshift(head.val);
    head = head.next
  }
  return arr
}

2.2 反转链表

题目

  • 输入一个链表，反转链表后，输出新链表的表头

分析

  • 以链表的头部节点为基准节点
  • 将基准节点的下一个节点挪到头部作为头节点
  • 当基准节点的next为null，则其已经成为最后一个节点，链表已经反转完成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 function ListNode(x){
    this.val = x;
    this.next = null;
}
function ReverseList(pHead)
{
    // write code here
  /*
  以链表的头部节点为基础,将头部节点的后面的节点插入到头部节点之前,
  */
  //保存当前的移动节点
  let currentNode = null;
  //始终指向链表的头结点,用于插入当前节点
  let headNode = pHead;
  while(pHead&&pHead.next){
    //从链表中取出当前节点
    currentNode = pHead.next;
    pHead.next = currentNode.next;
    //将取出的当前节点插入到头结点中
    currentNode.next = headNode;
    //将头结点始终指向第一个节点
    headNode = currentNode;
  }
  return headNode
}

2.3 删除链表中重复的节点

题目

  • 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路

  • 链表是排好顺序的，所以重复元素都会相邻出现 递归链表：
    • 1.当前节点或当前节点的next为空，返回该节点
    • 2.当前节点是重复节点：找到后面第一个不重复的节点
    • 3.当前节点不重复：将当前的节点的next赋值为下一个不重复的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function deleteDuplication(pHead)
{
    // write code here
  if(!pHead||!pHead.next) return pHead;
  else if(pHead.val == pHead.next.val){
    //递归查找连续的相等值,并找出下一个不连续相等的值,在递归中注意一定要有返回值才能不断进行递归有返回值
    var tempNode = pHead.next;
    while(tempNode&&tempNode.val==pHead.val){
      tempNode = tempNode.next;
    }
    return deleteDuplication(tempNode);
  }else{
    //当相邻的节点不同时,找到下一个不重复的节点连接在后面
    pHead.next = deleteDuplication(pHead.next)
    return pHead
  }
  
}
  • 时间复杂度O(n)
  • 空间复杂福O(1)

2.4 复杂链表的复制

题目

  • 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}
function Clone(pHead)
{
    // write code here
  if (!pHead) return  null
  var cloneHeadNode = new RandomListNode(pHead.label);
  cloneHeadNode.next = pHead.next;
  cloneHeadNode.random = pHead.random;
  
  //连接下一下节点
  cloneHeadNode.next = Clone(pHead.next);
  return cloneHeadNode;
}

3 环类链表

环类题目即从判断一个单链表是否存在循环而扩展衍生的问题

3.1 环形链表找出环的入口节点

题目

  • 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路

  • 首先判断是不是有环(设置fast->2,low->1)最终相遇则说明有环
  • 当fast或fast.next不存在,return null(排除了只有一个元素的情况)
  • 设置其中一个元素从开始节点出发,另一个从相遇点出发(fast->1,low->1)二者最终会相遇在环的入口与的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
  //定义两个变量
  var low = pHead;
  var fast = pHead;
  //判断是否有环
  while(fast&&fast.next){
     //快指针走2步
      fast = fast.next.next;
      //慢指针走1步
      low = low.next;
    if(low ==fast){
     break;
    }
  }
  
  //条件,有一个不存在则表示不是环,(排除只有一个元素的情况)
  if(!fast || !fast.next) return null;
  //有环寻找入口
  low = pHead;//low从表头出发
  while(low!=fast){
  //注意这里都是走一步
    fast = fast.next;
    low = low.next;
  }
  return fast;
}
  • 时间复杂度:O(n)

3.2 圆圈中最后剩下的数字(约瑟夫环的问题)

题目

  • 0,1,...,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
function LastRemaining_Solution(n, m)
{
    // write code here
  if(n<1) return -1;
  //编号为0的元素
  if(n==1) return 0;
  //这里通过递归的方式,每次都在去掉一个人的基础上在重新计算下一个要出的人
  /*
  k=1 m%n-1,下一次开始的是m%n f(1) = m%n,返回的是下一次开始的地方
  k=2 f(2) = (f(1)+m)%n
  */
  return (LastRemaining_Solution(n-1, m)+m)%n;
}

4 双指针

  • 双指针的思想在链表和数组中的题目都经常会用到，主要是利用两个或多个不同位置的指针，通过速度和方向的变换解决问题。
  • 两个指针从不同位置出发：一个从始端开始，另一个从末端开始；
  • 两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。

对于单链表，因为我们只能在一个方向上遍历链表，所以第一种情景可能无法工作。然而，第二种情景，也被称为慢指针和快指针技巧，是非常有用的。

4.1 两个链表的公共节点

题目

  • 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路:

  • 获取两个列表的长度,找到差值interval
  • 让长的列表先走interval,从同样的长度起点开始
  • 当节点存在,且不相等直接next,相等返回当前节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
  var l1 = getLength(pHead1);
  var l2 = getLength(pHead2);
  var interval,lang,short;
  if(l1>l2){
    interval = l1-l2;
    lang = pHead1;
    short = pHead2;
  }else{
    interval = l2-l1;
    lang = pHead2;
    short = pHead1;
  }
  //长的先走interval步
  while(interval--){
    lang = lang.next;
  }
  
  //比较两个数值,当存在的情况下
  while(lang){
    if(lang==short){
      return lang
    }
    lang = lang.next;
    short = short.next
  }
  return null
  
}
//获取两个链表的长度的
function getLength(head){
  var count = 0;
  while(head){
    count++
    head = head.next;
  }
  return count
}

4.2 链表中倒数第k个节点

题目

  • 输入一个链表，输出该链表中倒数第k个结点。

分析

  • 简单思路： 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    优化：

    设定两个节点，间距相差k个节点，当前面的节点到达终点，取后面的节点。

    前面的节点到达k后，后面的节点才出发。

    代码鲁棒性： 需要考虑head为null，k为0，k大于链表长度的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function FindKthToTail(head, k)
{
    // write code here
  /*两个链表中间相差k个节点,在同时走,当先走的节点到达终点,后走的节点所在的位置就是倒数第k个节点*/
  if(!head ||!k) return null
  //第一个节点先走k步
  var first = head;
  var last = head;
  var index = 1
  while(first.next){
    index++;
    first = first.next;
    if(index>k){
      last = last.next
    }
  }
  //first到达末尾,last就是所求节点,k要小于index的值,也就是链表的长度
  return (k<=index) && last;
}

5 其他

5.1 二叉搜索树与双向链表

题目

  • 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function Convert(pRootOfTree)
{
    // write code here
    //判断是否存在
    if(!pRootOfTree) return null
    //定义三个变量
    var stack = [];
    var p=pRootOfTree;
    var pre = null;
    //判断是不是第一个节点
    var isFirst = true;
    while(p||stack.length>0){
        while(p){
            stack.push(p);
            p=p.left
        }
        p = stack.pop();
        if(isFirst){
           var root = p;
            pre = p;
            isFirst = false
        }else{
            //连接p节点和前驱节点pre
            pre.right = p;
            p.left = pre;
            //pre指向p,
            pre = p;
        }
        p = p.right;
    }
    //全部结束返回root
    return root
}

5.2 合并两个有序链表

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

链表头部节点比较，取较小节点。

小节点的next等于小节点的next和大节点的较小值。

如此递归。

返回小节点。

考虑代码的鲁棒性，也是递归的终止条件，两个head为null的情况，取对方节点返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Merge(pHead1, pHead2)
{
    // write code here
  if(!pHead1) return pHead2;
  if(!pHead2) return pHead1;
  var head;
  if(pHead1.val<pHead2.val){
    head  = pHead1;
    head.next = Merge(pHead1.next,pHead2)
  }else{
    head = pHead2;
    head.next = Merge(pHead1,pHead2.next)
  }
  
  return head
}

二叉树

1 打印二叉树(层次遍历)

1.1 从上往下打印二叉树(层次遍历)

题目

从上往下打印出二叉树的每个节点，同层节点从左至右打印

思路

  • 借助队列(先进先出)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function PrintFromTopToBottom(root)
{
    // write code here
  var queue = [];
  var result = []
  if(root){
    queue.push(root)
    //循环进入队列,直到队列为空
    while(queue.length>0){
      var current = queue.shift();
      if(current.left){
        queue.push(current.left)
      }
      if(current.right){
        queue.push(current.right)
      }
      result.push(current.val);
    }
  }
  return result
}

1.2 把二叉树打印成多行

题目

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路

  • 在单行打印的基础上设置变量当前行节点数和子节点数,并保存每行的暂存节点数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print(pRoot)
{
    // write code here
  var queue = [];
  var result = [];
  //保存当前行的元素
  var tempArr=[];
  //当前行的元素个数;
  var currentNum = 1;
  //子节点的个数
  var childNums = 0
  if(pRoot){
    queue.push(pRoot);
    while(queue.length>0){
      let current = queue.shift()
      if(current.left){
        queue.push(current.left)
        childNums++
      }
      if(current.right){
        queue.push(current.right)
        childNums++
      }
      //将当前去取出保存在resule
      tempArr.push(current.val);
      currentNum--;
      //当前行的个数为0表示已经遍历完当前行,将当前行改为下一行的childNums
      if(currentNum===0){
        result.push(tempArr);
        currentNum = childNums;
        childNums = 0
        //置空保存下一行数据
        tempArr=[]
      }
    }
  }
  return result
}

1.3 按之字形顺序打印二叉树

题目

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

分析

  • 采用两个栈分别保存奇数行和偶数行
  • 奇数从左到右
  • 偶数从右到左
  • 边出栈边保存打印顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print(pRoot)
{
    // write code here
  var oddStack = [];
  var evenStack = [];
  var result = [];
  var tempt= []
  if(pRoot){
    oddStack.push(pRoot)
    while(oddStack.length>0 || evenStack.length>0){
      while(oddStack.length>0){
        var current = oddStack.pop();
        tempt.push(current.val)
        
        
        if(current.left){
          evenStack.push(current.left)
        }
        if(current.right){
          evenStack.push(current.right)
        }
      }
      if(tempt.length>0){
        result.push(tempt);
        tempt = []
      }
      while(evenStack.length>0){
         var current = evenStack.pop();
         tempt.push(current.val)
         //奇数层左子树先入
         
        if(current.right){
          oddStack.push(current.right)
        }
        if(current.left){
          oddStack.push(current.left)
        }
      }
      if(tempt.length>0){
        result.push(tempt);
        tempt = []
      }
    
    }
    
  }
  return result
}

哈希表

  • 哈希是通过哈希函数来进行映射检索地址,哈希是一种有效的检索技术,会出现同义词冲突

  • 如何设计哈希函数以及如何避免冲突就是哈希表的常见问题。 好的哈希函数的选择有两条标准：

    • 1.简单并且能够快速计算
    • 2.能够在址空间中获取键的均匀分布

当用到哈希表时我们通常是要开辟一个额外空间来记录一些计算过的值，同时我们又要在下一次计算的过程中快速检索到它们，例如上面提到的两数之和、三数之和等都利用了这种思想。

1 最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

1
2
3
4
5
6
7
8
9
function GetLeastNumbers_Solution(input, k)
{
    // write code here
  if(!input||input.length<k) return [];
  var result  = [];
  input.sort((a,b)=>a-b)
  result.push(...input.slice(0,k))
  return result
}

栈和队列

在上面的数组中，我们可以通过索引随机访问元素，但是在某些情况下，我们可能要限制数据的访问顺序，于是有了两种限制访问顺序的数据结构：栈（先进后出）、队列（先进先出）

1 栈和队列的互相实现

1.1 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路

栈1:

用于入队列存储

栈2:

出队列时将栈1的数据依次出栈，并入栈到栈2中

栈2出栈即栈1的底部数据即队列要出的数据。

注意:

栈2为空才能补充栈1的数据，否则会打乱当前的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定义两个栈,一个用于进,一个用于出(先进先出)
var stack1 = [];
var stack2 = [];
function push(element) {
  stack1.push(element)
}
function pop() {
  //判断stack2是不是为空,为空需要将statck1中的入栈在出栈
  if (stack2.length === 0) {
    //循环stack1不为空入栈
    while (stack1.length > 0) {
      stack2.push(stack1.pop());
    }
  }
  return stack2.pop() || null;
}

1.2 用两个队列实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 用两个队列实现栈(先进后出)
var queue1 = [];
var queue2 = [];
function push(x) {
  if (queue1.length === 0) {
    //后进的存储在队列的前面就会先出去
    queue1.push(x);
    while (queue2.length) {
      // queue2从头取进queue1
      queue1.push(queue2.shift())
    }
  } else if (queue2.length === 0) {
    queue2.push(x);
    while (queue1.length) {
      // queue2从头取进queue1
      queue2.push(queue1.shift())
    }
  }
}

function pop() {
  if (queue1.length !== 0) {
    return queue1.shift();
  } else {
    return queue2.shift()
  }
}

2 练习题

2.1包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

思路

  • 定义两个栈,一个用于存储数据,一个用于存储最小值
  • 每次进栈的元素和栈顶最小元素比较,将最小值存入
  • 数据栈出栈,最小值也出栈
  • 这样最小值的栈顶永远是当前栈的最小值

image-20200619080114951

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
var dataStack=[]
var minStack=[]
function push(node)
{
    // write code here
  dataStack.push(node)
  //最小值入栈
  if(minStack.length===0||node<min()){
    minStack.push(node)
  }else{
    minStack.push(min())
  }
}
function pop()
{
    // 弹出的时候两个栈同时弹出,保证当前最小栈中始终是当前数据栈中的最小值
  if(dataStack.length>0){
    minStack.pop();
    return dataStack.pop()
  }
}
function top()
{
    // write code here
  var length = dataStack.length;
  if(length>0)
  return dataStack[length-1]
}
function min()
{
    // write code here
  //长度大于1,直接返回最小值
  var length = minStack.length;
  if(length>0)
  return minStack[length-1]
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};

2.2 滑动窗口的最大值

题目

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。 返回滑动窗口最大值。

分析

image-20200619093535324

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function maxInWindows(num, size)
{
  if(!num || size>num.length||size<0) return []
  //定义变量保存当前值
  var result=[];
  var max = num[0];
  var flag = 0
  for(var i=0;i<num.length;i++){
    flag++;
    //将最大值保存在max中
    if(num[i]>max){
      max = num[i]
    }
    if(flag==size){
      result.push(max);
      //这里i回到窗口的起点,for后面有i++,开始位置时下一个起始位置
      i = i-size+1;
      //下一个位置为max
      max=num[i+1];
      flag=0
    }
  }
  return result
}

2.3 栈的压入,弹出序列

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路

image-20200619122146851

  • 借助一个中间栈temp来完成
  • 借助指针j->popV,i->pushV
  • 当最后的元素等于popV时,j++
  • 反之,pushV的[i]入栈temp,i++右移(前提是i<pushV.length)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function IsPopOrder(pushV, popV)
{
    //定义中间栈保存
  var stack = [];
  //分别指向pushV和popV(),开始遍历
  var i=0,j=0;
  while(j<popV.length){
    //判断pop和stack[stack.length-1]
    if(stack.length>0&&stack[stack.length-1]==popV[j])
    {
      //和最后元素相同stack出栈
      stack.pop();
      j++;
    }else{
      if(i==pushV.length){
        return false
      }else{
        //不相等见pushV[i]保存在stack中
        stack.push(pushV[i++]);
      }
    }
  }
  return true
}

2.4 数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路

  • 1.维护一个大顶堆，一个小顶堆，数据总数：

    • 小顶堆里的值全大于大顶堆里的；
    • 2个堆个数的差值小于等于1

  • 2.当插入数字后数据总数为奇数时：使小顶堆个数比大顶堆多1；当插入数字后数据总数为偶数时，使大顶堆个数跟小顶堆个数一样。

3.当总数字个数为奇数时，中位数就是小顶堆堆头；当总数字个数为偶数时，中位数数就是2个堆堆顶平均数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var arr = []
function Insert(num)
{
    // write code here
  //将num放进数组zrr,在排序
  arr.push(num);
  arr.sort();
}
function GetMedian(){
	// write code here
  var len = arr.length
  if(len==0) return 0
  //判断奇数还是偶数
  if(len%2==1){
    return arr[Math.floor(len/2)]
  }
  if(len%2==0){
    //偶数是中间两位数相加除以/2
    return (arr[arr.length/2]+arr[arr.length/2-1])/2
  }
}

字符串

1 练习题

1.1 替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

代码

1
2
3
4
5
6
7
8
function replaceSpace(str)
{
    // write code here
   
    //str = str.replace(/\s/g,'%20')
  str = str.split(' ').join('%20')
    return str
}

1.2 正则表达式匹配

题目

请实现一个函数用来匹配包括’.’和’‘的正则表达式。 模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。 例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

注意

  • 这里的*和点.的含义和正则表达式中一致
1
2
3
4
5
6
7
//s, pattern都是字符串
function match(s, pattern)
{
    // write code here
  reg = new RegExp('^'+pattern+'$')
  return reg.test(s)
}

1.3 字符串的排列(动态规划,递归,字符串)?????(有问题)

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

分析

  • 通过回朔法(不断做决策)最后的跳出条件不是很懂

image-20200619190137923

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 考察的是回溯法,全排列
function Permutation(str) {
  //定义数组保存不重复的字符串
  const result = []
  if (str) {
    //通过定义队列来保存当前元素中为添加的值
    const queue = str.split('');
    //递归开始决策树
    PermutationCore(queue, result);
  }
  //按照字典进行排序
  result.sort();
  return result
}
function PermutationCore(queue, result, temp = '', current = '') {
  //当前的字符串和当前字符(当前字符添加到当前字符串)
  current += temp;
  //如果当前队列=0表明当前三个元素已经添加到current中保存
  if (queue.length == 0) {
    //去重
    if (!result.includes(current)) {
      result.push(current)
    }
    return
  }
  //通过循环遍历不同的元素作为下一个元素的情况
  for (let i = 0; i < queue.length; i++) {
    //取出当前字符temp(从图开始取,保存路径)
    let temp = queue.shift();
    PermutationCore(queue, result, temp, current);
    //递归完成将当前元素入栈
    queue.push(temp)
  }
}

1.4 翻转字符串

题目

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student."，则输出"student. a am I"。

思路

  • 直接调用api
1
2
3
4
5
6
function ReverseSentence(str) {
  if (str) {
    return str.split(' ').reverse().join(' ')
  }
  return ''
}

1.5 左旋转字符串

题目

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

1
2
3
4
5
6
7
8
function LeftRotateString(str, n) {
  // write code here
  if (str && n!=null) {
    //字符串拼接并且进行截取str.length长度
    return (str + str).slice(n, str.length + n)
  }
  return ''
}

1.6 字符流中第一个不重复的字符

题目

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

分析

  • 借助map来保存当前的值和次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var map;
//Init module if you need
function Init()
{
    // write code here
  map={}
}
//Insert one char from stringstream
function Insert(ch)
{
    // write code here
  if(map[ch]){
    map[ch]++
  }else{
    map[ch]=1
  }
}
//return the first appearence once char in current stringstream
function FirstAppearingOnce()
{
    // write code here
  for(let item in map){
    if(map[item]==1){
      return item
    }
  }
  return '#'
}

1.7 表示数值的字符串

题目

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。 例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

思路

  • 正则表达式的解法

  • 考虑所有的情况

    • .只能出现数字、符号位、小数点、指数位
    • 2.小数点，指数符号只能出现一次、且不能出现在开头结尾
    • 3.指数位出现后，小数点不允许在出现
    • 4.符号位只能出现在开头和指数位后面

正则表达式的解析

1
2
3
4
5
6
7
//正则
  //[+-]?            -> 正或负符号出现与否
  //\d*                 -> 整数部分是否出现，如-.34 或 +3.34均符合
  //(\.\d+)?           -> 如果出现小数点，那么小数点后面必须有数字；
  //                        否则一起不出现
  //([eE][+-]?\d+)?  -> 如果存在指数部分，那么e或E肯定出现，+或-可以不出现，
  //                        紧接着必须跟着整数；或者整个部分都不出现
1
2
3
4
5
6
7
8
1.正则表达式的解法
//s字符串
function isNumeric(s)
{
    // write code here
  //通过匹配字符串match()返回的是数组,这里返回数组中的第一个符合正则表达式的子串[0]和字符串s相等结果
  return s.match(/[+-]?\d*(\.\d*)?([eE][+-]?\d+)?/g)[0]===s
}
1
2.考虑所有的情况

其他算法

1 回溯算法

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

1.1 机器人的运动范围(回溯)

题目

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路

1.2 剪绳子(贪心算法)

题目

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

1.3 矩阵中的路径(回溯和DFS)

本文作者： SparkParis
本文链接： https://sparkparis.github.io/2020/06/06/%E5%89%91%E6%8C%87offer/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

电子科技大学在读研究生<br><br> 专业:<br> 软件工程专业<br><br> 研究方向:<br> 计算机视觉 医学影像 图像超分辨率<br><br> 研究成果:<br> 发表专利一篇<br><br> 语言:<br> JAVA python JavaScript<br><br> 希望从事工作:<br> 前端开发<br><br> 爱好:<br> 摄影,旅游(ready)<br><br> 愿一世安好<br> 款步自然的音乐<br> 轻怀草意和花香<br>