《剑指offer》面试题3 数组中重复的数字

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3
4
5
6

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：
2 <= n <= 100000

来源：力扣（LeetCode）

题目解析

方法一 双层循环对比

a: [2, 3, 1, 0, 2, 5, 3]

b: [2, 3, 1, 0, 2, 5, 3]

拿第一层循环数组的i依次对比第二层循环的数组的i+1元素。

a 取2，然后分别遍历[3,1,0,2,5,3], 如果有重复的，就return，没有的话就i+1，依次类推。

代码如下

1
2
3
4
5
6
7
8
9
10

var findRepeatNumber = function(nums) {
  	let len = nums.length;
 	 for (let i = 0; i < len; i++) {
  		for (let j = i+1; j < len; j++) {
  			if (nums[i] === nums[j]){
  				return nums[i]
  			}
  	 	 }
	 }
};

因为有两层遍历，所以时间复杂度是O(n^2)

方法二 一层循环 + 哈希表

1. 首先定义一个Map
2. 然后遍历数组，判断Map里没有这个值，没有的话set一下，有的话说明这个值已经重复了，所以可以直接输出

代码如下

1
2
3
4
5
6
7
8
9
10
11

var findRepeatNumber = function(nums) {
    let map = new Map()
    let len = nums.length
    for (let i =0; i<len;i++) {
        if (map.has(nums[i])){
            return nums[i];
        } else {
            map.set(nums[i], 1)
        }
    }
};

因为只有一层遍历，所以时间复杂度是O(n)

总结

从时间复杂度上看，当然是建议使用方法二。

前言

最近才发现自己一直混淆了Number.Max_Value和Number.MAX_SAFE_INTEGER，然后经过一段的研究和学习，终于搞懂了。耐心看完这一篇你会了解到IEEE 754标准的浮点数的表示，了解到JS Number对象的最大（小）值，最大（小）安全值都是怎么来的；NAN，正负无穷大，正0，负0在计算机中都是怎么存储的；还有为什么0.1+0.2==0.3 为什么是false

为什么是1-2^53至2^53-1

双精度浮点数 （IEEE 754）

JavaScript的Number类型为双精度IEEE 754 64位浮点类型。我们来看下图

IEEE 754 双精度的格式：(-1)^s*1.M*2^(E-127)

符号位

1 代表负，0代表正

指数位

指数位是IEEE 754的阶码，是用移码表示，移码和补码只有符号位是相反的，所以补码的符号位1代表正数，0代表负数

结束语

前言

最近一两个月每天下班去健身房锻炼1到2个小时，回到家比较晚，又累（借口），所以就没有刷力扣了。

最近感觉，不行了，还是要继续刷题，不能太颓废。所以又开始刷题之旅。

之前一想到动态规划，什么状态方程，状态转移，看到就很头疼，现在开始攻克他。

这道题我还没有出生的时候就已经出现，是比我还老的一道经典题，用它来理解动态规划是比较好的。

题目

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 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

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]	
]
```	

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

## 解题思路及代码


其实我们可以把这个想象成一道数学题。

写数学题第一步是什么，写假设，假设x是什么，y是什么，然后找出x,y之间的关系。

这道题也是这样的。

### 动态规划

首先我们要知道它是要找到自顶向下的最小路径和，所以我们需要用一个数组去存储从顶到每个坐标的最小路径和，这样，我们算到最后一行的时候，只需要到比较最后一行到时候到最小值。

所以dp[i][j]代表着从顶到该坐标（i，j）的最小路径和，假设行数是row，列数是col，所以我们最后只需要找到第row行中最小的dp[row - 1 ][j]（0 <= j < col）

然后移动的时候是有条件的，每一步只能移动到下一行中相邻的结点上。

所以我们可以得到常规情况下:

dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][ j - 1]) + triangle[i][j]

1
2

然后我们考虑边界情况，左边界的话，也就是j===0的时候：

dp[i][j] = dp[i - 1][j]+ triangle[i][j]

1
2

右边界，也就是 i===j的时候

dp[i][j] = dp[i - 1][j - 1]+ triangle[i][j]

1
2

所以我们很容易得到如下代码

/**

• @param {number[][]} triangle
• @return {number}
• /
  var minimumTotal = function(triangle) {
  let row = triangle.length
  if(row === 0) return 0
  let col = triangle[row - 1].length
  let dp = Array.from({length: row}, x => Array.from({length: col}))
  dp[0][0] = triangle[0][0]
  for (let i = 1; i < row; i++) {

  for (let j = 0; j <= i; j++) {
      if (j === 0) {
          dp[i][j] = dp[i - 1][j]+ triangle[i][j] 
      }else if (i === j) {
          dp[i][j] = dp[i - 1][j - 1]+ triangle[i][j] 
      }else {
          dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][ j - 1]) + triangle[i][j]
      }
  }

  }
  let min = Math.min(…dp[row - 1])
  return min
  };

  1 2 3 4 5 6

  ### 优化1 - 时间 首先我们知道最后返回的是一个最小路径和，我们从顶到下去计算的话，最后要去判断一下最后一行中的最短路径的最小值，那么我们反过来呢，逆向思维，我们从底部开始往上走，最后我们走到顶的时候只有一个值了，那个值就是我们要找的最小值,这样就不需要去判断边界条件了。 所以我们可以把遍历的稍稍改动一下：

  /**
• @param {number[][]} triangle
• @return {number}
• /
  var minimumTotal = function(triangle) {
  let row = triangle.length
  if(row === 0) return 0
  let col = triangle[row - 1].length
  let dp = Array.from({length: row}, x => Array.from({length: col}).fill(0))
  for (let k = 0; k < col; k++) {

  dp[row - 1][k] = triangle[row - 1][k]

  }
  for (let i = row - 2; i >= 0; i–) {

  for (let j = 0; j <= i; j++) {
      dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][ j + 1]) + triangle[i][j]
  }

  }
  return dp[0][0]
  };

  1 2 3 4

  ### 优化2 - 空间 我们前面的方法都是用的二维数组存储每个坐标上的最小路径和，比如我们计算第二行的最小路径和的时候，第四行的数据我们已经用不上了，因为第三行的数据把第四行的数据加上了，所以其实我们只需要维护一个长度为col的数组，每次计算后将上次的值覆盖就可以了，

  /**
• @param {number[][]} triangle
• @return {number}
• /
  var minimumTotal = function(triangle) {
  let row = triangle.length
  if (row === 0) return 0
  let dp = new Array(row +1).fill(0)
  for (let i = row - 1; i >=0; i–) {
  for (let j = 0; j <= i; j++) {

  dp[j] = Math.min(dp[j], dp[j+1]) + triangle[i][j]

  }
  }
  return dp[0]
  };
  ```

