Rush

数组中重复的数字

找出数组中重复的数字。在一个长度为 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敲回车之后发生了哪些事

判断输入的是 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 连接 ...