LeetCode - 整数反转 & 回文数
题目链接LeetCode 7. 整数反转 解题思路思路主要就是转换成字符串，主要因为字符串是有反转的方法的。然后思路我对的，不过没想到 Math 有这几个方法，看到别人是这样用 Math 的，受教。 就是学习了 Math 的两个用法，一个是 sign 获取正负的，pow 平方。 代码实现12345678910var reverse = function(x) { let sign = Math.sign(x); let res = (Math.abs(x) + '').split('').reverse().join('') * sign; if (res > Math.pow(2, 31) - 1 || res < Math.pow(2, 31) * -1) { res = 0; } return res;}; 回文数判断在原题链接的基础上，添加符号判断即可。 1234567let sign =...
LeetCode - 合并两个有序链表
题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路递归解法123456789101112var mergeTwoLists = function(l1, l2) { if(l1 === null) return l2; if(l2 === null) return l1; if(l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; }}; 迭代解法123456789101112131415161718var mergeTwoLists = function(l1, l2) { const prehead = new ListNode(-1); ...
数据存储方式
数据存储方式概述1. 数组与链表 数组的存储方式主要为数组和链表。 散列表通过散列函数将键映射到一个大数组中，但需要考虑解决散列冲突。 2. 树结构 用数组实现的树就是堆，因为堆是一个完全二叉树，用数组存储不需要节点指针。 用链表表示，会衍生出巧妙的设计，比如二叉搜索树、AVL树、红黑树。 3. 数组的优缺点 优点: 可以随机访问，通过索引快速找到对应元素。 缺点: 链表不支持随机访问，需要通过顺序访问，通过前驱或者后继依次访问表内元素。 4. 链表的优缺点 优点: 不需要考虑扩容，方便插入和删除元素。如果知道某一个元素的前驱和后驱，插入和删除的时间复杂度就是 O(1)。 缺点: 随机访问效率低。 动态规划1. 动态规划的定义 动态规划问题的一般形式是求最值，求解动态规划的核心是穷举。 关键要素包括重叠子问题、最优子结构、状态转移方程。 2. 方法论 明确 base case。 明确状态，明确选择，定义数组或者函数的含义。 3. 斐波那契数列 暴力递归: 代码低效，主要原因在于出现大量的重复计算。 1234int fib(int N) { if...
LeetCode - 环形链表
题目链接LeetCode 141. 环形链表 解题思路主要思路是对于节点 val 修改数值，那么如果出现节点 next 存在，但是 val 不存在，那就是环形。然而这个明显不对的解，居然通过了。 代码实现1234567891011121314151617181920212223242526/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) { let current = new ListNode(); current.next = head; while (current.next && current.val)...
LeetCode - 数组异或操作
题目链接LeetCode 1486. 数组异或操作 解题思路关键在于首先设置头。 代码实现1234567891011121314151617/** * @param {number} n * @param {number} start * @return {number} */var xorOperation = function(n, start) { let sum = start; let nums = []; let i = 0; while(i < n) { sum = sum ^ (start + (i * 2)); i++; } return sum;}; 总结这个简单，也没啥好说的。
LeetCode - 链表中间节点
题目链接LeetCode 876. 链表的中间结点 解题思路这个一开始我自然只会用最笨的方法了。主要思路是使用快慢指针来找到链表的中间节点。 代码实现12345678910111213141516171819202122/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var middleNode = function(head) { let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; // 慢指针每次走一步 fast =...
LeetCode - 好数对的数目
题目链接LeetCode 1512. 好数对的数目 解题代码1234567891011121314151617181920212223/** * @param {number[]} nums * @return {number} */var numIdenticalPairs = function(nums) { let end = nums.length-1; let start = 0; let total = 0; while(start != nums.length-1) { if(nums[start] === nums[end]) { total++; } end--; if(end == start) { end = nums.length-1; start++; } ...
LeetCode - 旋转链表
题目链接LeetCode 61. 旋转链表 解题思路思路主要包括以下几个步骤： 找到链表的总长度。 计算 k 取余总长度，获取真实移动步数。 根据移动步数，打断链表。 将打断后的链表重新拼接，然后输出。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @param {number} k * @return {ListNode} */var rotateRight = function(head, k) { if (!head)...
LeetCode - 排序列表
题目链接LeetCode 148. 排序链表 解题思路这道题应该是基础的简单排序。主要思路是： 使用归并排序来对链表进行排序。 归并排序的时间复杂度为 O(n log n)，适合链表的排序。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var sortList = function(head) { if (!head || !head.next) { return...
LeetCode - 移除链表元素
题目链接LeetCode 203. 移除链表元素 解题思路这道题最大的困难在于如何处理表头。在掌握了 JS 的传递引用之后，处理链表就慢慢走上正轨。 但是在遍历之后会发现表头无法处理，所以就想出了虚拟一个表头来解决这个问题。在官方题解中，这个做法被认为是”哨兵节点”。 代码实现1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @param {number} val * @return {ListNode} */var removeElements = function(head, val) { let nextNode = null; ...
