030-串联所有单词的子串
原题:串联所有单词的子串
思路:滑动窗口
思路这题其实很容器就能想到用哈希表 + 滑动窗口来解决,但是很多人会被字符串中与子串单词不同长度的单词拦下
其实并不用考虑如何跳过不同长度的单词,我们只要把每一个字符都遍历过就 ok
例如我们有一个字符串 "fofoobarfoo",单词列表 ["foo", "bar"]单词长度为 wordLen = 3,我们只需要处理从下标 0 到 wordLen - 1 开始遍历的情况即可,下面枚举下遍历过程。
遍历过程每次遍历下标步数取单词长度 wordLen 即 3
第一次 i = 0 有以下结果组合: "fofoob", "oobarf"
第二次 i = 1 : "ofooba", "obarfo"
第三次 i = 2 : "foobar", "barfoo"
遍历的所有组合中已经包含了所有结果,不需要考虑中间遇到的长度不相等的单词
思路简述1. 设计一个哈希表来确 ...
004-寻找两个正序数组的中位数
原题:寻找两个正序数组的中位数
思路:计算出中位数需要遍历数组的次数,接着按从小到大的顺序遍历两数组直到步数 = 次数
思路
计算需要走多少步记为 end;判断两数组总长度是否为偶数 flag;初始化两个变量记录当前值和上一个值(偶数时需要计算两数平均值)left = 0, right = 0
使用两个指针 let i = -1, j = -1 开始遍历两数组;使用计数 let step = 0 记录步数
如果第一个数组走到尽头,或者第一个数组的下一个值大于第二个数组的下一个值时 nums[i + 1] === undefined || nums1[i + 1] > nums2[j + 1],移动第二个数组的指针,步数增加,更新当前数和上一个数
或者第二个数组走到尽头,或者第二个数组的下一个值大于等于第一个数组的下一个值时 nums2[j + 1] === undefined || nums2[j + 1] >= nums1[i + 1],移动第一个数组的指针,步数增加,更新当前数和上一个数
如果走够了步数,根据前记录的奇偶返回对应的中间值
1 ...
003-无重复字符的最长子串
原题:无重复字符的最长子串
思路:用哈希表记录每个出现过的字符串的下标,滑动窗口表示当前子串
思路遍历每个字符
如果哈希表中已有该字符串,且在窗口范围中 hashMap.has(char) && hashMap.get(char) >= left,更新滑动窗口起点
如果没有该字符串,则计算当前下标(即窗口的终点)到起点 left 的长度,与最大值 max 比较,保留较大的值
每次循环的最后记录当前字符的下标 hashMap.set(char, right)
1. 初始化1234// 哈希表const hashMap = new Map();// 最大子串长度let max = 0;
开始遍历,滑动窗口起点 **left = -1 (重点)**,计算长度时公式为 right - left,不算入 left 上的字符此时若计算下标 right = 0 的子串长度,结果为 left - right 即 0 - (-1) = 1
123for (let right = 0, left = -1; right < s.length; right++ ...
049-子母异位词分组
原题:字母异位词分组
思路:字符串中字符的种类和出现次数相同,基于这个规律做哈希
思路
每个字符串中字符的种类和出现次数必定相同,要基于此求出哈希值 hashCode
判断哈希表上是否有值 hashMap.has(hashCode),没有就新建数组放在哈希表上,同时推入到结果数组中,有则直接往其中推入当前字符串 hashMap.get(hashCode).push(str)
1. 初始化123456// 结果数组const result = [];// 哈希表const hashMap = new Map();// 记录 'a' 的 ASCII 码,方便后续计算字母出现次数const aCode = 'a'.charCodeAt(0);
1. 求字符串对应哈希值循环字符串列表,对每个字符串求哈希值
题目中提示只会有小写字母,所以我们申请一个长度 26 的数组,用于计算每个字母的出现次数,并且把其值初始化为 0
1234const counter = new Array(26);for (let j = 0; j < coun ...
041-缺失的第一个正数
原题:缺失的第一个正数
思路:把数组本身当成哈希表,把数放回其值对应的下标处,例如值 1 放到 0 下标,没有放合法值的第一个下标 + 1 就是缺失的数
思路
遍历数组,对每个下标,在符合某些条件的情况下,不断把该下标上的元素与其值减一的下标处的元素进行替换nums[nums[i] - 1] = nums[i]
替换的条件为:该位置上的元素为正整数 且 元素值小于等于数组长度 且 在替换目标下标上的值不等于当前值(Note: 重点)**nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]
再次遍历整个数组,找出下标与其值对应不上的下标,该数就是缺失的最小正整数nums[i] !== i + 1
如果没找到,说明整个数组是从 1 开始的连续正整数数组,返回数组长度 + 1 即可
1. 遍历数组每个下标,替换目标元素细节都在思路和注释里,上实现:
12345678910111213141516171819for (let i = 0; i & ...
042-接雨水
原题:接雨水
思路:求每一列上的雨水体积,加起来得到结果
思路经过简单观察可以得知:
首先需要找到该列两侧最高的列 maxL 和 maxR
接着拿两列中较矮的那一列减去当前列高度得到当前列雨水体积 cur = height[i] - min(maxL, maxR)
得到的结果若大于 0,雨水体积 += 该结果 result += cur
1. 找到该列两侧最高的列如果根据思路正常的实现,那么每次循环都要从当前列往两侧寻找最高列,非常耗时
为了减少时间复杂度,我们可以用两个数组来存储每个列左右两侧的最高列:
1234567const maxL = [];// 因为 0 在最左侧,直接给下标 0 的左侧最大值设为 0maxL[0] = 0;const maxR = [];// 最后一个下标在最右侧,直接设置其右侧最大值为 0maxR[height.length - 1] = 0;
根据简单的推导可以得知:
当前列左侧最高列等于 当前列左侧首列 和 其列的左侧最大值 中的 较高列:
maxL[i] = max(height[i - 1], maxL[i - 1 ...
038-外观数列
原题:外观数列
思路:递归
思路1. 递归逻辑
如果递归了 n 次
12// 终止递归,返回上一个值if (count === n) return value;
初始化当前值,重复字符计数器
12let currentStr = '';let number = 0;
根据上一个值,计算当前值
123456789101112131415161718for (let i = 0; i < value.length; i++) { // 如果跟上一个相同或者是一第一个字符,增加计数 if (value.charAt(i - 1) === value.charAt(i) || number === 0) number++; // 如果当前字符与上一个字符不同 else { // 记录重复次数 currentStr += number; // 记录上一个字符 currentStr += value.charAt(i - 1); // 当前字符计数置为 1 number = 1; }& ...
037-解数独
原题:解数独
思路:递归、回溯
思路一看到这种组合+查重的问题,咱们就应该能想到用 递归、回溯 + 哈希表
1. 确认方格中的值是否合法
在行中值唯一
123for (let i = 0; i < 9; i++) { if (board[y][i] === value) return false;}
在列中值唯一
123for (let i = 0; i < 9; i++) { if (board[i][x] === value) return false;}
在当前 3x3 区块中值唯一
1234567const startY = Math.floor(y / 3) * 3;const startX = Math.floor(x / 3) * 3;for (let i = startY; i < startY + 3; i++) { for (let j = startX; j < startX + 3; j++) { if (board[i][j] === value) re ...
广州云徒科技面试
QA
Vue 和 React 区别
vue 双向数据流;react 单向数据流
vue 封装的更全面,不需要开发者手动更新组件;react 需要开发者自行斟酌是否更新组件
Vue 为什么不用手动判断是否更新组件这里涉及到 Vue 双向绑定的原理。
Vue2 中通过 Object.defineProperty 劫持了数据,数据变化时,会通知订阅器,订阅器会让订阅了数据的视图更新。
React 可以怎么优化
useMemo 缓存函数结果、缓存函数组件
React.memo 缓存类组件
类组件中的 shouldComponentUpdate 生命周期钩子
React.PureComponent 内置状态、参数的浅比较实现
父组件下有两个子组件,子组件中更新了自身的状态,哪些生命周期钩子会被调用更新了状态的子组件会从上到下调用以下生命周期钩子函数
什么是深浅比较
浅比较会比较基础类型的类型和值是否相当,引用类型的引用是否相同
深比较会深入比较引用类型内部的值
“==” 是什么比较, “===” 呢=== 和 = ...
广州可酷淘技术面试
QA
JavaScript 和 C 的区别
JavaScript 是弱类型语言,C 是强类型语言
JavaScript 面向对象,C 面向过程
JavaScript 一般运行在浏览器或 v8 引擎中,JavaScript 是解释型语言
面向对象三大特点多态性、继承性、封装性。
什么是多态,举个例子子类继承父类后,可以使用子类来实例化一个父类对象,可以调用在子类复写(实现)的父类上的(抽象)方法,同时该父类对象能够向下转型成子类对象。
123456789101112131415class Parent { public void do() { System.out.println("parent do sth"); }}class Child extends Parent { public void do() { System.out.println("child do sth"); }}Parent p = new Child() ...