Posts

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 示例： 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。 限制： 0 <= n <= 1000 0 <= m <= 1000 解： 由于每行每列的元素大小都是递增的，所以在遍历时可以判断当前元素是否大于 tatget，如果大于，则开始下一轮遍历。 /** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var findNumberIn2DArray = function(matrix, target) { let result = false for(let i = 0; i < matrix.length; i++){ for(let j = 0; j < matrix[i].length; j++){ if(matrix[i][j] > target){ break } if(matrix[i][j] === target){ result = true return result } } } return result };

找出数组中重复的数字。 在一个长度为 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 } }