Leetcode

title: 每日一练（12）：链表中倒数第k个节点 categories:[剑指offer] tags:[每日一练] date: 2022/01/25 每日一练（12）：链表中倒数第k个节点输出一个链表，输入该链表中倒数第k个节点。为了合乎大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。 例如，一个链表有 6 个节点，从头节点开始，它们的值顺次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5. 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：程序查找具体过程如下： 1、第一次遍历失去链表总长度 n。2、第二次遍历到第n−k+1个节点，返回该节点所在的链表援用。实现细节： 当k > n时，链表中没有该节点，咱们返回 nullptr。工夫复杂度剖析： 链表总共遍历两次，所以工夫复杂度是 O(n)ListNode* getKthFromEnd(ListNode* head, int k) { int n = 0; for (ListNode *p = head; p; p = p->next) {//失去链表总长度 n n++; } if (k > n) { //当k > n时，链表中没有该节点 return nullptr; } ListNode *node = head; for (int i = 0; i < n-k; i++) { node = node->next; //遍历到第n−k+1个节点，返回该节点所在的链表援用 } return node;}办法二：快慢双指针快慢指针的思维。咱们将第一个指针 fast 指向链表的第 k + 1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow 二者之间刚好距离 k 个节点。此时两个指针同步向后走，当第一个指针 fast 走到链表的尾部空节点时，则此时 slow 指针刚好指向链表的倒数第k个节点。 ...

【 NO.1 元素计数】 解题思路签到题，排序后去除首尾的元素即可。 代码展现 class Solution { public int countElements(int[] nums) { Arrays.sort(nums); int start = 0, end = nums.length - 1; while (start < end && nums[start] == nums[start + 1]) { start++; } while (start < end && nums[end - 1] == nums[end]) { end--; } return Math.max(0, end - start - 1);}} 【 NO.2 按符号重排数组】 解题思路决裂再归并即可。 代码展现 class Solution { public int[] rearrangeArray(int[] nums) { List<Integer> pos = new ArrayList<>(); List<Integer> neg = new ArrayList<>(); for (int num : nums) { if (num > 0) { pos.add(num); } else { neg.add(num); } } List<Integer> res = new ArrayList<>(); for (int i = 0; i < pos.size(); i++) { res.add(pos.get(i)); res.add(neg.get(i)); } return res.stream().mapToInt(i -> i).toArray();}} ...

本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。【当然是基于js进行解答】。 题目相干原题地址: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/题目形容: 在一个 n * m 的二维数组中，每一行都依照从左到右递增的程序排序，每一列都依照从上到下递增的程序排序。请实现一个高效的函数，输出这样的一个二维数组和一个整数，判断数组中是否含有该整数。现有matric如下:[ [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思路解析首先，暴力破解必定是最容易想到的，然而很显然不对，如果是暴力破解，极限坏的状况复杂度是 m*n > 1000000 （如果暴力能够那题设的枯燥递增条件就没有意义了，如果面试答题用暴力破开破解，预计面试官就是这样的表情：） 而后是： 其次， 思考该如何利用枯燥性呢，如果是一维数组，很容易想到二分法， 然而这是二维数组， 这个思路显然也行不通。这样不行，那也不行。那么最初就只能从树来思考了，留神题设里写到数组的法则是：每一行从左到右递增，每一列从上到下递增，那么很显然（易知(#^.^#)），假如把右上角元素当做一棵树的根节点，那么以它基准，向左查找顺次递加，向下查找顺次递增，如下： 发现什么了没？ （新鸡次哇一次摸hi屡次！）这就是一颗二叉搜寻树啊！ 当然，可能还有同学不晓得啥是二叉搜寻树，问题不大。 简略的来说，每个节点的右边子节点肯定小于它的左边子节点。 那么解法也就跃然纸上了！ 从右上角节点（左下角也能够的，同理）开始搜寻： 如果targe < 以后节点，那么意味着后果只可能落在右边的子树，左边的子树都不必查了，对应到二维数组里也就是--往左挪动一列；如果targe > 以后节点, 那么意味着后果只可能落在左边的子树，右边的子树都不必查了，对应到二维数组里也就是--往下挪动一行；如果target = 以后节点， 那么好耶！ 查找到了，返回true如果遍历齐全部节点还是没找到，那么阐明指标节点不存在，完结；残缺代码了解了后面的核心内容，其实代码就不难写了，最初贴上实现代码： ...

title: 每日一练（11）：调整数组程序使奇数位于偶数后面 categories:[剑指offer] tags:[每日一练] date: 2022/01/24 每日一练（11）：调整数组程序使奇数位于偶数后面输出一个整数数组，实现一个函数来调整该数组中数字的程序，使得所有奇数在数组的前半部分，所有偶数在数组的后半局部。 示例： 输出：nums = [1,2,3,4] 输入：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。 提醒： 0 <= nums.length <= 50000 0 <= nums[i] <= 10000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：有手就行建设容器，第一次循环放入奇数，第二次循环放入偶数 . vector<int> exchange(vector<int>& nums) { vector<int>res; for (int i = 0; i < nums.size(); i++) { if ((nums[i] & 1) != 0) { //nums[i] & 1) != 0 可用 nums[i] % 2 代替 res.push_back(nums[i]); //放入奇数 } } for (int i = 0; i < nums.size(); i++) { if ((nums[i] & 1) != 1) { //nums[i] & 1) != 0 可用 (nums[i] % 2) == 0 代替 res.push_back(nums[i]); //放入偶数 } } return res;}办法二：首尾双指针定义头指针 left ，尾指针 right .left 始终往右移，直到它指向的值为偶数 .right 始终往左移， 直到它指向的值为奇数 .替换 nums[left] 和 nums[right] .反复上述操作，直到 left == right .vector<int> exchange(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left < right) { if ((nums[left] & 1) != 0) { //如果为偶数 left++; continue; } if ((nums[right] & 1) != 1) { //如果为奇数 right--; continue; } swap(nums[left++], nums[right--]); //替换值 } return nums;}办法三：快慢双指针定义快慢双指针 fast 和 slow ，fast 在前， slow 在后 .fast 的作用是向前搜寻奇数地位，slow 的作用是指向下一个奇数该当寄存的地位 .fast 向前挪动，当它搜寻到奇数时，将它和 nums[slow ] 替换，此时 slow 向前挪动一个地位 .反复上述操作，直到 fast 指向数组开端 .vector<int> exchange(vector<int>& nums) { int slow = 0, fast = 0; while (fast < nums.size()) { if ((nums[fast]) & 1) { //奇数 swap(nums[slow], nums[fast]);//替换 slow++; } fast++; } return nums;}

题目：给你一个二叉树的根节点 root ， 查看它是否轴对称。 链接： 力扣Leetcode—高级算法—树—对称二叉树. 示例1 ： 输出：root = [1,2,2,3,4,4,3]输入：true示例2 ： 输出：root = [1,2,2,null,3,null,3]输入：false标签：树、深度优先搜寻、广度优先搜寻、二叉树 思路：同时遍历两棵树，一棵树的程序是左右中，另一棵是右左中 次要Go代码如下： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func isSymmetric(root *TreeNode) bool { // 根节点为空，输入 true if root == nil { return true } // 如不为空，同时遍历左右两棵树 return isSymmetrical(root.Left, root.Right)}func isSymmetrical(life, right *TreeNode) bool { // 如果左树和右树都为空，输入 true if life == nil && right == nil { return true } // 如果左树和右树有一个为空，输入 false if life == nil || right == nil { return false } // 如果左树不等于右数，输入 false if life.Val != right.Val { return false } return isSymmetrical(life.Left, right.Right) && isSymmetrical(life.Right, right.Left)}提交截图： ...

title: 每日一练（10）：删除链表的节点 categories:[剑指offer] tags:[每日一练] date: 2022/01/23 每日一练（10）：删除链表的节点给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 留神：此题比照原题有改变 示例 1: 输出: head = [4,5,1,9], val = 5 输入: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2: 输出: head = [4,5,1,9], val = 1 输入: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. 阐明： 题目保障链表中节点的值互不雷同 若应用 C 或 C++ 语言，你不须要 free 或 delete 被删除的节点 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：惯例解法（循环遍历）如果头部的值是val间接返回头的next即可，不是遍历头部，找到val后间接跳过该节点，并返回head即可 ListNode* deleteNode(ListNode* head, int val) { if (head->val == val) { //头部的值是val间接返回头的next return head->next; } ListNode *node = head; while (node->next != nullptr) {//遍历 if (node->next->val == val) { node->next = node->next->next; return head; } node = node->next; } return head;}办法二：递归递归的形式就比拟奇妙，能够了解从尾部到头判断，空则返回空，非空判断是否等于val，等于返回其next，不等于则返回自身 ...

题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长门路上的节点数。 阐明：叶子节点是指没有子节点的节点。 链接： 力扣Leetcode—高级算法—树—二叉树的最大深度. 示例 ： 给定二叉树 [3，9，20，null，null，15，7] 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。标签：树、深度优先搜寻、广度优先搜寻、二叉树 思路：找出树中深度最大的子树，把他看成一个新树，再持续从新树中找出深度较大者。始终递归到临界点，即当树根为空时，阐明树不存在，深度为 0，递归完结，在其中每递归一次，深度就+1。 次要Go代码如下： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func maxDepth(root *TreeNode) int { i := 0 j := 0 if root == nil { return 0 } i = maxDepth(root.Left) + 1 j = maxDepth(root.Right) + 1 if i < j { i, j = j, i } return i}提交截图：官网解答：官网用了递归 DFS（深度优先搜寻 Depth-First-Search），树的最大深度 = 根节点的高度（基本身为 1 ）+ 左右子树的最大深度中的较大者。而左右子树最大深度怎么求呢？以左子树为例，把它看成新的一棵树，那么它的最大深度就是：根节点的高度（基本身为 1 ）+ 左右子树的最大深度中的较大者。这样就发现递归的所在点了。到临界点即当树根为空时，阐明树不存在，深度为 0，递归完结。 ...

题目：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。 为了示意给定链表中的环，评测零碎外部应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。如果链表中存在环，则返回 true 。 否则，返回 false 。 链接： 力扣LeetBook—高级算法—链表—环形链表. 示例 1： 输出：head = [3,2,0,-4], pos = 1输入：true解释：链表中有一个环，其尾部连贯到第二个节点。示例 2： 输出：head = [1,2], pos = 0输入：true解释：链表中有一个环，其尾部连贯到第一个节点。示例 3： 输出：head = [1], pos = -1输入：false解释：链表中没有环。标签：哈希表、链表、双指针 思路：定义两个指针，一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，如果链表中有环得话，那么快慢指针肯定会相遇。 次要Go代码如下： /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func hasCycle(head *ListNode) bool { //先定义两个指针，一个快指针，一个慢指针，都指向头 fast, slow := head, head for fast != nil && slow != nil && fast.Next != nil { slow = slow.Next //慢指针每次走一步 fast = fast.Next.Next //快指针每次走两步 if slow == fast { //当链表是有环得话，那么快慢指针肯定会相遇 return true } } return false}提交截图： ...

title: 每日一练（9）：打印从1到最大的n位数 categories:[剑指offer] tags:[每日一练] date: 2022/01/22 每日一练（9）：打印从1到最大的n位数输出数字 n，按程序打印出从 1 到最大的 n 位十进制数。比方输出 3，则打印出 1、2、3 始终到最大的 3 位数 999。 示例 1: 输出: n = 1 输入: [1,2,3,4,5,6,7,8,9] 阐明： 用返回一个整数列表来代替打印 n 为正整数 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：间接打印（暴力for循环输入）C 库函数 double pow(double x, double y) 返回 x 的 y 次幂，即 x^y。 复杂度剖析： 工夫复杂度 O(10^n)) ： 生成长度为 10^n 的列表需应用 O(10^n)工夫。空间复杂度 O(1) ： 建设列表需应用 O(1) 大小的额定空间（ 列表作为返回后果，不计入额定空间 ）。vector<int> printNumbers(int n) { vector<int> res; if(n == 0) return res; int max = pow(10,n); //增加到容器数组中 for(int i = 1 ; i < max ; i++) { res.push_back(i); } return res;}办法二：递归实现全排列复杂度剖析： ...

题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 链接： 力扣LeetBook—高级算法—链表—回文链表. 示例 1： 输出：head = [1,2,2,1]输入：true示例 2： 输出：head = [1,2]输入：false标签：栈、递归、链表、双指针 思路： 循环遍历链表，快指针每次走两个节点，慢指针每次走一个节点，当快指针遍历完链表，慢指针停下的地位就是中心点。（因为快指针从第二个节点开始走，所以不须要思考奇偶的状况）当找到中心点后，把慢指针走过的节点从头到中心点截断，为待比拟的第一局部链表。将从中心点到链表结尾的局部所有节点进行倒序操作。作为待比拟的第二局部链表。比拟两个链表每个节点是否相等，如果相等则为回文。次要Go代码如下： /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func isPalindrome(head *ListNode) bool { if head == nil || head.Next == nil { return true } fast := head.Next // 快指针，从第二个开始，能够解决奇偶问题 slow := head // 慢指针 // 因为快指针从第二个节点开始走，所以不须要思考奇偶的状况。 for fast != nil && fast.Next != nil { fast = fast.Next.Next // 快指针每次走两个节点 slow = slow.Next // 慢指针每次走一个节点 } // 当快指针遍历完链表，慢指针停下的地位就是中心点 cur := slow.Next // 保留前面还没有遍历的链表 slow.Next = nil // 将整个列表进行截断，保留为第一个链表 p := reverseLink(cur) // 将前面的链表倒序 // 比拟两个链表 for p != nil && head != nil { if p.Val != head.Val { return false } p = p.Next head = head.Next } return true}// reverseLink 将链表倒序func reverseLink(listHead *ListNode) *ListNode { if listHead == nil && listHead.Next == nil { return listHead } p := listHead // 遍历链表的指针 var rst *ListNode // 保留最初后果链表的指针 var q *ListNode // 保留下一个节点的长期指针 for p != nil { q = p.Next p.Next = rst rst = p p = q } return rst}提交截图： ...

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 链接： 力扣LeetBook—高级算法—链表—反转链表. 示例 1： 输出：head = [1,2,3,4,5]输入：[5,4,3,2,1]示例 2： 输出：head = [1,2]输入：[2,1]示例 3： 输出：head = []输入：[]标签：递归、链表 思路：在遍历链表时，将以后节点的 next 指针改为指向前一个节点。因为节点没有援用其前一个节点，因而必须当时存储其前一个节点。在更改援用之前，还须要存储后一个节点。最初返回新的头援用。 地位调换次数pre（转换后）cur（原来）whole0nil1->2->3->4->51->2->3->4->511->nil2->3->4->52->3->4->5->1->nil22->1->nil3->4->53->4->5->2->1->nil33->2->1->nil4->54->5->3->2->1->nil44->3->2->1->nil55->4->3->2->1->nil次要Go代码如下： type ListNode struct { Val int // 值 Next *ListNode // 指针}func reverseList(head *ListNode) *ListNode { cur := head var pre *ListNode = nil // 空指针 for cur != nil { pre, cur, cur.Next = cur, cur.Next, pre // 这句话最重要 } return pre}提交截图：

title: 每日一练（7）：旋转数组的最小数字 categories:[剑指offer] tags:[每日一练] date: 2022/01/20 每日一练（7）：旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的开端，咱们称之为数组的旋转。 给你一个可能存在 反复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情景进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。 示例 1： 输出：[3,4,5,1,2] 输入：1 示例 2： 输出：[2,2,2,0,1] 输入：0 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：二分查找算法流程： 1.初始化： 申明 i, j 双指针别离指向 nums 数组左右两端；2.循环二分： 设 m = (i + j) / 2 为每次二分的中点（ "/" 代表向下取整除法，因而恒有 i ≤ m < j ）， 可分为以下三种状况： 1.当 nums[m] > nums[j] 时： m 肯定在 左排序数组 中，即旋转点 x 肯定在 [m + 1, j] 闭区间内，因而执行 i=m+1；2.当 nums[m] < nums[j] 时： m 肯定在 右排序数组 中，即旋转点 x 肯定在 [i, m] 闭区间内，因而执行 j = m；3.当 nums[m] = nums[j]时： 无奈判断 m 在哪个排序数组中，即无奈判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案： 执行 j = j - 1 放大判断范畴，剖析见下文。3.返回值： 当 i=j 时跳出二分循环，并返回 旋转点的值 nums[i] 即可。复杂度： ...

title: 每日一练（6）：青蛙跳台阶问题 categories:[剑指offer] tags:[每日一练] date: 2022/01/19 每日一练（6）：青蛙跳台阶问题一只青蛙一次能够跳上1级台阶，也能够跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案须要取模 1e9+7（1000000007），如计算初始后果为：1000000008，请返回 1。 示例 1： 输出：n = 2输入：2示例 2： 输出：n = 7输入：21示例 3： 输出：n = 0输入：1提醒： 0 <= n <= 100 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：动静布局dp方程状态转移公式为dp[i] = dp[i - 1] + dp[i - 2]，实质上与斐波那契数列一样，采纳优化的办法 int numWays(int n) { if(n == 0)return 1; if(n == 1)return 1; if(n == 2)return 2; vector<int> dp(n+1,0); //开数组，留神大小为n+1，含意为第i个台阶有多少中办法 dp[0] = 0; //初始化 dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) { //从第三个台阶开始遍历 dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;//转移方程，留神依据题意取模 } return dp[n];//最初返回dp[n]}办法二：滑动窗口算法流程： ...

title: 每日一练（5）：斐波那契数列 categories:[剑指offer] tags:[每日一练] date: 2022/01/18 每日一练（5）：斐波那契数列写一个函数，输出 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案须要取模 1e9+7（1000000007），如计算初始后果为：1000000008，请返回 1。 示例 1： 输出：n = 2输入：1示例 2： 输出：n = 5输入：5 提醒： 0 <= n <= 100 起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl... 办法一：动静布局算法流程： 斐波那契数的边界条件是 F(0) = 0 和 F(1) = 1。当 n > 1 时，每一项的和都等于前两项的和，因而有如下递推关系： F(n) = F(n - 1) + F(n - 2) ...

【 NO.1 将字符串拆分为若干长度为 k 的组】 解题思路签到题。 代码展现 class Solution { public String[] divideString(String s, int k, char fill) { String[] res = new String[(s.length() + k - 1) / k]; for (int i = 0; i < res.length; i++) { if (k * i + k <= s.length()) { res[i] = s.substring(k * i, k * i + k); } else { res[i] = s.substring(k * i) + repeat(fill, k - (s.length() - k * i)); } } return res;} ...

title: 每日一练（4）：用两个栈实现队列 categories:[剑指offer] tags:[每日一练] date: 2022/01/17 每日一练（4）：用两个栈实现队列用两个栈实现一个队列。队列的申明如下，请实现它的两个函数 appendTail 和 deleteHead ，别离实现在队列尾部插入整数和在队列头部删除整数的性能。(若队列中没有元素，deleteHead 操作返回 -1 ) 示例 1： 输出：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输入：[null,null,3,-1]示例 2： 输出：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]输入：[null,-1,null,null,5,2]提醒： 1 <= values <= 10000最多会对 appendTail、deleteHead 进行 10000 次调用 起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl... 办法：栈一入，栈二出算法流程： 栈 ： 先入后出，后入先出队列 ： 先入先出，后入后出栈s1负责appendTail，栈s2负责deleteHead 插入元素对应办法 appendTail stack1 直接插入元素删除元素对应办法 deleteHead 如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回复杂度剖析 工夫复杂度：对于插入和删除操作，工夫复杂度均为 O(1)。插入不多说，对于删除操作，尽管看起来是 O(n)的工夫复杂度，然而认真思考下每个元素只会「至少被插入和弹出 stack2 一次」，因而均摊下来每个元素被删除的工夫复杂度仍为 O(1)。空间复杂度：O(n)。须要应用两个栈存储已有的元素。class CQueue { stack<int> stack1 , stack2;public: CQueue() { while (!stack1.empty()) { stack1.opo(); } while (!stack2.empty()) { stack2.pop(); } } void appendTail(int value) { stack1.push(value); } int deleteHead() { //如果第二个栈为空 if (stack2.empty()) { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } } if (stack2.empty()) { return -1; } else { int deleteItem = stack2.top(); stack2.pop(); return deleteItem; } }}/** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */

题目：给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。 留神：本题中，咱们将空字符串定义为无效的回文串。 链接： 力扣LeetBook—高级算法—字符串—验证回文串. 示例 1： 输出："A man, a plan, a canal: Panama"输入：true解释："amanaplanacanalpanama" 是回文串示例 2： 输出："race a car"输入：false解释："raceacar" 不是回文串标签：双指针、字符串 思路：因为输出的字符串有除数字、字母外的其余元素，所以咱们定义一个切片来寄存筛选后的字符串，把除数字、字母外的其余元素去除，把大写字母转换成小写字母，失去操作后的切片再进行遍历，验证是否为回文串。 次要Go代码如下： package mainimport "fmt"func main() { fmt.Println(isPalindrome("race a car"))}func isPalindrome(s string) bool { var r []rune // 定义一个切片来寄存筛选后的数组 for _, i := range s { // Ascii编码中 0-9:[48-57], A-Z:[65-90], a-z:[97-122] if i < 48 || (i > 57 && i < 65) || i > 122 || (i > 90 && i < 97) { continue // 把不属于数字、字母筛选去除 } else if i >= 65 && i <= 90 { r = append(r, i+32) // 转换为小写字母 // 为切片动静增加元素 } else { r = append(r, i) } } // fmt.Println("r:", r) for i := 0; i < len(r)/2; i++ { if r[i] != r[len(r)-1-i] { return false } } return true}提交截图： ...

题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 留神：若 s 和 t 中每个字符呈现的次数都雷同，则称 s 和 t 互为字母异位词。 链接： 力扣LeetBook—高级算法—字符串—无效的字母异位词. 示例 1： 输出: s = "anagram", t = "nagaram"输入: true示例 2： 输出: s = "rat", t = "car"输入: false标签：哈希表、字符串、排序 思路：先申明一个map用来寄存每个字符呈现的次数，而后遍历s，统计每个字符呈现的次数，最初遍历t，每遇到一个字符就将统计的次数减去1，一旦呈现正数，就证实不是异位词 次要Go代码如下： package mainimport "fmt"func isAnagram(s string, t string) bool { str1 := len(s) str2 := len(t) CharMap := make(map[rune]int) if str1 != str2 { return false } for _, ss := range s { CharMap[ss]++ } for _, tt := range t { CharMap[tt]-- if CharMap[tt] < 0 { return false } } return true}func main() { fmt.Println(isAnagram("rat", "car"))}提交截图： ...

题目：给定一个字符串，找到它的第一个不反复的字符，并返回它的索引。如果不存在，则返回 -1。 链接： 力扣LeetBook—高级算法—字符串—字符串中的第一个惟一字符. 示例 1： 输出：s = "leetcode"输入：0示例 2： 输出：s = "loveleetcode"输入：2标签：队列、哈希表、字符串、计数 提醒：你能够假设该字符串只蕴含小写字母。 大多数的人会使用暴力拆解，这里咱们用的是哈希Map，先遍历上来，记录下每个单词呈现的次数，记录在Map中，再遍历一次，把字符串中的第一个惟一字符的索引返回。 次要Go代码如下： package mainimport ( "fmt")func firstUniqChar(s string) int { str := len(s) CharMap := make(map[byte]int) //map_variable := make(map[key_data_type]value_data_type) for i := 0; i < str; i++ { CharMap[s[i]]++ //fmt.Println(CharMap[s[i]]) } for i := 0; i < str; i++ { if CharMap[s[i]] == 1 { return i } } return -1}func main() { fmt.Println(firstUniqChar("loveleetcode"))}提交截图：

title: 每日一练（3）：从尾到头打印链表 categories:[剑指offer] tags:[每日一练] date: 2022/01/14 每日一练（3）：从尾到头打印链表输出一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1： 输出：head = [1,3,2]输入：[2,3,1] 限度： 0 <= 链表长度 <= 10000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：遍历反转算法流程： 先遍历一遍获取链表大小从新遍历，将数据insert到arr容器里/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: vector<int> reversePrint(ListNode* head) { int len = 0; ListNode *node = head; while (node != NULL) { len++; //失去数据的长度 node = node->next; } vector<int> arr; ListNode *p = head; for (int i = 0; i < len; i++) { arr.insert(arr.begin(), p->val); //insert倒插 p = p->next; } return arr; }};办法二：应用栈先进后出算法流程： ...

title: 每日一练（2）：替换空格 categories:[剑指offer] tags:[每日一练] date: 2022/01/13 每日一练（2）：替换空格请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1： 输出：s = "We are happy."输入："We%20are%20happy." 限度： 0 <= s 的长度 <= 10000 起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl... 办法：原地批改因为须要将空格替换为 "%20" ，字符串的总字符数减少，因而须要扩大原字符串 s 的长度，计算公式为：新字符串长度 = 原字符串长度 + 2 * 空格个数 算法流程：1.初始化：空格数量 count ，字符串 s 的长度 len ；2.统计空格数量：遍历 s ，遇空格则 count++ ；3.批改 s 长度：增加完 "%20" 后的字符串长度应为 len + 2 * count ；4.倒序遍历批改：i 指向新字符串尾部元素， j 指向原字符串尾部元素；当 i = j 时跳出（代表左方已没有空格，无需持续遍历）； 当 s[i] 不为空格时：执行 s[j] = s[i] ；当 s[i] 为空格时：将字符串闭区间 [j-2, j] 的元素批改为 "%20" ；因为批改了 3 个元素，因而须要 j -= 2 ；5.返回值：已批改的字符串 s ； ...

title: 每日一练（1）：找出数组中反复的数字 categories:[剑指offer] tags:[每日一练] date: 2022/01/12 每日一练（1）：找出数组中反复的数字在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。 示例 1： 输出：[2, 3, 1, 0, 2, 5, 3]输入：2 或 3 限度： 2 <= n <= 100000 起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl... 办法一：哈希表算法流程： 初始化： 新建 HashSet ，记为 dicdic ；遍历数组 numsnums 中的每个数字 numnum ：当 numnum 在 dicdic 中，阐明反复，间接返回 numnum ；将 numnum 增加至 dicdic 中；返回 -1−1 。本题中肯定有反复数字，因而这里返回多少都能够。复杂度剖析： 工夫复杂度 O(N)O(N) ： 遍历数组应用 O(N)O(N) ，HashSet 增加与查找元素皆为 O(1)O(1) 。空间复杂度 O(N)O(N) ： HashSet 占用 O(N)O(N) 大小的额定空间。int findRepeatNumber(vector<int>& num) { unordered_map<int, bool> map; for (int num : nums) { //循环遍历 if (map[num]) { return num; } map[num] = true; } return -1;}办法2：原地替换算法流程： ...

零 题目：算法（leetode，附思维导图 + 全副解法）300题之（39）组合总和码农三少 ，一个致力于编写极简、但齐全题解（算法）的博主一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “回溯（实质：递归）法”// 技巧：说白了，就是通过回溯去穷举所有的状况，依据当前情况进行不同的解决。// 思路：// 1）状态初始化// 2）调用 - 回溯// 3）返回后果 resList var combinationSum = function(candidates, target) { const dfs = (curIndex, l, curSum, target, curArr, resList) => { // 1）递归进口 if (curSum === target) { // 注：须要应用 slice 获取其正本值！ resList.push(curArr.slice()); return; } if (curIndex >= l || curSum > target) { return; } // 2）递归主体（“外围：回溯 = 选 + 不选”） // 2.1）选 curSum += candidates[curIndex]; curArr.push(candidates[curIndex]); dfs(curIndex, l, curSum, target, curArr,resList); // 2.2）不选（“边界：可能须要复原环境！”） curSum -= candidates[curIndex]; curArr.pop(); dfs(curIndex + 1, l, curSum, target, curArr, resList); }; // 1）状态初始化 const l = candidates.length; let curIndex = 0, curSum = 0, curArr = [], resList = []; // 2）调用 - 回溯 dfs(curIndex, l, curSum, target, curArr, resList); // 3）返回后果 resList return resList;};2 计划21)代码： ...

剑指 Offer 03. 数组中反复的数字题目形容： 找出数组中反复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。 示例1： 输出：[2, 3, 1, 0, 2, 5, 3]输入：2 或 3 限度： 2 <= n <= 100000解题思路： 遍历数组，用哈希表存储呈现过的数字： func findRepeatNumber(nums []int) int { var res int existed := make(map[int]struct{}, len(nums)) // Go语言空构造体不占空间；容量是确定的，能够在初始化时分配内存，节约工夫 for _, i := range nums { if _, ok := existed[i]; ok { res = i break } else { existed[i] = struct{}{} } } return res}剑指 Offer 53 - I. 在排序数组中查找数字 I题目形容： ...

剑指 Offer 05. 替换空格题目形容： 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例1： 输出：s = "We are happy."输入："We%20are%20happy."限度： 0 <= s 的长度 <= 10000解题思路： 遍历字符串中每个字符进行替换： func replaceSpace(s string) string { var res []byte for _, c := range []byte(s) { if string(c) == " " { res = append(res, []byte("%20")...) } else { res = append(res, c) } } return string(res)}剑指 Offer 58 - II. 左旋转字符串题目形容： 字符串的左旋转操作是把字符串后面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的性能。比方，输出字符串"abcdefg"和数字2，该函数将返回左旋转两位失去的后果"cdefgab"。 示例1： 输出: s = "abcdefg", k = 2输入: "cdefgab"示例2： ...

回顾链表链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非间断的。链表的节点对象具备两个成员变量：「值 val」，「后继节点援用 next」 。 剑指 Offer 06. 从尾到头打印链表问题形容： 输出一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例1： 输出：head = [1,3,2]输入：[2,3,1]限度： 0 <= 链表长度 <= 1000解题思路： 遍历链表时逆序保留节点的值： /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func reversePrint(head *ListNode) []int { if head == nil { return nil } res := []int{} for cur := head; cur != nil; cur = cur.Next { res = append([]int{cur.Val}, res...) } return res}剑指 Offer 24. 反转链表题目形容： ...

转自：https://leetcode-cn.com/probl... 思路每一位都有3种抉择：1、2、3。 每一次都做抉择，开展出一棵空间树，如下图。 利用约束条件「不能反复选」，做剪枝，剪去不会产生正确解的选项（分支）。 利用 hashMap，记录选过的数，下次遇到雷同的数，跳过。这样就不会进入「不会得出解的分支」，不做有效的搜寻。 怎么写递归函数咱们要在这个蕴含解的空间树上，用 DFS 的形式搜寻出所有的解。 dfs 函数：基于以后的 path，持续选数，直到构建出非法的 path，退出解集。 递归的入口：dfs 执行传入空 path，什么都还没选。 函数体内，用 for loop 枚举出以后所有的选项，并用 if 语句跳过剪枝项。 每一轮迭代，作出一个抉择，基于它，持续选（递归调用）。递归的进口：当构建的 path 数组长度等于 nums 长度，就选够了，退出解集。 为什么要回溯咱们不是找到一个排列就完事，要找出所有满足条件的排列。 当一个递归调用完结，完结的是以后的递归分支，还要去别的分支持续搜。 所以，要撤销以后的抉择，回到抉择前的状态，再选下一个选项，即进入下一个分支。 留神，往 map 存入的以后抉择也要撤销，示意撤销这个抉择。 退回来，把路走全，能力在一棵空间树中，回溯出所有的解。 代码jsgo const permute = (nums) => { const res = [];const used = {};function dfs(path) { if (path.length == nums.length) { // 个数选够了 res.push(path.slice()); // 拷贝一份path，退出解集res return; // 完结以后递归分支 } for (const num of nums) { // for枚举出每个可选的选项 // if (path.includes(num)) continue; // 别这么写！查找是O(n)，减少工夫复杂度 if (used[num]) continue; // 应用过的，跳过 path.push(num); // 抉择以后的数，退出path used[num] = true; // 记录一下 应用了 dfs(path); // 基于选了以后的数，递归 path.pop(); // 上一句的递归完结，回溯，将最初选的数pop进去 used[num] = false; // 撤销这个记录 }}dfs([]); // 递归的入口，空path传进去return res;};解答评论区的困惑为什么退出解集时，要将数组内容拷贝到一个新的数组里，再退出解集？ ...

记字节前端面试一道简略的算法题 70. 爬楼梯 （medium）假如你正在爬楼梯。须要 n 阶你能力达到楼顶。 每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？ 留神：给定 n 是一个正整数。 示例 1： 输出： 2输入： 2解释： 有两种办法能够爬到楼顶。 1 阶 + 1 阶2 阶办法1.动静布局 思路：因为每次能够爬 1 或 2 个台阶，所以到第n阶台阶能够从第n-2或n-1上来，其实就是斐波那契的dp方程复杂度剖析：工夫复杂度O(n)，空间复杂度O(1)Js: var climbStairs = function (n) { const memo = []; memo[1] = 1; memo[2] = 2; for (let i = 3; i <= n; i++) { memo[i] = memo[i - 2] + memo[i - 1];//所以到第n阶台阶能够从第n-2或n-1上来 } return memo[n];};//状态压缩var climbStairs = (n) => { let prev = 1; let cur = 1; for (let i = 2; i < n + 1; i++) { [prev, cur] = [cur, prev + cur] // const temp = cur; // 暂存上一次的cur // cur = prev + cur; // 以后的cur = 上上次cur + 上一次cur // prev = temp; // prev 更新为 上一次的cur } return cur;}Java: ...

须要该PDF文档的敌人扫码关注下方二维码【入门小站】，回复 「1002」 四个字自取 以后面试各个互联网大厂除了扎实的编程技术外,还须要把握常见的一些算法。搞不定就被有情的秒杀了。最近我花工夫搜寻了网络上流传的LeetCode刷题手册,找到一个覆盖面比拟广的PDF文档,供大家学习参考。开源地址https://github.com/halfrost/LeetCode-Go(大佬写的开源书籍,Star 22.1k) 看完这本书内解说的常见数据结构和算法，在 Leetcode 上遇到中等难度的题根本不会卡顿了。这本书蕴含了 LeetCode Online Judge 所有题目的答案，所有的代码实现是十分优雅且执行效率极高的。 不论你是 Java、C++、Go都能够学习，编码标准良好，适宜刷题的同学重复学习，琢磨其中的框架思维。 冒泡排序插入排序抉择排序希尔 Shell 排序疾速排序归并排序堆排序线性排序算法自省排序间接排序计数排序基数排序桶排序内部排序 - k 路归并败者树内部排序 - 最佳归并树这是一本十分用心的刷题类书籍，全书总共 1200 页，分编程技巧、线性表、字符串、栈队列、树、排序、查找、BFS、DFS、贪婪、动静布局等。 须要该PDF文档的敌人扫码关注下方二维码【入门小站】，后盾回复 「1002」 自取 https://rumenz.com/examples/L... 点击上面题目即可获取对应材料LeetCode刷题开源手册 LeetCode题解【java语言实现】 Java根底外围总结PDF下载 程序员简洁简历模板 C语言C++常见面试题【含答案】 设计模式的JAVA实现 3669页vim参考手册 阿里巴巴Java开发手册 阿里云ECS运维Linux系统诊断 Docker速查手册 Linux学习笔记【强悍总结值得一看】 shell扼要教程 前端(HTML5,CSS3,Vue,React,Angular,跨域)面试大全(含答案)

环和杆签到题，遍历一次即可。 class Solution { public int countPoints(String rings) { boolean[][] color = new boolean[10][26]; for (int i = 0; i < rings.length(); i += 2) { color[rings.charAt(i + 1) - '0'][rings.charAt(i) - 'A'] = true; } int result = 0; for (int i = 0; i < 10; i++) { if (color[i]['R' - 'A'] && color[i]['G' - 'A'] && color[i]['B' - 'A']) { result++; } } return result; }}子数组范畴和枚举所有子数组即可。 ...

题目*n 皇后问题 钻研的是如何将 n 个皇后搁置在 n × n 的棋盘上，并且使皇后彼此之间不能互相攻打。给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。* 皇后走法规则皇后的走法是：能够横直斜走，格数不限。因而要求皇后彼此之间不能互相攻打，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。 示例示例 1： 输出：n = 4输入：2解释：如上图所示，4 皇后问题存在两个不同的解法。 示例 2： 输出：n = 1输入：1提醒：1 <= n <= 9 思路定义判断以后地位的检验函数，约束条件蕴含 ，不能同行，不能同列，不能同对角线（45度和135度）定义棋盘；规范回溯解决；应用回溯的具体做法是：顺次在每一行搁置一个皇后，每次新搁置的皇后都不能和曾经搁置的皇后之间有攻打，即新搁置的皇后不能和任何一个曾经搁置的皇后在同一列以及同一条斜线上。当 NNN 个皇后都搁置结束，则找到一个可能的解，将可能的解的数量加 111。 图片起源 解题代码var totalNQueens = function (n) { let count = 0; //皇后可搁置的总数 let isValid = (row, col, board, n) => { //所在行不必判断，每次都会下移一行 //判断同一列的数据是否蕴含 for (let i = 0; i < row; i++) { if (board[i][col] === 'Q') { return false } } //判断45度对角线是否蕴含 for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] === 'Q') { return false } } //判断135度对角线是否蕴含 for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) { if (board[i][j] === 'Q') { return false } } return true } let backTracing = (row, board) => { //走到最初一行，统计次数 if (row === n) { count++; return } for (let x = 0; x < n; x++) { //判断该地位是否能够搁置 皇后 if (isValid(row, x, board, n)) { board[row][x] = 'Q'; //搁置皇后 backTracing(row + 1, board); //递归 board[row][x] = '.'; //回溯，撤销处理结果 } } } backTracing(0, board) let board = [...Array(n)].map(v => v = ([...Array(n)]).fill('.')) //棋盘 return count};总结次要使用了回溯算法；而解决一个回溯问题，实际上就是一个决策树的遍历过程。 ...

题目：给定两个有序数组，将其合并为一个有序数组。思路：采纳双指针的形式，顺次遍历两个数组 a，b。而后比照两个数组各个地位的元素，a小于b，则将a的元素存入新数组，而后a的指针加1，a==b，则将两个元素都放入新数组，下标都加1，如果a大于b，则将b的元素放入新数组，而后b的指针加1。 代码gofunc combine(a, b []int) { left,right := 0,0 lena,lenb := len(a),len(b) res := make([]int, 0) for { if left == lena { res = append(res, b[right:]...) break } if right == lenb { res = append(res, a[left:]...) break } if a[left] < b[right] { res = append(res, a[left]) left++ } else if a[left] == b[right] { res = append(res, []int{a[left], b[right]}...) left++ right++ } else { res = append(res, b[right]) right++ } } fmt.Println(res)}phpfunction test($a, $b):array { $lena = count($a); $lenb = count($b); $res = []; $left = $right = 0; while ($left < $lena && $right < $lenb) { if ($a[$left] < $b[$right]) { $res[] = $a[$left]; $left++; } else if ($a[$left] == $b[$right]) { $res[] = $a[$left]; $res[] = $b[$right]; $left++; $right++; } else { $res[] = $b[$right]; $right++; } } if ($left == $lena) { $res = array_merge($res, array_slice($b, $right)); } if ($right == $lenb) { $res = array_merge($res, array_slice($a, $left)); } return $res;}

题目1：给定一个整数数组，将数组中元素 0 挪动到开端并放弃非 0 元素的程序 结题思路：使用双指针，顺次遍历，将非 0 元素向前移，而后将对应地位的数字设置为 0. 代码gofunc moveZeroes(nums []int){ lens := len(nums) if lens == 0 { return } index := 0 for i := 0; i < lens; i++ { if nums[i] != 0 { nums[index] = nums[i] index++ } } if index < lens { for { nums[index] = 0 index++ if index == lens { break } } }}phpfunction test($arr):array { $len = count($arr); if ($len < 1) { return []; } $index = 0; for ($i=0; $i < $len; $i++) { if ($arr[$i] != 0) { $arr[$index] = $arr[$i]; $index++; } } while($index < $len) { $arr[$index++] = 0; } return $arr;}题目2：给定两个整数数组 nums1 和 nums2，返回它们的交加数组。 ...

零 题目：算法（leetode，附思维导图 + 全副解法）300题之（33）搜寻旋转排序数组一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “忽视要求，间接调用 indexOf 等函数”var search = function(nums, target) { return nums.indexOf(target);};2 计划21)代码： // 计划2 “忽视要求，单指针”// 技巧：// 1）nums是有序的，而后以某个下标进行翻转。// 2）通过观察，能够得悉 新的nums 走势根本就是 “升序-降序-升序”。// 思路（整体分2种状况）：// 1）状态初始化// 2）分 2种 状况 。// 2.1）若 nums[left] <= target ，则 一直判断 nums[left] === target 。// 若 相等，则 间接返回 left，否则 left++ 。// 2.2）若 nums[right] >= target ，则 一直判断 nums[right] === target 。// 若 相等，则 间接返回 right，否则 right-- 。var search = function(nums, target) { // 1）状态初始化 const l = nums.length; let left = 0, right = l - 1; // 2）分 2种 状况 。 // 2.1）若 nums[left] <= target ，则 一直判断 nums[left] === target 。 // 若 相等，则 间接返回 left，否则 left++ 。 if (nums[left] <= target) { while(left < l) { if (nums[left] === target) { return left; } left++; } return -1; } // 2.2）若 nums[right] >= target ，则 一直判断 nums[right] === target 。 // 若 相等，则 间接返回 right，否则 right-- 。 else if(nums[right] >= target){ while(right >= 0) { if (nums[right] === target) { return right; } right--; } return -1; } // 边界case： [4,5,6,7,0,1,2] 3 return -1;}3 计划31)代码： ...

大厂算法面试之leetcode精讲18.队列视频解说（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 队列的特点：先进先出（FIFO）队列的工夫复杂度：入队和出队O(1)，查找O(n)优先队列：priorityQueue，按优先级出队，实现 Heap(Binary,Fibonacci...)js里没有队列，然而能够用数组模仿 225. 用队列实现栈 (easy)办法1.应用两个 Queue 实现思路：还是考查栈和队列的相熟水平，没有什么具体的工程实际意义，能够用两个队列来实现栈的性能，然而一个队列的数据导入另一个队列程序还是没有扭转，所以其中一个队列只是用来做备份的，在代码里queue2就是备份队列，入栈的时候，队列1入队，出栈的时候，如果队列1为空，则替换队列1和队列2，为的是将备份队列的元素全副退出队列1，而后将队列1中除了最初一个元素外全副出队，并且退出备份队列，复杂度剖析：push的工夫复杂度为O(1)，pop的工夫复杂度为O(n)。空间复杂度O(n)，其中n是栈内元素的个数，用两个队列来存储动画过大，点击查看 Js: var MyStack = function() { this.queue1 = []; this.queue2 = [];//备份的队列};MyStack.prototype.push = function(x) { this.queue1.push(x);};MyStack.prototype.pop = function() { // 缩小两个队列替换的次数， 只有当queue1为空时，替换两个队列 if(!this.queue1.length) { [this.queue1, this.queue2] = [this.queue2, this.queue1]; } while(this.queue1.length > 1) {//当队列1的元素数量大于1的时候一直将元素push进备份队列 this.queue2.push(this.queue1.shift()); } return this.queue1.shift();//最初将队列1最初一个元素出队};MyStack.prototype.top = function() { const x = this.pop();//查看栈顶，队列出队，而后在push进队列1 this.queue1.push(x); return x;};MyStack.prototype.empty = function() { return !this.queue1.length && !this.queue2.length;};Java: ...

大厂算法面试之leetcode精讲14.排序算法视频解说（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 常见排序算法复杂度 n^2除nlogn在不同数据规模下的后果 常见排序算法算法可视化起源：http://visualgo.net/ 冒泡排序：工夫复杂度O(n^2) 比拟相邻元素，如果第一个比第二个大，则替换他们一轮下来，能够保障最初一个数是最大的执行n-1轮，就能够实现排序 function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { //相邻元素两两比照 var temp = arr[j+1]; //元素替换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr;}抉择排序：工夫复杂度O(n^2) ...

前言每天保持做一道算法题，并写出本人的解题思路，看看本人能保持多久，答案均以javascript为主,欢送监督 2021/11/29第一题给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。你能够按任意程序返回答案。示例： 输出：nums = [2,7,11,15], target = 9输入：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。解题思路想到这类求和类型的题，第一想到的就是哈希表，将每个值以HAS[KEY]的形式存入Map中，而后遍历看看以后地位的值是否存在[target - nums[i]]这个KEY如果存在则将后果返回，如果不存在持续往MAP里存值~ 答案如下： var twoSum = function(nums, target) { let map = {}; for (let i = 0, len = nums.length; i < len; i++) { const num = nums[i]; if (map.hasOwnProperty(target - num)) { return [map[target - num], i] } map[num] = i }};

16. 最靠近的三数之和给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最靠近。返回这三个数的和。假设每组输出只存在恰好一个解。 示例 1：输出：nums = [-1,2,1,-4], target = 1输入：2解释：与 target 最靠近的和是 2 (-1 + 2 + 1 = 2) 。 示例 2：输出：nums = [0,0,0], target = 1输入：0 提醒：3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104 My Answer: /** * @param {number[]} nums * @param {number} target * @return {number} *//** * 应用三个指针指向这三个数。 * 将数组排序后能够更快地找到指标三个数。 * 第一个指针遍历一遍，下标为i * 第二个指针j初始值为i+1,可右移（++） * 第三个指针k初始值为n,可左移（--） * 当三个数的和小于目标值时，j++ * 当三个数的和大于目标值时，k-- * 当三个数的和等于目标值时，返回 */var threeSumClosest = function(nums, target) { const n = nums.length; const ascArr = nums.sort((a,b)=> a-b); console.log(ascArr); let minDist = Math.abs(ascArr[0]+ascArr[1]+ascArr[2] - target); let res = ascArr[0]+ascArr[1]+ascArr[2]; // i记录第一个数地位 // j记录第二个数地位 // k记录第三个数地位 for (let i = 0; i < n-2; i++) { let j = i+1; let k = n-1; while(j<k) { // 三数之和与目标值更靠近的话，替换 if(Math.abs(ascArr[i]+ascArr[j]+ascArr[k] - target) < minDist){ res = ascArr[i]+ascArr[j]+ascArr[k]; minDist = Math.abs(ascArr[i]+ascArr[j]+ascArr[k] - target); } if(ascArr[i]+ascArr[j]+ascArr[k] < target) { j++; } else if(ascArr[i]+ascArr[j]+ascArr[k] > target){ k--; } else { return target; } } } return res;};17.电话号码的字母组合给定一个仅蕴含数字 2-9 的字符串，返回所有它能示意的字母组合。答案能够按 任意程序 返回。给出数字到字母的映射如下（与电话按键雷同）。留神 1 不对应任何字母。 ...

大厂算法面试之leetcode精讲7.双指针视频教程（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 双指针一般指针：两指针同一方向或不同方向对撞指针：两指针相互聚拢快慢指针：一快一慢141. 环形链表 (easy)办法1.哈希表或set:动画过大，点击查看 思路：筹备一个map或者set，而后循环链表，每次遍历到一个节点的时候，判断以后节点是否在map中存在，如果不存在就把以后节点退出map中，如果存在的话阐明之前拜访过此节点，也就阐明了这条链表有环。复杂度剖析：工夫复杂度O(n)，n是链表的数量，最差的状况下每个节点都要遍历。空间复杂度O(n)，n是存储遍历过的节点的map或者setjs: var hasCycle = (head) => { let map = new Map(); while (head) { if (map.has(head)) return true;//如果以后节点在map中存在就阐明有环 map.set(head, true);//否则就退出map head = head.next;//迭代节点 } return false;//循环实现发现没有反复节点，阐明没环};java: public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<ListNode>(); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; }}办法2.快慢指针动画过大，点击查看 ...

【 NO.1 两栋色彩不同且间隔最远的房子】 解题思路签到题，循环判断即可。 代码展现 class Solution { public int maxDistance(int[] colors) { for (int len = colors.length; len >= 1; len--) { for (int i = 0; i + len <= colors.length; i++) { if (colors[i] != colors[i + len - 1]) { return len - 1; } } } return 0;}} 【 NO.2 给动物浇水】 解题思路模仿浇水过程即可。 代码展现 class Solution { public int wateringPlants(int[] plants, int capacity) { int res = 0; int water = capacity; for (int i = 0; i < plants.length; i++) { if (water < plants[i]) { water = capacity; res += i * 2; } res++; water -= plants[i]; } return res;}} ...

搞定大厂算法面试之leetcode精讲2.工夫空间复杂度视频教程（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 什么工夫复杂度工夫复杂度是一个函数，它定性描述该算法的运行工夫，在软件开发中，工夫复杂度就是用来不便开发者估算出程序运行工夫，通常用算法的操作单元数量来代表程序耗费的工夫，这里默认CPU的每个单元运行耗费的工夫都是雷同的。假如算法的问题规模为n，那么操作单元数量便用函数f(n)来示意，随着数据规模n的增大，算法执行工夫的增长率和f(n)的增长率出现肯定的关系，这称作为算法的渐近工夫复杂度，简称工夫复杂度，记为 O(f(n))，其中n指的是指令集的数目。 什么是大O大O用来示意算法执行工夫的上界，也能够了解为最差状况下运行的工夫，数据量和程序等状况对算法的执行工夫有十分大的影响，这里假如的是某个输出数据用该算法运行的工夫，比其余数据的运算工夫都要长。 插入排序的工夫复杂度咱们都说是O(n^2) ，然而插入排序的工夫复杂度和输出数据有很大的关系，如果输出数据是齐全有序的，则插入排序的工夫复杂度是O(n)，如果输出的数据是齐全倒序的，则工夫复杂度是O(n^2)，所以最坏是O(n^2) 的工夫复杂度，咱们说插入排序的工夫复杂度为O(n^2)。 疾速排序是O(nlogn)，疾速排序的在最差的状况下工夫复杂度是O(n^2) ，个别状况下是O(nlogn)，所以严格从大O的定义来讲，疾速排序的工夫复杂度应该是O(n^2)，然而咱们仍然说疾速排序的工夫复杂度是O(nlogn)，这是业内默认的规定。 二分查找的工夫复杂度是O(logn)，每次二分数据规模减半，直到数据规模缩小为 1，最初相当于求2的多少次方等于n，相当于宰割了logn次。 归并排序的工夫复杂度是O(nlogn)，自顶而下的归并，从数据规模为n宰割到1，工夫复杂度是O(logn)，而后一直向上归并的工夫复杂度是O(n)，总体工夫复杂度是O(nlogn)。 树的遍历复杂度个别是O(n)，n是树的节点个数，抉择排序工夫复杂度是O(n^2)，咱们会在对应的章节逐渐剖析各个数据结构和算法的复杂度。更多的工夫复杂度剖析和推导可参阅主定理。 剖析复杂度的一些规定多个工夫复杂度相加，如果都是与n相干，则取取复杂度高的那一个，例如：O(nlogn + n) = O(nlogn)，O(nlogn + n^2) = O(n^2)。多个工夫复杂度相加，如果其中有些项的复杂度和n不相干则不能疏忽任何项，例如：O(AlogA + B)，O(AlogA + B^2)两个循环顺次执行，则取复杂度高的那个，嵌套多个循环则须要累乘复杂度。常见工夫复杂度：O(1):常数复杂度 let n = 100;O(logn):对数复杂度 //二分查找非递归var search = function (nums, target) { let left = 0, right = nums.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (nums[mid] === target) { return mid; } else if (target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } return -1;};O(n):线性工夫复杂度 ...

如果你想加入算法比赛的倡议越早越好。大一或者更早就须要筹备起来了。如果你曾经快毕业了，那就没有必要筹备了，当做趣味加入一些力扣的较量也是不错的。 <!-- more --> 题库算法面试的考查内容相比算法面试更多，难度也更大。比方数位 dp，倍增，乘法逆元都须要把握。而这些内容在算法面试中呈现的却不多。 题库的话有很多 OJ 网站。然而题目都太多了。 这里举荐两个网站，一个适宜比赛选手，一个适宜一般求职者。 CSES 这个网站比拟适宜比赛选手，题目有 300 道，刷完还是比拟快的（绝对于其余老牌 OJ 平台），地址：https://cses.fi/problemset/ 另外一个是 BinarySearch。用户体验做的很好，题目难度和力扣差不多，难度稳定感觉比力扣小一点点，地址：binarysearch.com/ 练手较量权且先举荐三个平台吧。 其中一个是 codeforces， 这个参加比赛的人晓得的比拟多， codeforces 是寰球范畴内每次较量加入人数最多的比赛平台。普通人可能不太晓得。这个网站的比拟难度偏大一点，品质也更高。打过的人都晓得。 第二个是 Leetcode。这个大家可能据说过。目前力扣有两种赛事。 周赛：每周日早上 10：30双周赛：每两周一次，北京工夫周六的早晨 10：30开始力扣的难度比拟入门，适宜老手。不过难度稳定其实也不小，难度低的时不时是手速场，难度高的话只有能做进去（即便是卡点做进去）都能进前 100。 最初举荐一个是 Google 较量，有三个等级。 Kick Start：新手入门级，也是Google面试的敲门砖，每年举办八轮。Code Jam ：Google的王牌赛事，也是最重要的赛事，分为资格赛、A轮、B轮、C轮和决赛。决赛每年有25个名额。Hash Code：一项团队赛，与个别编程比赛不同，赛题个别为没有最优答案的优化问题。分为资格赛和决赛两轮。学习网站OI wiki 是一个内容比拟全，深度也笼罩较量的网站。外面的内容大略看了下，大部分不错，少部分是从网上抄的，品质也个别。如果你有肯定的鉴别能力，这个网站是十分不错的。地址：https://oi-wiki.org/ 比方图论的 OI-wiki 目录是这样的： CP-Wiki 是集体的 Competitive Programming 学习材料总结。外面不仅有各个知识点的总结。 常识总结是纲要性质的，比拟简略，适宜拿来查缺补漏。 而且还有各个较量的题解，强烈建议学习比赛的你珍藏。 学习图书《算法比赛进阶指南》举荐浏览李煜东的《算法比赛进阶指南》。他有丰盛的参加比赛以及培训比赛的教训，同时他也是 Google 的工程师。 李煜东曾为NOI系列比赛、NOI导刊培训基地以及全国各地多所学校的选手授课，并在网络上组织模仿赛数十场，经验丰富、解说透彻、广受好评。屡次帮助石家庄市第二中学的信息学比赛集训工作，参加北京大学“数据结构与算法”、“算法设计与剖析”的课程教学、考试命题工作。 豆瓣评分 9.1 ，大众的眼睛还是雪亮的！ 这种书在算法比赛中知名度还是很高的。你如果筹备算法面试的话可能据说过。 如果没有据说过，当初无妨买来看看。 附上这种书的目录给大家： 0x00 根本算法0x01 位运算0x02 枚举、模仿、递推0x03 递归0x04 二分0x05 排序0x06 倍增0x07 贪婪0x08 总结与练习0x10 根本数据结构0x11 栈0x12 队列0x13 链表与邻接表0x14 Hash0x15 字符串0x16 Trie0x17 二叉堆0x18 总结与练习0x20 搜寻0x21 树与图的遍历0x22 深度优先捜索0x23 剪枝0x24 迭代加深0x25 广度优先捜索0x26 广捜变形0x27 A*0x28 IDA*0x29 总结与练习0x30 数学知识0x31 质数0x32 约数0x33 同余0x34 矩阵乘法0x35 高斯消元与线性空间0x36 组合计数0x37 容斥原理与Möbius函数0x38 概率与数学冀望0x39 0/1分数布局0x3A 博弈论之SG函数0x3B 总结与练习0x40 数据结构进阶0x41 并査集0x42 树状数组0x43 线段树0x44 分块0x45 点分治0x46 二叉査找树与均衡树初步0x47 总结与练习0x50 动静布局0x51 线性DP0x52 背包0x53 区间DP0x54 树形DP0x55 环形与后效性解决0x56 状态压缩DP0x57 倍增优化DP0x58 数据结构优化DP0x59 枯燥队列优化DP0x5A 斜率优化0x5B 四边形不等式0x5C 计数类DP0x5D 数位统计DP0x5E 总结与练习0x60 图论0x61 最短路0x62 最小生成树0x63 树的直径与最近公共先人0x64 基环树0x65 负环与差分束缚0x66 Tarjan算法与无向图连通性0x67 Tarjan算法与有向图连通性0x68 二分图的匹配0x69 二分图的笼罩与独立集0x6A 网络流初步0x6B 总结与练习0x70 综合技巧与实际0x71 C++ STL0x72 随机数据生成与对拍0x7F 附录如果你不打算参加算法比赛，我也倡议你买过去看看，不过内容能够选择性看看即可。如果你也不晓得应该看哪局部，能够在我的交换群中进行探讨，公众号力扣加加回复 leetcode 进群。 ...

本系列次要记录 LeetCode 经典算法题的解题记录以及从看到题目到解出答案，最终多思维拓展的的过程。仅作为题目记录以及解题思路探讨（心愿大家能够一起沟通解题思路），以管中窥豹的形式学习算法！目前理解并浏览过的书籍举荐 漫画算法、数据结构注：贴出来的代码为了不便，一个思路中可能多个逻辑解法，如需复制运行留神正文阐明 回文数题目形容： 题意拆解:判断一串数字是否是回文数，返回boolean值 回文数(回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。)思路一：遍历顺叙判断是否和原始值完全一致var isPalindrome = function(x) { if (x < 0) return false; // 思路一：正序和顺叙的值是完全一致的则是回文 // 这里可利用遍历、顺叙、等数组/字符串的原生办法 // 利用 reverse （76-80ms） x = x.toString(); let reverse_x = x.split("").reverse().join(""); return x === reverse_x; // 遍历 (60-84ms) x = x.toString().split(""); let reverse_x = ''; for (let i = 0; i < x.length; i++) { const ele = x[i]; reverse_x = ele + reverse_x; } return reverse_x === x.join('');};思路二：基于数字个性的进制替换 既然是数字能够利用进制替换（60-92ms）// 思路二：既然是数字能够利用进制替换（60-92ms）var isPalindrome = function(x) { let reverse_x = 0; for (let i = x; i >= 1; i = Math.floor(i / 10)){ reverse_x = reverse_x * 10 + (i % 10); } return reverse_x === x; // 既然是回文那么我只遍历一半呢 let reverse_x = 0; let center_index, minVal = 1; let x_leng = x.toString().length; center_index = Math.ceil(x_leng / 2); minVal = Math.pow(10, center_index); for (let i = x; i >= minVal; i = Math.floor(i / 10)) { reverse_x = reverse_x * 10 + (i % 10); } return reverse_x === Math.floor(x / minVal); // 利用 which 替换for if (x < 0) return false; let temp = x; let res = 0; while (x) { res = res * 10 + (x % 10); x = Math.floor(x / 10); } return res == temp;};此处回文的只是数字利用数字位替换，判断连个位数知否相等；既然是回文那么咱们只遍历个别数字判断遍历的前半部分和未解决的后半局部是否统一即可 ...

栈和排序跟多题解，关注公众号【程序员学长】，送你上百本经典计算机电子书 问题形容给你一个由1~n，n个数字组成的一个排列和一个栈，要求依照排列的程序入栈。如何在不打乱入栈程序的状况下，仅利用入栈和出栈两种操作，输入字典序最大的出栈序列。 排列：指 1 到 n 每个数字呈现且仅呈现一次。 示例： 输出：[2,1,5,3,4] 输入：[5,4,3,1,2] 剖析问题因为咱们只能应用出栈和入栈两种操作，要想使得出栈序列字典序最大，首先想到的就是令高位尽可能地大，咱们出栈的机会就是：以后入栈元素若是大于之后将要入栈的元素，那么就将其出栈。当元素出栈后，还须要判断栈顶元素与之后将要入栈元素之间的大小关系，如果此时栈顶元素大于之后将要入栈的元素，那么就将其出栈，一直判断直到栈为空或条件不满足。 为了疾速判断“以后入栈元素是否大于之后将要入栈的元素”，咱们须要创立一个辅助数组temp，其中temp[i]示意i之后的最大元素。借助辅助数组，咱们能够以O(1)的工夫复杂度去判断以后入栈元素是否大于之后将要入栈的元素。 上面咱们来看一下代码的实现。 import sysclass Solution: def solve(self , a): n=len(a) res=[] if n==0: return res stack=[] temp=[0]*n temp[n-1]=-sys.maxsize-1 #从右往左遍历数组a,而后取填充temp #使得temp[i]示意i之后的最大元素 for i in range(n-2,-1,-1): temp[i]=max(a[i+1],temp[i+1]) #遍历数组a for i in range(0,n): if a[i] > temp[i]: #若以后元素大于之后将要入栈的元素,将其退出后果中 res.append(a[i]) # 若栈不为空，且栈顶元素大于temp[i], # 栈顶出栈，退出后果中 while stack and stack[-1] > temp[i]: res.append(stack[-1]) stack.pop() else: stack.append(a[i]) while stack: res.append(stack[-1]) stack.pop() return res该算法的工夫复杂度是O(n)，空间复杂度也是O(n)。 ...

序列化二叉树更多题解，欢送关注公众号【程序员学长】，欢送退出 问题形容剑指 Offer 37. 序列化二叉树请实现两个函数，别离用来序列化和反序列化二叉树。你须要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只须要保障一个二叉树能够被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 示例： 输出：root = [1，2，3，null，null，4，5] 输入：[1，2，3，null，null，4，5] 剖析问题咱们都晓得对于不同的二叉树进行先序、中序、后序或者层序遍历失去的遍历后果有可能是雷同的，即如果晓得了遍历序列，咱们不能确定惟一的一颗二叉树，而题目要求的序列化和反序列化是一对可逆操作，即对一棵树进行序列化后，咱们还能通过序列化后的后果反序列化还原成原来的那棵树。所以咱们须要对二叉树的遍历过程革新一下，这里以层序遍历为例。在遍历的过程中，为了残缺的示意二叉树，思考将叶节点下的 null 也记录。上面咱们来看一下具体的实现。 序列化咱们能够借助队列来实现二叉树的层序遍历，在层序遍历的过程中，咱们把越过叶子节点的null也退出序列化的后果中。具体算法流程如下所示： 如果给定的二叉树为空，间接返回"[]"初始化一个队列queue，并把根节点退出。对二叉树进行层序遍历。当队列为空时跳出。 节点出队，记为node。如果node不为空，将node.val退出后果列表中，并且将node的左、右子节点入队。如果node为空，将“null”退出后果列表中。拼接后果列表，用 ',' 隔开，首尾增加中括号；并将其返回。 反序列化利用队列按层构建二叉树。具体算法流程如下所示： 如果data为空，间接返回null。初始化列表vals（去掉首尾括号，再用逗号隔开），指针 i = 1 ，将根节点 root （值为 vals[0] ）入队；按层构建二叉树，当队列为空时跳出； 节点出队，记为node。构建 node 的左子节点，node.left 的值为 vals[i] ，并将 node.left 入队；而后执行i=i+1。构建 node 的右子节点，node.right 的值为 vals[i] ，并将 node.right 入队；而后执行i=i+1。返回根节点 root 即可。 上面咱们来看一下代码的实现。 class Codec: def serialize(self, root): #如果二叉树为空，间接返回"[]" if not root: return "[]" #初始化一个队列 queue = collections.deque() #将根节点退出队列中 queue.append(root) #后果列表 res = [] #记录null的个数，遇到非空节点就将之前的null节点退出到后果列表中 null_count=0 while queue: node = queue.popleft() if node: #遇到非空节点就将之前的null节点退出到后果列表中 if null_count != 0: res.extend(["null"] * null_count) null_count=0 res.append(str(node.val)) #node的左、右子节点入队 queue.append(node.left) queue.append(node.right) else: #记录null节点的个数 null_count=null_count+1 return '[' + ','.join(res) + ']' def deserialize(self, data): #如果data为"[]",代表二叉树是空，间接返回 if data == "[]": return #初始化 vals = data[1:-1].split(',') i=1 #初始化根节点，并将其入队 root = TreeNode(int(vals[0])) queue = collections.deque() queue.append(root) while queue: if i>=len(vals): break node = queue.popleft() #增加左子节点 if vals[i] != "null": node.left = TreeNode(int(vals[i])) queue.append(node.left) i += 1 if i>=len(vals): break #增加右子节点 if vals[i] != "null": node.right = TreeNode(int(vals[i])) queue.append(node.right) i += 1 return root

大家好，我是程序员学长~ 明天给大家带来一篇面试高频算法题之数组的具体解析，全文蕴含19道大厂口试面试算法真题，一举拿下数组这个知识点，让算法不在成为进入大厂的绊脚石。 如果喜爱，记得点个关注哟~ 本文有点长，我已将本文制作成带目录的PDF版本，获取本文PDF版本，请关注【程序员学长】，私信我。 github地址曾经更新，欢送star。https://github.com/meetalgo/m... 全文概览 数组的基础知识数组的定义及特点数组是一种线性表数据结构，是在间断内存空间上的存储雷同类型数据的汇合。 数组次要有以下特点。 数组的下标是从0开始的。间断的内存空间和雷同的数据类型。正是因为数组的内存空间是间断的，所以咱们能够“随机拜访”数组内的元素。但有利有弊，如果想要在数组中插入或者删除一个元素，为了保障数组的内存空间的间断，就不免要挪动其余元素。 例如要删除下标为2的元素，须要对下标2前面的元素都须要向前挪动。如图所示： 解题有妙招二分法如果给定的数组是有序的，咱们就须要思考是否能够应用二分法来求解（二分法的工夫复杂度是O(logn)）。面试中二分法是面试中常考的知识点，倡议大家肯定要多锤炼手撕二分的能力。 双指针法咱们能够通过一个快指针和慢指针在一个for循环下实现两个for循环的工作。例如，当咱们须要枚举数组中的两个元素时，如果咱们发现随着第一个元素的递增，第二个元素是递加的，那么就能够应用双指针的办法，将枚举的工夫复杂度从O(N^2)减低到O(N)。 滑动窗口顾名思义，所谓的滑动窗口就是能够在一个序列上进行滑动的窗口。其中窗口大小有固定长度的，也有可变长度的。例如给定数组[2,2,3,4,8,99,3]，窗口大小为3，求出每个窗口的元素和就是固定大小窗口的问题，如果求数组[2,2,3,4,8,99,3]的最长间断子数组就是窗口可变的问题。应用滑动窗口，咱们能够减低算法是工夫复杂度。 应用滑动窗口求解问题时，次要须要理解什么条件下挪动窗口的起始地位，以及何时动静的扩大窗口，从而解决问题。 哈希表法如果须要在数组中查找某个元素是否存在时，咱们能够应用哈希表法，能够将查找元素的工夫复杂度从O(n)减低到O(1)。 两数之和问题形容LeetCode 1. 两数之和 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。你能够按任意程序返回答案。 示例 1： 输出：nums = [2,7,11,15], target = 9 输入：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 剖析问题拿到这个问题，最简略直观的想法就是对于数组中的每个元素x，去寻找数组中是否存在target-x。 def twoSum(nums, target): n = len(nums) for i in range(n): #对于数组中的每个元素i #位于它之前的元素都曾经和它匹配过了，不须要反复进行匹配 for j in range(i + 1, n): if nums[i] + nums[j] == target: return [i, j] return []咱们能够很分明的晓得，这个算法的工夫复杂度是O(n^2)。那咱们该如何升高工夫复杂度呢？能够留神到该算法复杂度高的起因在于寻找元素target-x的时候，须要遍历一遍数组，所以咱们须要对这一块进行优化。咱们能够采纳哈希表，将寻找元素target-x的工夫复杂度由O(n)升高到O(1)。 ...

划分链表更多算法题解，请关注公众号【程序员学长】 问题形容LeetCode 面试题 02.04. 宰割链表 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都呈现在 大于或等于 x 的节点之前。并且两个局部之内的节点之间与原来的链表要放弃绝对程序不变。 示例： 输出：head = [1,4,3,2,5,2], x = 3 输入：[1,2,2,4,3,5] 剖析问题简略来说，咱们只须要保护两个链表small和large即可，使得small链表按顺序存储所有小于x的节点，large链表按顺序存储所有大于等于x的节点。当咱们遍历完链表之后，只须要将small链表的尾节点指向large链表的头结点即可实现宰割链表的操作。 首先，咱们创立两个节点smallHead和largeHead别离为两个链表的哑结点，这是为了不便的解决头结点为空的边界条件，同时smallTail和largeTail别离指向两个链表的开端节点。开始时，smallHead=smallTail，largeHead=largeTail，而后从前往后遍历链表head，判断以后节点的值是否小于x，如果小于x，就将smallTail的next指针指向该节点，否则将largeTail的next指针指向该节点。 遍历完结后，咱们将largeTail的next指针置为空，这是因为以后节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x的节点，咱们须要切断这个援用。而后将smallTail的next指针指向largeHead的next指针指向的节点，来将两个链表合并起来，最初返回smallHead.next即可。 上面咱们来看一下代码实现。 class Solution(object): def partition(self, head, x): #创立两个哑结点 smallHead = smallTail = ListNode(0) largeHead = largeTail = ListNode(0) #遍历链表 while head: #如果head.val<x,将以后节点插入small中，否则插入large中 if head.val < x: smallTail.next=head smallTail=smallTail.next else: largeTail.next=head largeTail=largeTail.next head=head.next largeTail.next=None #合并两个链表 smallTail.next=largeHead.next return smallHead.next该算法的工夫复杂度是O(n)，空间复杂度是O(1)。 ...

链表中倒数最初k个节点更多算法题解，请关注公众号【程序员学长】 问题形容LeetCode 剑指 Offer 22. 链表中倒数第k个节点 输出一个链表，输入该链表中倒数第k个节点。为了合乎大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值顺次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例： 输出：{1,2,3,4,5}，2 输入：{4,5} 剖析问题这道题比较简单，咱们能够间接应用快慢指针来求解，开始时申请两个指针同时指向链表的头结点，记为slow和fast，而后让fast先挪动k步，再而后让两个指针slow和fast同时挪动，使得fast和slow在挪动的过程中总是相隔k个单位，当fast指针走到开端的时候，此时slow正好指向的是倒数第k个地位。 上面咱们来看一下代码的实现。 class Solution: def FindKthToTail(self, pHead, k): #快慢指针同时执行头结点 slow=fast=pHead #快指针挪动k步 for i in range(0,k): #如果还没走完k步就走到了链表尾，间接返回None if not fast: ‘return None fast = fast.next #两个指针同时挪动,直到fast为空 while fast: slow=slow.next fast=fast.next return slow

重排链表更多算法题解，请关注公众号【程序员学长】 问题形容LeetCode 143. 重排链表 给定一个单链表 L 的头节点head ，单链表 L 示意为：L0 -> L1 -> ... -> Ln-1 -> Ln，将其重新排列后变成 L0 -> Ln -> L1 -> Ln-1 -> ...。不能只是单纯的扭转节点的值，而须要理论的进行节点的替换。 示例： 输出： head = [1，2，3，4] 输入： [1，4，2，3] 剖析问题首先，咱们来察看一下链表重置前和重置后的变动。如下图所示： 咱们能够晓得，重置后的链表是将原链表的左半端和反转后的右半段进行节点穿插合并而成的，所有咱们能够分三步来求解。 找到原链表的中点，将链表宰割成左右两局部。对后半局部进行反转。建原链表的左半局部和反转后的右半局部进行合并。class Solution: def reorderList(self, head): #如果链表为空，间接返回 if not head: return #寻找链表的中点，将链表宰割成左右两局部 mid = self.middleNode(head) left = head right = mid.next mid.next = None #对右半局部的链表进行反转 right = self.reverseList(right) #左右链表进行合并 self.mergeList(left, right) def middleNode(self, head): #应用快慢指针法求中点 slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow #对链表进行反转 def reverseList(self, head): prev = None curr = head while curr: tmp = curr.next curr.next = prev prev = curr curr = tmp return prev #对两个链表进行合并操作 def mergeList(self, l1, l2): #l1和l2的节点数量相差不会超过一个 #所以间接合并就好 while l1 and l2: tmp1 = l1.next tmp2 = l2.next l1.next = l2 l1 = tmp1 l2.next = l1 l2 = tmp2该算法的工夫复杂度是O(N)，空间复杂度是O(1)。 ...

链表的奇偶重排更多算法题解，请关注公众号【程序员学长】 问题形容LeetCode 328. 奇偶链表 给定一个单链表，把所有的奇数节点和偶数节点别离排在一起。请留神，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 示例： 输出：{1，2，3，4，5，6} 输入：{1，3，5，2，4，6} 剖析问题要想把一个链表的奇数节点和偶数节点别离排在一起，咱们能够先拆散链表，把一个链表拆分成两个链表，其中一个是奇数链表，另一个是偶数链表，最初将偶数链表拼接在奇数链表后即可。 咱们都晓得，对于一个链表来说，相邻节点的奇偶性是不同的。原始链表的头节点head是奇数链表的头节点，head的后一个节点是偶数链表的头节点，咱们假如是evenHead ，则evenHead = head.next。咱们保护两个指针odd和even别离指向奇数链表和偶数链表的最初一个节点，初始时 odd=head，even=evenHead。通过一直的更新odd和even，将链表宰割成奇数链表和偶数链表。 更新奇数节点，咱们令 odd.next=even.next，此时奇数链表的最初一个节点指向了偶数节点even的后一个节点。而后令odd=odd.next，此时odd变成了even的后一个节点。更新偶数节点，咱们令 even.next=odd.next，此时偶数节点的最初一个节点指向了奇数节点odd的后一个节点。而后令even=even.next，此时even变成了odd的后一个节点。通过以上两步，咱们就实现了对一个奇数节点和一个偶数节点的拆散。反复上述操作，直到全副节点拆散实现。最初令 odd.next = evenHead，将偶数链表连贯在奇数链表之后，即实现了奇数链表和偶数链表的合并。 上面咱们来看一下代码的实现。 class Solution: def oddEvenList(self, head): #如果链表为空，间接返回 if not head: return head #evenHead指向偶数链表的头节点 evenHead = head.next #指向奇数链表和偶数链表的开端节点 odd = head even = evenHead while even and even.next: #奇数链表的开端节点指向偶数节点的下一个节点 odd.next = even.next #奇数链表开端节点后移 odd = odd.next #偶数链表的开端节点指向奇数节点的下一个节点 even.next = odd.next #偶数链表开端节点后移 even = even.next #偶数链表连贯到奇数链表的开端 odd.next = evenHead return head该算法的工夫复杂度是O(n)，空间复杂度是O(1)。 ...

更多算法常识，请关注公众号《程序员学长》 删除有序链表中反复的元素-II问题形容LeetCode 82. 删除排序链表中的反复元素 II 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字反复状况的节点，只保留原始链表中没有反复呈现的数字。返回同样按升序排列的后果链表。 示例: 输出：head = [1，2，3，3，4，5] 输入：[1，2，5] 剖析问题因为给定的链表是有序的，所以链表中反复的元素在地位上必定是相邻的。因而，咱们能够对链表进行一次遍历，就能够删除反复的元素。 这里须要留神一点，因为可能会删除头结点head，咱们引入了一个哨兵节点dummy，让dummy.next=head，这样即便head被删除了，那么也会操作dummy.next指向新的链表头结点，所以最终返回dummy.next即可。 首先，咱们让cur指针指向链表的哨兵节点，而后开始对链表进行遍历。如果cur.next与cur.next.next对应的元素值雷同，那么咱们就须要将cur.next以及前面所有值雷同的链表节点全副删除，直到cur.next为空节点或者其元素值与其不同。如果cur.next与cur.next.next对应的元素值不雷同，那么咱们就能够将cur 指向 cur.next。 上面咱们来看一下代码的实现。 class Solution: def deleteDuplicates(self, head): #如果链表为空，间接返回 if not head: return head #创立一个哨兵节点 dummy = ListNode(0) dummy.next=head #开始时，将cur指向哨兵节点 cur = dummy while cur.next and cur.next.next: #如果cur.next.val和cur.next.next.val雷同，删除反复元素 if cur.next.val == cur.next.next.val: data = cur.next.val while cur.next and cur.next.val == data: cur.next = cur.next.next else: cur = cur.next return dummy.next该算法的工夫复杂度是O(n)，空间复杂度是O(1)。 ...

链表内指定区间反转更多算法常识，请关注公众号《程序员学长》 问题形容LeetCode 92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从地位 left 到地位 right 的链表节点，返回反转后的链表 。 示例： 输出：head = [1,2,3,4,5]， left = 2，right = 4 输入：[1,4,3,2,5] 剖析问题对于链表相干的题目，咱们肯定要先想分明思路，搞懂指针挪动的先后顺序。 对于这道题，咱们能够采纳头插法来求解。在链表反转的区间内，当咱们每次遍历到一个节点时，就让该节点插入到反转局部的起始地位。如下图所示： 具体来说，咱们定义三个指针pre、cur、next变量。 咱们首先将pre挪动到第一个要反转的节点的后面，即pre->next=left而后将指针cur挪动到第一个要反转的节点地位上，即cur=left，而后将 cur->next 赋值给变量next。将cur的下一个节点指向next的下一个节点，即cur->next=next->next而后将next的下一个节点指向pre的下一个节点，即next->next=pre->next而后将next插入到链表头部，即pre->next=next。而后周而复始执行3、4、5、6，直到反转完链表区间内的节点。 上面咱们来看一下代码如何实现。 class Solution: def reverseBetween(self, head, left, right): #设置哨兵节点，对于链表相干的问题，咱们通过设置哨兵节点 #能够省去边界条件的判断 dummynode = ListNode(-1) #哨兵节点指向链表头 dummynode.next = head pre = dummynode #遍历，使得pre指向链表反转局部 #的第一个结点left for _ in range(left - 1): pre = pre.next #cur指向链表反转局部的第一个节点 cur = pre.next for _ in range(right - left): next = cur.next cur.next = next.next next.next = pre.next pre.next = next return dummynode.next该算法的工夫复杂度是O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就实现了反转。空间复杂度是O(1)，只用到了常数个变量。 ...

判断一个链表是否为回文结构更多算法题解，请关注公众号【程序员学长】 问题形容LeetCode 剑指 Offer II 027. 回文链表 给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。 示例： 输出：{1,2,2,1} 输入：true 阐明：1 -> 2 -> 2 -> 1 剖析问题回文串是斧正读反读都一样的字符串，最简略的是应用双指针法。然而对于链表这种数据结构来说，指针只能向一个方向挪动，也就是说只能找到后继节点，没方法找到前驱节点。所以没方法应用双指针法，要想应用双指针，咱们就须要把链表元素放入一个数组中，而后再去判断是否是回文，这须要O（n）的空间复杂度，这里就不在赘述。大家能够去看第44题。 咱们能够这么思考，将链表的后半局部进行反转，而后将前半部分和后半局部进行比拟，如果雷同就代表是回文链表，否则不是回文链表。寻找链表的中点咱们能够应用快慢指针的形式。 快慢指针寻找链表中点。 对链表的后半局部进行翻转 前半部分和后半局部进行比拟。 class Solution: def isPalindrome(self, head) -> bool: #链表为空，间接返回true if head is None: return True #找到链表的中点 middle_point = self.middle_point(head) second_start = self.reverse_list(middle_point.next) #判断前半部分和后半局部是否相等 result = True first = head second = second_start while result and second is not None: if first.val != second.val: result = False first = first.next second = second.next #还原链表并返回后果 middle_point.next = self.reverse_list(second_start) return result #快慢指针寻找中点 def middle_point(self, head): fast = head slow = head while fast.next is not None and fast.next.next is not None: fast = fast.next.next slow = slow.next return slow #翻转链表 def reverse_list(self, head): previous = None current = head while current is not None: next_node = current.next current.next = previous previous = current current = next_node return previous

更多算法题解，请关注公众号《程序员学长》 单链表的排序问题形容LeetCode 148. 排序链表 给定一个节点数为n的无序单链表，对其按升序排序。 要求：空间复杂度 O(n)，工夫复杂度 O(nlogn)。 示例： 输出：[-1,0,-2] 返回值：{-2,-1,0} 剖析问题因为题目要求工夫复杂度是O(nlogn)，那工夫复杂度是O(nlogn)的排序算法有归并排序、疾速排序和堆排序，其中最适宜链表的排序算法是归并排序。 归并排序是基于分治思维，最容易想到的就是自顶向下的递归实现。自顶向下的递归实现次要包含二个环节。 宰割环节 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点能够应用快慢指针法，快指针每次挪动2步，慢指针每次挪动1步，当快指针走到链表的开端时，慢指针恰好指向了链表的中点地位。找到中点后，将链表在中点处宰割成两个子链表。而后递归的进行宰割，直到宰割后的链表只有一个节点或者为Null。这时，宰割的子链表都是有序的，因为只蕴含一个节点。合并环节 将两个有序的链表合并成一个有序链表。咱们能够采纳双指针法求解。递归执行，直到合并实现。 class Solution: def sortList(self, head): #如果链表为空或者只蕴含一个节点，递归终止 if not head or not head.next: return head #应用快慢指针法来寻找链表的中点 slow=head fast=head.next while fast and fast.next: fast=fast.next.next slow=slow.next #slow指向的就是链表的中点，将链表在中点处进行宰割 head2=slow.next slow.next=None #递归的切割宰割链表 left = self.sortList(head) right = self.sortList(head2) #合并链表，应用双指针法 tmp = res = ListNode(0) while left and right: if left.val < right.val: tmp.next=left left=left.next else: tmp.next=right right=right.next tmp=tmp.next if left: tmp.next=left else: tmp.next=right return res.next该算法的工夫复杂度是O(n)。因为自顶向下是通过递归来实现的，如果思考递归调用栈的栈空间，那么该算法的空间复杂度是O(logn)。 ...

更多算法题解，请关注公众号【程序员学长】 两个链表生成相加链表问题形容LeetCode 剑指 Offer II 025. 链表中的两数相加 假如链表中每一个节点的值都在 0 - 9 之间，那么链表整体就能够代表一个整数。给定两个这种链表，请生成代表两个整数相加值的后果链表。 示例： 输出：[9,3,7]，[6,3] 返回值：{1,0,0,0} 剖析问题因为两个数字相加是从个位数开始，而后再十位数、百位数。对于的链表中，咱们须要将两个链表进行右端对齐，而后从右往左进行计算。 要想让两个链表右端对齐，咱们有两种实现形式。 将两个链表进行反转，而后间接求和。借助栈这种先进后出的个性，来实现链表的右端对齐。咱们先来看一下如何应用链表反转来实现。 class Solution(object): def reverse(self, head): cur = head #初始化时，pre为None pre = None while cur: next=cur.next cur.next = pre pre = cur cur = next return pre def addTwoNumbers(self, l1, l2): #将两个链表翻转 l1 = self.reverse(l1) l2 = self.reverse(l2) head=ListNode(0) pre=head #代表是否进位 carray=0 while l1 or l2: v1=l1.val if l1 else 0 v2=l2.val if l2 else 0 sum=v1+v2+carray #进位数 carray=int(sum/10) tmp=sum%10 node=ListNode(tmp) pre.next=node pre=pre.next if l1: l1=l1.next if l2: l2=l2.next if carray==1: node=ListNode(carray) pre.next=node return self.reverse(head.next)上面咱们来看一下如何应用栈来求解。咱们首先将两个链表从头到尾放入两个栈中，而后每次同时出栈，就能够实现链表的右端对齐相加，咱们来看一下代码如何实现。 ...

更多算法题解，请关注公众号《程序员学长》 两个链表的第一个公共结点问题形容LeetCode 剑指 Offer 52. 两个链表的第一个公共节点 输出两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。 要求：空间复杂度是O(1)，工夫复杂度是O(m+n)。 示例： 剖析问题这个问题最直观的想法就是遍历链表headA，而后把headA中的所有每个节点都退出到汇合中。而后再循环遍历链表headB，判断结点是否在汇合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，持续遍历，直到完结。如果headB的所有结点都不在汇合中，则表明不相交，间接返回null。 def getIntersectionNode(headA,headB): nodes=set() while headA: nodes.add(headA) headA=headA.next while headB: if nodes.__contains__(headB): return headB headB=headB.next return None该算法的工夫复杂度是O(m+n)，空间复杂度是O(n)。其中m和n别离是链表headA和headB的长度。 因为题目要求工夫复杂度是O(m+n)，空间复杂度是O(1)。咱们这里能够应用双指针法将空间复杂度升高到O(1)。咱们别离用两个指针p1和p2别离指向headA和headB，而后同时挪动指针p1和p2。当p1达到headA的开端时，让p1指向headB，当p2达到headB的开端时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。 Tips:假如headA不相交的局部是a，headB不相交的局部是b，公共局部是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，能够晓得p1和p2指针同时达到第一个公共结点；当a不等于b时，在p1挪动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，而后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。 def getIntersectionNode(headA,headB): p1 = headA p2 = headB while p1 != p2: if p1: p1=p1.next else: p1=headB if p2: p2=p2.next else: p2=headA return p1更多算法题解，请关注公众号《程序员学长》

更多算法题解，关注公众号《程序员学长》 删除链表倒数第n个节点问题形容LeetCode 剑指 Offer II 021. 删除链表的倒数第 n 个结点 给定一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。 示例： 输出：head = [1,2,3,4,5], n = 2 输入：[1,2,3,5] 剖析问题这个问题最简略的求解形式就是遍历一遍链表，获取到链表的长度m，而后求出倒数第n个结点的地位m-n+1，而后再遍历一次链表，找到第m-n+1的地位，删掉这个结点就好。其实，咱们这里能够应用双指针法，只须要遍历一次链表就能够解决问题。 首先，咱们能够设置两个指针slow和fast都指向头结点，而后让fast先走n步，之后slow和fast一起走，直到fast.next为空为止，这是slow指向的就是倒数第n+1个结点，咱们通过slow.next=slow.next.next就能够把倒数第n个结点删掉。 上面咱们来看一下代码的实现。 def removeNthFromEnd(self,head,n): #左右指针指向头结点 slow = fast = head #fast先走n步 while n>0 and fast: fast = fast.next n=n-1 if not fast: return head.next while fast.next: slow = slow.next fast = fast.next slow.next = slow.next.next return head该算法只遍历一遍链表，所以工夫复杂度是O(n)，空间复杂度是O(1)。

更多算法题解，关注公众号《程序员学长》 链表中环的入口结点问题形容LeetCode 剑指 Offer II 022. 链表中环的入口节点 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。留神，pos 仅仅是用于标识环的状况，并不会作为参数传递到函数中。 阐明：不容许批改给定的链表。 剖析问题拿到这个问题，咱们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否曾经被拜访过。如果被拜访过，就代表这个结点是链表中环的入口点，咱们间接返回就好。如果没有被拜访过，咱们就标记一下，而后接着去遍历下一个结点，直到遍历残缺个链表为止。上面咱们来看一下代码的实现。 def EntryNodeOfLoop(self, pHead): tags = set() while pHead: #示意曾经被拜访过了，代表有环 if pHead in tags: return pHead tags.add(pHead) pHead = pHead.next return None咱们能够看到该算法的工夫复杂度和空间复杂度都是O(n)。 优化咱们这里也能够采纳快慢指针来求解，就和上一题的解法相似，咱们来看一下。 咱们能够应用两个指针fast和slow。他们都从链表的头部开始登程，slow每次都走一步，即slow=slow->next，而fast每次走两步，即fast=fast->next->next。如果链表中有环，则fast和slow最终会在环中相遇。 咱们假如链表中环外的长度为a，show指针进入环后又走了b的间隔与fast相遇，此时fast指针曾经绕着环走了n圈。所以快指针一共走了a+n(b+c)+b=a+(n+1)b+nc的间隔，咱们晓得快指针每次走2步，而慢指针每次走一步，所以，咱们能够得出快指针走的间隔是慢指针的两倍，即a+(n+1)b+nc=2(a+b)，所以a=c+(n-1)(b+c)。这里你会发现：从相遇点到入环的间隔c，再加上n-1圈的环长，恰好等于从链表头部到入环点的间隔。 因而，当发现slow和fast相遇时，咱们再额定应用一个指针ptr指向链表头部，而后它和slow指针每次都向后挪动一个地位。最终，他们会在入环点相遇。 Tips: 你兴许会有疑难，为什么慢指针在第一圈没走完就会和快指针相遇呢？咱们来看一下，首先，快指针会率先进入环内。而后，当慢指针达到环的入口时，快指针在环中的某个地位，咱们假如此时快指针和慢指针的间隔为x，若x=0，则示意在慢指针刚入环时就相遇了。咱们假如环的长度为n，如果看成快指针去追赶慢指针，那么快指针须要追赶的间隔为n-x。因为快指针每次都比慢指针多走一步，所以一共须要n-x次就能追上慢指针，在快指针遇上慢指针时，慢指针一共走了n-x步，其中x>=0，所以慢指针走的途程小于等于n，即走不完一圈就会相遇。 上面，咱们来看一下代码实现。 def detectCycle(head): if not head: return None #快慢指针 slow = head fast = head while True: if not fast or not fast.next: return None fast=fast.next.next slow=slow.next #相遇时，跳出循环 if fast == slow: break ptr = head while ptr != slow: ptr=ptr.next slow=slow.next return ptr该算法的工夫复杂度是O(n)，空间复杂度是O(1)。 ...

更多算法题解，请关注公众号《程序员学长》，欢送退出。 判断链表是否有环问题形容LeetCode141. 环形链表 给定一个链表，判断链表中是否有环。如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。 为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。 如果链表中存在环，则返回 true 。 否则，返回 false 。 示例： 输出：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3 输入：true 解释：链表中有一个环，其尾部连贯到第二个节点。 剖析问题拿到这个问题，咱们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否曾经被拜访过。如果被拜访过，那么就代表该链表有环，间接返回。如果没有被拜访过，咱们就标记一下，而后接着去遍历下一个结点，直到遍历残缺个链表为止。上面咱们来看一下代码的实现。 def hasCycle(self, head): tags = set() while head: #示意曾经被拜访过了，代表有环 if head in tags: return True tags.add(head) head = head.next return False咱们能够晓得该算法的工夫复杂度和空间复杂度都是O(n)。那咱们有更好的解法吗？ 优化你能够这么思考，当有两名同学在操场上以不同的速度进行跑步，它们最终必定会相遇。因为操场是环形的，如果在直线上跑，那他们必定不会相遇。 咱们假如同学1以速度1在跑，同学2以速度2在跑。 上面咱们来看一下代码如何实现。 def hasCycle(self, head): #如果链表为空或者链表只有一个结点 #间接返回false,因为不可能有环 if not head or not head.next: return False #快慢指针 slow = fast = head start = True while slow != fast || start: start=False if not fast or not fast.next: return False slow = slow.next fast = fast.next.next return True咱们这里引入了一个变量start示意是否是起跑。 ...

链表中的节点每k个一组翻转问题形容LeetCode25. K 个一组翻转链表 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最初剩下的节点放弃原样。你不能更改节点中的值，只能更改节点自身。 例如： 给定的链表是：1 -> 2 -> 3 -> 4 -> 5 对于 k=2，你应该返回 2 -> 1 -> 4 -> 3 -> 5 对于 k=3， 你应该返回 3 -> 2 -> 1 -> 4 -> 5 剖析问题咱们把这个问题进行拆分。 咱们首先将链表依照k个一组进行分组。对于最初一组，有可能元素个数不满足k个。对于每一个分组，咱们去判断元素的个数是否为k，如果是k的话，咱们进行反转，否则不须要进行反转。 咱们上面来看一下代码实现。 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: #反转链表，并且返回链表头和尾 def reverse(self, head, tail): prev = tail.next p = head while prev != tail: next = p.next p.next = prev prev = p p = next return tail, head def reverseKGroup(self, head, k): #初始化一个哨兵节点，防止临界条件简单的判断 prehead = ListNode(0) #哨兵节点指向头结点 prehead.next = head pre = prehead while head: tail = pre #查看残余局部长度是否大于等于k for i in range(k): tail = tail.next #如果残余长度小于k,则不须要反转，间接返回 if not tail: return prehead.next #tail指向子链表的尾部 #所以next指向下一个子链表的头部 next = tail.next #将链表进行反转，并返回链表头和尾 head, tail = self.reverse(head, tail) #把子链表从新接回原链表 pre.next = head tail.next = next pre = tail head = tail.next return prehead.next更多算法题解，请关注公众号《程序员学长》，欢送退出。 ...

爬楼梯解法与斐波那契数列相似，都是基于 f(n) = f(n - 1) + f(n - 2) 1. 暴力递归工夫复杂度 O(2^n)空间复杂度 O(n)（堆栈会溢出） // 全局变量，示意递归的深度let depth = 0;function climbStairs(n) { if (n < 1) { return 0; } if (n == 1) { return 1; } if (n == 2) { return 2; } return climbStairs(n - 2) + climbStairs(n - 1);}2. 备忘录递归工夫复杂度 O(n)空间复杂度 O(n)应用map数组存储计算的后果 function climbStairs(n) { let mapData = new Map(); return myClimbStairs(n, mapData);}function myClimbStairs(n, mapData) { if (n < 1) { return 0; } if (n === 1) { return 1; } if (n === 2) { return 2; } // 曾经计算过间接返回 if (mapData.get(n)) { return mapData.get(n); } let value = climbStairs(n - 1) + climbStairs(n - 2); mapData.set(n, value); return value;}3. 动静布局工夫复杂度 O(n)空间复杂度 O(1)function climbStairs(n) { if (n < 1) { return 0; } // base case if (n === 1) { return 1; } if (n === 2) { return 2; } // 因为状态转移只和上一次迭代和上上次迭代的后果无关，所以只用两个变量存储，不须要用数组，缩小了空间 let pre = 1; let cur = 2; for (let i = 3; i <= n; i++) { let sum = pre + cur; pre = cur; cur = sum; } return cur;}

最长公共前缀工夫复杂度：O(s) （s 为所有字符串的长度之和） 空间复杂度：O(1)排除字符串数组为空假如第一个字符串为最长公共前缀遍历数组的其它字符串将第一个字符串的字符逐个纵向匹配遇到不匹配 / 遍历实现字符串则退出 var longestCommonPrefix = function(strs) { if(strs.length == 0) return ""; let ans = strs[0]; for(let i =1;i<strs.length;i++) { let j=0; for(;j<ans.length && j < strs[i].length;j++) { if(ans[j] != strs[i][j]) break; } ans = ans.substr(0, j); if(ans === "") return ans; } return ans;};

和几位始终保持刷题好敌人探讨了一下刷题的顿悟时刻，他们几位大都获得了不错的 offer，比方 Google 微软，Amazon，BAT 等。 通过和他们的沟通，我发现了大家顿悟时刻都是相似的。那具体他们有哪些类似点呢？咱们一起来看下。 1. 同样的类型要刷很多能力顿悟比方你想顿悟二分，那么首先你须要做足够多的二分题。 而因为二分其实是一个大的分类。因而实践上你如果想对二分大类顿悟，那么必不可少的是先做足够多的二分题，并且这些题目能够笼罩所有的二分类型。 比方西法总结的根底二分，最左最右二分以及能力检测二分，其中大部分有点艰难的题目都是能力检测二分。 对二分不相熟的能够看下西法之前总结的《二分专题》： 简直刷完了力扣所有的二分题，我发现了这些货色（上）简直刷完了力扣所有的二分题，我发现了这些货色（下）那么推而广之，如果你想对刷算法题整体进行顿悟，那么就不得不先做足够多的题目，且这些题目能笼罩所有你想顿悟的考点。 这也就是说为什么你看的大佬中的大佬都刷了上千道题的起因。因为没有上千道题目的积攒，你很难对所有题目类型都顿悟的。当然你如果只是应酬大多数的考点并且不参加比赛的话，兴许小几百道也是 ok 的。 2. 回顾做过的题目有的同学比拟间接，他们就是间接温习做过的题目。而有的同学则是通过做新的题目回想到之前做过的某些题，从而达到温习的作用。 不论是哪种类型。他们都必须通过一个阶段，那就是和曾经做过的题目建立联系。如果你只是自觉做题的话，效率必定上不去。 最开始刷题的时候，我会建设一些 anki 卡片。这其实就是为了强制回顾做过的题目。另外做新的题目的时候，我会强制本人思考： 这道题考查了什么常识？和之前做过的哪些题能够建立联系？是否能够用之前刷题的解法套？corner case 有哪些？。。。通过这些思考，缓缓就会把做过的题目有机地联合起来，而不是让这些题目变成彼此的信息孤岛。 3. 对做过的题目进行形象这个是我要讲的最初一点，然而这点却尤为重要，说它是最重要也不过分。 一方面，如果一道题目没有通过形象，那么咱们很难记住，很难在将来回顾起来。另一方面，如果一道题目可能形象为纯正的题目，那么阐明你对这个题目看的比拟透彻了。未来碰到换皮题，你一形象，就会发现: 这不就是之前 xxxx 的换皮题么？ 常常看我题解和文章的同学晓得我之前写过不少换皮题的扒皮解析，这就是我做题和写文章格调。 在这里，我再举个例子。 留神：上面举的三道题例子都须要你把握二分法的能力检测二分，如果不理解倡议先看下我下面的文章。 Shopee 的零食柜这是 shopee 的校招编程题。 题目形容shopee的零食柜，有着各式各样的零食，然而因为贪吃，小虾同学体重日益减少，终于被人叫为小胖了，他终于下定决心减肥了，他决定每天晚上去操场跑两圈，然而跑步太累人了，他想转移注意力，遗记苦楚，正在听着音乐的他，忽然有个想法，他想跟着音乐的节奏来跑步，音乐有7种音符，对应的是1到7，那么他对应的步长就能够是1-7分米，这样的话他就能够转移注意力了，然而他想放弃本人跑步的速度，在规定工夫m分钟跑完。为了防止被累死，他须要布局他每分钟须要跑过的音符，这些音符的步长总和要尽量小。上面是小虾同学听的歌曲的音符，以及规定的工夫，你能通知他每分钟他应该跑多少步长？输出形容:输出的第一行输出 n（1 ≤ n ≤ 1000000，示意音符数），m（1<=m< 1000000, m <= n）组成，第二行有 n 个数，示意每个音符（1<= f <= 7）输入形容:输入每分钟应该跑的步长示例1输出8 5 6 5 6 7 6 6 3 1输入11链接：https://www.nowcoder.com/ques...起源：牛客网 思路通过形象，这道题实质上就是给你一个数组（数组值范畴是 1 到 7 的整数），让你将数组分为最多 m 子数组，求 m 个子数组和的最小值。 ...

【 NO.1 查看句子中的数字是否递增】 解题思路签到题。 代码展现 class Solution { public boolean areNumbersAscending(String s) { var strList = s.split(" "); int last = -1; for (var str : strList) { try { int num = Integer.parseInt(str); if (num <= last) { return false; } last = num; } catch (NumberFormatException ignored) { } } return true;}} 【 NO.2 繁难银行零碎】 解题思路约等于签到题。如果题目阐明 “可能多集体同时操作” 还好一些，那就须要加锁了。 代码展现 class Bank { long[] balance; public Bank(long[] balance) { ...

D135 20. Valid Parentheses题目链接20. Valid Parentheses 题目剖析这道题也比拟经典，就是括号匹配题。 给出一个蕴含小、中、大括号的字符串，判断左右括号是否匹配。 要留神呈现程序，不能串。也要留神有可能会呈现空字符串。 解题思路这道题的经典做法是用栈来实现。 遇到左括号时，间接入栈。遇到右括号时，判断以后括号类型和栈顶端，即出栈时的括号类型是否雷同。如果雷同则持续判断。如果不同则返回false。 遍历完所有字符时，如果栈内还有括号残余，即有括号没有被匹配，也视为false。 最终代码<?phpclass Solution { /** * @param String $s * @return Boolean */ function isValid($s) { if(!strlen($s)){ return true; } $parentheses_array = str_split($s); $stack = []; foreach($parentheses_array as $parenthes){ if($parenthes == '(' || $parenthes == '[' || $parenthes == '{'){ $stack[] = $parenthes; } else{ $prev = array_pop($stack); if(( $prev== '(' && $parenthes == ')') || ($prev == '[' && $parenthes == ']') || ($prev == '{' && $parenthes == '}') ){ continue; } return false; } } var_dump(count($stack)); if(count($stack)){ return false; } else{ return true; } }}若感觉本文章对你有用，欢送用爱发电赞助。 ...

Given the root of a binary tree, return the inorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3]Output: [1,3,2]<!-- more --> Example 2: Input: root = []Output: []Example 3: Input: root = [1]Output: [1]Example 4: Input: root = [1,2]Output: [2,1]Example 5: Input: root = [1,null,2]Output: [1,2]Constraints: The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively? ...

解法一：双层循环解题思路察看函数块返回类型为int[] 引入int[] 对象 result。双层循环，i从0开始，j在i后面，二者相加判断，不等于target就持续循环。等于target就将i,j放进result内。返回result。 代码class Solution { public int[] twoSum(int[] nums, int target) { int[] result=new int[2]; for(int i=0;i< nums.length;i++){ for(int j= i+1;j< nums.length;j++){ if(nums[i]+nums[j]==target){ result[0]=i; result[1]=j; } } } return result; }}解法二: 优化解法一解题思路由解法一可知，j和i有关系，j总是在i的后一位，那么咱们是否能够依据这个条件将代码简化呢？将i,j设为0，1.当下标元素相加等于target时，返回长度为2元素为i,j的一维数组。下标元素相加不等于target时，挪动j的地位，直到j达到数组长度。此时阐明在i这个地位的元素后的任意一个数和它相加，都得不到target，咱们将i的地位后移，j也随之后移。 代码class Solution { public int[] twoSum(int[] nums, int target) { int i=0; int j=1; int max=nums.length-1; while(nums[i]+nums[j]!=target){ if(j==max){ i++; j=i; } j++; } return new int[]{i,j}; }}解法三 应用哈希表解题思路应用哈希表来存储数组元素。只需一层循环。if条件要点为：哈希表maps中是否存在有 target-nums[i] 这个值。如果没有，则将nums[i]的值放入表中。 代码class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> maps=new HashMap<>(); for(int i=0;i<nums.length;++i){ if(maps.containsKey(target-nums[i])){ return new int[]{maps.get(target-nums[i]),i}; } maps.put(nums[i],i); } return new int[0]; }}

如何无效学习算法学习算法的基本思路就是：先学习算法思维，而后通过做题消化思维，并在做题过程中缓缓学习，把握一些小技巧。这其中算法思维就是道，而经典题目以及做题技巧就是术。做题是通过术来欠缺道。 然而很多人都反馈看讲义和做题之间断层重大，也就是一看就会，一些就废。这怎么办呢？ <!-- more --> 除了多写，多练习之外，我认为以下两点能够帮忙你： 做题的时候和讲义（学习材料）进行联合这是一个很重要的也容易被疏忽的点。拿《91 天学算法》来说：看讲义就是学思维，每日一题就是坚固消化思维。做每日一题的时候，要多往讲义上靠靠，比方想一下这道题对应讲义哪一部分，考查的是讲义中提到的哪一个知识点。 看讲义（学习材料）的时候将例题用可视化的形式本人跑一遍我刚开始学习算法的时候，基本上也是这种思路。学习完思维做题的时候对例题都在电脑或者纸上画一下代码执行流程，而后和学习的算法思维进行联合。这样不仅算法思维容易排汇，而且也收效缓解了一看就会，一写就废的难堪地步。 然而毕竟本人画图还是有点老本的，不是所有的人都有能源本人画图的。程序员都很懒，其实我刚开始刷题的时候始终有一个想法， 如果做题有可视化显示该有多好？最好是和我讲义图相似的那种， 这样无疑对老手来说排汇思维效率必定高。 可视化调试插件无巧不成书，前几天《91 天学算法》群里有人提到 LeetCode 刷题调试。大家有的用 IDE 调试，有的用会员的调试性能在网页调试。 其实前一阵子我分享刷题技巧的时候也分享了调试插件，没有看过的同学能够看下 力扣刷题的正确姿态是什么？。 明天再分享一个适宜老手的调试工具，简略易用，直观不便。更要害的是，其曾经内置到我的刷题插件 leetcode-cheatsheet 中，间接开箱即用，插件版本大于等于 0.9.0 即可。尽管它临时还无奈主动生成像我讲义外面那么残缺的图和动画，然而比文字要直观太多了。前期思考集成更多的语言以及更多的语法个性以及更好的展现成果。 该应用形式非常简单，齐全满足了大家偷懒的需要。你只须要： 装置刷题插件 leetcode-cheatsheet插件如何下载与装置能够在公众号回复插件获取关上 leetcode 中任意一道题目，写代码。目前反对 Python3，CPP，JavaScript点击下方的可视化调试 按提醒批改代码后点击Visualize Execution按钮如果无奈批改代码，能够先点击 edit code 这里我就想吐槽一下 leetcode 了。干嘛每一道题函数名字都不一样，真没这个必要。比方都叫 solve 不好么？心愿力扣能够考虑一下这个倡议。 通过管制区域控制代码执行，右侧会主动同步的可视化地显示变量信息 最初情谊提醒一下。可视化调试举荐在看材料（比方 91 天学算法的讲义）的时候把其中的例题用可视化的形式调试一遍，填平思路到代码的鸿沟。 之后大家做题不要依赖调试性能，而是先在大脑中调试一下，而后用工具验证。也就是说这个工具，我仅举荐你在两种状况下应用： 看算法思维材料，做其中的例子的时候一步步调试学习。代码有 case 跑不通，先在脑子中过一下，猜想大略出问题的点，而后用工具间接定位到左近通过可视化的形式帮忙你剖析。最初大家有什么想要的 feature 能够给我公众号后盾或交换群里留言。

【 NO.1 增量元素之间的最大差值】 解题思路遍历数组保护全局最小值，若以后值较大就是一个正当的答案，遍历过程取最大的正当答案即可。 代码展现 public class Solution { public int maximumDifference(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int res = -1; int minNum = Integer.MAX_VALUE; for (int n : nums) { if (n > minNum) { res = Math.max(n - minNum, res); } minNum = Math.min(minNum, n); } return res;}} 【 NO.2 网格游戏】 解题思路留神到网格只有两行，所以第一个机器人须要抉择的实际上就是从哪一列向下。在它确定了向下的那一列之后，第二个机器人要么只能拿到第一行开始局部的分数，要么只能拿到第一行结尾局部的分数。 代码展现 public class Solution { public long gridGame(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int n = grid[0].length; long left = 0, rihgt = 0; for (int i = 1; i < n; i++) { rihgt += grid[0][i]; } long res = rihgt; for (int i = 1; i < n; i++) { left += grid[1][i - 1]; rihgt -= grid[0][i]; res = Math.min(res, Math.max(left, rihgt)); } return res;}} ...

【 NO.1 执行操作后的变量值】 解题思路签到题。 代码展现 class Solution { public int finalValueAfterOperations(String[] operations) { int v = 0; for (String op : operations) { if (op.contains("++")) { v++; } else { v--; } } return v;}} 【 NO.2 数组漂亮值求和】 解题思路由前缀最大值和后缀最小值即可失去两头元素的漂亮值，所以预处理出前缀最大值和后缀最小值数组即可。 代码展现 class Solution { public int sumOfBeauties(int[] nums) { int[] preMax = new int[nums.length]; preMax[0] = nums[0]; for (int i = 1; i < nums.length; i++) { preMax[i] = Math.max(preMax[i - 1], nums[i]); } int[] sufMin = new int[nums.length]; sufMin[nums.length - 1] = nums[nums.length - 1]; for (int i = nums.length - 2; i >= 0; i--) { sufMin[i] = Math.min(sufMin[i + 1], nums[i]); } int res = 0; for (int i = 1; i < nums.length - 1; ++i) { if (preMax[i - 1] < nums[i] && nums[i] < sufMin[i + 1]) { res += 2; } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) { res += 1; } } return res;}} ...

上一篇 你不晓得的 LeetCode 技巧（第一篇） 讲述了三个 JS 刷题的小技巧。明天来分享几个 leetcode 通用小技巧，不论你是用什么语言刷题都能够应用。 tip1 - 中英文切换力扣中国局部题目形容因为翻译的起因，会变得难以了解，甚至呈现翻译谬误导致题意发生变化的状况。 这个时候举荐大家应用切换语言性能，将其转化为英文。 如下是中文题目形容： 接下来，能够点击上面的图标切换语言。 这只是切换单个题目的语言，如果你想切换整个网站的语言，能够点击力扣中国顶部右侧的这个按钮。 tip2 - 快捷键应用快捷键能够显著提高效率，刷力扣也是一样。 如下是我罕用的两个快捷键，强烈推荐应用。 提交代码：cmd + enter执行代码（测试）：cmd + `目前力扣编辑器提供八个快捷键绑定，更多快捷键能够参考力扣的提醒。如下所示： 另外如果你是 windows 那么上述快捷键必定不失效，那么你能够依照如上形式查看文档理解具体的快捷键绑定。 tip3 - 限定工夫刷题之前我提到过：举荐大家给本人做题设定一个工夫限度。能够采纳如下形式： 力扣模仿面试力扣周赛大家能够做题时点击这个给本人限定工夫。 值得注意的是，默认限度工夫是 30 分钟。倡议大家逐渐缩短工夫，做到 15 分钟以内，有条件的话挑战一下五分钟。 tip4 - 在线面试如果你是面试官，也可间接应用力扣来出题。力扣中的很多性能都能够应用。 你能够自在增加力扣原题，当然也能够本人出题。 更有意思的的是，居然能够出前端题 。其实前端题就是一个相似于 stackblitz 的货色。不得不说，如果你是前端面试官，这个在线面试性能能够说很全面了。 另外也反对文字聊天，语音，视频，在线评估等常见的面试性能。 简略实用了一下，一个月能够收费创立 10 次面试，每次面试不能超过三个小时，总体来说还蛮不便的。 tip5 - 刷题插件我本人做了一个刷题插件 leetcode-cheatsheet，它扩大了力扣平台的性能。 比方： 一键写题解 一键复制所有内置测试用例 数据结构可视化 复杂度对照表， 间接依据数据规模反猜答案的算法复杂度 性能太多了，不一一介绍了。 ...

本文本来是打算加到我的新书《算法通关之路》的附录局部。不过因为力扣官网不过审，因而只好作罢。将这部分内容发到这里给大家参考。 《算法通关之路》介绍以及购买可拜访：https://leetcode-solution.cn/... 力扣（LeetCode ）网站应用办法力扣（LeetCode ）官网收录了许多互联网公司的算法题目，一度被称为刷题神器。这里咱们就来介绍下如何应用 力扣（LeetCode ）网站。 因为力扣（LeetCode）自身也处于一直迭代之后，因而本文局部内容有可能在未来会变得不再实用。以力扣国内站为例，其官网给出了四个分类：Algorithms、Database、Shell 和 Concurrency，别离示意算法题、数据库题、Shell 和并发题，第一个就是咱们所须要刷的算法题。 并发是 2019 年才增加的新的模块。点开 Algorithms 后，咱们能够看到一个题目的列表，每个题目都有一个惟一的序号。力扣（LeetCode ）目前有 1000 多道题目，并且始终继续更新，其中有一些是带锁的，须要会员能力查看。 前面的承受率（Acceptance）示意提交的正确率，Difficulty 示意难易水平。难易水平有三个级别，别离是 Easy、Medium 和 Hard。 Easy 通常不须要太多思考和也不会有简单的细节，比拟特地适宜老手或者拿来热身。Medium 级别就会有些难度，个别都会波及到经典的算法，须要肯定的思考。Hard 级别是最难的，有些时候是算法自身的难度，有些时候特地须要你思考到各种细节。这里分享一个小技巧给大家。掂量一道题目难不难除了看难度之外，还能够看下承受率，承受率越低代表题目越难，这个指标有时候比难度更靠谱。你能够对题目进行筛选和排序。 如果咱们只想要找某一类型的题或者某个公司的题库，能够通过 Tags 或 Company 来筛选。 另外咱们在做某一题时，感觉还想再做一个相似的，能够点击题目形容下方 Show Similar Problems 或 Tags 来找到类似的问题。 每个题目都有各自的 Discuss 区域。在这里，许多人都把本人的思路和代码放到了下面，你能够发贴发问，也能够回复他人，外面大神很多，题解品质都很高，如果切实没有思路或者想看下有没有更好的思路能够来逛一下。通常来说我倡议你优先看留言最多或者投票最多的。 点开某一个题目，会跳转到具体题目详情页面，你能够在右侧的代码区切换抉择本人须要的编程语言。 代码编写完了之后，不要急着提交，先测试运行一下（Run Code 按钮）。你能够多写几个测试使劲跑一下，没有问题再提交，要晓得较量的时候谬误提交要加工夫的。 提交通过之后，能够点开 More Details 查看具体运行后果信息。 每道题旁边的 My Submissions 能够找到本人的对于该题的提交状况，这里能够看到本人过来所有的提交，点 Accepted 或 Wrong Answer 就能够查看本人过来提交的代码状况，包含代码是什么，运行工夫以及全副用户提交的工夫分布图等。 以上就是 力扣（LeetCode ）的次要性能，心愿通过这一节内容能让你对 力扣（LeetCode ）网站有所理解，从而更快地进行刷题。 刷题工具所谓“工欲善其事必先利其器”，接下来给大家带来一些进步刷题效率的小工具。 ...

【 NO.1 反转单词前缀】 解题思路 签到题。 代码展现 class Solution { public String reversePrefix(String word, char ch) { int index = word.indexOf(ch); return new StringBuffer(word.substring(0, index + 1)).reverse().toString() + word.substring(index + 1);} } 【 NO.2 可调换矩形的组数】 解题思路 将矩形依照长宽比分类，计数即可。 代码展现 class Solution { static class Frac { int den; int num; public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public Frac(int num, int den) { int g = gcd(num, den); this.num = num / g; this.den = den / g; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Frac frac = (Frac) o; return den == frac.den && num == frac.num; } @Override public int hashCode() { return Objects.hash(num, den); }} ...

【 NO.1 统计非凡四元组】 解题思路签到题，枚举即可。 代码展现 class Solution { public int countQuadruplets(int[] nums) { int n = nums.length; int res = 0; for (int a = 0; a < n; a++) { for (int b = a + 1; b < n; b++) { for (int c = b + 1; c < n; c++) { for (int d = c + 1; d < n; d++) { if (nums[a] + nums[b] + nums[c] == nums[d]) { res++; } } } } } return res;}} ...

【 NO.1 学生分数的最小差值】 解题思路 排序，而后枚举每间断的 K 个元素即可。 代码展现 class Solution { public int minimumDifference(int[] nums, int k) { if (nums.length < 2 || k == 1) { return 0; } Arrays.sort(nums); int res = nums[k - 1] - nums[0]; for (int i = k; i < nums.length; i++) { res = Math.min(res, nums[i] - nums[i - k + 1]); } return res;}} 【 NO.2 找出数组中的第 K 大整数】 解题思路 依照数值从大到小排序即可。 ...

作为子字符串呈现在单词中的字符串数目签到题，枚举、统计即可。 class Solution { public int numOfStrings(String[] patterns, String word) { int cnt = 0; for (String p : patterns) { if (word.contains(p)) { cnt++; } } return cnt; }}结构元素不等于两相邻元素平均值的数组依照一大一小的程序重排数组即可，这样一个数字相邻的数字要么都比它大，要么都比它小。 class Solution { public int[] rearrangeArray(int[] nums) { Arrays.sort(nums); LinkedList<Integer> list = new LinkedList<>(); for (int num : nums) { list.add(num); } int[] res = new int[nums.length]; for (int i = 0; i < res.length; i++) { if (i % 2 == 0) { res[i] = list.pollFirst(); } else { res[i] = list.pollLast(); } } return res; }}数组元素的最小非零乘积最终肯定是若干个 1、1 个 $2^p - 1$、若干个 $2^p - 2$，并且 $2^p - 2$ 的数量和 1 的数量相等。 ...

【 NO.1 查看字符串是否为数组前缀】 解题思路签到题，暴力连贯字符串查看是否相等即可。 代码展现 class Solution { public boolean isPrefixString(String s, String[] words) { String t = ""; for (var word : words) { t += word; if (s.equals(t)) { return true; } } return false;}} 【 NO.2 移除石子使总数最小】 解题思路贪婪，每次移除最多的那一堆。 代码展现 class Solution { public int minStoneSum(int[] piles, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> (b - a)); for (int p : piles) { heap.add(p); } for (int i = 0; i < k; i++) { heap.add((heap.poll() + 1) / 2); } return heap.stream().mapToInt(a -> a).sum();}} ...

1.leetCode第28题 实现 strStr需要：https://leetcode-cn.com/probl... 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串呈现的第一个地位（下标从 0 开始）。如果不存在，则返回  -1 示例 1：输出：haystack = "hello", needle = "ll"输入：2示例 2：输出：haystack = "aaaaa", needle = "bba"输入：-1示例 3：输出：haystack = "", needle = ""输入：01 看下面的例子首先想到的是应用indexOf办法function print(haystack, needle) { return haystack.indexOf(needle)};2 本人实现一个indexOf办法 function print(haystack, needle) { let reg = new RegExp(needle, "g"); let matchResult = reg.exec(haystack); return matchResult ? matchResult["index"] : -1; }2 leetCode第35题 搜寻插入地位https://leetcode-cn.com/probl... 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。请必须应用工夫复杂度为 O(log n) 的算法。示例 1:输出: nums = [1,3,5,6], target = 5输入: 2示例 2:输出: nums = [1,3,5,6], target = 2输入: 1示例 3:输出: nums = [1,3,5,6], target = 7输入: 4示例 4:输出: nums = [1,3,5,6], target = 0输入: 0示例 5:输出: nums = [1], target = 0输入: 0function print(nums, target) { let index = nums.indexOf(target); if (index > -1) return index; for (let i = nums.length; i >= 0; i--) { if (nums[i] < target) { nums.splice(i+1, 0, target); index=i+1 break; } if(i==0){ index=0 nums.unshift(target) } } return index }

力扣第 252 场周赛解题报告NO1.三除数n 是三除数当且仅当它的除数为 1, n 和 sqrt(n) class Solution { public boolean isThree(int n) { for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return i * i == n; } } return false; }}NO.2 你能够工作的最大周数咱们并不需要关怀如何安顿工作。只有工作量最大的工作不超过其余工作的总和，那么肯定能够实现所有的工作，否则工作量最大的工作将会剩下一部分无奈实现。 class Solution { public long numberOfWeeks(int[] milestones) { long sum = 0, max = 0; for (int i : milestones) { sum += i; max = Math.max(max, (long) i); } if (sum - max >= max) { return sum; } return sum - (max * 2 - sum - 1); }}NO.3 收集足够苹果的最小花园周长二分答案 + 数学推导。能够写出两层循环，而后数列求和，即可失去总的求和公式。 ...

1.leetCode第26题 删除有序数组中的反复项需要： 给你一个有序数组 nums ，请你 原地 删除反复呈现的元素，使每个元素 只呈现一次 ，返回删除后数组的新长度。不要应用额定的数组空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。示例 1：输出：nums = [1,1,2]输入：2, nums = [1,2]解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被批改为 1, 2 。不须要思考数组中超出新长度前面的元素。示例 2：输出：nums = [0,0,1,1,1,2,2,3,3,4]输入：5, nums = [0,1,2,3,4]解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被批改为 0, 1, 2, 3, 4 。不须要思考数组中超出新长度前面的元素。这道题咱们能够应用双指针的解法，其工夫复杂度为O(1),设置两个指针，s(slow),f(fast)，s初始为0，f初始为1，依据条件扭转s的下一个元素。 if (nums[s] != nums[f]) { nums[s + 1] = nums[f]; s++; } function print(nums) { let s = 0; for (let f = 1; f < nums.length; f++) { if (nums[s] != nums[f]) { nums[s + 1] = nums[f]; s++; } } return s+1; }2.leetCode第27题 移除元素给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素。示例 1：输出：nums = [3,2,2,3], val = 3输入：2, nums = [2,2]解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不须要思考数组中超出新长度前面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。示例 2：输出：nums = [0,1,2,2,3,0,4,2], val = 2输入：5, nums = [0,1,4,0,3]解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。留神这五个元素可为任意程序。你不须要思考数组中超出新长度前面的元素。 function print(nums) { let n = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] != val) { nums[n] = nums[i]; n++; } } return n; }

1.leetCode第七题需要：https://leetcode-cn.com/probl...给你一个 32 位的有符号整数 x ，返回将 x 中的数字局部反转后的后果。如果反转后整数超过 32 位的有符号整数的范畴 [−2^31,  2^31 − 1] ，就返回 0。假如环境不容许存储 64 位整数（有符号或无符号）。 示例 1：输出：x = 123输入：321示例 2：输出：x = -123输入：-321示例 3：输出：x = 120输入：21示例 4：输出：x = 0输入：0 let x = -120; function print(x) { let border = 2 ** 31; let num =(x >= 0 ? 1 : -1) *x.toString().split("").filter((v) => v != "-").reverse().join(""); if (num >= -border && x <= border) return num; }2.leetCode第九题需要：https://leetcode-cn.com/probl...给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。 ...

2.两数相加给你两个 非空 的链表，示意两个非负的整数。它们每位数字都是依照 逆序 的形式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以雷同模式返回一个示意和的链表。 你能够假如除了数字 0 之外，这两个数都不会以 0 结尾。 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var addTwoNumbers = function(l1, l2) { let temp = 0; let head = null; let tail = null; while(l1 || l2){ let a = l1 ? l1.val : 0; let b = l2 ? l2.val : 0; let sum = a + b + temp; if(!head){ head = tail = new ListNode(sum%10, null); } else{ tail.next = new ListNode(sum%10); tail = tail.next; } temp = sum > 9 ? 1 : 0; if(l1){ l1 = l1.next; } if(l2){ l2 = l2.next; } } if(temp>0){ tail.next = new ListNode(temp); } return head;};1.两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。 ...

题目形容这是 LeetCode 上的 「354. 俄罗斯套娃信封问题」 ，难度为 「艰难」。 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，示意第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就能够放进另一个信封里，如同俄罗斯套娃一样。 请计算「最多能有多少个」信封能组成一组“俄罗斯套娃”信封（即能够把一个信封放到另一个信封外面）。 留神：不容许旋转信封。 示例 1： 输出：envelopes = [[5,4],[6,4],[6,7],[2,3]]输入：3解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。示例 2： 输出：envelopes = [[1,1],[1,1],[1,1]]输入：1提醒： 1 <= envelopes.length <= 5000envelopes[i].length == 21 <= wi, hi <=动静布局这是一道经典的 DP 模型题目：最长回升子序列（LIS）。 首先咱们先对 envelopes 进行排序，确保信封是从小到大进行排序。 问题就转化为咱们从这个序列中抉择 k 个信封造成新的序列，使得新序列中的每个信封都能严格笼罩后面的信封（宽高都严格大于）。 咱们能够定义状态 为思考前 i 个物品，并以第 个物品为结尾的最大值。 对于每个 而言，最小值为 ，代表只抉择本人一个信封。 那么对于个别的 该如何求解呢？因为第 i 件物品是必须抉择的。咱们能够枚举后面的 件物品，哪一件能够作为第 件物品的上一件物品。 在前 件物品中只有有符合条件的，咱们就应用 更新 。 而后在所有计划中取一个 max 即是答案。 代码： class Solution {    public int maxEnvelopes(int[][] es) {        int n = es.length;        if (n == 0) return n;        // 因为咱们在找第 i 件物品的前一件物品时，会对后面的 i - 1 件物品都遍历一遍，因而第二维（高度）排序与否都不影响        Arrays.sort(es, (a, b)->a[0]-b[0]);        int[] f = new int[n]; // f(i) 为思考前 i 个物品，并以第 i 个物品为结尾的最大值        int ans = 1;        for (int i = 0; i < n; i++) {            // 对于每个 f[i] 都满足最小值为 1            f[i] = 1;             // 枚举第 i 件物品的前一件物品，            for (int j = i - 1; j >= 0; j--) {                // 只有有满足条件的前一件物品，咱们就尝试应用 f[j] + 1 更新 f[i]                if (check(es, j, i)) {                    f[i] = Math.max(f[i], f[j] + 1);                }            }            // 在所有的 f[i] 中取 max 作为 ans            ans = Math.max(ans, f[i]);        }        return ans;    }    boolean check(int[][] es, int mid, int i) {        return es[mid][0] < es[i][0] && es[mid][1] < es[i][1];    }}工夫复杂度：空间复杂度：二分 + 动静布局上述计划其实算是一个奢侈计划，复杂度是 的，也是我最先想到思路，然而题目没有给出数据范畴，也不晓得能不能过。 ...

题目形容这是 LeetCode 上的「1162. 地图分析」 ，难度为「中等」。 你当初手里有一份大小为  的 网格 ，下面的每个 单元格 都用  和  标记好了。 其中  代表陆地， 代表海洋，请你找出一个陆地单元格，这个陆地单元格到离它最近的海洋单元格的间隔是最大的。 咱们这里说的间隔是「曼哈顿间隔」： 和  这两个单元格之间的间隔是 。 如果网格上只有海洋或者陆地，请返回 。 示例 1： 输出：[[1,0,1],[0,0,0],[1,0,1]]输入：2解释：陆地单元格 (1, 1) 和所有海洋单元格之间的间隔都达到最大，最大间隔为 2。示例 2： 输出：[[1,0,0],[0,0,0],[0,0,0]]输入：4解释：陆地单元格 (2, 2) 和所有海洋单元格之间的间隔都达到最大，最大间隔为 4。提醒： 1 <= grid.length == grid[0].length <= 100grid[i][j] 不是  就是 单源 BFS通常咱们应用 BFS 求最短路，都是针对如下场景：从特定的终点登程，求解达到特定起点的最短距离。 这是一类非凡的「单源最短路」问题：实质是在一个边权为 的图上，求从特定「源点」登程达到特定「汇点」的最短门路。 对于本题，如果套用「单源最短路」做法，咱们须要对每个「陆地」地位做一次 BFS：求得每个「陆地」的最近海洋间隔，而后在所有的间隔中取 作为答案。 单次 BFS 的最坏状况须要扫描残缺个矩阵，复杂度为 。 同时，最多有 个陆地区域须要做 BFS，因而这样的做法复杂度为 ，并且 可间接取满。 PS. 数据范畴为 ，实践上是肯定会超时，但本题数据较弱，Java 2021/06/28 可过。 一些细节：为了不便，咱们在应用哈希表记录间隔时，将二维坐标 转化为对应的一维下标 作为 key 进行存储。 代码： class Solution {    int n;    int[][] grid;    public int maxDistance(int[][] _grid) {        grid = _grid;        n = grid.length;        int ans = -1;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 0) {                    ans = Math.max(ans, bfs(i, j));                }            }        }        return ans;    }    // 单次 BFS：求解陆地地位 (x,y) 最近的海洋间隔    int bfs(int x, int y) {        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};        Deque<int[]> d = new ArrayDeque<>();        Map<Integer, Integer> map = new HashMap<>();        d.addLast(new int[]{x, y});        map.put(x * n + y, 0);        while (!d.isEmpty()) {            int[] poll = d.pollFirst();            int dx = poll[0], dy = poll[1];            int step = map.get(dx * n + dy);            if (grid[dx][dy] == 1) return step;            for (int[] di : dirs) {                int nx = dx + di[0], ny = dy + di[1];                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;                int key = nx * n + ny;                if (map.containsKey(key)) continue;                d.addLast(new int[]{nx, ny});                map.put(key, step + 1);            }        }        return -1;    } }工夫复杂度：空间复杂度：多源 BFS这其实还是道「多源 BFS」入门题。 与「单源最短路」不同，「多源最短路」问题是求从「多个源点」达到「一个/多个汇点」的最短门路。 在实现上，最外围的搜寻局部，「多源 BFS」与「单源 BFS」并无区别。 并且通过建设「虚构源点」的形式，咱们能够「多源 BFS」转换回「单源 BFS」问题。 什么意思？ ...

leetcode-525-间断数组<!--more--> [题目形容]给定一个二进制数组 nums , 找到含有雷同数量的 0 和 1 的最长间断子数组，并返回该子数组的长度。 示例 1: 输出: nums = [0,1]输入: 2阐明: [0, 1] 是具备雷同数量0和1的最长间断子数组。 示例 2: 输出: nums = [0,1,0]输入: 2阐明: [0, 1] (或 [1, 0]) 是具备雷同数量0和1的最长间断子数组。 提醒： 1 <= nums.length <= 105 nums[i] 不是 0 就是 1 Related Topics 哈希表 293 0[题目链接]leetcode题目链接 [github地址]代码链接 [思路介绍]思路一：暴力法（这种办法没什么意义，遍历所有子数组） 工夫复杂度(O(n^2^)) 思路二：hash表 因为数组中只有0 1 两个元素，当子元素长度为n（n为正偶数）时，子数组和为（n/2）所以能够把0换成-1 这样 子数组和即为0,题意转化成了求间断子数组和为0的最大长度子数组最近做的两道题都有这种思维，通过前缀和求间断区间相干题目链接leetcode-523-间断子数组和每日一题系列也就是说间断子数组长度则能够通过前缀和的差值来判断首先定义一个prefix[]数组 prefix[i] = nums[0] +……+ nums[i]nums[i] +……+ nums[j] = prefix[j] - prefix[i-1]如果只是这样计算每一个子数组的和其实和暴力法没有区别甚至是多了O(n)的工夫复杂度能够依据题目含意得出，指标是求出prefix[j] - prefix[i]== 0的时候 j 与 i的最大差值也就是说须要求得使prefix[j]与prefix[i]相等状况j 与 i差值最大因而能够思考引入hashmap进行计算，将prefix[i]的值作为key存入hashmap并记录以后坐标为value每次求出前缀和的时候判断求Math.max(j-i) public int findMaxLength(int[] nums) { int n = nums.length,max = 0; Map<Integer,Integer> map = new HashMap<>(); int[] prefix = new int[n]; prefix[0] = (nums[0] == 0 ? -1 : 1); map.put(prefix[0],0); //求前缀和数组 for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + (nums[i] == 0 ? -1 : 1); //以后前缀和曾经满足，则进入计算范畴 if (prefix[i] == 0){ max = Math.max(i+1,max); } if (map.containsKey(prefix[i])){ max = Math.max(i-map.get(prefix[i]),max); }else{ map.put(prefix[i], i); } } return max; }工夫复杂度O(n) ...

title: tags: [算法, 动静布局]date: 2021-05-18categories: [动静布局]我在动静布局专题反复强调了先学习递归，再学习记忆化，最初再学动静布局。 其中起因曾经讲得很透了，置信大家曾经明确了。如果不明确，强烈建议先看看那篇文章。 只管很多看了我文章的小伙伴晓得了先去学记忆化递归，然而还是有一些粉丝问我：“记忆化递归转化为动静布局老是出错，不得要领怎么办？有没有什么要领呀？” 明天我就来答复一下粉丝的这个问题。 实际上我的动静布局那篇文章曾经讲了将记忆化递归转化为动静布局的大略的思路，只是可能不是特地细，明天咱们就尝试细化一波。 咱们依然先以经典的爬楼梯为例，给大家讲一点基础知识。接下来，我会带大家解决一个更加简单的题目。 <!-- more --> 爬楼梯题目形容一个人爬楼梯，每次只能爬 1 个或 2 个台阶，假如有 n 个台阶，那么这个人有多少种不同的爬楼梯办法？ 思路因为第 n 级台阶肯定是从 n - 1 级台阶或者 n - 2 级台阶来的，因而到第 n 级台阶的数目就是 到第 n - 1 级台阶的数目加上到第 n - 1 级台阶的数目。 记忆化递归代码： const memo = {};function climbStairs(n) { if (n === 1) return 1; if (n === 2) return 2; if (n in memo) return memo[n]; ans = climbStairs(n - 1) + climbStairs(n - 2); memo[n] = ans; return ans;}climbStairs(10);首先为了不便看出关系，咱们先将 memo 的名字改一下，将 memo 换成 dp： ...

哈希表实践根底用来疾速判断某个原生是否在汇合内(疾速查找)哈希函数将传入的key映射到符号表的索引上哈希抵触解决多个key映射到符号表雷同索引上的问题，罕用的解决办法有拉链法和线性探测法c++ stl中有四种常见的哈希构造数组 std::array汇合 std::set std::multiset std::unordered_set映射 std::map std::multimap std::unordered_map汇合底层实现是否有序增删查的效率std::setRB-Tree是O(logn)std::multisetRB-Tree是O(logn)std::unordered_setHash否O(1)std::unordered_multisetHash否O(1)映射底层实现是否有序增删查的效率std::mapRB-Tree是O(logn)std::multimapRB-Tree是O(logn)std::unordered_mapHash否O(1)std::unordered_multimapHash否O(1)

Quicksortclass Sort: def quickSort(self, arr): self.quicksort_helper(arr, 0, len(arr)-1) return arr def quicksort_helper(self, arr, left, right): if left < right: pivot_final_resting_position = self.partition(arr, left, right) self.quicksort_helper(arr, left, pivot_final_resting_position-1) self.quicksort_helper(arr, pivot_final_resting_position+1, right) def partition(self, arr, left, right): pivot = arr[right] i = left - 1 for j in range(left, right): if arr[j] <= pivot: i += 1 self.swap(arr, i, j) self.swap(arr, i+1, right) return i+1 def swap(self, arr, first, second): temp = arr[first] arr[first] = arr[second] arr[second] = tempBubble Sortclass Sort: def bubbleSort(self, nums): for i in range(len(nums)-1, 0, -1): for j in range(i): if nums[j] > nums[i]: temp = nums[i] nums[i] = nums[j] nums[j] = temp return numsMerge Sortclass Sort: def merge(self, left, right): result = [] while len(left)>0 and len(right)>0: if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) if left: result.extend(left) if right: result.extend(right) return result def mergeSort(self, arr): num = len(arr) if num < 2: return arr middle = num // 2 left = arr[:middle] right = arr[middle:] left_sort = mergeSort(left) right_sort = mergeSort(right) return self.merge(left_sort, right_sort)反转链表# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # 返回ListNode def ReverseList(self, pHead): # write code here current = pHead previous = None while current: temp = current.next current.next = previous previous = current current = temp return previous ...

链表先不去钻研规范库里的List了，新的gnu里写的巨简单恶心人了。链表可分为单链表，双链表，循环链表// 链表节点struct ListNode { int val; // 节点上存储的元素 ListNode *prev; // 指向上一个节点的指针 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), prev(nullptr), next(nullptr) {} // 节点的构造函数};203-移除链表元素 - 虚构头结点「设置一个虚构头结点」，这样原链表的所有节点就都能够依照对立的形式进行移除了。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; *///输出：head = [1,2,6,3,4,5,6], val = 6//输入：[1,2,3,4,5]class Solution {public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0, head); ListNode* cur = dummyHead; while(cur->next != nullptr){ if(cur->next->val == val){ tmp = cur->next; cur->next = cur->next->next; delete tmp; } else{ cur = cur->next; } } return dummyHead->next; }};707-设计链表-链表增删查改「链表操作的两种形式：」 ...

数组int array[5] std::array<int,5> 倡议应用std::array代替简略数组，平安可保护1.数组下标都是从0开始2.数组内存空间的地址是间断且数组元素的类型雷同3.在删除或者削减元素的时候，就不免要挪动其余元素的地址4.在C++中二维数组是间断散布的，int array[2][3], 然而二维vector不是间断的 vector<vector<int>> matrix(2, vector<int>(3)); 35-搜寻插入地位-二分查找左闭右开的写法，也就是[left, right) //O(logn) + O(1)int searchInsert(vector<int>& nums, int target) { int n = nums.size(); int left = 0; int right = n; // 定义target在左闭右开的区间里，[left, right) target while (left < right) { // 因为left == right的时候，在[left, right)是有效的空间 int middle = ((right + left) >> 1); if (nums[middle] > target) { right = middle; // target 在左区间，在[left, middle)中 } else if (nums[middle] < target) { left = middle + 1; // target 在右区间，在 [middle+1, right)中 } else { // nums[middle] == target return middle; // 数组中找到目标值的状况，间接返回下标 } } // 别离解决如下四种状况 // 目标值在数组所有元素之前 [0,0) // 目标值等于数组中某一个元素 return middle // 目标值插入数组中的地位 [left, right) ，return right 即可 // 目标值在数组所有元素之后的状况 [left, right)，return right 即可 return right;}27-移除元素-快慢指针 int removeElement(vector<int>& nums, int val) { //[3, 1, 2, 4, 6, 8, 2, 9, 0] val = 2 //[3, 1, 4, 6, 8, 9, 0] int slow_idx = 0; for(int i = 0; i < nums.size() ++i){ if(nums[i] != val){ nums[slow_idx++] = nums[i]; } } }209-长度最小的子数组-滑动窗口滑动窗口算法能够用以解决数组/字符串的子元素问题，它能够将嵌套的循环问题，转换为单循环问题，升高工夫复杂度。 ...

笔者最近在刷LeetCode习题，故想将一些经典算法以及一些经典的数据结构汇编成一个系列，分享给大家和当前的本人。本文次要波及枯燥栈。 枯燥栈枯燥栈自身的概念并不难理解，然而理论利用起来须要了解粗浅才行。笔者当初了解了一个早晨才弄明确，而你们只须要看完这半篇文章即可齐全了解。 对于递增栈和递加栈很多中央说法不一，此处为了不便阐明，将栈底到栈顶枯燥增的即为递增栈；枯燥减的即为递加栈。（不肯定正确，然而不影响之后的了解）。先探讨递增栈，此处我定义一个概念：极左邻元素和极右邻元素。假如数组nums，其中以后元素的下标为k，那么若满足nums[q] < nums[k]，且在区间[q+1,k-1]中的元素全都大于nums[k]。那么nums[q]即为nums[k]的极左邻元素，同理能够定义极右邻元素。 递加栈中相似，此处不再赘述。 光看下面的定义的确很好了解，让咱们来思考一下枯燥栈的作用。它可能帮忙咱们找到以后元素的极左邻元素和极右邻元素，从而实现一些性能。搬一道经典题目， 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，可能勾画进去的矩形的最大面积。 图中暗影局部为所能勾画出的最大矩形面积，其面积为 10 个单位。 此题若采纳暴力搜寻的形式诚然很简单，其实用枯燥栈即可在O（n）的工夫内解决。大家先了解一个“扩散”的概念，假如我当初抉择倒数第二个柱子（值为2），要想以此为核心，勾画出最大的矩形，那么从这个柱子开始，左右扩散。右边的柱子比本人高，扩散胜利，左边的柱子也比本人高，扩散胜利。所以最终能够扩散到[5,6,2,3]这几根柱子上，那么以以后这个柱子为高，所能勾画最大矩形面积即为2*4 = 8。那么这种“扩散”是在哪里进行的呢？显然，是在比以后元素小的且离以后元素最近的元素进行，这不就是上文中提到的极左邻元素嘛！所以只有能确定每个元素的极左邻元素和极右邻元素，那么间接一减就是宽度了呀。 如何利用枯燥栈找极左邻、极右邻元素？保护一个递增栈。留神：栈中放的是元素的下标。要获取元素比大小的话，间接通过下标去数组中找就好了。 枯燥栈的代码模板int stack_F(vector<int>& nums){ int maxx; stack<int>st; //此处的-1是比nums中所有数都要小的数，也能够-1000，本人定。次要是为了让栈中的所有元素都能够被弹出，因为要保护枯燥栈，遇到一个很小的数，栈中的元素必定全都会被弹出来。有利于将所有解都遍历到。 nums.push_back(-1); for(int i=0;i<nums.size();i++){ //此处等号可取可不取 if(st.empty() || nums[st.top()] <= nums[i]){ //存的是下标哦！ st.push(i); } else{ while(!st.empty() && nums[st.top()] > nums[i]){ //留神你是站在栈顶元素的立场来看的喔！ int index = st.top();st.pop(); int left_boder = st.top(); int right_boder = i; //有了这些边界点，就能够自定义统计左右符合条件的数量啦！比拟maxx的值等。 //your code ... } st.push(nums[i]); } } return maxx;}至此枯燥栈就完结了，下次更新的主题《递归的好基友，动静布局？啥是无后效性？》，欢送点赞珍藏！ ...

165. 比拟版本号给你两个版本号 version1 和 version2 ，请你比拟它们。 版本号由一个或多个订正号组成，各订正号由一个 '.' 连贯。每个订正号由 多位数字 组成，可能蕴含 前导零 。每个版本号至多蕴含一个字符。订正号从左到右编号，下标从 0 开始，最右边的订正号下标为 0 ，下一个订正号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是无效的版本号。 比拟版本号时，请按从左到右的程序顺次比拟它们的订正号。比拟订正号时，只需比拟 疏忽任何前导零后的整数值 。也就是说，订正号 1 和订正号 001 相等 。如果版本号没有指定某个下标处的订正号，则该订正号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的订正号雷同，而下标为 1 的订正号别离为 0 和 1 ，0 < 1 。 返回规定如下： 如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1，除此之外返回 0 思路别离指向两个版本号，遇到.进行宰割将数据用整数示意存储顺次比拟大小class Solution {public: int compareVersion(string version1, string version2) { int v1 = 0, v2 = 0; int maxLen = max(version1.size(), version2.size()); while (v1 < maxLen && v2 < maxLen) { int cur1 = 0, cur2 = 0; while (v1 < version1.size() && version1[v1] != '.') { cur1 = cur1*10 + (version1[v1]- '0'); v1++; } while (v2 < version2.size() && version2[v2] != '.') { cur2 = cur2*10 + (version2[v2]- '0'); v2++; } if (cur1 < cur2) { return -1; } else if (cur1 > cur2) { return 1; } v1++; v2++; } return 0; }};

941. 无效的山脉数组给定一个整数数组 arr，如果它是无效的山脉数组就返回 true，否则返回 false。 如果 A 满足下述条件，那么它是一个山脉数组： arr.length >= 3在 0 < i < arr.length - 1 条件下，存在 i 使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]思路留神全递增或者全递加不属于山脉class Solution {public: bool validMountainArray(vector<int>& arr) { if (arr.size() < 3) { return false; } int i = 0; while (i < arr.size()-1 && arr[i] < arr[i+1]) { i++; } //只有递加0；只有递增arr.size()-1 if (i == 0 || i == arr.size()-1) { return false; } while (i < arr.size()-1 && arr[i] > arr[i+1]) { i++; } if (i == arr.size()-1) { return true; } else { return false; } }};852. 山脉数组的峰顶索引找到山脉数组的山顶元素山脉数组定义同上。 ...

最大间断1的个数4854871004485给定一个二进制数组， 计算其中最大间断 1 的个数 输出：[1,1,0,1,1,1]输入：3 办法1int findMaxConsecutiveOnes(vector<int>& nums) { int maxNum = 0, tmp = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == 1) { tmp++; } else { maxNum = max(maxNum, tmp); tmp = 0; } } return max(maxNum, tmp);}办法2//dp[i] = dp[i-1]+1;int findMaxConsecutiveOnes2(vector<int>& nums) { vector<int> dp(nums.size()); for (int i = 0; i < nums.size(); i++) { if (i == 0) { if (nums[i] == 1) { dp[i] = 1; } else { dp[i] = 0; } } else { if (nums[i] == 1) { dp[i] = dp[i-1] + 1; } else { dp[i] = 0; } } } sort(dp.begin(), dp.end()); return dp[nums.size()-1];}487给定一个二进制数组，你能够最多将 1 个 0 翻转为 1，找出其中最大间断 1 的个数.输出：[1,0,1,1,0] 输入：4 ...

给定 n 个整数，找出平均数最大且长度为 k 的间断子数组，并输入该最大平均数。 示例： 输出：[1,12,-5,-6,50,3], k = 4输入：12.75解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75  提醒： 1 <= k <= n <= 30,000。所给数据范畴 [-10,000，10,000]。 起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl... 滑动窗口解法具体介绍：https://leetcode-cn.com/probl... /** * @param {number[]} nums * @param {number} k * @return {number} */var findMaxAverage = function(nums, k) { let sum = 0 ,length = nums.length; for(let i = 0; i <k ;i ++){ sum += nums[i] } var maxSum = sum; for(let i = k ; i < length; i ++){ sum = sum - nums[i-k] +nums[i] maxSum = Math.max(maxSum,sum) } return maxSum/k};

一点题外话上次在我的公众号给大家做了一个小考察《投出你想要的题解编程语言吧~》。以下是考察的后果： 而对于其余，则大多数是 Go 语言。 因为 Java 和 Python 所占比例曾经超过了 60%，这次我尝试一下 Java 和 Python 双语言来写，感激 @CaptainZ 提供的 Java 代码。同时为了不让文章又臭又长，我将 Java 本文所有代码（Java 和 Python）都放到了力扣加加官网上，网站地址：https://leetcode-solution.cn/... 如果不迷信上网的话，可能关上会很慢。注释 大家好，我是 lucifer。明天给大家带来的是《堆》专题。先高低本文的提纲，这个是我用 mindmap 画的一个脑图，之后我会持续欠缺，将其余专题逐步完善起来。 大家也能够应用 vscode blink-mind 关上源文件查看，外面有一些笔记能够点开查看。源文件能够去我的公众号《力扣加加》回复脑图获取，当前脑图也会继续更新更多内容。vscode 插件地址：https://marketplace.visualstu...本系列蕴含以下专题： 简直刷完了力扣所有的链表题，我发现了这些货色。。。简直刷完了力扣所有的树题，我发现了这些货色。。。简直刷完了力扣所有的堆题，我发现了这些货色。。。（第一弹）<!-- more --> 本次是下篇，没有看过上篇的同学强烈建议先浏览上篇简直刷完了力扣所有的堆题，我发现了这些货色。。。(第一弹) 这是第二局部，前面的内容更加干货，别离是三个技巧和四大利用。这两个主题是专门教你怎么解题的。把握了它，力扣中的大多数堆的题目都不在话下（当然我指的仅仅是题目中波及到堆的局部）。 正告： 本章的题目根本都是力扣 hard 难度，这是因为堆的题目很多标记难度都不小，对于这点在后面也介绍过了。 一点阐明在上主菜之前，先给大家来个开胃菜。 这里给大家介绍两个概念，别离是元组和模仿大顶堆 。之所以进行这些阐明就是避免大家前面看不懂。 元组应用堆不仅仅能够存储繁多值，比方 [1,2,3,4] 的 1，2，3，4 别离都是繁多值。除了繁多值，也能够存储复合值，比方对象或者元组等。 这里咱们介绍一种存储元组的形式，这个技巧会在前面被宽泛应用，请务必把握。比方 [(1,2,3), (4,5,6), (2,1,3),(4,2,8)]。 h = [(1,2,3), (4,5,6), (2,1,3),(4,2,8)]heapq.heappify(h) # 堆化（小顶堆）heapq.heappop() # 弹出 (1,2,3)heapq.heappop() # 弹出 (2,1,3)heapq.heappop() # 弹出 (4,2,8)heapq.heappop() # 弹出 (4,5,6)用图来示意堆构造就是上面这样： ...

class Trie { class TrieNode { private boolean isEnd; private TrieNode[] links; TrieNode() { links = new TrieNode[26]; } public boolean containsKey(char ch) { return links[ch-'a'] != null; } public TrieNode get(char ch) { return links[ch-'a']; } public void put(char ch, TrieNode node) { links[ch-'a'] = node; } public void setEnd() { isEnd = true; } public boolean isEnd() { return isEnd; } } private TrieNode root; /** Initialize your data structure here. */ public Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ public void insert(String word) { TrieNode node = root; for(char ch : word.toCharArray()) { if(!node.containsKey(ch)) { node.put(ch, new TrieNode()); } node = node.get(ch); } node.setEnd(); } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode node = root; for(char ch : word.toCharArray()) { if(!node.containsKey(ch)) { return false; } node = node.get(ch); } return node.isEnd(); } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { TrieNode node = root; for(char ch : prefix.toCharArray()) { if(!node.containsKey(ch)) { return false; } node = node.get(ch); } return true; }}/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

办法一、贪婪算法 #include <stdio.h>#include <string.h>#include <stdlib.h>char * intToRoman(int num) { struct intToRoman { int num; char *str; } list[13] = { {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}, }; int count[13] = {0}; char *str = (char*)malloc(17 * sizeof(char)); memset(str, '\0', 17); for (int i = 0; i < 13; i++) { int count = num / list[i].num; while (count-- > 0) { strcat(str, list[i].str); } num %= list[i].num; } strcat(str, '\0'); return str;}int main(void) { int num = 3999; printf("%s\n", intToRoman(num));}或者 ...

0 前言本专题将基于LeetCode的题目来剖析最佳解决方案背地的一些数据结构与算法原理。本文将基于题目#1两数之和来剖析JAVA中HashMap原理及高性能起因。 1 题目形容两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。 你能够按任意程序返回答案。 示例 1：输出：nums = [2,7,11,15], target = 9输入：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2：输出：nums = [3,2,4], target = 6输入：[1,2] 示例 3：输出：nums = [3,3], target = 6输入：[0,1] 提醒： 2 <= nums.length <= 103-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个无效答案2 最佳计划及疑难最容易想到的解决方案是暴力枚举，循环嵌套，空间复杂度只有O(1)，但工夫复杂度是O(N ^2)。更优的计划是基于哈希表（如JAVA中HashMap）来放慢数据查问的效率，用空间来换工夫，使工夫和空间的复杂度均为O(N)。 具体形容及代码可见：https://leetcode-cn.com/probl...此处的疑难是，为什么用哈希表就能够显著晋升查问效率呢？ 3 哈希表原理剖析1、为什么会有哈希表这种构造、它由什么组成？ 咱们已知的构造有数组和链表，两者各有优缺点： 数组：数组存储构造是间断的，空间复杂度大，但查问的工夫复杂度小。其寻址(通过下标搜寻)效率高，个别的插入和删除效率低。即，查问快，增删慢。链表：链表存储构造是离散的，空间复杂度小。其寻址(通过下标搜寻)效率低，个别的插入和删除效率高。即，查问慢，增删快。哈希表是基于数组和链表构建的，目标是为了充分发挥这两个构造的劣势。 对于一个哈希表，其蕴含四个局部的内容： key：即键值value：即数值hash：key对应的hash值，基于hash进行某种操作后失去的是表的indexnext：当index抵触时，寄存抵触的数据，链表构造2、为什么哈希表的查问效率会高于数组呢？ 因为哈希表的构造也有点相似于字典。字典通过key能够疾速查问到value，哈希表一样能够通过key疾速查问到value，但其中间进行了散列变换（即hash计算），通过hash值来确定value所在的index，从而实现数据的获取。 一个确定的key能够计算失去惟一的hash值，而index是hash通过某种操作失去的，难以不免hash值的抵触，为了解决这个抵触才引入了链表，来高效的存储hash值雷同的值。3、 hashMap.containsKey(value)的工夫复杂度是多少？ HashMap在不同版本的JDK之间有着如下的区别： JDK 1.8以前 HashMap由数组和链表形成。JDK 1.8之后 HashMap由数组、链表和红黑树形成。红黑树的特点是查问快，增删慢。红黑树 作为一种二叉查找树，但它在二叉查找树的根底上减少了着色和相干的性质使得红黑树绝对均衡，从而保障了红黑树的查找、插入、删除的工夫复杂度最坏为O(log n)。因为链表的查问工夫复杂度为O(n)，所以当链表很长时转换成红黑树将很好的提高效率！ ...