面试题53 - I. 在排序数组中查找数字 I

题目

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

示例 1:

1
2

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

1
2

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制：

1

0 <= 数组长度 <= 50000

算法题-找出数组中只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2

输入: [2,2,1]
输出: 1

1
2
3

示例 2:
输入: [4,1,2,1,2]
输出: 4

前言

上一篇主要分享了怎么在vue+ts项目中搭建Jest环境，这一篇主要是分享Jest联合vue官方出的单元测试库vue-test-utils一起在项目的使用

Jest

匹配器

基本的测试我们通过expect(value)去实现，比如我们有一个函数sum, 它的返回值是20，然后我们要校验它的返回值是不是20，就可以这么写测试

1
2
3

test('test function sum', () = > {
    expect(sum()).toBe(20)
})

toBe函数就是一个匹配，校验expect的参数的结果是不是和toBe的参数一致，如果一致，验证通过，否则验证不通过。

除了toBe，还有很多匹配器，可以去官网看下 API

toBe是使用Object.is(),如果需要测试精确的相等，需要用toEqual

1
2
3
4
5

test('object assignment', () => {
  const data = {one: 1};
  data['two'] = 2;
  expect(data).toEqual({one: 1, two: 2});
});

下面图中显示了我们常用的一些匹配器

所有匹配器都可以用.not取反

异步测试

回调函数

Promise

async/await

钩子函数

beforeEach

beforeAll

afterEach

afterAll

分组–describe

作用域

Mock

Vue Test Utils

Vue Test Utils 是vue官方的test工具

引入Vue Test Utils

1

import { mount, shallowMount, createLocalVue } from '@vue/test-utils'

可以在测试文件的顶部通过上面的代码引入Vue Test Utils

Wrapper

Vue Test Utils 是一个基于包裹器的 API。

一个 Wrapper 是一个包裹器，它包括了一个挂载组件或 vnode，以及测试该组件或 vnode 的方法。

Wrapper 属性

Wrapper 方法

api

实战

1
2

1. 测试查询的表单的输入框的初始值是不是都是空
2. 测试添加按钮是不是正常
3. 测试table请求是不是返回正常（或者下拉框的请求是不是正常）
4. 测试操作列是不是正常
5. 测试事件点击时候的操作正常不正常
6. dialog的表单的初始值是不是正常
7. dialog的按钮点击事件是不是正常
8. ？ 下拉框的事件

什么是单元测试

先上个图

这个图我们很熟悉，这个在大学某软件课程里会看到这个，这是一个简易的软件的生命周期。

可以看到我们单元测试对应的是编码。单元测试是对我们软件中的最小可测试单元进行检查和验证，比如一个函数，一个模块。单元测试一般来说是开发人员去执行，剩下的集成测试，系统测试等由专业的测试人员来进行。

单元测试不需要访问数据库

单元测试不需要访问网络

单元测试不需要访问文件系统

前言

工作了一年多，发现自己其实学习路线是存在问题的，刚开始学习前端就是直接学习着三个基础HTML，CSS,JavaScript，然后就学习框架vue，然后vue脚手架，vuex，路由，webpack这些。

从来没有考虑过本质，比如浏览器的运行，渲染机制，浏览器怎么和服务器通行等等。所有的认知都只是停留在表面。

所以意识到自己的短板后，开始深入学习。