Posts

找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1： 输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 限制： 2 <= n <= 100000 解： 哈希，构造一个空对象，遍历数组，每次遍历数组时检查 hash 中是否包含有该元素 var findRepeatNumber = function(nums) { let hash = {} let result = [] for(let item of nums){ hash[item] ? result.push(item) : hash[item] = true } return result[0] };

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 解: 方法1: 暴力法：检查当前元素之后是否有符合条件的元素，时间复杂度为O(n^2)，空间复杂度O(1) /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { for(let i = 0; i < nums.length; i++){ let num = target - nums[i] for(let j = i + 1; j < nums.length; j++){ if(nums[j] === num){ return [i, j] } } } return [] }; 方法2： Hash表：每次迭代都回头检查 Hash 中是否有匹配元素，没有的话则将元素插入 Hash 中，时间复杂度O(n)，空间复杂度O(n) /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let hash = {} for(let i = 0; i < nums.length; i++){ let result = target - nums[i] if(hash[result] !== undefined) return [hash[result], i] hash[nums[i]] = i } return [] };

链表的区别 链表也分为单链表和双链表。 单链表：每个节点包含 value 和 next，next 指向下一个节点 双链表：每个节点包含 prev、value 和 next，prev 指向前一个节点，next 指向下一个节点 单链表的实现 class Node{ constructor(value){ this.value = value this.next = null } } class MyLinkedList{ constructor(){ this.head = null this.length = 0 } // 按索引获取节点 value get(index){ if(index >= 0 && index < this.length){ let current = this.head if(index === 0){ return current.value }else{ let position = 0 while(position < index){ current = current.next position++ } return current.value } } return -1 } // 在头部添加节点 addAtHead(val){ const node = new Node(val) let current = this.head this.head = node this.head.next = current this.length++ } // 添加节点到尾部 addAtTail(val){ const node = new Node(val) if(this.length){ let current = this.head while(current.next){ current = current.next } current.next = node }else{ this.head = node } this.length++ } // 在给定位置添加节点 addAtIndex(index, val){ const node = new Node(val) let position = 0 let current = null let previous = null let length = this.length if(length === 0 && index <= 0){ this.head = node this.length++ }else if (index <= 0){ this.addAtHead(val) }else if(index === length){ this.addAtTail(val) }else if(index > 0 && index < length){ current = this.head while(position < index){ previous = current current = current.next position++ } previous.next = node node.next = current this.length++ } } // 按索引删除 deleteAtIndex(index){ if(index >= this.length) return let current = this.head let previous = null let position = 0 if(index === 0 && index === this.length){ this.head = null }else if(index === 0 ){ this.head = current.next }else{ while(position < index){ previous = current current = current.next position++ } previous.next = current.next } this.length-- } } 双链表的实现 class Node{ constructor(value){ this.value = value this.next = null this.prev = null } } class MyLinkedList{ constructor(){ this.head = null this.length = 0 } get(index){ if(index >= 0 && index < this.length){ let current = this.head if(index === 0){ return current.value }else{ let position = 0 while(position < index){ current = current.next position++ } return current.value } } return -1 } addAtHead(val){ const node = new Node(val) let current = this.head this.head = node this.head.next = current this.length++ if(this.length === 1){ return }else{ current.prev = this.head } } addAtTail(val){ const node = new Node(val) if(this.length){ let current = this.head while(current.next){ current = current.next } current.next = node node.prev = current }else{ this.head = node } this.length++ } addAtIndex(index, val){ const node = new Node(val) let position = 0 let current = null let previous = null let length = this.length if(length === 0 && index <= 0){ this.head = node this.length++ }else if (index <= 0){ this.addAtHead(val) }else if(index === length){ this.addAtTail(val) }else if(index > 0 && index < length){ current = this.head while(position < index){ previous = current current = current.next position++ } previous.next = node current.prev = node node.prev = previous node.next = current this.length++ } } deleteAtIndex(index){ if(index >= this.length) return let current = this.head let previous = null let position = 0 if(index === 0 && this.length === 1){ this.head = null }else if(index === 0){ this.head = current.next current.next.prev = null }else{ while(position < index){ previous = current current = current.next position++ } if(index === this.length - 1){ previous.next = null }else{ previous.next = current.next current.next.prev = previous } } this.length-- } } 环形链表 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 ...

栈 栈是一种线性数据结构，其修改顺序是后进先出(last in first out)，因此也被成为 LIFO表。 在现实生活中可以映射到我们堆叠在桌子上的书、餐具柜中队列的餐盘之类。 我们可以用数组模拟栈： class Static{ constructor(){ this.items = [] } // 检查栈是否为空 get isEmpty(){ return !this.items.length } // 获取栈的长度 get size(){ return this.items.length } // 查看栈顶 get top(){ return this.items[this.items.length - 1] } // 入栈 push(val){ this.items.push(val) return this.items } // 出栈 pop(){ return this.items.pop() } // 清空栈 clear(){ this.items.length = [] return this.items } } 队列 与栈相反，队列是修改顺序是先进先出(first in first out)，称为 FIFO表。 在现实生活中可以映射到点餐队列、打印队列。 用数组模拟队列： class Queue{ constructor(){ this.items = [] } // 检查队列是否为空 get isEmpty(){ return !this.items.length } // 获取队列的长度 get size(){ return this.items.length } // 获取首元素 get first(){ return this.items[0] } // 获取尾元素 get last(){ return this.items[this.items.length - 1] } // 入队 enqueue(val){ this.items.push(val) return this.items } // 出队 dequeue(){ return this.items.shift() } // 清空队列 clear(){ this.items.length = 0 } }

判断输入的是 URL 还是搜索的关键字 转换非 ASCII 的 Unicode 字符 比如：中文、空格 检查HSTS 列表 浏览器检查自带的“预加载 HSTS（HTTP严格传输安全）”列表，这个列表里包含了那些请求浏览器只使用HTTPS进行连接的 URL，如果这个 URL在列表里，则默认使用 HTTPS 协议而不是 HTTP 协议 查找域名的 IP 地址 查找浏览器的 DNS 缓存，没找到则执行下一步 查找操作系统中的 DNS 缓存，没找到则执行下一步 查找 OS 中的 hosts 文件，没找到则执行下一步 在 OS 的 LDNS 中查找域名对应的 IP（这一步可能会遇到 DNS 污染，解决方案为：1. 切换 DNS 服务器；2. 清空 DNS 缓存；3. 修改系统 hosts 文件，将域名与对应的 IP 地址绑定写死），没找到则发起一个迭代 DNS 解析请求 LDNS 向 根域名服务器 发起请求，RDNS 返回 一级域名 对应的 IP 地址 LDNS 向 一级域名服务器 发起请求，得到 二级域名 对应的 IP 地址 LDNS 向 二级域名服务器 发起请求，得到 三级域名 对应的 IP 地址 LDNS 将得到的 IP 地址返回给 OS，并且将这个 IP 地址缓存起来 OS 将 IP 地址返回给浏览器，并且将这个 IP 地址缓存起来 浏览器得到域名对应的 IP 地址，并且将这个 IP 地址缓存起来 建立 TCP 连接 ...