Leetcode

一、题目粗心给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 示例 1： 输出：head = [4,2,1,3]输入：[1,2,3,4]示例 2： 输出：head = [-1,5,3,4,0]输入：[-1,0,3,4,5]示例 3： 输出：head = []输入：[]提醒： 链表中节点的数目在范畴 [0, 5 * 104] 内-105 <= Node.val <= 105进阶：你能够在 O(n log n) 工夫复杂度和常数级空间复杂度下，对链表进行排序吗？ 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路用快慢指针将列表分成两局部，将两局部列表递归排序，再将排序后的列表合并 三、解题办法3.1 Java实现class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } // 应用快慢指针找出两头节点，将链表一分为二 ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode mid = slow.next; slow.next = null; return merge(sortList(head), sortList(mid)); } ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val > l2.val) { tail.next = l2; l2 = l2.next; } else { tail.next = l1; l1 = l1.next; } tail = tail.next; } if (l1 != null) { tail.next = l1; } if (l2 != null) { tail.next = l2; } return dummy.next; }}四、总结小记2022/9/3 要与邻里打好交道，远亲不如近邻呀

题目形容给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。 换而言之，对于每个 nums[i] 你必须计算出无效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。 以数组模式返回答案。 示例 1： 输出：nums = [8,1,2,2,3]输入：[4,0,1,1,3]解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。示例 2： 输出：nums = [6,5,4,8]输入：[2,1,0,3]示例 3： 输出：nums = [7,7,7,7]输入：[0,0,0,0]力扣原题目地址：https://leetcode.cn/problems/...思路解法题目并不难，就是做大小的比拟并统计次数，遇到这样的题目，咱们首先相到的就是暴力循环破解的形式 双层循环比拟第一层循环，取到以后的每一项，再套一层循环，顺次比拟其余项是否小于以后项，当然本身项不必比拟，间接跳过即可，如下代码： var smallerNumbersThanCurrent = function (nums) { // 1. 创立一个和传进来的数组长度统一的数组，且每一项都是0（为0是为了后续统计次数） let resultArr = (new Array(nums.length)).fill(0) for (let i = 0; i < nums.length; i++) { // 2. 外层遍历是为了拿到每一项与其余项作比拟 let item = nums[i] // 3. 拿到当下项 for (let j = 0; j < nums.length; j++) { // 4. 再循环一次是为了拿到别的项 if (i == j) { // 5. 本身不必比拟大小 // console.log('本身跳过不统计次数'); } else { if (item > nums[j]) { // 6. 若不是本身项，能够比拟大小 resultArr[i] = resultArr[i] + 1 // 7. 应用初始创立的0进行次数统计 } } } } return resultArr};双层循环比拟提交图 ...

题目形容丑数 就是只蕴含质因数 2、3 和 5的正整数。 给你一个整数 n，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。 示例 1： 输出：n = 6输入：true解释：6 = 2 × 3示例 2： 输出：n = 1输入：true解释：1 没有质因数，因而它的全副质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。示例 3： 输出：n = 14输入：false解释：14 不是丑数，因为它蕴含了另外一个质因数 7 。力扣原题目地址：https://leetcode.cn/problems/...思路解法题目不难，外围就是如何把一个数进行合成，如：6分解成2*3、12分解成3*4。一直依照2或3或5进行合成，直到合成不进去了（不能被2 3 5整除）。形象即为：某个操作始终执行，直到合乎某个条件才会停止下来。 所以咱们会相到应用递归，或者应用while循环 递归写法在写代码之前，咱们能够为了更好的理一下思路，能够应用枚举法，多举几个例子。如： /** * 0不是丑数 * 1是丑数 * 2是丑数 * 3是丑数 * 4是丑数 = 2 * 2 * 5是丑数 * 6是丑数 = 2 * 3 * 7不是丑数，没法被 2 3 5整除 * 8是丑数 = 2 * 4 * 9是丑数 = 3 * 3 * 10是丑数 = 2 * 5 或 5 * 2 * 11不是丑数，没法被 2 3 5整除 * */所以咱们为了代码的可读性更强一些，能够多写几个if判断，如下解法代码： ...

一、题目粗心将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 输出：l1 = [1,2,4], l2 = [1,3,4]输入：[1,1,2,3,4,4]示例 2： 输出：l1 = [], l2 = []输入：[]示例 3： 输出：l1 = [], l2 = [0]输入：[0]提醒： 两个链表的节点数目范畴是 [0, 50]-100 <= Node.val <= 100l1 和 l2 均按 非递加程序 排列起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路还是分递归和迭代两种思路来实现，要了解链表 三、解题办法3.1 Java实现-递归/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 提示信息： // 两个链表的节点数目范畴是 [0, 50] // -100 <= Node.val <= 100 // l1 和 l2 均按 非递加程序 排列 if (list1 == null) { return list2; } if (list2 == null) { return list1; } if (list1.val > list2.val) { list2.next = mergeTwoLists(list1, list2.next); return list2; } list1.next = mergeTwoLists(list1.next, list2); return list1; }}3.2 Java实现-迭代class Solution2 { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode ans = new ListNode(0); ListNode cursor = ans; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cursor.next = list1; list1 = list1.next; } else { cursor.next = list2; list2 = list2.next; } cursor = cursor.next; } cursor.next = list1 != null ? list1 : list2; return ans.next; }}四、总结小记2022/9/2 沟通合作老本大呀

一、题目粗心给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 输出：head = [1,2,3,4,5]输入：[5,4,3,2,1]示例 2： 输出：head = [1,2]输入：[2,1]示例 3： 输出：head = []输入：[] 提醒： 链表中节点的数目范畴是 [0, 5000]-5000 <= Node.val <= 5000 进阶：链表能够选用迭代或递归形式实现反转。你是否用两种办法解决这道题？ 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路用迭代和递归来实现，迭代思路：在原镮之前建设一个空的prev节点，因为首节点会变，从head开始，将之后的一个节点移到prev之后，反复此操作直到head成为末节点为止 递归思路：终止条件head为空，定义一个节点prev作为返回链表，每次将旧链表的head的下一个元素指向到prev，这样旧链表原来的下一个元素作为head，旧链表的head作为prev来调用递归函数 三、解题办法3.1 Java实现-迭代/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode next; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; }}3.2 Java实现-递归public class Solution2 { public ListNode reverseList(ListNode head) { ListNode prev = null; return reverseList(head, prev); } public ListNode reverseList(ListNode head, ListNode prev) { if (head == null) { return prev; } ListNode next = head.next; head.next = prev; return reverseList(next, head); }}四、总结小记220901 9月第1天

一、题目粗心给定一个蕴含大写字母和小写字母的字符串 s ，返回 通过这些字母结构成的 最长的回文串 。 在结构过程中，请留神 辨别大小写 。比方 "Aa" 不能当做一个回文字符串。 示例 1: 输出:s = "abccccdd"输入:7解释:咱们能够结构的最长的回文串是"dccaccd", 它的长度是 7。示例 2: 输出:s = "a"输出:1提醒: 1 <= s.length <= 2000s 只由小写 和/或 大写英文字母组成起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路：先统计每个字符呈现的次数，再遍历统计后的字符次数，如果是偶数次，那么肯定能够是回文字符串的一部分，加上该次数；如果是奇数n字，那么加上n-1次；最初判断如果呈现过奇数次的字符，那么最初后果加1。 三、解题办法3.1 Java实现public class Solution { public int longestPalindrome(String s) { Map<Character, Integer> map = new HashMap<>(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } boolean odd = false; int ans = 0; for (Integer count : map.values()) { if (count % 2 == 0) { ans += count; } else { odd = true; ans += (count - 1); } } ans += odd ? 1 : 0; return ans; }}四、总结小记2022/8/31 不合理的治理是造成内耗的起因之一

一、题目粗心实现 strStr() 函数。 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串呈现的第一个地位（下标从 0 开始）。如果不存在，则返回 -1 。 阐明： 当 needle 是空字符串时，咱们该当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时咱们该当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 示例 1： 输出：haystack = "hello", needle = "ll"输入：2示例 2： 输出：haystack = "aaaaa", needle = "bba"输入：-1提醒： 1 <= haystack.length, needle.length <= 104haystack 和 needle 仅由小写英文字符组成起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路1:此题可用KMP算法，能够o(m+n)工夫利用动静布局实现。 思路2:遍历线字符串，只须要遍历m-n长度即可，这样能够进步运算效率。而后对每个字符，都遍历一遍子字符串，一个一个字符的对应比拟，如果对应地位有不等的，则跳出循环，如果始终没有跳出循环，则阐明子字符串呈现了，返回起始地位即可。 三、解题办法3.1 Java实现public class Solution { public int strStr(String haystack, String needle) { int m = haystack.length(); int n = needle.length(); if (m < n) { return -1; } for (int i = 0; i <= m - n; i++) { int j; for (j = 0; j < n; j++) { if (haystack.charAt(i + j) != needle.charAt(j)) { break; } } if (j == n) { return i; } } return -1; }}四、总结小记2022/8/30 工作啊，工作啊

题目形容~查看是否所有字符呈现次数雷同给你一个字符串 s ，如果 s 是一个 好 字符串，请你返回 true ，否则请返回 false 。 如果 s 中呈现过的 所有 字符的呈现次数 雷同 ，那么咱们称字符串 s 是 好 字符串。 示例 1： 输出：s = "abacbc"输入：true解释：s 中呈现过的字符为 'a'，'b' 和 'c' 。s 中所有字符均呈现 2 次。示例 2： 输出：s = "aaabb"输入：false解释：s 中呈现过的字符为 'a' 和 'b' 。'a' 呈现了 3 次，'b' 呈现了 2 次，两者呈现次数不同。力扣原题目地址：https://leetcode.cn/problems/...解法代码var areOccurrencesEqual = function (s) { // 仍然是相熟的map汇合统计次数 let map = new Map() for (let i = 0; i < s.length; i++) { let item = s[i] if (map.has(item)) { let count = map.get(item) count = count + 1 map.set(item, count) } else { map.set(item, 1) } } // 次数统计好了当前，再看是不是map汇合中的每一项value都相等 let flag = true // 假如每一项都相等 let val = null // 定义一个初始值为null，后续用于比拟 for (const [key, value] of map) { // 应用forof遍历map汇合 // 这个if是初始去赋值，取第一项的value的值 if (val == null) { val = value } // 这个是后续所有项的，再看后续项是否和第一项相等 else { if (val != value) { // 只有有一个不相等就返回false，即不必持续比拟了 return false } } } // 若操作了一波没有变动，即为true return flag};提交后果图 ...

一、题目粗心给定一个字符串 s，统计并返回具备雷同数量 0 和 1 的非空（间断）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组间断的。 反复呈现（不同地位）的子串也要统计它们呈现的次数。 示例 1： 输出：s = "00110011"输入：6解释：6 个子串满足具备雷同数量的间断 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。留神，一些反复呈现的子串（不同地位）要统计它们呈现的次数。另外，"00110011" 不是无效的子串，因为所有的 0（还有 1 ）没有组合在一起。示例 2： 输出：s = "10101"输入：4解释：有 4 个子串："10"、"01"、"10"、"01" ，具备雷同数量的间断 1 和 0 。提醒： 1 <= s.length <= 105s[i] 为 '0' 或 '1'起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路1:从左往右遍历数组，记录和以后地位数字雷同中且间断的长度，以及其之前间断的不同数字的长度。举例来说，对于00110的最初一位，咱们记录的雷同数字长度是1，因为只有一个间断0；咱们记录的不同数字长度是2，因为在0之前有两个间断的1。若不同数字的间断长度大于等于以后数字的间断长度，则阐明存在一个且只存在一个以后数字结尾的满足条件的子字符串。 思路2:还能够从字符串的每个地位开始，向左向右缩短，判断存在多少以后地位为中轴的由01间断二进制字符串。 三、解题办法3.1 Java实现public class Solution { public int countBinarySubstrings(String s) { // 输出：s = "00110011" // 输入：6 int ans = 0; for (int i = 0; i < s.length() - 1; i++) { ans += extendSubstrings(s, i, i + 1); } return ans; } private int extendSubstrings(String s, int l, int r) { char lc = s.charAt(l); char rc = s.charAt(r); if (!((lc == '1' && rc == '0') || (lc == '0' && rc == '1'))) { return 0; } int count = 0; while (l >= 0 && r < s.length() && lc == s.charAt(l) && rc == s.charAt(r)) { count++; l--; r++; } return count; }}四、总结小记2202/8/28 忽如一夜秋风至，吹落黄花满地金

一、题目粗心给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过去读一样的字符串。 子字符串 是字符串中的由间断字符组成的一个序列。 具备不同开始地位或完结地位的子串，即便是由雷同的字符组成，也会被视作不同的子串。 示例 1： 输出：s = "abc"输入：3解释：三个回文子串: "a", "b", "c"示例 2： 输出：s = "aaa"输入：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"提醒： 1 <= s.length <= 1000s 由小写英文字母组成起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路题意：给定一个字符串，求其有多少个回文字符串。回文的定义是左右对称。输出是一个字符串，输入一个整数，示意回文字符串的数量。 咱们能够从字符串的每个地位开始，向左向右缩短，判断存在多少以后地位为中轴的回文字符串。 三、解题办法3.1 Java实现public class Solution { public int countSubstrings(String s) { // 咱们能够从字符串的每个地位开始，向左向右缩短，判断存在多少以以后地位为中轴的回文 子字符串。 int count = 0; for (int i = 0; i < s.length(); i++) { // 奇数长度 count += extendSubstrings(s, i, i); // 偶数长度 count += extendSubstrings(s, i, i+1); } return count; } private int extendSubstrings(String s, int l, int r) { int count = 0; while (l >=0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; count++; } return count; }}四、总结小记2208/8/27 小孩子的哭声让人急的一身汗

一、题目粗心给定两个字符串 s 和 t ，判断它们是否是同构的。 如果 s 中的字符能够按某种映射关系替换失去 t ，那么这两个字符串是同构的。 每个呈现的字符都该当映射到另一个字符，同时不扭转字符的程序。不同字符不能映射到同一个字符上，雷同字符只能映射到同一个字符上，字符能够映射到本人自身。 示例 1: 输出：s = "egg", t = "add"输入：true示例 2： 输出：s = "foo", t = "bar"输入：false示例 3： 输出：s = "paper", t = "title"输入：true提醒： 1 <= s.length <= 5 * 104t.length == s.lengths 和 t 由任意无效的 ASCII 字符组成起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路咱们能够记录两个字符串每个地位的字符第一次呈现的地位，如果两个字符串中雷同地位的字符与它们第一次呈现的地位一样，那么这两个字符串同构。例如：paper和title，当咱们当初遍历到第三个字符p和t，发现它们第一次呈现的地位都在第一个字符，阐明目前地位满足同构。 三、解题办法3.1 Java实现public class Solution { public boolean isIsomorphic(String s, String t) { int[] sFirstIndex = new int[256]; int[] tFirstIndex = new int[256]; for (int i = 0; i < s.length(); i++) { if (sFirstIndex[s.charAt(i)] != tFirstIndex[t.charAt(i)]) { return false; } sFirstIndex[s.charAt(i)] = i + 1; tFirstIndex[t.charAt(i)] = i + 1; } return true; }}四、总结小记2022/8/26 在汽车上刷的题

一、题目粗心https://leetcode.cn/problems/... 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 留神：若 s 和 t 中每个字符呈现的次数都雷同，则称 s 和 t 互为字母异位词。 示例 1: 输出: s = "anagram", t = "nagaram"输入: true示例 2: 输出: s = "rat", t = "car"输入: false提醒: 1 <= s.length, t.length <= 5 * 104s 和 t 仅蕴含小写字母进阶: 如果输出字符串蕴含 unicode 字符怎么办？你是否调整你的解法来应答这种状况？ 二、解题思路建设一个哈希表映射，一共26个字母，能够用一个数组来代替哈希表，咱们先判断两个字符串长度不雷同返回false。而后把s中所有字符呈现个数统计起来，存入一个大小为26的数组中。再统计t字符串，如果发现不匹配则返回false。 三、解题办法3.1 Java实现public class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] m = new int[26]; for (char c : s.toCharArray()) { m[c - 'a']++; } for (char c : t.toCharArray()) { if (--m[c - 'a'] < 0) { return false; } } return true; }}四、总结小记2022/8/25 最怕只知其一;不知其二给瞎出主见

一、题目粗心https://leetcode.cn/problems/... 谐和数组是指一个数组里元素的最大值和最小值之间的差异 正好是 1 。 当初，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的谐和子序列的长度。 数组的子序列是一个由数组派生进去的序列，它能够通过删除一些元素或不删除元素、且不扭转其余元素的程序而失去。 示例 1： 输出：nums = [1,3,2,2,5,2,3,7]输入：5解释：最长的谐和子序列是 [3,2,2,2,3]示例 2： 输出：nums = [1,2,3,4]输入：2示例 3： 输出：nums = [1,1,1,1]输入：0提醒： 1 <= nums.length <= 2 * 104-109 <= nums[i] <= 109二、解题思路思路：题目给咱们一个数组，让咱们找出最长的谐和子序列，谐和子序列就是序列中数组的最大最小差值均为1，这里只让咱们求长度，而不须要返回具体的子序列。所以咱们能够对数组进行排序，实际上只有找进去相差为1的两个数的总共呈现个数就是一个谐和子序列长度了。 三、解题办法3.1 Java实现public class Solution { public int findLHS(int[] nums) { Map<Integer, Integer> countMap = new HashMap<>(); for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1); } // a-b由小到大 b-a由大到小 PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getKey)); for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) { priorityQueue.add(entry); } int ans = 0; Map.Entry<Integer, Integer> pre = priorityQueue.poll(); while (!priorityQueue.isEmpty()) { Map.Entry<Integer, Integer> cur = priorityQueue.poll(); if (cur.getKey() - pre.getKey() == 1) { ans = Math.max(ans, cur.getValue() + pre.getValue()); } pre = cur; } return ans; }}四、总结小记2022/8/24 什么时候能水果自在呀

一、题目粗心https://leetcode.cn/problems/... 给定一个非空且只蕴含非正数的整数数组 nums，数组的 度 的定义是指数组里任一元素呈现频数的最大值。 你的工作是在 nums 中找到与 nums 领有雷同大小的度的最短间断子数组，返回其长度。 示例 1： 输出：nums = [1,2,2,3,1]输入：2解释：输出数组的度是 2 ，因为元素 1 和 2 的呈现频数最大，均为 2 。间断子数组外面领有雷同度的有如下所示：[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]最短间断子数组 [2, 2] 的长度为 2 ，所以返回 2 。示例 2： 输出：nums = [1,2,2,3,1,4,2]输入：6解释：数组的度是 3 ，因为元素 2 反复呈现 3 次。所以 [2,2,3,1,4,2] 是最短子数组，因而返回 6 。提醒： nums.length 在 1 到 50,000 范畴内。nums[i] 是一个在 0 到 49,999 范畴内的整数。二、解题思路首先给数组的度下一个定义，给一个数组，某个或某些数字呈现最多的次数为该数组的度。题目要求咱们找到最短的子数组使其和原数组领有雷同的度。 ...

题目形容给定一个由 整数 组成的 非空 数组所示意的非负整数，在该数的根底上加一。 最高位数字寄存在数组的首位， 数组中每个元素只存储单个数字。 你能够假如除了整数 0 之外，这个整数不会以零结尾。 示例 1： 输出：digits = [1,2,3]输入：[1,2,4]解释：输出数组示意数字 123。示例 2： 输出：digits = [4,3,2,1]输入：[4,3,2,2]解释：输出数组示意数字 4321。示例 3： 输出：digits = [0]输入：[1]力扣原题目地址：https://leetcode.cn/problems/...应用Bigint解决大数精度失落问题当本宗看到此题时，登时黑人问号涌上心头，什么？这么简略的力扣题目，不会吧!不会吧!（白岩松式纳闷）这不就是： 把数组转化成字符串再转成数字，而后加一（因为数字能力加一）而后再把数字转回去，转成数组于是乎，本宗祭出飞天指法，敲击在本宗秘宝、远古仙器机械茶轴键盘上，霎时间，诡异的声音直冲云霄，恐怖的威压席卷大地。周遭一些实力不济的程序猿兽，一口鲜血从七窍喷涌而出，身材倒飞而出，在地上犁出一条长几十米深半米多的沟壑，最终狠狠地撞击在公司杂物间的墙壁上，带起漫天烟尘。烟尘散去，条条稀稀拉拉蛛网般的裂缝爬满墙壁。三秒后，苦苦撑持的皲裂墙壁终于轰然倒塌，将哪些气若游丝的程序员兽埋在废墟下方，不知死活。 本宗不禁大喜，飞天指法，恐怖如斯、仙器键盘，强悍至此！ 本宗心神一动，顷刻间，玄而又玄的代码便是凭空出现： var plusOne = function (digits) { digits = digits.join('') * 1 // 数组转字符串再转数字 digits = digits + 1 // 数字加一 return (digits + '').split('') // 再把数字转成字符串并宰割成数组即可};本宗得意的望着本人发明出的玄妙代码，捋了捋胡须，从容不破的点了提交，本认为会胜利通过，然而接下来的画面，让本宗倒吸一口凉气： 没通过测试用例！ 本宗眉头一皱，发现这道题并没有这么简略，因为本宗忽然想起来远古斗码大陆流传的一部《玄天js古经书》，书中有这样一段艰涩难懂的真奥之理： js中数字类型无奈示意大数，即超过16位数字，会呈现精度失落问题 果然如此！ 报错的用例是达到了恐怖的19位数，远超16位啊，所以呈现精度失落，所以答案不正确。 看来出题人应该就是传说中的bug强人！本宗纵横此斗码大陆多年，没想到明天竟然阴沟里翻车，若传出去本宗颜面何在？岂不叫小辈贻笑大方？ 不行，本宗心一横，心中盘算道：此问题不能留！ 突然，虚空中一道苍老的声音传出：吾乃代码老怪，感觉与你颇有机缘，今日赠你一部js修炼大法《M帝恩》！ 多写前辈大恩，本宗就勉为其难收下了。 不知何时，本宗的电脑屏幕上多了一个链接：https://developer.mozilla.org... 先不论这么多了，此人到没有歹意... 于是在js修炼大法《M帝恩》的帮忙下，本宗解决了这道题 var plusOne = function (digits) { let number = BigInt(digits.join('')); // 应用BigInt避免精度失落 number = number + BigInt(1) // BigInt与BigInt同类型相加 let res = (number + '').split('') // 再转回数组即可 return res }; ...

一、题目粗心https://leetcode.cn/problems/... 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历程序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜寻它的下一个更大的数。如果不存在，则输入 -1 。 示例 1: 输出: nums = [1,2,1]输入: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数须要循环搜寻，后果也是 2。示例 2: 输出: nums = [1,2,3,4,3]输入: [2,3,4,-1,4]提醒: 1 <= nums.length <= 104-109 <= nums[i] <= 109二、解题思路咱们能够用枯燥栈来解决这个问题，因为是循环数组，咱们遍历两倍的数组，而后对坐标i取余，取出数字，如果此时栈不为空，且栈顶元素小于以后数字，阐明以后数字就是栈顶元素的左边第一个较大的数，此时建设二者的映射并且去除以后栈顶元素，最初如果i小于n，则把i压入栈。因为res的长度必须是n，超过n的局部咱们只是为了给之前栈中的数字找较大值，所以不能压入栈。 三、解题办法3.1 Java实现public class Solution { public int[] nextGreaterElements(int[] nums) { // 输出: nums = [1,2,3,4,3] // 输入: [2,3,4,-1,4] int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); Stack<Integer> desStack = new Stack<>(); for (int i = 0; i < n * 2; i++) { int num = nums[i % n]; while (!desStack.isEmpty() && nums[desStack.peek()] < num) { ans[desStack.peek()] = num; desStack.pop(); } if (i < n) { desStack.push(i); } } for (int tmp : ans) { System.out.print(tmp + ", "); } return ans; }}四、总结小记2022/8/22 明天适宜穿短裤

一、题目粗心https://leetcode.cn/problems/... 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的间断子数组的个数 。 示例 1： 输出：nums = [1,1,1], k = 2输入：2示例 2： 输出：nums = [1,2,3], k = 3输入：2提醒： 1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107二、解题思路三个思路，第一个：三层遍历，遍历i从0到n，第二层遍历j从i到n，第三层遍历i-j，求和，这种办法会超时 第二个：求累加和sum[i] = num[0]-num[i-1]，这样二层遍历失去(i,j)，查看 sum[j]-sum[i] 第三个：定义一个hash来保留sum呈现的次数，这样累加sum-k呈现的次数就是答案了 三、解题办法3.1 Java实现class Solution { public int subarraySum(int[] nums, int k) { int ans = 0; int sum = 0; Map<Integer, Integer> d = new HashMap<>(); d.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; ans += d.getOrDefault(sum - k, 0); d.put(sum, d.getOrDefault(sum, 0) + 1); } return ans; }}四、总结小记2022/8/21 得买个头盔了

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（103）二叉树的锯齿形层序遍历一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1: “本人。层序遍历法”。// 思路：// 1）边界：若 root 为null，则 间接返回 [] 。// 2）状态初始化：q1 = [root], q2 = [], resList = [], level = 0 。// 3）遍历：条件为 队列 q1 不为空 。// 4）返回后果：resList 里，下标为奇数的 元素项（数组模式）进行翻转。// resList.map((item, level) => level%2 === 1 ? item.reverse() : item);var zigzagLevelOrder = function(root) { // 1）边界：若 root 为null，则 间接返回 [] 。 if(root === null){ return []; } // 2）状态初始化：q1 = [root], q2 = [], resList = [], level = 0 。 let q1 = [root], q2 = [], resList = [], level = 0; // 3）遍历：条件为 队列 q1 不为空 。 while(q1.length !== 0){ let temp = q1.shift(); if(temp.left !== null){ q2.push(temp.left); } if(temp.right !== null){ q2.push(temp.right); } if(resList[level] === undefined){ resList[level] = []; } resList[level].push(temp.val); if(q1.length === 0){ q1 = q2; q2 = []; level++; } } // 4）返回后果：resList 里，下标为奇数的 元素项（数组模式）进行翻转。 // resList.map((item, level) => level%2 === 1 ? item.reverse() : item); return resList.map((item, level) => level%2 === 1 ? item.reverse() : item);};2 计划21)代码： ...

一、题目粗心请你仅应用两个队列实现一个后入先出（LIFO）的栈，并反对一般栈的全副四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 留神： 你只能应用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所应用的语言兴许不反对队列。 你能够应用 list （列表）或者 deque（双端队列）来模仿一个队列 , 只有是规范的队列操作即可。 示例： 输出：["MyStack", "push", "push", "top", "pop", "empty"][[], [1], [2], [], [], []]输入：[null, null, null, 2, 2, false] 解释：MyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.top(); // 返回 2myStack.pop(); // 返回 2myStack.empty(); // 返回 False ...

一、题目粗心https://leetcode.cn/problems/... 给定一个二维矩阵 matrix，以下类型的多个申请： 计算其子矩形范畴内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所形容的子矩阵的元素 总和 。 示例 1： /1626332422-wUpUHT-image.png) 输出: ["NumMatrix","sumRegion","sumRegion","sumRegion"][[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]输入: [null, 8, 11, 12] 解释:NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和) ...

一、题目粗心https://leetcode.cn/problems/range-sum-query-immutable 给定一个整数数组  nums，解决以下类型的多个查问: 计算索引 left 和 right （蕴含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right实现 NumArray 类： NumArray(int[] nums) 应用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，蕴含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )  示例 1： 输出：["NumArray", "sumRange", "sumRange", "sumRange"][[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]输入：[null, 1, -1, -3]解释：NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))提醒： ...

问题形容给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。 混合字符串 由小写英文字母和数字组成。 示例 1： 输出：s = "dfa12321afd"输入：2解释：呈现在 s 中的数字包含 [1, 2, 3] 。第二大的数字是 2 。示例 2： 输出：s = "abc1111"输入：-1解释：呈现在 s 中的数字只蕴含 [1] 。没有第二大的数字。力扣原题目地址：https://leetcode.cn/problems/...思路剖析形式一 先遍历再去重再排序取最初第二大的数首先字符串中除了有数字字符，也有字母字符。所以咱们在遍历的时候，只需保留数字字符，疏忽字母字符即可。这里应用字符串的charCodeAt办法做一个转换判断即可。字符串0到字符串9别离对应Unicode的是： console.log( '0'.charCodeAt() ) // 48console.log( '1'.charCodeAt() ) // 49...... // 顺次递增console.log( '8'.charCodeAt() ) // 56console.log( '9'.charCodeAt() ) // 57排除了字母字符当前，遍历拿到的每一个数字字符，都能够追加到数组中去。这样数组中就记录了所有的数字字符而后把数组中的数字字符做一个去重，去完重当前，再做一个排序，再取第二大的数即可。代码如下：var secondHighest = function (s) {    let arr = [] // 1. 定义一个空数组，用于存储    for (let i = 0; i < s.length; i++) { // 2. 遍历，并剔除字母字符，只保留数字字符        let item = s[i]        if (item.charCodeAt() >= 48 & item.charCodeAt() <= 57) { // charCodeAt()办法过滤            arr.push(item)       }   }    let newArr = Array.from(new Set([...arr])) // 3. 去个重    newArr.sort((a, b) => { // 4. 排个序        return b - a   })    return newArr[1] ? newArr[1] : -1 // 5. 有第二项，就返回第二项，没有就返回-1};形式二 定义俩变量示意第一大第二大的数并一直迭代更新定义两个变量用来示意第一大和第二大的数遍历中不断更新第一大和第二大的数字这种定义变量通过遍历一直比照并比拟大小的操作力扣也有相似的题目 ...

239. Sliding Window Maximum 滑动窗口最大值一、题目粗心标签: 双端队列 https://leetcode.cn/problems/... 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。 返回 滑动窗口中的最大值 。   示例 1： 输出：nums = [1,3,-1,-3,5,3,6,7], k = 3输入：[3,3,5,5,6,7]解释：滑动窗口的地位 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 ...

一、题目粗心标签: 栈和队列 https://leetcode.cn/problems/... 给你一个链表数组，每个链表都曾经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。   示例 1： 输出：lists = [[1,4,5],[1,3,4],[2,6]]输入：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中失去。1->1->2->3->4->4->5->6示例 2： 输出：lists = []输入：[]示例 3： 输出：lists = [[]]输入：[]  提醒： k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= listsi <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4二、解题思路这里须要将k个排序链表交融成一个排序链表，多个输出一个输入，相似于漏斗，因而能够利用最小堆的概念。 取每个Linked List的最小节点放入一个heap中，排成最小堆，而后取出堆顶最小的元素放入合并的List中，而后将该节点在其对应的List中的下一个节点插入到heap中，循环下面步骤。 三、解题办法3.1 Java实现public class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val)); for (ListNode node : lists) { if (node != null) { pq.add(node); } } ListNode ret = null; ListNode cur = null; while (!pq.isEmpty()) { ListNode node = pq.poll(); if (ret == null) { cur = node; ret = cur; } else { cur.next = node; cur = cur.next; } if (node.next != null) { pq.add(node.next); } } return ret; } /** * Definition for singly-linked list. */ public class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }}四、总结小记2022/8/11 疫情常态化了

一、题目粗心标签: 栈和队列 https://leetcode.cn/problems/daily-temperatures 给定一个整数数组 temperatures ，示意每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度呈现在几天后。如果气温在这之后都不会升高，请在该地位用 0 来代替。   示例 1: 输出: temperatures = [73,74,75,71,69,72,76,73]输入: [1,1,4,2,1,1,0,0]示例 2: 输出: temperatures = [30,40,50,60]输入: [1,1,1,0]示例 3: 输出: temperatures = [30,60,90]输入: [1,1,0]  提醒： 1 <= temperatures.length <= 10530 <= temperatures[i] <= 100 二、解题思路什么是枯燥栈？枯燥栈通过维持栈内值的枯燥递增（递加）性，在整体O(n)的工夫内解决须要大小比拟的问题。 思路：能够维持一个枯燥递加的栈，示意每天的温度，为了不便计算天数差，这里寄存地位（即日期）而非温度自身。从左向右遍历温度数组，对于每个日期p，如果p的温度比栈顶存储地位q的温度高，则咱们取出q，并记录q须要期待的天数p-q；反复这一过程，直到p的温度小于等于栈顶地位的温度或空栈时，咱们将p插入栈顶，而后思考下一天。在这个过程中栈内数组永远放弃枯燥递加，防止了应用排序进行比拟。最初若栈内残余一些日期，则阐明它们之后都没有呈现更温暖的日期。 三、解题办法3.1 Java实现public class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] ans = new int[temperatures.length]; Stack<Integer> desStack = new Stack<>(); for (int i = 0; i < temperatures.length; i++) { while (!desStack.isEmpty()) { int preIndex = desStack.peek(); if (temperatures[i] <= temperatures[preIndex]) { break; } desStack.pop(); ans[preIndex] = i - preIndex; } desStack.push(i); } return ans; }}四、总结小记2022/8/10 下雨、下雪本是很好玩的事，大了之后也不尽然，出行、生产、工作都会受到影响

一、题目粗心标签: 栈和队列 https://leetcode.cn/problems/valid-parentheses 给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。 无效字符串需满足： 左括号必须用雷同类型的右括号闭合。左括号必须以正确的程序闭合。  示例 1： 输出：s = "()"输入：true示例 2： 输出：s = "()[]{}"输入：true示例 3： 输出：s = "(]"输入：false示例 4： 输出：s = "([)]"输入：false示例 5： 输出：s = "{[]}"输入：true提醒： 1 <= s.length <= 104s 仅由括号 '()[]{}' 组成二、解题思路思路：括号匹配是典型的应用栈来解决的问题。从左向右遍历，每当遇到左括号便放入栈内，遇到右括号则判断其和栈顶的括号是否是对立类型，是则从栈内取出左括号，否则阐明字符不串不非法。 实现：遍历字符串，如果栈为空则将以后字符入栈，如果栈顶字符与以后字符匹配则栈顶字符出栈，不匹配以后字符入栈，遍历完结如果栈为空阐明字符串非法。 三、解题办法3.1 Java实现public class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (Character c : s.toCharArray()) { if (isPush(stack, c)) { stack.push(c); } else { stack.pop(); } } return stack.isEmpty(); } private boolean isPush(Stack<Character> stack, Character c) { if (stack.isEmpty()) { return true; } // {[( boolean isPop = (stack.peek().equals('[') && c.equals(']') || stack.peek().equals('{') && c.equals('}') || stack.peek().equals('(') && c.equals(')')); return !isPop; }}3.2 2014年的实现public class Solution { public boolean isValid(String s) { if (s == null || s.length() == 0) { return true; } Stack<Byte> ps = new Stack<Byte>(); byte[] bArr = s.getBytes(); boolean isValid = true; for (byte b : bArr) { if (!isValid) { break; } switch (b) { case '(': case '[': case '{': ps.push(b); break; case ')': case ']': case '}': if (!ps.empty()) { byte tmpB = ps.pop(); if (tmpB == 40) { tmpB++; } else { tmpB+=2; } if (tmpB != b) { isValid = false; } } else { isValid = false; } break; default: // do nothing } } if (!ps.empty()) { isValid = false; } return isValid; }}四、总结小记2022/8/9 一场秋雨一场寒

问题形容给定两个字符串 s 和 t ，它们只蕴含小写字母。 字符串 t 由字符串 s 随机重排，而后在随机地位增加一个字母。 请找出在 t 中被增加的字母。 示例 1： 输出：s = "abcd", t = "abcde"输入："e"解释：'e' 是那个被增加的字母。示例 2： 输出：s = "", t = "y"输入："y"力扣原题目地址：https://leetcode.cn/problems/... 解法一 转数组比照删除思路把长字符串t转成数组，同时遍历短字符串s，能够拿到s中的每一项，而后把同样项，在t数组中删掉（t比s多一项，s中有的t中肯定有） 比方t为'abc'，s为'ab'，那么不停比照，不停删除，最初t中只剩一个'c'，是s中没有的，即为t中增加的字母。即找到了，代码如下： 代码var findTheDifference = function (s, t) { let stack = t.split('') // 1. 把长字符串t转成数组 for (let j = 0; j < s.length; j++) { // 2. 遍历短字符串s let ind = stack.indexOf(s[j]) // 3. 拿到这一项在对应数组中的索引地位 stack.splice(ind, 1) // 4. 并做对应删除，就这样不停删除，数组中就会只剩一个了 } return stack[0] // 5. 剩的这一个就是t中被增加的字母};解法二 统计t和s字符串合并后单词呈现的次数（找奇数）思路首先把t和s字符串做一个合并，而后统计各个字母呈现的字数。已知t和s原本长得就一样的，只不过t多了一个字母。假如t和s一样的，那么两个字符串合并当前统计下来，每个字母呈现的次数都是偶数当初t多了一个字母，所以便会呈现某个字母呈现的次数是奇数次数为奇数的那个字母，就是t中被增加的字母代码var findTheDifference = function (s, t) { let ss = s + t // 1. 合并字符串 let map = new Map() // 2. 应用汇合进行次数统计 for (let i = 0; i < ss.length; i++) { if (map.has(ss[i])) { let count = map.get(ss[i]) count = count + 1 map.set(ss[i], count) } else { map.set(ss[i], 1) } } // 3. 统计好当前，遍历这个map联合，看看谁呈现的次数是奇数 for (const [key, value] of map) { if (value % 2 == 1) { return key // 4. 次数为奇数的那个字母，就是t中被增加的字母 } }};解法三 应用String.charCodeAt()办法和String.fromCharCode()办法常识回顾String.charCodeAt() 把字符串转换成Unicode数字值(UTF-16 编码单元) ...

一、题目粗心标签: 栈和队列 https://leetcode.cn/problems/min-stack 设计一个反对 push ，pop ，top 操作，并能在常数工夫内检索到最小元素的栈。 实现 MinStack 类: MinStack() // 初始化堆栈对象。void push(int val) // 将元素val推入堆栈。void pop() // 删除堆栈顶部的元素。int top() // 获取堆栈顶部的元素。int getMin() // 获取堆栈中的最小元素。  示例 1: 输出：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]] 输入：[null,null,null,null,-3,null,0,-2] 解释：MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2. 提醒： -231 <= val <= 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次二、解题思路能够额定建设一个栈（最小值栈），栈顶示意原栈中最小值。插入一个数字时，如果该值小于新栈的栈顶值阐明该数是最小值，将其同时插入原栈和最小值栈。取数时，如果原栈的值等于最小值栈的值，阐明这个数是原栈中的最小值，原栈和最小值栈须要同时移除该元素。 实现：每次插入栈时，都向最小值栈插入一个原栈里所有值的最小值。 三、解题办法3.1 Java实现class MinStack { Stack<Integer> s; /** * 辅助栈 */ Stack<Integer> minS; public MinStack() { s = new Stack<>(); minS = new Stack<>(); } public void push(int val) { s.push(val); // 留神这里是>= if (minS.isEmpty() || minS.peek() >= val) { minS.push(val); } } public void pop() { int val = s.pop(); if (!minS.isEmpty() && minS.peek() == val) { minS.pop(); } } public int top() { return s.peek(); } public int getMin() { return minS.isEmpty() ? 0 : minS.peek(); }}// Integer 与 int 比拟/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */四、总结小记2022/8/8 这两天有大到暴雨，能凉爽一些吧

一、题目粗心标签: 栈和队列 https://leetcode.cn/problems/implement-queue-using-stacks 请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的开端int pop() 从队列的结尾移除并返回元素int peek() 返回队列结尾的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false阐明： 你 只能 应用规范的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是非法的。你所应用的语言兴许不反对栈。你能够应用 list 或者 deque（双端队列）来模仿一个栈，只有是规范的栈操作即可。  示例 1： 输出：["MyQueue", "push", "push", "peek", "pop", "empty"][[], [1], [2], [], [], []]输入：[null, null, null, 1, 1, false]解释： MyQueue myQueue = new MyQueue();myQueue.push(1); // queue is: [1]myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)myQueue.peek(); // return 1myQueue.pop(); // return 1, queue is [2]myQueue.empty(); // return false  ...

一、题目粗心标签: 数组 https://leetcode.cn/problems/max-chunks-to-make-sorted 给定一个长度为 n 的整数数组 arr ，它示意在 [0, n - 1] 范畴内的整数的排列。 咱们将 arr 宰割成若干 块 (即分区)，并对每个块独自排序。将它们连接起来后，使得连贯的后果和按升序排序后的原数组雷同。 返回数组能分成的最多块数量。   示例 1: 输出: arr = [4,3,2,1,0]输入: 1解释:将数组分成2块或者更多块，都无奈失去所需的后果。例如，分成 [4, 3], [2, 1, 0] 的后果是 [3, 4, 0, 1, 2]，这不是有序的数组。示例 2: 输出: arr = [1,0,2,3,4]输入: 4解释:咱们能够把它分成两块，例如 [1, 0], [2, 3, 4]。然而，分成 [1, 0], [2], [3], [4] 能够失去最多的块数。  提醒: n == arr.length1 <= n <= 100 <= arr[i] < narr 中每个元素都 不同二、解题思路思路：从左往右遍历，同时记录以后的最大值，每当以后最大值等于数组地位时，咱们能够多一次宰割。 剖析：如果以后最大值大于数组地位，则阐明左边肯定有小于数组地位的数字，须要把它也退出待排序的子数组；又因为只蕴含不反复的0到n，所以以后最大值肯定不会小于数组地位。所以每当以后最大值等于数组地位时，假如为p，咱们能够胜利实现一次宰割，并且其与上一次宰割地位q之间的值肯定是q+1到p的所有数字。 ...

问题形容在整数数组中，如果一个整数的呈现频次和它的数值大小相等，咱们就称这个整数为「侥幸数」。 给你一个整数数组 arr，请你从中找出并返回一个侥幸数。 如果数组中存在多个侥幸数，只需返回 最大 的那个。 如果数组中不含侥幸数，则返回 -1 。 示例 1： 输出：arr = [2,2,3,4]输入：2解释：数组中惟一的侥幸数是 2 ，因为数值 2 的呈现频次也是 2 。示例 2： 输出：arr = [1,2,2,3,3,3]输入：3解释：1、2 以及 3 都是侥幸数，只须要返回其中最大的 3 。示例 3： 输出：arr = [2,2,2,3,3]输入：-1解释：数组中不存在侥幸数。示例 4： 输出：arr = [5]输入：-1示例 5： 输出：arr = [7,7,7,7,7,7,7]输入：7力扣原题目地址：https://leetcode.cn/problems/...思路剖析题目简略，就是统计数组中每一项呈现的次数（统计谁呈现了几次），看看谁正好等于呈现的次数；当然可能正好有多个 谁 等于 其对应呈现的次数，这个时候，就看谁更大即可 一想到要统计数组中每一项呈现的次数，咱们就会想到应用Map汇合进行统计 比方for循环数组，而后往map里追加，map中存储的键值对中的key为数组中的项，value为数组中这一项呈现的次数。代码： let map = new Map()for (let i = 0; i < arr.length; i++) {    if (map.has(arr[i])) {        let count = map.get(arr[i])        count = count + 1        map.set(arr[i], count)   } else {        map.set(arr[i], 1)   }}而后再应用forof遍历map汇合，做次数判断即可或者想到应用对象Object统计 ...

一、题目粗心标签:数组 https://leetcode.cn/problems/search-a-2d-matrix-ii 编写一个高效的算法来搜寻 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具备以下个性： 每行的元素从左到右升序排列。每列的元素从上到下升序排列。  示例 1： 输出：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输入：true示例 2： 输出：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20输入：false提醒： m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrixi <= 109每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-109 <= target <= 109二、解题思路解题技巧：从右上角开始查找，若以后值大于待搜寻值，向左挪动一位，若以后值小于待搜寻值，向下挪动一位。如果最终挪动到左下角时仍不等于待搜寻值，则阐明待搜寻值不存在于矩阵中。 三、解题办法3.1 Java实现public class Solution { public boolean searchMatrix(int[][] matrix, int target) { // 从右上角开始搜寻，比target大就向左移，比target小就向下移 int x = matrix.length - 1; int y = 0; while (x >=0 && y < matrix[0].length) { if (matrix[x][y] == target) { return true; } else if (matrix[x][y] > target) { x--; } else { y++; } } return false; }}四、总结小记2022/8/5 疫情啊，什么时候能消停一会

问题形容给你一个整数数组 nums ，请你将数组依照每个值的频率 升序 排序。如果有多个值的频率雷同，请你依照数值自身将它们 降序 排序。  请你返回排序后的数组。 示例 1： 输出：nums = [1,1,2,2,2,3]输入：[3,1,1,2,2,2]解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。示例 2： 输出：nums = [2,3,1,3,2]输入：[1,3,3,2,2]解释：'2' 和 '3' 频率都为 2 ，所以它们之间依照数值自身降序排序。示例 3： 输出：nums = [-1,1,-6,4,5,-6,1,4,1]输入：[5,-1,4,4,-6,-6,1,1,1]力扣原题目地址：https://leetcode.cn/problems/... 知识点回顾之Map汇合和二维数组咱们晓得Map汇合能够用于存储一组组键值对数据。比方咱们要创立一个Map汇合，汇合中有三组数据，别离对应为姓名和年龄。 原始数据如下： 姓名 年龄孙悟空 500猪八戒 88沙和尚 1000创立进去的Map汇合如下图 接下来回顾一下创立这个Map汇合的两种形式 应用Map.set()办法创立Map汇合个别状况下，咱们都是应用Map的set办法去创立本人想要的汇合，如下代码： let map1 = new Map()map1.set('孙悟空', 500)map1.set('猪八戒', 88)map1.set('沙和尚', 1000)console.log('map1', map1);应用二维数组创立Map汇合既然Map汇合能够存储一组组键值对的数据，那么咱们能够把这个一组组数据，当成一个个只蕴含两个项（第0项是键key、第二项是值value）的数组，而后把整个汇合当成一个大数组。 于是一个二维数组就应运而生了。所以在构造函数的协同下，咱们能够在实例化Map对象的时候，传入一个二维数组，便是能够达到同样的成果，如下代码： let map2 = new Map( [ ['孙悟空', 500], ['猪八戒', 88], ['沙和尚', 1000], ])console.log('map2', map2);由上述两个案例，能够晓得Map汇合，如同就是二维数组的一种变形形式，一种非凡的二维数组，当然理论不是哦。 上方案例应用二维数组创立Map汇合可了解为，把二维数组转成对应Map汇合；同样的，Map汇合也可转为二维数组，应用Array.from(map)即可留神，上述二维数组转Map汇合案例，是固定项个数。如 内层数组只有两项key项、value项。如果再多几项，会疏忽后续的项。因为Map汇合的一组数据只有key和value。如下代码let map = new Map( [ ['孙悟空', 500, '花果山水帘洞'], ['猪八戒', 88, '高老庄'], ['沙和尚', 1000, '通天河'], ] )console.log('map', map);打印进去的后果如下： ...

一、题目粗心标签: 数组 https://leetcode.cn/problems/rotate-image 给定一个 n × n 的二维矩阵 matrix 示意一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你须要间接批改输出的二维矩阵。请不要 应用另一个矩阵来旋转图像。 示例 1： 输出：matrix = [[1,2,3],[4,5,6],[7,8,9]]输入：[[7,4,1],[8,5,2],[9,6,3]]示例 2： 输出：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输入：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]提醒： n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrixi <= 1000 二、解题思路一个元素每次90度旋转，旋转4次后回到原点，这样咱们找出这四个点的坐标所有就简略了，令N=martrix.length-1： (i, j)(N-j, i)(N-i, N-j)(j, N-i)为了旋转这四个元素，咱们能够用一个长期变量保留其中一个元素，而后让几个元素顺次赋值。那么，一共有多少个这样的四元素组呢？这要分状况来看。两层遍历数组，第一层i 从0到n/2，第二层j 从j到n-i，这样遍历的元素为n/4或(n-1)/4； 三、解题办法3.1 Java实现public class Solution { public void rotate(int[][] matrix) { // 输出：matrix = [[1,2,3],[4,5,6],[7,8,9]] // 输入：[[7,4,1],[8,5,2],[9,6,3]] // x示意行 y示意列 /** * i 0->n/2 0->2 * j i->n-i i->3-i * 00 01 02 03 * 11 12 * 从上到下 (j,n-i) * 从右到左 * * (j,n-i)<-(i,j) * (i,j)<-(n-j,i) * (n-j,i)<-(n-i, n-j) */ int temp = 0; int n = matrix.length - 1; for (int i = 0; i <= n / 2; i++) { for (int j = i; j < n - i; j++) { // 0行n列 temp = matrix[j][n - i]; matrix[j][n - i] = matrix[i][j]; matrix[i][j] = matrix[n-j][i]; matrix[n-j][i] = matrix[n-i][n-j]; matrix[n-i][n-j] = temp; } } }}四、总结小记2022/8/4 须要总结一下60多天的刷题了

问题形容给你两个字符串数组 word1 和 word2 。如果两个数组示意的字符串雷同，返回 true ；否则，返回 false 。 数组示意的字符串 是由数组中的所有元素 按程序 连贯造成的字符串。 示例 1： 输出：word1 = ["ab", "c"], word2 = ["a", "bc"]输入：true解释：word1 示意的字符串为 "ab" + "c" -> "abc"word2 示意的字符串为 "a" + "bc" -> "abc"两个字符串雷同，返回 true示例 2： 输出：word1 = ["a", "cb"], word2 = ["ab", "c"]输入：false示例 3： 输出：word1 = ["abc", "d", "defg"], word2 = ["abcddefg"]输入：true力扣原题目地址：https://leetcode.cn/problems/...解决方案思路很简略，就是把数组转成字符串，而后做一个比照看看是否相等即可。 数组转字符串有以下计划： toString()办法String()办法join()办法数组循环字符串拼接本题目用到第3和第4办法 计划一 join()办法var arrayStringsAreEqual = function (word1, word2) { let str1 = word1.join('') let str2 = word2.join('') return str1 === str2};计划二 数组循环字符串拼接var arrayStringsAreEqual = function (word1, word2) { let str1 = '' word1.forEach((item) => { str1 = str1 + item }) let str2 = '' word2.forEach((item) => { str2 = str2 + item }) return str1 === str2};

一、题目粗心标签: 数组 https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范畴内但没有呈现在 nums 中的数字，并以数组的模式返回后果。 示例 1： 输出：nums = [4,3,2,7,8,2,3,1]输入：[5,6]示例 2： 输出：nums = [1,1]输入：[2]提醒： n == nums.length1 <= n <= 1051 <= nums[i] <= n进阶：你能在不应用额定空间且工夫复杂度为 O(n) 的状况下解决这个问题吗? 你能够假设返回的数组不算在额定空间内。二、解题思路把所有反复呈现的地位进行标记，而后再遍历一遍数组，即可找到没有呈现过的数字。进一步优化，能够间接对原数组进行标记：把反复呈现的数字在原数组呈现的地位设为正数，最初依然为负数的地位即为没有呈现过的数。 三、解题办法3.1 Java实现public class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { for (int num : nums) { // 这个中央要留神 -1，数组下标从0开始 int pos = Math.abs(num) - 1; if (nums[pos] > 0) { nums[pos] = -nums[pos]; } } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { ans.add(i + 1); } } return ans; }}四、总结小记2022/8/3 上面做按数据结构开始做，先从数组开始

一、题目粗心https://leetcode.cn/problems/base-7 给定一个整数 num，将其转化为 7 进制，并以字符串模式输入。 示例 1: 输出: num = 100输入: "202"示例 2: 输出: num = -7输入: "-10"提醒： -107 <= num <= 107二、解题思路输出一个整数，输入一个字符串，示意其七进制。进制转换类的题，通常是利用除法和取模来进行计算，同时也要留神一些细节，如正数和零。如果输入是数字类型而非字符串，则也须要思考是否会超出整数上下界。举例：100，求其7进制 100 / 7 = 14 ...... 214 / 7 = 2 ...... 0七进制数为最初一位商+余数倒排 三、解题办法3.1 Java实现public class Solution { public String convertToBase7(int num) { if (num == 0) { return "0"; } boolean isNegative = num < 0; num = isNegative ? -num : num; StringBuilder ans = new StringBuilder(); while (num >= 7) { int a = num / 7; int b = num % 7; ans.append(b); num = a; } ans.append(num); return (isNegative ? "-" : "") + ans.reverse(); }}四、总结小记2022/8/2 余数和模的区别？

一、题目粗心https://leetcode.cn/problems/count-primes 给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。 示例 1： 输出：n = 10输入：4解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。示例 2： 输出：n = 0输入：0示例 3： 输出：n = 1输入：0提醒： 0 <= n <= 5 * 106 二、解题思路输出一个整数，输入也是一个整数，示意小于输出数的质数的个数。埃拉托斯特尼筛法，是判断一个整数是否是质数的办法。并且它能够在判断一个整数n时，同时判断所小于n的整数，因而非常适合这个问题。其原理是：从1到n遍历，假如以后遍历到m，则把所有小于n的、且是m的倍数的整数标为和数；遍历实现后，没有被标为和数的数字即为质数。 三、解题办法3.1 Java实现public class Solution { public int countPrimes(int n) { if (n <= 2) { return 0; } boolean[] prime = new boolean[n]; Arrays.fill(prime, true); int i = 3; int sqrtn = (int) Math.sqrt(n); // 偶数肯定不是质数 int count = n / 2; while (i <= sqrtn) { // 最小质因子肯定小于等于开方数 for (int j = i * i; j < n; j += 2 * i) { // 防止偶数和反复遍历 if (prime[j]) { count--; prime[j] = false; } } do { i+= 2; // 防止偶数和反复遍历 } while (i <= sqrtn && !prime[i]); } return count; }}四、总结小记2022/8/1 7月完结了贪婪算法的题，开启“巧解数学问题”类的题目

题目编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1：输出：strs = ["flower","flow","flight"]输入："fl"示例 2：输出：strs = ["dog","racecar","car"]输入：""解释：输出不存在公共前缀。提醒：1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] 仅由小写英文字母组成地址leetcode题目地址 刷题源码地址 纵向扫描找到 strs 中最短的字符串，循环最短长度，每一遍比照每一个的字符的第一个、第二个...字符是否相等，如果不想等，间接返回；循环完结，找到公共前缀（如果循环没有提前退出，也就是最短字符串为公共前缀）。 export function longestCommonPrefix(strs: string[]): string { let j = 0; let prefix = ""; let minLength = Math.min(...strs.map((v) => v.length)); while (minLength > 0) { prefix += strs[0][j]; for (let i = 0; i < strs.length; i++) { if (strs[i][j] !== prefix[j]) { return prefix.slice(0, j); } } j++; minLength--; } return prefix;}工夫复杂度是 O(mn)，m 是字符串数量，n 是最短字符串长度+2。 ...

问题形容给出由小写字母组成的字符串 S，反复项删除操作会抉择两个相邻且雷同的字母，并删除它们。 在 S 上重复执行反复项删除操作，直到无奈持续删除。 在实现所有反复项删除操作后返回最终的字符串。答案保障惟一。 示例： 输出："abbaca"输入："ca"解释：例如，在 "abbaca" 中，咱们能够删除 "bb" 因为两字母相邻且雷同，这是此时惟一能够执行删除操作的反复项。之后咱们失去字符串 "aaca"，其中又只有 "aa" 能够执行反复项删除操作，所以最初的字符串为 "ca"。力扣原题目地址：https://leetcode.cn/problems/...解决方案计划一 数组栈思维var removeDuplicates = function (s) { let stack = [] // 1. 创立一个栈数组，用于存放数据 for (let i = 0; i < s.length; i++) { // 2. 遍历字符串执行入栈出栈操作 // 3. 一开始栈是空的，所以不必看if，间接看else的操作 if (stack.at(-1) === s[i]) { // 5. 若栈中已有的顶部数据项（最初一项）和行将要入栈的数据统一，就阐明是反复项了 stack.pop() // 6. 反复项的话，就删除呗（行将入栈的这一项疏忽，同时把栈顶部数据即最初一项删除） } // 4. 新来的这一项，入栈（尾部追加） else { stack.push(s[i]) // 栈是非凡的数组，只会用到尾部增push、尾部删pop } } // 7. 最初栈中寄存的数据就是不相邻反复的数据 return stack.join('') // 8. 而后把栈数组转成字符串返回进去即可};栈的利用挺多的，不过如果遇到"成对"的问题需要，能够思考应用栈的思维去解决。即，尾部增、尾部删。 ...

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/non-decreasing-array 给你一个长度为 n 的整数数组 nums ，请你判断在 最多 扭转 1 个元素的状况下，该数组是否变成一个非递加数列。 咱们是这样定义一个非递加数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。 示例 1: 输出: nums = [4,2,3]输入: true解释: 你能够通过把第一个 4 变成 1 来使得它成为一个非递加数列。示例 2: 输出: nums = [4,2,1]输入: false解释: 你不能在只扭转一个元素的状况下将其变为非递加数列。提醒： n == nums.length1 <= n <= 104-105 <= nums[i] <= 105二、解题思路最多只有一次批改某个数字的机会，问是否将数组变为非递加数组。举例 例1:4， 2， 3 例2:-1， 4， 2， 3 例3:2， 3， 3， 2， 4当前面的数字小于后面的数字后，例如例1中的2小于4，这时能够将批改后面的数字将4批改为2或批改前面的数字将2改为4。咱们须要找到这个法则，判断批改哪个数字其实跟再后面的一个数大小有关系： 如果再后面的数不存在，例1中，4后面没有数字了咱们间接批改后面的数字为以后数字2即可； 如果再后面的数字存在，并且小于以后数字时，例2中，咱们须要批改后面的数字4为以后数字2； 如果再后面的数字存在，且大于以后数，例3中，咱们须要批改以后数字2为后面的数3。 因为只有一次批改的机会，所以用一个变量cnt，初始化为1，批改数字后cnt自减1，当下次再须要批改时，如果cnt为0，间接返回false。遍历完结后返回true。 三、解题办法3.1 Java实现public class Solution { public boolean checkPossibility(int[] nums) { int cnt = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] < nums[i - 1]) { if (cnt == 0) { return false; } cnt--; if (i == 1) { nums[i - 1] = nums[i]; } else if (nums[i] >= nums[i - 2]) { nums[i - 1] = nums[i]; } else { nums[i] = nums[i - 1]; } } } return true; }}四、总结小记2022/7/31 今天天气很闷热呀

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/queue-reconstruction-by-height 假如有打乱程序的一群人站成一个队列，数组 people 示意队列中一些人的属性（不肯定按程序）。每个 people[i] = [hi, ki] 示意第 i 集体的身高为 hi ，后面 正好 有 ki 个身高大于或等于 hi 的人。 请你从新结构并返回输出数组 people 所示意的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 集体的属性（queue[0] 是排在队列后面的人）。   示例 1： 输出：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]输入：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]解释：编号为 0 的人身高为 5 ，没有身高更高或者雷同的人排在他后面。编号为 1 的人身高为 7 ，没有身高更高或者雷同的人排在他后面。编号为 2 的人身高为 5 ，有 2 个身高更高或者雷同的人排在他后面，即编号为 0 和 1 的人。编号为 3 的人身高为 6 ，有 1 个身高更高或者雷同的人排在他后面，即编号为 1 的人。编号为 4 的人身高为 4 ，有 4 个身高更高或者雷同的人排在他后面，即编号为 0、1、2、3 的人。编号为 5 的人身高为 7 ，有 1 个身高更高或者雷同的人排在他后面，即编号为 1 的人。因而 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是从新结构后的队列。示例 2： ...

零 题目：算法（leetode，附思维导图 + 全副解法）300题之（2129）将题目首字母大写一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “字符串切割成数组 - 解决法”。// 思路：// 1）状态初始化：const wordList = title.split(' '), l = wordList.length; let resStr = '' 。// 2）外围：遍历 wordList 。// 2.1）若 以后word的长度小于 3，则 将word里的所有字符串转成小写。// 2.2）若 以后word的长度大于 3，则 将word里的首字母大写、残余的全小写。// 2.3）resStr 前面，拼上 word + ' ' 。// 3）resStr 前面，去掉多余的 ' ' 。// 4）返回后果 resStr 。var capitalizeTitle = function(title) { // 1）状态初始化：const wordList = title.split(' '), l = wordList.length; let resStr = '' 。 const wordList = title.split(' '), l = wordList.length; let resStr = ''; // 2）外围：遍历 wordList 。 for (let i = 0; i < l; i++) { let word = wordList[i]; // 2.1）若 以后word的长度小于 3，则 将word里的所有字符串转成小写。 if (word.length < 3) { word = word.toLowerCase(); } // 2.2）若 以后word的长度大于 3，则 将word里的首字母大写、残余的全小写。 else { word = word.toLowerCase(); word = word[0].toUpperCase() + word.slice(1); } // 2.3）resStr 前面，拼上 word + ' ' 。 resStr += word + ' '; } // 3）resStr 前面，去掉多余的 ' ' 。 resStr = resStr.slice(0, resStr.length - 1); // 4）返回后果 resStr 。 return resStr;};2 计划21)代码： ...

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（240）搜寻二维矩阵 II一 题目形容 二 解法总览（思维导图） 三 全副解法面试官：题目看得差不多了吧，怎么样、有无思路呀？ 狂徒张三：波及“映射、数量、重复性（即去重）、唯一性（即次数）等”，我可能会优先思考hash（JS里对应的是 map数据结构）。 面试官：那你先讲讲大抵思路吧 狂徒张三： 1）遍历二维数组里的每个元素，将它们放在哈希表里。2）最初判断 target 值，是否在哈希表里即可~ 面试官：嗯嗯，整体思路是ok的，那么开始写吧 狂徒张三：过了2分52秒后，张三就写完了程序 1 计划11)代码： // 计划1 “本人。哈希法”。// 注：通过 124 / 129，会超时。// 用时：15：14 - 15：16。// 技巧：波及“映射、数量、重复性（即去重）、唯一性（即次数）等”可优先思考hash（JS里对应的是 map数据结构）。// 思路：// 1）状态初始化：m = matrix.length, n = matrix[0].length;// resMap = new Map();// 2）遍历二维数组，将每个元素放入 resMap 中。// 3）返回后果： resMap.has(target) 。var searchMatrix = function(matrix, target) { // 1）状态初始化：m = matrix.length, n = matrix[0].length; // resMap = new Map(); const m = matrix.length, n = matrix[0].length; let resMap = new Map(); // 2）遍历二维数组，将每个元素放入 resMap 中。 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const tempVal = matrix[i][j]; resMap.set(tempVal, 1); } } // 3）返回后果： resMap.has(target) 。 return resMap.has(target);};旁边：代码在后盾运行中，过了3秒，屏幕忽然【闪现】出【通过 124 / 129，超出工夫限度】。 ...

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii 给你一个整数数组 prices ，其中 prices[i] 示意某支股票第 i 天的价格。 在每一天，你能够决定是否购买和/或发售股票。你在任何时候 最多 只能持有 一股 股票。你也能够先购买，而后在 同一天 发售。 返回 你能取得的 最大 利润 。 示例 1： 输出：prices = [7,1,5,3,6,4]输入：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 - 1 = 4 。  随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。示例 2： 输出：prices = [1,2,3,4,5]输入：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 - 1 = 4 。  总利润为 4 。示例 3： ...

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/partition-labels 字符串 S 由小写字母组成。咱们要把这个字符串划分为尽可能多的片段，同一字母最多呈现在一个片段中。返回一个示意每个字符串片段的长度的列表。 示例： 输出：S = "ababcbacadefegdehijhklij"输入：[9,7,8]解释：划分后果为 "ababcbaca", "defegde", "hijhklij"。每个字母最多呈现在一个片段中。像 "ababcbacadefegde", "hijhklij" 的划分是谬误的，因为划分的片段数较少。提醒： S的长度在[1, 500]之间。S只蕴含小写字母 'a' 到 'z' 。 二、解题思路一个字符串S，将其尽可能多的宰割为子字符串，条件是每种字符最多只能呈现在一个子串中。下面的示例中，字符串S中有多个a，这些a必须只能在第一个子串中，字母e呈现在第二个子串中。这道题难点就是如何找到字符串的断点，即拆分成为子串的地位。察看上述例子，一旦某个字母屡次呈现，那么其最初一个呈现地位必须要在以后子串中，字母a，e，j别离是三个子串中的完结字母。所以咱们关注的是每个字母最初的呈现地位，咱们能够应用一个Map来建设字母和其最初呈现地位之间的映射，建设好映射之后，就须要开始遍历字符串S，咱们保护一个start变量，是以后子串的起始地位，还有一个last变量，是以后子串的完结地位，每当咱们遍历到一个字母，须要在Map中提取出其最初一个地位，因为一旦以后子串饮食了一个字母，其必须饮食所有的雷同字母，所以咱们要不停的用以后字母的最初一个地位来更新last变量，只有当i和last雷同了，即i=last时，以后子串饮食了所有已呈现过的字母的最初一个地位，即之后的字符串不会有之前呈现过的字母了，此时就应该是断开的地位，咱们将子串长度退出到后果中。 三、解题办法3.1 Java实现public class Solution { public List<Integer> partitionLabels(String s) { Map<Character, Integer> map = new HashMap<>(); char[] cArr = s.toCharArray(); for (int i = 0; i < cArr.length; i++) { map.put(cArr[i], i); } List<Integer> res = new ArrayList<>(); int start = 0; int last = 0; for (int i = 0; i < cArr.length; i++) { last = Math.max(map.get(cArr[i]), last); if (i == last) { res.add(last - start + 1); start = last + 1; } } return res; }}四、总结小记2022/7/28 把思路理清了，代码就牵强附会进去了

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons 有一些球形气球贴在一堵用 XY 立体示意的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 示意程度直径在 xstart 和 xend之间的气球。你不晓得气球的确切 y 坐标。 一支弓箭能够沿着 x 轴从不同点 齐全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和完结坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。能够射出的弓箭的数量 没有限度 。 弓箭一旦被射出之后，能够有限地后退。 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。  示例 1： 输出：points = [[10,16],[2,8],[1,6],[7,12]]输入：2解释：气球能够用2支箭来爆破:-在x = 6处射出箭，击破气球[2,8]和[1,6]。-在x = 11处发射箭，击破气球[10,16]和[7,12]。示例 2： 输出：points = [[1,2],[3,4],[5,6],[7,8]]输入：4解释：每个气球须要射出一支箭，总共须要4支箭。示例 3： 输出：points = [[1,2],[2,3],[3,4],[4,5]]输入：2解释：气球能够用2支箭来爆破: 在x = 2处发射箭，击破气球[1,2]和[2,3]。在x = 4处射出箭，击破气球[3,4]和[4,5]。提醒: 1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1二、解题思路区间重叠问题，个别都要想到贪婪（部分最优等于全局最优）。本题给咱们一堆大小不等的气球，用区间范畴来示意气球大小，可能会有重叠区间，咱们用起码的箭打爆所有气球。咱们把所有区间依照右边界进行排序，因为每个气球都要被突破，因而排序失去的第一组数据咱们肯定要应用。只有沿着该数据最右边界的地位进行射箭肯定能突破尽可能多的气球。而后顺次挪动射箭的地位，进行统计即可。 三、解题办法3.1 Java实现public class Solution { public int findMinArrowShots(int[][] points) { // 二维数组的排序？？ Arrays.sort(points, Comparator.comparingInt(o -> o[1])); int res = 1; int end = points[0][1]; for (int i = 1; i < points.length; i++) { if (points[i][0] <= end) { end = Math.min(end, points[i][1]); } else { res++; end = points[i][1]; } } return res; }}四、总结小记2022/7/27 复原每日一题

题目给你一个字符串 s，找到 s 中最长的回文子串。 示例 1：输出：s = "babad"输入："bab"解释："aba" 同样是合乎题意的答案。示例 2：输出：s = "cbbd"输入："bb"提醒：1 <= s.length <= 1000s 仅由数字和英文字母组成解法本题我的项目地址 解题源代码 测试用例代码 暴力求解判断是否是回文串function isPalindrome(s: string): boolean { let l = 0; let r = s.length - 1; while (l < r) { if (s[l] === s[r]) { l++; r--; } else { return false; } } return true;}间接获取每个字符子串判断是否为回文串，最初输入最长子串 用数组保留回文子串，下标为长度，最初输入最初一个（比拟占内存） export function longestPalindrome(s: string): string { const arr = [""]; for (let i = 0; i < s.length; i++) { for (let j = i + 1; j <= s.length; j++) { const value = s.slice(i, j); if (isPalindrome(value)) { arr[value.length] = value; } } } return arr.pop()!;}暴力求解的形式在字符串很长的时候就慢了一些，须要 17ms ...

两数相加leetcode题目地址 解题源码及测试 题目给你两个非空的链表，示意两个非负的整数。它们每位数字都是依照逆序的形式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以雷同模式返回一个示意和的链表。 你能够假如除了数字 0 之外，这两个数都不会以 0  结尾。 示例 1：输出：l1 = [2,4,3], l2 = [5,6,4]输入：[7,0,8]解释：342 + 465 = 807.示例 2：输出：l1 = [0], l2 = [0]输入：[0]示例 3：输出：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输入：[8,9,9,9,0,0,0,1]提醒： 每个链表中的节点数在范畴 [1, 100] 内0 <= Node.val <= 9题目数据保障列表示意的数字不含前导零解答遍历两个两个链表，有值取值，无值取 0；因为一个节点只保留一位数字，因而不会>10； 因而只有两种状况，>=10时进位，<10间接赋值；这里用一个变量去记录是否有进位，如果有，下一次计算时+1，这里间接用Number(flag)的模式偷了个懒。 挪动 move 指针，并对 next 创立 ListNode 节点；这里须要判断是否新增最初一个节点。当最初两个节点数相加没有进位时，不须要减少，>10时才减少，此时 val = 1。 export class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val === undefined ? 0 : val; this.next = next === undefined ? null : next; }}export function addTwoNumbers( l1: ListNode | null, l2: ListNode | null): ListNode | null { let sum = 0; const result = new ListNode(0, null); let move = result; let flag = false; while (l1 || l2) { sum = (l1?.val ?? 0) + (l2?.val ?? 0) + Number(flag); if (sum >= 10) { move.val = sum % 10; flag = true; } else { move.val = sum; flag = false; } l1 && (l1 = l1.next); l2 && (l2 = l2.next); if (l1 || l2 || flag) { move = move.next = new ListNode(Number(flag), null); } } return result;}

问题形容编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1： 输出：strs = ["flower","flow","flight"]输入："fl"示例 2： 输出：strs = ["dog","racecar","car"]输入：""解释：输出不存在公共前缀。力扣原题目地址：https://leetcode.cn/problems/...解决方案思路剖析对于这样的题目，首先要排除非凡状况，比方数组中只有一项，若只有一项，即这一项就是最长公共前缀。所以独自判断length是否等于1即可天然是公共前缀，那么咱们能够取到字符串的单词去判断，当下的这个单词是否后续每一项都存在，所以咱们会相当数组的every办法既然是公共前缀，即为，对应字符串结尾的前缀，咱们会想到字符串的startsWith办法比方数组为：['abc','abcd','abcde']。咱们就间接以第一项为基准，取到第一项的第一个单词，a，而后看看这个a是不是后续每一项也是以a结尾的。若是的，再往后取一位（这里要拼接变成ab），而后往后看一下，是不是每一项都是以ab结尾的。如此循环，直到其中有一项不合乎以ab结尾的。当不合乎某个条件的时候，退出循环，咱们就会相到while循环代码如下// 额定抽离出一个函数，用于判断function startFn(strs, s) { let flag = strs.every((item) => { if (item.startsWith(s)) { // 必须每一项都要合乎以xxx结尾，才返回true return true } }) return flag}var longestCommonPrefix = function (strs) { // 如果数组只有一项，那么最长公共前缀就是本身 if (strs.length == 1) { return strs[0] } // 如果数组有多项，就要去遍历比照 if (strs.length >= 2) { // 如果数组中第一项是空字符串的，那么所有的公共前缀就是空字符串 // 这里须要留神空字符串没有第0项即： ""[0] === undefined if (!strs[0][0]) { return '' } // 排除空字符串的状况，咱们在失常遍历即可 let i = 0 // 这里的i是为了让第一项的单词累加 let s = strs[0][i] while (startFn(strs, s)) { i = i + 1 if (i > strs[0].length - 1) { // while外部的return阐明曾经全副循环完了（每一项长得都一样） return s } else { s = s + strs[0][i] } } // while内部的循环阐明到某一个单词的时候，别的单词没有，即没有更大的最长公共前缀了 return s.slice(0, -1) // 留神这里须要截取一下，多了一个单词。因为上方的s = s + strs[0][i] 多加了一次 }};性能还能够截图如下 ...

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（124）二叉树中的最大门路和一 题目形容 二 解法总览（思维导图） 三 全副解法面试官：题目看得差不多了吧，怎么样、有无思路呀？ 狂徒张三：对于二叉树的题目，咱们能够优先思考应用【递归】。 面试官：哦？这是为什么呢？ 狂徒张三：生物上书上有讲 —— “构造与性能相适应”，那我认为“算法”里，也有相似的货色，如 “数据结构与算法相适应” —— 仔细观察，你会发现，以后根节点、其左右节点的构造是 “同构” 的，那那么咱们天然会联想到应用 “递归” 。 面试官： 狂徒张三： 面试官（一脸庄重）： 旁白：过了4分41秒，张三便齐刷刷的写完了如下代码。 1 计划11)代码： // 计划1 “就地更新 - 再次遍历法（本人）”。// 技巧：二叉树的题目应优先思考应用递归。// 思路：// 1）状态初始化：resVal = Number.NEGATIVE_INFINITY （因 要求最大值，故 先置为 最大的负数值 ）// 2）外围1：依据状况，更新 树上各节点的值 。// 3）外围2：遍历新树，更新最大值 resVal 。// 4）返回后果 resVal 。var maxPathSum = function(root) { // 依据状况，更新 树上各节点的值 。 const updateTree = (root = null) => { // 1.1）递归进口1 if (!root) { return; } // 1.2）递归进口2 let {left, right, val} = root; if ((!left) && (!right)) { return; } // 2）递归主体 // 2.1）更新 左子树的值 。 updateTree(left); // 2.2）更新 右子树的值 。 updateTree(right); // 2.3）更新 根节点的值 。 // 分3种状况：带上左子树的值 或 带上右子树的值 或 左、右子树值均不带。 root.val = val + Math.max((left?.val || 0), (right?.val || 0), 0); // 2.4）更新后果值 resVal 。 resVal = Math.max(resVal, val + (left?.val || 0) + (right?.val || 0)); }; // 遍历新树，更新最大值 resVal 。 const getMaxValByNewTree = (root = null) => { // 1）递归进口 if (!root) { return; } // 2）递归主体 const {left, right, val} = root; // 2.1）根节点 resVal = Math.max(resVal, val); // 2.2）左子树 getMaxValByNewTree(left); // 2.3）右子树 getMaxValByNewTree(right); }; // 1）状态初始化：resVal = Number.NEGATIVE_INFINITY （因 要求最大值，故 先置为 最大的负数值 ） let resVal = Number.NEGATIVE_INFINITY; // 2）外围1：依据状况，更新 树上各节点的值 。 updateTree(root); // 3）外围2：遍历新树，更新最大值 resVal 。 getMaxValByNewTree(root); // 4）返回后果 resVal 。 return resVal;};狂徒张三：怎么样，还算过关吧？ ...

问题形容~只呈现一次的数字给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。 阐明：你的算法应该具备线性工夫复杂度。 你能够不应用额定空间来实现吗？ 示例 1: 输出: [2,2,1]输入: 1示例 2: 输出: [4,1,2,1,2]输入: 4力扣原题目地址：https://leetcode.cn/problems/...解决方案计划一 应用map统计各个项呈现的次数，看谁呈现的次数是一var singleNumber = function (nums) { let map = new Map() // 1. 创立一个map用来统计数据 for (let i = 0; i < nums.length; i++) { // 2. 遍历数组开始统计 // 3. 一开始map汇合是空的，所以持续往下看 if (map.has(nums[i])) { // 5. 后续来了一项，新来的这一项原汇合中有一样的项 let conut = map.get(nums[i]) // 6. 就看看原汇合中这一项呈现了几次 conut = conut + 1 // 7. 把原有次数新增一次 map.set(nums[i], conut) // 8. 而后更新次数 } else { // 4. 来一项，就把这一项存进map外面，key是这一项，value是这一项呈现的次数 map.set(nums[i], 1) } } // 9. 通过这么一波操作，map汇合中就记录了，各个项呈现的次数了 for (const [key, value] of map) { // 10. 应用forof遍历汇合 if (value === 1) { // 11. 看看谁呈现的次数是一次 return key // 12. 就把对应项返回进来告知即可 } }};当然这里也能够应用对象去统计次数，一个情理，在此不赘述 ...

问题形容给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最初一个 单词的长度。 单词 是指仅由字母组成、不蕴含任何空格字符的最大子字符串。 示例 1： 输出：s = "Hello World"输入：5解释：最初一个单词是“World”，长度为5。示例 2： 输出：s = "   fly me   to   the moon "输入：4解释：最初一个单词是“moon”，长度为4。示例 3： 输出：s = "luffy is still joyboy"输入：6解释：最初一个单词是长度为6的“joyboy”。力扣原题目地址：https://leetcode.cn/problems/...解决方案计划一 去空格加空格顺叙遍历计数因为题目是求最初一个单词的长度，所以要顺叙遍历，而后呈现一个字母词，就记一个数。当遇到空格的时候，阐明单词完结(为了以防万一，所以手动在单词的最左侧增加一个空格) var lengthOfLastWord = function (s) {    // 1. 先把左右空格都去掉，再手动增加一个左空格。之所以增加左空格是因为遍历到空格时，就进行遍历    s = ' ' + s.trimEnd() // 2. 遍历到空格时候，阐明一个单词正好实现了    let n = 0 // 3. 定义一个n用来统计次数    for (let i = s.length - 1; i >= 0; i--) { // 4. 因为求最初一个单词的长度，所以顺叙遍历即可。留神i要>=0，只>0就会少统计一次        if (s[i] == ' ') { // 5. 若是遇到空格了，就间接返回已统计好的次数，即：单词的长度            return n       } else { // 6. 没遇到空格阐明是单词，那么就统计单词的词个数            n = n + 1       }   }};计划二 去空格转数组，并获得最初一项的长度去空格转数组，并获得最初一项的长度，最初的一项即为最初一个单词 ...

Read N Characters Given read4 II - Call Multiple TimesAsteroid Collision留神只有正+负会相遇，负+正是反方向不相遇。辨别几种状况，正大负小，一样大，正小负大。用Stack存储，打消就pop。Max Stack1）用list模仿stack2) Double Linked List + TreeMapProduct of Array Except Self记录0的数量，和非0的其余所有数的乘积，分类探讨Design Search Autocomplete System

问题形容给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。 示例 1： 输出：[3, 2, 1]输入：1解释：第三大的数是 1 。示例 2： 输出：[1, 2]输入：2解释：第三大的数不存在, 所以返回最大的数 2 。示例 3： 输出：[2, 2, 3, 1]输入：1解释：留神，要求返回第三大的数，是指在所有不同数字中排第三大的数。此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。力扣原题目地址：https://leetcode.cn/problems/...解决方案计划一 去重并排序当前，再看是否存在第三大的数var thirdMax = function (nums) { let n = [...new Set(nums)].sort(function (a, b) { // 1. 应用Set去重，并从大到小排列 return b - a }) if (n.length >= 3) { // 2. 操作完当前，如果还有3或多项，就间接取第三大的数返回即可 return n[2] } else { // 3. 操作完当前，有可能只剩一个或者两个了，依照题意，那就间接返回最大的即可 return n[0] }};计划二 定义三个-Infinity循环比拟赋值在看下方代码之前，咱们要回顾两个常识 常识温习一：替换两个变量的值 最常见的就是定义一个长期变量temp作为替换的中转站，比方下方咱们要替换a和b的值 ...

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/can-place-flowers 假如有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会抢夺水源，两者都会死去。 给你一个整数数组  flowerbed 示意花坛，由若干 0 和 1 组成，其中 0 示意没种植花，1 示意种植了花。另有一个数 n ，是否在不突破种植规定的状况下种入 n 朵花？能则返回 true ，不能则返回 false。 示例 1： 输出：flowerbed = [1,0,0,0,1], n = 1输入：true示例 2： 输出：flowerbed = [1,0,0,0,1], n = 2输入：false提醒： 1 <= flowerbed.length <= 2 * 104flowerbed[i] 为 0 或 1flowerbed 中不存在相邻的两朵花0 <= n <= flowerbed.length 二、解题思路思路：有间断的三个0的话，两头的这个地位种上一朵花。 实现：遍历数组，判断以后元素、左侧和右侧都为0就能够种花，可种植花数加1，并将以后元素置为2，避免影响下一元素判断。当可种值花数大于n返回true。 三、解题办法3.1 Java实现public class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { if (n == 0) { return true; } int count = 0; int len = flowerbed.length; for (int i = 0; i < len; i++) { boolean left = i == 0 ? true : flowerbed[i - 1] == 0; boolean right = i == len - 1 ? true : flowerbed[i + 1] == 0; if (flowerbed[i] == 0 && left && right) { count++; flowerbed[i] = 2; if (count >= n) { return true; } } } return false; }}四、总结小记2022/7/15 养成平时记录的习惯，因为有些从天而降的想法，吃顿饭的功夫就能够遗记。

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/non-overlapping-intervals 给定一个区间的汇合 intervals ，其中 intervals[i] = [starti, endi] 。返回 须要移除区间的最小数量，使残余区间互不重叠 。 示例 1: 输出: intervals = [[1,2],[2,3],[3,4],[1,3]]输入: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。示例 2: 输出: intervals = [ [1,2], [1,2], [1,2] ]输入: 2解释: 你须要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3: 输出: intervals = [ [1,2], [2,3] ]输入: 0解释: 你不须要移除任何区间，因为它们曾经是无重叠的了。提醒: 1 <= intervals.length <= 105intervals[i].length == 2-5 104 <= starti < endi <= 5 104二、解题思路求最小的移除区间个数，等价于尽量多保留不重叠的区间。在抉择要保留区间时，区间的结尾非常重要：抉择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因而咱们采取的贪婪策略为：优先保留结尾小且不相交的区间。具体实现办法为，先把区间依照结尾的大小进行增序排序，每次抉择结尾最小且和前一个抉择的区间不重叠的区间。输出数组区间为[[1, 2], [2, 4], [1, 3]]，排序后的数组为[[1, 2], [1, 3], [2, 4]]。依照贪婪策略，首先初始化为区间[1, 2]，因为[1, 2]与[1, 3]相交，咱们跳过该区间；因为[2, 4]与[1, 2]不相交，咱们将其保留，因而最终保留的区间为[[1, 2], [2, 4]]。 ...

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/candy n 个孩子站成一排。给你一个整数数组 ratings 示意每个孩子的评分。 你须要依照以下要求，给这些孩子散发糖果： 每个孩子至多调配到 1 个糖果。相邻两个孩子评分更高的孩子会取得更多的糖果。请你给每个孩子散发糖果，计算并返回须要筹备的 起码糖果数目 。 示例 1： 输出：ratings = [1,0,2]输入：5解释：你能够别离给第一个、第二个、第三个孩子散发 2、1、2 颗糖果。示例 2： 输出：ratings = [1,2,2]输入：4解释：你能够别离给第一个、第二个、第三个孩子散发 1、2、1 颗糖果。 第三个孩子只失去 1 颗糖果，这满足题面中的两个条件。 提醒： n == ratings.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104 二、解题思路这题咱们只须要遍历2次即可：把所有孩子的糖果初始化为1；先从左往右遍历一遍，如果左边孩子的评分比右边的高，则左边孩子的糖果数更新为右边孩子的糖果数加1；再从右往左遍历一遍，如果右边孩子的评分比左边的高，且右边孩子以后的糖果数不大于左边孩子的糖果数，则右边孩子的糖果数更新为左边孩子的糖果数加1。通过两次遍历，调配的糖果就能够满足题目要求了。这里的贪婪策略即为，在每次遍历中，只思考并更新相邻一侧的大小关系。 三、解题办法3.1 Java实现public class Solution { public int candy(int[] ratings) { int size = ratings.length; if (size < 2) { return size; } int[] num = new int[size]; Arrays.fill(num, 1); for (int i = 1; i < size; i++) { if (ratings[i] > ratings[i - 1]) { num[i] = num[i - 1] + 1; } } for (int i = size - 1; i > 0; i--) { if (ratings[i] < ratings[i - 1]) { num[i - 1] = Math.max(num[i - 1], num[i] + 1); } } return Arrays.stream(num).sum(); }}四、总结小记2022/7/13 倒数3天

问题形容给你一个整数数组 nums 。如果任一值在数组中呈现 至多两次 ，返回 true ；如果数组中每个元素互不雷同，返回 false 。 示例 1： 输出：nums = [1,2,3,1]输入：true示例 2： 输出：nums = [1,2,3,4]输入：false示例 3： 输出：nums = [1,1,1,3,3,4,3,2,4,2]输入：true力扣原题目地址：https://leetcode.cn/problems/...解决方案计划一 遍历数组并应用对象记录元素之前是否呈现过思路：初始时，定义一个对象用于记录。当咱们遍历数组的时候，能够拿到数组中每一项，看看这一项在对象中是否已经呈现过，如果呈现过，就阐明和之前的反复了；如果没呈现过，阐明是新的项，就把新的项装进对象中去，期待后续持续匹配看看会不会和当下的这个反复的。代码如下： var containsDuplicate = function (nums) { let obj = {} // 1. 定义对象用于存储记录每一项是否呈现过 for (let i = 0; i < nums.length; i++) { // 2. 遍历数组进行一项一项的比拟 let key = nums[i] // 3. 拿到每一项的值 // 4. 看看此项是否在对象中。对象中是否有某个属性名key key in obj ? if (key in obj) { // 7. 将来的某一时刻，忽然呈现了，以后项之前有过 return true // 8. 就阐明有反复项，返回告知后果即可 } else { // 5. 一开始必定是没有的，所以咱就给对象记录一下 obj[key] = 1 // 6. 给对象加上一个key、value属性名属性值 } } return false};leetcode提交后果图 ...

一、题目粗心标签: 贪婪 https://leetcode.cn/problems/assign-cookies 假如你是一位很棒的家长，想要给你的孩子们一些小饼干。然而，每个孩子最多只能给一块饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，咱们能够将这个饼干 j 调配给孩子 i ，这个孩子会失去满足。你的指标是尽可能满足越多数量的孩子，并输入这个最大数值。  示例 1: 输出: g = [1,2,3], s = [1,1]输入: 1解释: 你有三个孩子和两块小饼干，3个孩子的胃口值别离是：1,2,3。尽管你有两块小饼干，因为他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输入1。示例 2: 输出: g = [1,2], s = [1,2,3]输入: 2解释: 你有两个孩子和三块小饼干，2个孩子的胃口值别离是1,2。你领有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输入2.  提醒： 1 <= g.length <= 3 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1二、解题思路应用贪婪策略是，给残余孩子里最小饥饿度的孩子调配最小的能饱腹的饼干。 三、解题办法3.1 Java实现public class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int child = 0; int cookie = 0; while (child < g.length && cookie < s.length) { if (g[child] <= s[cookie]) { child++; } cookie++; } return child; }}四、总结小记2202/7/12 明天能把《富人思维》这本书看完

leetcode 2320. Count Number of Ways to Place Houses原题形容There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed. Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10^9 + 7.Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.Example 1: ...

D139 38. Count and Say题目链接38. Count and Say 题目剖析这道题有点裴波那切数列： 先从数字数字1开始，因为有1个1，所以记作”11“；第二个呢，就把下面的”11“，再”转换“成文字，即：两个1，记作”21“；如此类推上来，第三个就是1个2，1个1，记作”1211“；持续，1个1，1个2，2个1，111221；持续，3个1，2个2，1个1，312211；持续，13112221；持续，1113213111；至此应该了解了吧？ 为说像什么裴波那切数列呢，因为下一个的后果和上一个的后果是无关的。 题目会给一个数字n，要返回第n个的数字对应的读法。即，下面的列表序号是n，要返回”记作“的局部。 解题思路既然像裴波那切数列，那就得须要用到递归了。 递归套娃有两个特点不能遗记：善始善终 有始就是本人调本人，要在本人的娃外面再放个一样的娃有终就是要有终止条件，套到最小的娃之后再也套不上来了终止条件须要先写，要不然就有限套娃了。 他给定了一个数字n后，咱们须要晓得前一个数字是什么，所以咱们须要先本人调用本人。调用本人的时候参数就须要n-1。 如果传入的是数字1，那么咱们要返回的就是数字1，或者字符串1。因为咱们还没有解决数字对应的念法，因而不能返回”1个1"对应的数字”11“。 好了，拿到数字1之后要失去它的念法，就须要晓得元素个数和元素内容。遍历是跑不掉的了。 如果以后数字和前一个数字雷同，那么咱们要计数。 当和后面的数字不同时，完结计数，并把念法拼接到最终念法的开端中。 因为第一个数字并没有”前一个数字“，因而先记为NULL。只有以后一个数字不是NULL时，才把念法拼接到最终念法的开端。 最终代码<?phpclass Solution { /** * @param Integer $n * @return String */ function countAndSay($n) { if($n == 1){ return '1'; } $str = $this->countAndSay($n-1); $arr = str_split($str); $counts = []; $prev = NULL; $count = 0; foreach($arr as $key => $val){ if($val == $prev){ $count++; } else{ if(!is_null($prev)){ $counts[] = $count.$prev; } $prev = $val; $count = 1; } } $counts[] = $count.$prev; return implode($counts); }}若感觉本文章对你有用，欢送用爱发电赞助。 ...

一、题目粗心标签: 分治 https://leetcode.cn/problems/burst-balloons 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 当初要求你戳破所有的气球。戳破第 i 个气球，你能够取得 nums[i - 1] nums[i] nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。 求所能取得硬币的最大数量。 示例 1： 输出：nums = [3,1,5,8]输入：167解释：nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []coins = 315 + 358 + 138 + 181 = 167示例 2： 输出：nums = [1,5]输入：10提醒： n == nums.length1 <= n <= 3000 <= nums[i] <= 100 ...

一、题目粗心标签: 分治 https://leetcode.cn/problems/beautiful-array 对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得： 对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。 那么数组 A 是丑陋数组。 给定 N，返回任意丑陋数组 A（保障存在一个）。 示例 1： 输出：4输入：[2,1,4,3]示例 2： 输出：5输入：[3,1,2,5,4]提醒： 1 <= N <= 1000 二、解题思路题解参考：https://www.cnblogs.com/grandyang/p/12287146.html分治法，按奇偶来分的话，因为奇数加偶数等于奇数，就不会是任何一个数字的2倍了。这就是奇偶分堆的益处，这时任意两个数字必定不能别离从奇偶堆里取了，那可能你会问，奇数堆会不会有三个奇数突破这个规定呢？只有这个奇数堆是从一个丑陋数组按固定的规定变动而来的，就能保障肯定也是丑陋数组，因为对于任意一个丑陋数组，若对每个数字都加上一个雷同的数字，或者都乘上一个雷同的数字，则肯定还是丑陋数组，因为数字的之间的外在关系并没有扭转。明确了下面这些，根本就能够解题了，假如此时曾经有了一个长度为n的丑陋数组，如何将其扩充呢？能够将其中每个数字都乘以2并加1，就都会变成奇数，并且这个奇数数组还是丑陋的，而后再将每个数字都乘以2，那么都会变成偶数，并且这个偶数数组还是丑陋的，两个数组拼接起来，就会失去一个长度为 2n 的丑陋数组。就是这种思路，能够从1开始，1自身就是一个丑陋数组，而后将其扩充，留神这里要卡一个N，不能让扩充的数组长度超过N，只有在变为奇数和偶数时加个断定就行了，将不大于N的数组退出到新的数组中 三、解题办法3.1 Java实现public class Solution { public int[] beautifulArray(int n) { List<Integer> ans = new ArrayList<>(); ans.add(1); while (ans.size() < n) { List<Integer> t = new ArrayList<>(); for (int num : ans) { if (num * 2 - 1 <= n) { t.add(num * 2 - 1); } } for (int num : ans) { if (num * 2 <= n) { t.add(num * 2); } } ans = t; } return ans.stream() .mapToInt(Integer::intValue) .toArray(); }}四、总结小记2022/7/9 洗衣服涤不干会有味

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（264）丑数 II一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1：“本人。三指针法”。// 想法：// 因为每个数字都要被计算三次，一次是乘以2，一次是乘以3，一次是乘以5，// 所以定义三个指针 —— index_2、index_3、index_5。// 这三个指针的终点是一样的，都是0，// 如果以后的数字是乘以2失去的，就将 index_2 向后挪动，// 如果以后的是乘以3失去的，就将 index_3 向后挪动，// 如果以后的是乘以5失去的，就将 index_5 向后挪动。// 思路：// 1）状态初始化：resList = [1], index_2 = 0, index_3 = 0, index_5 = 0; 。// 2）外围：循环解决，条件为 resList.length < n 。// 2.1）求得下一个丑数 temp = Math.min(resList[index_2] * 2, resList[index_3] * 3, resList[index_5] * 5) 。// 2.2）看以后丑数是乘哪个数失去的，那么对应的指针就向后挪动。// 2.3）将以后丑数塞到 数组 resList 里。// 3）返回后果 resList[n-1] 。var nthUglyNumber = function(n) { // 1）状态初始化：resList = [1], index_2 = 0, index_3 = 0, index_5 = 0; 。 let resList = [1], index_2 = 0, index_3 = 0, index_5 = 0; // 2）外围：循环解决，条件为 resList.length < n 。 while(resList.length < n){ // 2.1）求得下一个丑数 temp = Math.min(resList[index_2] * 2, resList[index_3] * 3, resList[index_5] * 5) 。 let temp = Math.min(resList[index_2] * 2, resList[index_3] * 3, resList[index_5] * 5); // 能够用 switch 代替 3个if语句、显得逼格高。不晓得为啥行不通 很奇怪！！ // switch(temp){ // case resList[index_2] * 2: // index_2++; // break; // case resList[index_3] * 3: // index_3++; // break; // case resList[index_5] * 5: // index_5++; // break; // } // 2.2）看以后丑数是乘哪个数失去的，那么对应的指针就向后挪动。 if(temp === resList[index_2] * 2){ index_2++; } if(temp === resList[index_3] * 3){ index_3++; } if(temp === resList[index_5] * 5){ index_5++; } // 2.3）将以后丑数塞到 数组 resList 里。 resList.push(temp); } // 3）返回后果 resList[n-1] 。 return resList[n-1];};2 计划21)代码： ...

题目形容给定一个数组 nums，编写一个函数将所有 0 挪动到数组的开端，同时放弃非零元素的绝对程序。 请留神 ，必须在不复制数组的状况下原地对数组进行操作。 示例 1: 输出: nums = [0,1,0,3,12]输入: [1,3,12,0,0]示例 2: 输出: nums = [0]输入: [0]力扣原题目地址：https://leetcode.cn/problems/...思路剖析解法一 遍历统计0呈现了几次并删除之，最初依据0呈现的次数往尾部追加0var moveZeroes = function (nums) { let count = 0 // 1. 定义一个变量，用来统计0呈现的次数 for (let i = 0; i < nums.length; i++) { // 2. 遍历这个数组，看看0呈现了几次 if (nums[i] == 0) { // 3. 如果遇到的不是0，不做任何操作；如果遇到0了，就把0删掉 nums.splice(i, 1) // 4. 把遇到的这一项（0）给删除掉 i-- // 5. 留神 数组塌陷，索引对立往前平移一位 count = count + 1 // 6. 而后统计一下0呈现的次数 } } for (let i = 0; i < count; i++) { // 7. 依据0呈现的次数，决定往数组的尾部追加几个0 nums.push(0) // 8. 呈现了几个0，最初就追加几个0, }};这种形式，须要遍历两次，咱们遍历一次也是能够解决的，思路略有类似。如下代码 ...

一、题目粗心标签: 分治 https://leetcode.cn/problems/different-ways-to-add-parentheses 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的后果。你能够 按任意程序 返回答案。 生成的测试用例满足其对应输入值合乎 32 位整数范畴，不同后果的数量不超过 104 。 示例 1： 输出：expression = "2-1-1"输入：[0,2]解释：((2-1)-1) = 0 (2-(1-1)) = 2示例 2： 输出：expression = "23-45"输入：[-34,-14,-10,-10,10]解释：(2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10提醒： 1 <= expression.length <= 20expression 由数字和算符 '+'、'-' 和 '*' 组成。输出表达式中的所有整数值在范畴 [0, 99] 二、解题思路题目中的例子1，input 是 "2-1-1" 时，就有两种状况了，(2-1)-1 和 2-(1-1)，因为括号的不同，失去的后果也不同，但如果咱们把括号里的货色当作一个黑箱的话，那么其就变为 ()-1 和 2-()，其最终的后果跟括号内可能失去的值是非亲非故的，那么再 general 一点，实际上就能够变成 () ? () 这种模式，两个括号内别离是各自的表达式，最终会别离计算失去两个整型数组，两头的问号示意运算符，能够是加，减，或乘。那么问题就变成了从两个数组中任意选两个数字进行运算，霎时变成咱们会做的题目了有木有？而这种左右两个括号代表的黑盒子就交给递归去计算，像这种分成左右两坨的 pattern 就是赫赫有名的分治法 Divide and Conquer 了，是必须要把握的一个神器。 ...

题目形容给定两个数组 nums1 和 nums2 ，返回 它们的交加 。输入后果中的每个元素肯定是 惟一 的。咱们能够 不思考输入后果的程序 。 示例 1： 输出：nums1 = [1,2,2,1], nums2 = [2,2]输入：[2]示例 2： 输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输入：[9,4]解释：[4,9] 也是可通过的力扣原题目地址：https://leetcode.cn/problems/...思路剖析计划一 循环一个数组失去每一项值，判断另一个数组中有没有这个值var intersection = function (nums11, nums22) { let nums1 = [...new Set(nums11)] // 1. 两个数组别离去重 let nums2 = [...new Set(nums22)] // 2. 不去重就反复比拟判断了，会节约性能 let arr = [] // 3. 定义一个数组用来存储两个数组的交加 for (let i = 0; i < nums1.length; i++) { if (nums2.indexOf(nums1[i]) > -1) { // 4. 看看一个数组中的一项一项的值，在另一个数组中有没有，当然这里也能够应用includes办法 arr.push(nums1[i]) // 5. 有的话，就阐明是两个数组共有的项，即为 交加 } } return arr // 6. 最初返回即可};计划二 两个数组去重当前再合并，而后统计，每一项呈现的次数，呈现次数为两次的即为交加应用对象统计次数写法： ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/maximum-subarray 给你一个整数数组 nums ，请你找出一个具备最大和的间断子数组（子数组起码蕴含一个元素），返回其最大和。 子数组 是数组中的一个间断局部。 示例 1： 输出：nums = [-2,1,-3,4,-1,2,1,-5,4]输入：6解释：间断子数组 [4,-1,2,1] 的和最大，为 6 。示例 2： 输出：nums = [1]输入：1示例 3： 输出：nums = [5,4,-1,7,8]输入：23提醒： 1 <= nums.length <= 105-104 <= nums[i] <= 104进阶：如果你曾经实现复杂度为 O(n) 的解法，尝试应用更为精妙的 分治法 求解。 二、解题思路定义一个max保留遍历过程中呈现的最大子数组和，也是返回后果，定义一个dp[i]，用来示意以第i个元素为结尾的数组的最大数组和。状态转移方程为：dp[i] = max(dp[i-1]+nums[i], nums[i]) 三、解题办法3.1 Java实现public class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; int max = dp[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); max = Math.max(dp[i], max); } return max; }}四、总结小记2022/7/6 程序员是不是也有“文人相轻”的故障

leetcode 2320. Count Number of Ways to Place Houses（python）原题形容There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed. Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10^9 + 7.Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.Example 1: ...

题目形容给定一个字符串 s ，你须要反转字符串中每个单词的字符程序，同时仍保留空格和单词的初始程序。 示例 1： 输出：s = "Let's take LeetCode contest"输入："s'teL ekat edoCteeL tsetnoc"示例 2: 输出： s = "God Ding"输入："doG gniD"力扣原题目地址：https://leetcode.cn/problems/...思路剖析解法一 字符串转数组反转再转字符串这种形式可读性能够，即先把字符串以空格为宰割转换成数组，而后map循环把数组中的每一项（字符串），再转成一个个的小数组反转再转回来即可。代码如下： let s = "abc fgg kks"var reverseWords = function (s) { let arr = s.split(' ') // 此时arr为： ['abc', 'fgg', 'kks'] arr = arr.map((item) => { return item.split('').reverse().join('') // 把每一项字符串转成数组，在反转颠倒，再转回字符串 }) // map循环加工当前的arr为： ['cba', 'ggf', 'skk'] return arr.join(' ') // 最终变成：'cba ggf skk'};解法二 顺叙遍历分堆数组头部追加思路： 比方：let s = "abc fgg kks"，当咱们顺叙遍历的时候，就会失去'k','k','s',' ','g','g','f',' ','c','b','a'，此时咱们发现，反转确实是反转了，不过地位也反转了。 ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/regular-expression-matching 给你一个字符串 s 和一个字符法则 p，请你来实现一个反对 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符'*' 匹配零个或多个后面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是局部字符串。 示例 1： 输出：s = "aa", p = "a"输入：false解释："a" 无奈匹配 "aa" 整个字符串。示例 2: 输出：s = "aa", p = "a*"输入：true解释：因为 '*' 代表能够匹配零个或多个后面的那一个元素, 在这里后面的元素就是 'a'。因而，字符串 "aa" 可被视为 'a' 反复了一次。示例 3： 输出：s = "ab", p = ".*"输入：true解释："." 示意可匹配零个或多个（''）任意字符（'.'）。  提醒： 1 <= s.length <= 201 <= p.length <= 30s 只蕴含从 a-z 的小写字母。p 只蕴含从 a-z 的小写字母，以及字符 . 和 *。保障每次呈现字符 * 时，后面都匹配到无效的字符 二、解题思路定义一个二维数组dp，其中dpi示意字符串s的子串s[0, i]是否能够被字符串p的子串p[0,j]匹配，依据正则表达式的不同状况，即星号、点号、非星号点号的字符，咱们能够分状况探讨来更新dp数组。 三、解题办法3.1 Java实现public class Solution2 { public boolean isMatch(String s, String p) { int m = s.length(); int n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int i = 1; i < n + 1; i++) { if (p.charAt(i - 1) == '*') { // 星号 不会在第1个地位 dp[0][i] = dp[0][i - 2]; } } for (int i = 1; i < m + 1; i++) { for (int j = 1; j < n + 1; j++) { // 上个通配符可能是 点号、星号、字符 if (p.charAt(j - 1) == '.') { // 上个通配符是 点号 dp[i][j] = dp[i - 1][j - 1]; } else if (p.charAt(j - 1) != '*') { // 上个通配符不是 星号 dp[i][j] = dp[i - 1][j - 1] && p.charAt(j - 1) == s.charAt(i - 1); } else if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') { dp[i][j] = dp[i][j - 2]; } else { dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i][j - 2]; } } } return dp[m][n]; }}四、总结小记2022/7/5 上行下效，皇帝的新装

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/edit-distance 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所应用的起码操作数  。 你能够对一个单词进行如下三种操作： 插入一个字符删除一个字符替换一个字符 示例 1： 输出：word1 = "horse", word2 = "ros"输入：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2： 输出：word1 = "intention", word2 = "execution"输入：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u') 提醒： 0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成 ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock 给定一个数组 prices ，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。 你只能抉择 某一天 买入这只股票，并抉择在 将来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输出：[7,1,5,3,6,4]输入：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。示例 2： 输出：prices = [7,6,4,3,1]输入：0解释：在这种状况下, 没有交易实现, 所以最大利润为 0。提醒： 1 <= prices.length <= 1050 <= prices[i] <= 104二、解题思路遍历一次数组，在每个地位i时，记录i地位之前所有价格中的最低价格，而后将以后价格作为售出价格，查看以后收益是不是最大收益即可。 三、解题办法3.1 Java实现public class Solution { public int maxProfit(int[] prices) { // 记录i地位之前所有价格中的最低价格 int buy = prices[0]; // 以后最大利润 int profit = 0; for (int i = 1; i < prices.length; i++) { buy = Math.min(buy, prices[i]); profit = Math.max(profit, prices[i] - buy); } return profit; }}四、总结小记2022/7/3 接下来几天都有雨

题目形容给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1: 输出: nums = [-1,0,3,5,9,12], target = 9输入: 4解释: 9 呈现在 nums 中并且下标为 4示例 2: 输出: nums = [-1,0,3,5,9,12], target = 2输入: -1解释: 2 不存在 nums 中因而返回 -1力扣原题目地址：https://leetcode.cn/problems/...解法一，应用数组原生办法indexOfvar search = function (nums, target) { return nums.indexOf(target)};数组的原生办法，应用真不便。不过有时候须要多拓展一些解决问题的形式，当前遇到需要时，大有裨益 解法二，循环所有判断是否等于目标值var search = function (nums, target) { let whichIndex = -1 for (let i = 0; i < nums.length; i++) { if (nums[i] == target) { whichIndex = i return whichIndex } } return whichIndex};假如咱们要找的值，就是正好在最初一个地位，那么就得把整个循环全副走一遍，能力找到咱们所要找的那个数值。所以工夫复杂度就是O(n)。为了进一步晋升效率，缩小用时，所以二分法解题的形式就应运而生 ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/2-keys-keyboard 最后记事本上只有一个字符 'A' 。你每次能够对这个记事本进行两种操作： Copy All（复制全副）：复制这个记事本中的所有字符（不容许仅复制局部字符）。Paste（粘贴）：粘贴 上一次 复制的字符。给你一个数字 n ，你须要应用起码的操作次数，在记事本上输入 恰好 n 个 'A' 。返回可能打印出 n 个 'A' 的起码操作次数。 示例 1： 输出：3输入：3解释：最后, 只有一个字符 'A'。第 1 步, 应用 Copy All 操作。第 2 步, 应用 Paste 操作来取得 'AA'。第 3 步, 应用 Paste 操作来取得 'AAA'。示例 2： 输出：n = 1输入：0提醒： 1 <= n <= 1000 二、解题思路还是动静布局，这里须要乘除法来计算地位，因为粘贴操作是位数减少的。咱们应用一个一维数组dp，其中地位i示意延展到长度i的起码操作次数。对于每个地位j，如果j能够被i整除，那么长度i就能够由长度j操作失去，其操作次数等价于把一个长度为1的A延展到长度为i/j。因而咱们能够失去递推公式dp[i] = dp[j] + dp[i/j]。 三、解题办法3.1 Java实现public class Solution { public int minSteps(int n) { int[] dp = new int[n + 1]; int h = n * n; for (int i = 2; i <= n; i++) { dp[i] = i; for (int j = 2; j <= h; j++) { if (i % j == 0) { dp[i] = dp[j] + dp[i / j]; break; } } } return dp[n]; }}四、总结小记2022/7/2 期待7月11号

题目形容在一个数组 nums 中除一个数字只呈现一次之外，其余数字都呈现了三次。请找出那个只呈现一次的数字。 示例 1： 输出： nums = [3,4,3,3]输入： 4示例 2： 输出： nums = [9,1,7,9,7,9,7]输入： 1思路剖析应用对象统计数字呈现的次数思路分两步： 第一步，统计值呈现的次数第二步，看看谁呈现的次数是一次var singleNumber = function (nums) { /** 第一步 统计值呈现的次数 */ let obj = {} // 1. 定义一个对象用来存储 '谁' 呈现了 '几次' for (let i = 0; i < nums.length; i++) { if (nums[i] in obj) { // 2. 若对象中有，就把对应次数加一，当然一开始是没有的 obj[nums[i]] = obj[nums[i]] + 1 // 4. 比方{9:1} 变成了 {9:2} 由原来的一次，变成两次了 } else { obj[nums[i]] = 1 // 3. 原本是空对象，当初变成{9:1} 后续若还呈现9 就次数加一，变成{9:2} } } /** 第二步，看看谁呈现的次数是一次 */ for (const key in obj) { if (obj[key] == 1) { return key } }};留神obj计数：咱们以nums = [3,4,3,3]为例，那么obj就变成了{3:3,4:1} ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/coin-change 给你一个整数数组 coins ，示意不同面额的硬币；以及一个整数 amount ，示意总金额。 计算并返回能够凑成总金额所需的 起码的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你能够认为每种硬币的数量是有限的。 示例 1： 输出：coins = [1, 2, 5], amount = 11输入：3 解释：11 = 5 + 5 + 1示例 2： 输出：coins = [2], amount = 3输入：-1示例 3： 输出：coins = [1], amount = 0输入：0提醒： 1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104 二、解题思路每个硬币能够用有限屡次，所以是齐全背包问题。dp[i]示意，达到总金额i所需的起码硬币数，因为求起码硬币数所以先将dp初始化为amount+2，状态转移方程为：dp[i] = min(dp[i], dp[i-coin] + 1) 三、解题办法3.1 Java实现public class Solution { public int coinChange(int[] coins, int amount) { if (coins.length == 0) { return -1; } int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 2); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] == amount + 2 ? -1 : dp[amount]; }}四、总结小记2022/7/1 周五了，明天是个承前启后的日子

D138 35. Search Insert Position题目链接35. Search Insert Position 题目剖析给定一个有序数组和一个数字，返回这个数字呈现的地位。如果这个数字没有呈现，那么返回这个数字本该呈现的地位。 解题思路这题也很简略，一一遍历，直到前面的数字大于给定的数字就能够了。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer */ function searchInsert($nums, $target) { foreach($nums as $index => $num){ if($num == $target){ return $index; } if($num > $target){ return max(0,$index); } } return $index+1; }}若感觉本文章对你有用，欢送用爱发电赞助。

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/partition-equal-subset-sum 给你一个 只蕴含正整数 的 非空 数组 nums 。请你判断是否能够将这个数组宰割成两个子集，使得两个子集的元素和相等。 示例 1： 输出：nums = [1,5,11,5]输入：true解释：数组能够宰割成 [1, 5, 5] 和 [11] 。示例 2： 输出：nums = [1,2,3,5]输入：false解释：数组不能宰割成两个元素和相等的子集。 提醒： 1 <= nums.length <= 2001 <= nums[i] <= 100二、解题思路设所有数字和为sum，咱们的指标是选取一个子数组，使它的总和为sum/2，定义二维boolean数组dpi，其意义是应用前i个数字的和能不能形成整数j。咱们须要把每个地位都进行遍历，同时也要对0-target之间的所有负数进行遍历。状态转移方程是，遍历到i地位时能不能形成target=后面的数字的和能形成target||后面的数字能形成target-nums[i]。这两个状态别离是选不选取nums[i]的两种状况，如果有一种状况成立即可：dpi = dpi-1 || dpi-1] 三、解题办法3.1 Java实现public class Solution { public boolean canPartition(int[] nums) { // 数组求和 int sum = Arrays.stream(nums).sum(); // 场景1：和为奇数不能均分 if (sum % 2 == 1) { return false; } int target = sum / 2; int n = nums.length; boolean[][] dp = new boolean[n + 1][target + 1]; dp[0][0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j <= target; j++) { if (j < nums[i - 1]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]; } } } return dp[n][target]; }}四、总结小记2022/6/29 期待7.5号

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/longest-common-subsequence 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不扭转字符的绝对程序的状况下删除某些字符（也能够不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所独特领有的子序列。 示例 1： 输出：text1 = "abcde", text2 = "ace" 输入：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2： 输出：text1 = "abc", text2 = "abc"输入：3解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3： 输出：text1 = "abc", text2 = "def"输入：0解释：两个字符串没有公共子序列，返回 0 。提醒： 1 <= text1.length, text2.length <= 1000text1 和 text2 仅由小写英文字符组成。 二、解题思路应用动静布局来解决本题，定义一个二维数组dp，其中dpi示意到第一个字符串地位i为止、到第二个字符串地位j为止、最长的公共子序列长度。这样一来咱们就能够很不便地分状况探讨这两个地位对应的字母雷同中与不同的状况了。 三、解题办法3.1 Java实现public class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); // 示意到第一个字符串地位i为止、到第二个字符串地位j为止、最长的公共子序列长度 int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i < m + 1; i++) { for (int j = 1; j < n + 1; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }}四、总结小记2022/6/26 今天周一，持续加油

一、题目粗心标签: 动静布局https://leetcode.cn/problems/longest-increasing-subsequence 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不扭转其余元素的程序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1： 输出：nums = [10,9,2,5,3,7,101,18]输入：4解释：最长递增子序列是 [2,3,7,101]，因而长度为 4 。示例 2： 输出：nums = [0,1,0,3,2,3]输入：4示例 3： 输出：nums = [7,7,7,7,7,7,7]输入：1提醒： 1 <= nums.length <= 2500-104 <= nums[i] <= 104进阶： 你能将算法的工夫复杂度升高到 O(n log(n)) 吗? 二、解题思路核心思想是应用一个数组dp来保留，dp[i]的意义是到该地位为止的最长递增子序列。最初求所有地位的最大值，而不是dp的最初元素。 三、解题办法3.1 Java实现public class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; if (n <= 1) { return n; } int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; } int ret = dp[0]; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } ret = Math.max(dp[i], ret); } return ret; }}四、总结小记2022/6/25 明后两天大到爆雨

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（剑指 Offer II 091）粉刷房子一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。动静规划法”。// 用时：10：47 - 10：57。// 想法：// 1）“题干有最字眼，优先思考动静布局”。// 2）状态定义：dp[i][j] —— 以房子i结尾 且 其刷成色彩j 的最低价格。// 3）状态转移：dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);// i的范畴：[1, l - 1]，j的范畴：[0, 2]，j与k的关系 j !== k 。// 思路：// 1）状态初始化：l = costs.length;// dp = new Array(l).fill(0).map(v => new Array(3).fill(Number.POSITIVE_INFINITY));// dp[0] = costs[0]; 。// 2）外围：状态转移：dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);// i的范畴：[1, l - 1]，j的范畴：[0, 2]，j与k的关系 j !== k 。// 3）返回后果：Math.min(...dp[l - 1]); 。var minCost = function(costs) { // 1）状态初始化：l = costs.length; // dp = new Array(l).fill(0).map(v => new Array(3).fill(Number.POSITIVE_INFINITY)); // dp[0] = costs[0]; 。 const l = costs.length; let dp = new Array(l).fill(0).map(v => new Array(3).fill(Number.POSITIVE_INFINITY)); dp[0] = costs[0]; // 2）外围：状态转移：dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]); // i的范畴：[1, l - 1]，j的范畴：[0, 2]，j与k的关系 j !== k 。 for (let i = 1; i < l; i++) { // 注：如下6行代码等价于如下 // for (let j = 0; j <= 2; j++) { // for (let k = 0; k <= 2; k++) { // if (j !== k) { // dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]); // } // } // } dp[i][0] = Math.min(dp[i][0], dp[i - 1][1] + costs[i][0]); dp[i][0] = Math.min(dp[i][0], dp[i - 1][2] + costs[i][0]); dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + costs[i][1]); dp[i][1] = Math.min(dp[i][1], dp[i - 1][2] + costs[i][1]); dp[i][2] = Math.min(dp[i][2], dp[i - 1][0] + costs[i][2]); dp[i][2] = Math.min(dp[i][2], dp[i - 1][1] + costs[i][2]); } // 3）返回后果：Math.min(...dp[l - 1]); 。 return Math.min(...dp[l - 1]);};2 计划21)代码： ...

引言原文地址:优雅地翻转数组 欢送拜访我的博客: http://blog.duhbb.com/ 感觉本人的代码写的不简洁, 而且容易出错, 搞得每次都很赶一样. 翻转的写法题目很简略, 然而有个中央能够学习下: 就是数组翻转. 之前我喜爱这么写: for (int k = j; k <= (i+j)/2; k++) { char tmp = s[k]; s[k] = s[i - (k - j)]; s[i-(k-j)] = tmp;}明天看了 leetcode 上的解答, 原来这么写更优雅, for 循环写的看上去就比较复杂, 还容易出错. int left = start, right = i - 1;while (left < right) { swap(s[left], s[right]); left++; right--;}#include <iostream>#include <vector>#include <climits>#include <bits/stdc++.h>using namespace std;class Solution {public: string reverseWords(string s) { int i = 0, j = 0; while(true) { while (s[i+1] != ' ' && s[i+1] != '\0') { i++; } // 这个 for 循环写的就很丑, 而且还容易出错 for (int k = j; k <= (i+j)/2; k++) { char tmp = s[k]; s[k] = s[i - (k - j)]; s[i-(k-j)] = tmp; } if (! s[i+1]) { break; } i += 2; j = i; } return s; }};int main() { Solution s; cout << s.reverseWords("hello world") << endl; return 0;}结束语原文地址:优雅地翻转数组 ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/word-break 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否能够利用字典中呈现的单词拼接出 s 。 留神：不要求字典中呈现的单词全副都应用，并且字典中的单词能够重复使用。 示例 1： 输出: s = "leetcode", wordDict = ["leet", "code"]输入: true解释: 返回 true 因为 "leetcode" 能够由 "leet" 和 "code" 拼接成。示例 2： 输出: s = "applepenapple", wordDict = ["apple", "pen"]输入: true解释: 返回 true 因为 "applepenapple" 能够由 "apple" "pen" "apple" 拼接成。  留神，你能够重复使用字典中的单词。示例 3： 输出: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输入: false提醒： 1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s 和 wordDict[i] 仅有小写英文字母组成wordDict 中的所有字符串 互不雷同 ...

一、题目粗心标签: 动静布局https://leetcode.cn/problems/decode-ways 一条蕴含字母 A-Z 的音讯通过以下映射进行了 编码 ： 'A' -> "1"'B' -> "2"...'Z' -> "26"要 解码 已编码的音讯，所有数字必须基于上述映射的办法，反向映射回字母（可能有多种办法）。例如，"11106" 能够映射为： "AAJF" ，将音讯分组为 (1 1 10 6)"KJF" ，将音讯分组为 (11 10 6)留神，音讯不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是因为 "6" 和 "06" 在映射中并不等价。 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 办法的 总数 。 题目数据保障答案必定是一个 32 位 的整数。 示例 1： 输出：s = "12"输入：2解释：它能够解码为 "AB"（1 2）或者 "L"（12）。示例 2： 输出：s = "226"输入：3解释：它能够解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。示例 3： ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/perfect-squares 给你一个整数 n ，返回 和为 n 的齐全平方数的起码数量 。 齐全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是齐全平方数，而 3 和 11 不是。 示例 1： 输出：n = 12输入：3 解释：12 = 4 + 4 + 4示例 2： 输出：n = 13输入：2解释：13 = 4 + 9提醒：1 <= n <= 104 二、解题思路动静布局，dp[i]示意i有几个齐全平方数的加和形成，枚举比i小的齐全平方数，状态转移方程为dp[i] = min(dp[i-k] + 1) ，k就是齐全平方数 三、解题办法3.1 Java实现class Solution { public int numSquares(int n) { // 找小于n的齐全平方数 List<Integer> squares = new ArrayList<>(); for (int i = 1; i < n + 1; i++) { int tmp = i * i; if (tmp < n + 1) { squares.add(tmp); } else { break; } } int[] dp = new int[n + 1]; for (int i = 1; i < n + 1; i++) { dp[i] = Integer.MAX_VALUE; } for (int i = 1; i < n + 1; i++) { for (int square : squares) { if (i < square) { break; } dp[i] = Math.min(dp[i], dp[i - square] + 1); } } return dp[n]; }}四、总结小记2022/6/21 保持每天一道leetcode，养成一个习惯

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/maximal-square 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只蕴含 '1' 的最大正方形，并返回其面积。示例 1： 输出：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输入：4示例 2： 输出：matrix = [["0","1"],["1","0"]]输入：1示例 3： 输出：matrix = [["0"]]输入：0提醒： m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrixi 为 '0' 或 '1' 二、解题思路应用动静布局来解决，应用dpi示意以(i,j)为右下角，且只饮食1的正方形的边长最大值。如果咱们能计算出所有dpi的值，那么其中的最大值即为矩阵中只饮食1的下方形的边长最大值，其平方即为最大下方形的面积。如何计算dp中每个元素的值：若该地位的值为0，则dpi=0，因为以后地位不可能在由1组成的正方形中若该地位的值为1，则dpi的值由其上方、左方和左上方的三个相邻地位的dp值决定，具体就是以后地位的元素值等于三个相邻的元素中的最小值加1，其状态方程如下：dpi = min(dpi-1, dpi-1, dpi) + 1 三、解题办法3.1 Java实现public class Solution { public int maximalSquare(char[][] matrix) { int maxSize = 0; int rows = matrix.length; int columns = matrix[0].length; int[][] dp = new int[rows][columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (matrix[i][j] == '1') { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]); dp[i][j] = Math.min(dp[i][j-1], dp[i][j]) + 1; } maxSize = Math.max(maxSize, dp[i][j]); } } } return maxSize * maxSize; }}四、总结小记2022/6/20 倒计时14天

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/01-matrix 给定一个由 0 和 1 组成的矩阵 mat ，请输入一个大小雷同的矩阵，其中每一个格子是 mat 中对应地位元素到最近的 0 的间隔。 两个相邻元素间的间隔为 1 。示例 1： 输出：mat = [[0,0,0],[0,1,0],[0,0,0]]输入：[[0,0,0],[0,1,0],[0,0,0]]示例 2： 输出：mat = [[0,0,0],[0,1,0],[1,1,1]]输入：[[0,0,0],[0,1,0],[1,2,1]]提醒： m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mati is either 0 or 1.mat 中至多有一个 0  二、解题思路判断应用动静布局思路解决问题，先定义一个数组dp[][]来，找到状态转移方程式。本题须要从左上开始搜寻一次，右下开始搜寻一次。 三、解题办法3.1 Java实现public class Solution { public int[][] updateMatrix(int[][] mat) { int n = mat.length; int m = mat[0].length; int[][] dp = new int[n][m]; // mat[i][j] == 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i+1][j], dp[i][j+1]) // mat[i][j] == 0, dp[i][j] = 0 // 将dp中的值置为最大 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = Integer.MAX_VALUE - 1; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 0) { dp[i][j] = 0; } else { if (j > 0) { dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1); } if (i > 0) { dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1); } } } } for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { if (mat[i][j] != 0) { if (j < m - 1) { dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1); } if (i < n - 1) { dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1); } } } } return dp; }}四、总结小记2022/6/19 夏至未到，温度曾经到了；波及到数组问题行列老是搞混

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（508）呈现次数最多的子树元素和一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。后续遍历法”。// 用时：14分钟。// 思路：// 1）状态初始化：resMap = new Map() 。// 2）调用递归函数 updateRootValByDfs(root) 。// 3）求得 呈现次数最多的子树元素和 resMaxCount = getMaxCountByMap(resMap) 。// 4）若 以后值（即 key ）呈现的次数 val 与 resMaxCount，// 则 将 val 放入 resList 中。// 5）返回后果 resList 。var findFrequentTreeSum = function(root) { const updateRootValByDfs = (curRoot = null) => { // 1）递归进口 if (!curRoot) { return; } const {left, right} = curRoot; if (!left && !right) { if (resMap.has(curRoot.val)) { resMap.set(curRoot.val, resMap.get(curRoot.val) + 1); } else { resMap.set(curRoot.val, 1); } return; } // 2）递归主体 // 2.1）先更新 left 节点上的 val 。 updateRootValByDfs(left); // 2.2）接着更新 right 节点上的 val 。 updateRootValByDfs(right); // 2.3）最初更新 curRoot 节点上的 val 。 if (left) { curRoot.val += (left.val); } if (right) { curRoot.val += (right.val); } if (resMap.has(curRoot.val)) { resMap.set(curRoot.val, resMap.get(curRoot.val) + 1); } else { resMap.set(curRoot.val, 1); } }; const getMaxCountByMap = (map = new Map()) => { let resMaxCount = Number.NEGATIVE_INFINITY; for (const [key, val] of map) { resMaxCount = Math.max(resMaxCount, val); } return resMaxCount; }; // 边界（依据提醒，如下代码可疏忽） if (!root) { return []; } // 1）状态初始化：resMap = new Map() 。 let resMap = new Map(); // 2）调用递归函数 updateRootValByDfs(root) 。 updateRootValByDfs(root); // 3）求得 呈现次数最多的子树元素和 resMaxCount = getMaxCountByMap(resMap) 。 let resMaxCount = getMaxCountByMap(resMap), resList = []; // 4）若 以后值（即 key ）呈现的次数 val 与 resMaxCount， // 则 将 val 放入 resList 中。 for (const [key, val] of resMap) { if (val === resMaxCount) { resList.push(key); } } // 5）返回后果 resList 。 return resList;};2 计划21)代码： ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/minimum-path-sum 给定一个蕴含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的门路，使得门路上的数字总和为最小。 阐明：每次只能向下或者向右挪动一步。 示例 1： 输出：grid = [[1,3,1],[1,5,1],[4,2,1]]输入：7解释：因为门路 1→3→1→1→1 的总和最小。示例 2： 输出：grid = [[1,2,3],[4,5,6]]输入：12提醒： m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= gridi <= 100二、解题思路二维的动静规定，定义一个二维dp数组，其中dpi示意从左上角开始到(i, j)地位的最优门路的数字和。因为每次只能向下或者向右挪动，咱们能够失去状态转移方程dpi = min(dpi-1, dpi) + gridi。 三、解题办法3.1 Java实现public class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; // dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] dp[0][0] = grid[0][0]; for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { if (x == 0 && y == 0) { dp[x][y] = grid[x][y]; } else if (x == 0) { dp[x][y] = dp[x][y-1] + grid[x][y]; } else if (y == 0) { dp[x][y] = dp[x-1][y] + grid[x][y]; } else { dp[x][y] = Math.min(dp[x-1][y], dp[x][y-1]) + grid[x][y]; } } } return dp[m - 1][n - 1]; }}四、总结小记2022/6/18 来到电商就对618无感了

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（46）全排列一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。回溯法（实现：用递归）”。// 用时：6分钟。// 思路：// 1）状态初始化：l = nums.length;// curList = [], restList = nums, resList = []; 。// 2）调用回溯函数。// 3）返回后果 resList 。// 回溯法框架：// ```// result = []// def backtrack(门路, 抉择列表):// if 满足完结条件:// result.add(门路)// return// for 抉择 in 抉择列表:// # 做抉择// 门路.add(抉择)// 将该抉择从抉择列表移除// # 外围：递归调用之前【做抉择】，调用之后【撤销抉择】// backtrack(门路, 抉择列表) // # 撤销抉择// 门路.remove(抉择)// 将该抉择再退出抉择列表// ```// 参考：// 1）https://leetcode.cn/problems/permutations/solution/by-huan-huan-20-hblf/var permute = function(nums) { const backtrace = (curList = [], restList = []) => { const restListLength = restList.length; // 1）递归进口。 if (restListLength === 0) { resList.push(curList.slice()); return; } // 2）递归主体。 for (let i = 0; i < restListLength; i++) { const tempVal = restList[i], tempRestList = restList.filter((value, index) => index !== i); curList.push(tempVal); backtrace(curList, tempRestList); // 注：清理环境！！ curList.pop(); } }; // 1）状态初始化：l = nums.length; // curList = [], restList = nums, resList = []; 。 const l = nums.length; let curList = [], restList = nums, resList = []; // 2）调用回溯函数。 backtrace(curList, restList); // 3）返回后果 resList 。 return resList;}四 资源分享 & 更多1 历史文章 - 总览文章名称解法浏览量1. 两数之和（Two Sum）共 3 种2.7 k+2. 两数相加 （Add Two Numbers）共 4 种2.7 k+3. 无反复字符的最长子串（Longest Substring Without Repeating Characters）共 3 种2.6 k+4. 寻找两个正序数组的中位数（Median of Two Sorted Arrays）共 3 种2.8 k+5. 最长回文子串（Longest Palindromic Substring）共 4 种2.8 k+6. Z 字形变换（ZigZag Conversion）共 2 种1.9 k+7. 整数反转（Reverse Integer）共 2 种2.4 k+8. 字符串转换整数 (atoi)（String to Integer (atoi)）共 3 种4.2 k+9. 回文数（Palindrome Number）共 3 种4.3 k+ 11. 盛最多水的容器（Container With Most Water）共 5 种4.0 k+12. 整数转罗马数字（Integer to Roman）共 3 种3.2 k+13. 罗马数字转整数（Roman to Integer）共 3 种3.8 k+14. 最长公共前缀（Longest Common Prefix）共 4 种3.0 k+15. 三数之和（3Sum）共 3 种60.7 k+16. 最靠近的三数之和（3Sum Closest）共 3 种4.7 k+17. 电话号码的字母组合（Letter Combinations of a Phone Number）共 3 种3.1 k+18. 四数之和（4Sum）共 4 种11.5 k+19. 删除链表的倒数第 N 个结点（Remove Nth Node From End of List）共 4 种1.2 k+20. 无效的括号（Valid Parentheses）共 2 种1.8 k+ 21. 合并两个有序链表（Merge Two Sorted Lists）共 3 种1.2 k+22. 括号生成（Generate Parentheses）共 4 种1.1 k+23. 合并K个升序链表（Merge k Sorted Lists）共 4 种0.9 k+24. 两两替换链表中的节点（Swap Nodes in Pairs）共 3 种0.5 k+25. K 个一组翻转链表（Reverse Nodes in k-Group）共 5 种1.3 k+26. 删除有序数组中的反复项（Remove Duplicates from Sorted Array）共 4 种1.3 k+27. 移除元素（Remove Element）共 4 种0.4 k+28. 实现 strStr()（Implement strStr()）共 5 种0.8 k+29. 两数相除（Divide Two Integers）共 4 种0.6 k+30. 串联所有单词的子串（Substring with Concatenation of All Words）共 3 种0.6 k+ 31. 下一个排列（Next Permutation）共 2 种0.8 k+32. 最长无效括号（Longest Valid Parentheses）共 2 种1.4 k+33. 搜寻旋转排序数组（Search in Rotated Sorted Array）共 3 种1.0k+34. 在排序数组中查找元素的第一个和最初一个地位（Find First and Last Position of Element in Sorted Array）共 3 种0.5 k+35. 搜寻插入地位（Search Insert Position）共 3 种0.3 k+36. 无效的数独（Valid Sudoku）共 1 种0.6 k+38. 外观数列（Count and Say）共 5 种1.1 k+39. 组合总和（Combination Sum）共 3 种1.4 k+40. 组合总和 II（Combination Sum II）共 2 种1.6 k+ 41. 缺失的第一个负数（First Missing Positive）共 3 种1.2 k+53. 最大子数组和（Maximum Subarray）共 3 种0.3k+88. 合并两个有序数组（Merge Sorted Array）共 3 种0.4 k+102. 二叉树的层序遍历（Binary Tree Level Order Traversal）共 3 种0.4 k+146. LRU 缓存（LRU Cache）共 2 种0.5 k+160. 相交链表（Intersection of Two Linked Lists）共 2 种0.1 k+200. 岛屿数量（Number of Islands）共 4 种0.1 k+206. 反转链表（Reverse Linked List）共 3 种1.0 k+215. 数组中的第K个最大元素（Kth Largest Element in an Array）共 3 种0.5 k+236. 二叉树的最近公共先人（Lowest Common Ancestor of a Binary Tree）共 3 种0.1 k+2119. 反转两次的数字（A Number After a Double Reversal）共 2 种0.3 k+2120. 执行所有后缀指令（Execution of All Suffix Instructions Staying in a Grid）共 1 种0.4 k+2124. 查看是否所有 A 都在 B 之前（Check if All A's Appears Before All B's）共 4 种0.4 k+2125. 银行中的激光束数量（Number of Laser Beams in a Bank）共 3 种0.3 k+2126. 捣毁小行星（Destroying Asteroids）共 2 种1.6 k+2129. 将题目首字母大写（Capitalize the Title）共 2 种0.6 k+2130. 链表最大孪生和（Maximum Twin Sum of a Linked List）共 2 种0.6 k+2133. 查看是否每一行每一列都蕴含全副整数（Check if Every Row and Column Contains All Numbers）共 1 种0.6 k+ ...

一、题目粗心标签: 动静归划 https://leetcode.cn/problems/arithmetic-slices 如果一个数列 至多有三个元素 ，并且任意两个相邻元素之差雷同，则称该数列为等差数列。 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。 子数组 是数组中的一个间断序列。 示例 1： 输出：nums = [1,2,3,4]输入：3解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 本身。示例 2： 输出：nums = [1]输入：0提醒： 1 <= nums.length <= 5000-1000 <= nums[i] <= 1000 二、解题思路因为是求等差数列，能够想到满足num[i]-num[i-1]=num[i-1]-num[i-2]。咱们对于dp数组的定义通常为以i结尾的，满足某些条件的子数组数量，而等差子数组能够在任意一个地位终结，因而此题在最初须要对dp数组求和。如果num[i] - num[i-1]=num[i-1]-num[i-2]，阐明num[i]能和后面形成等差数列，那么dp[i] = dp[i-1] + 1;如果num[i] - num[i-1]!=num[i-1]-num[i-2]，阐明num[i]不能和后面形成等差数列，所以dp[i] = 0 三、解题办法3.1 Java实现public class Solution { public int numberOfArithmeticSlices(int[] nums) { if (nums.length < 3) { return 0; } int[] dp = new int[nums.length]; for (int i = 2; i < nums.length; i++) { if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) { dp[i] = dp[i-1] + 1; } } int sum = 0; for (int i : dp) { sum += i; } return sum; }}四、总结小记2022/6/17 泉城马上要进入40度天气了

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/house-robber 你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。 给定一个代表每个屋宇寄存金额的非负整数数组，计算你 不触动警报安装的状况下 ，一夜之内可能偷窃到的最高金额。 示例 1： 输出：[1,2,3,1]输入：4解释：偷窃 1 号屋宇 (金额 = 1) ，而后偷窃 3 号屋宇 (金额 = 3)。  偷窃到的最高金额 = 1 + 3 = 4 。示例 2： 输出：[2,7,9,3,1]输入：12解释：偷窃 1 号屋宇 (金额 = 2), 偷窃 3 号屋宇 (金额 = 9)，接着偷窃 5 号屋宇 (金额 = 1)。  偷窃到的最高金额 = 2 + 9 + 1 = 12 。提醒： 1 <= nums.length <= 1000 <= nums[i] <= 400 二、解题思路定义一个数组dp，dp[i]示意抢劫到第i个房子时，能够抢劫的最大数量。先找状态转移方程，思考dp[i]，此时能够抢劫的最大数量有两种可能，一种是咱们抉择不抢劫这个房子，此时累计的金额即为dp[i-1]；另一种是咱们抉择抢劫这个房子，那么此前累计的最大金额只能是dp[i-2]，因为咱们不可能抢劫第i-1个房子，否则会触发警报机关。因而状态转移方程为dp[i] = max(dp[i-1], nums[i-1] + dp[i-2]) 。 ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/climbing-stairs 假如你正在爬楼梯。须要 n 阶你能力达到楼顶。 每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？ 示例 1： 输出：n = 2输入：2解释：有两种办法能够爬到楼顶。 1 阶 + 1 阶2 阶示例 2： 输出：n = 3输入：3解释：有三种办法能够爬到楼顶。 1 阶 + 1 阶 + 1 阶1 阶 + 2 阶2 阶 + 1 阶提醒： 1 <= n <= 45 二、解题思路给定n节台阶，每次能够走一步或两步，求一共有多少种形式能够走完这些台阶。这是个斐波那契数列题。定义一个数组dp，dp[i]示意走到第i阶的办法数。因为咱们每次能够走一步或两步，所以第i阶能够从第i-1阶或i-2阶达到。换句话说，走到第i阶的办法数为走到第i-1阶的办法数加上走到第i-2阶的办法数。这样咱们就失去了状态转移方程dp[i]=dp[i-1]+dp[i-2]。留神边界条件的解决。优化：咱们能够对动静布局进行空间压缩。因为dp[i]只与dp[i-1]与dp[i-2]无关，因而能够只用两个变量来存储dp[i-1]和dp[i-2]，使得原来的O(n)空间复杂度优化为O(1)复杂度。 三、解题办法3.1 Java实现public class Solution { public int climbStairs(int n) { if (n == 1 || n == 2) { return n; } int[] steps = new int[n]; steps[0] = 1; steps[1] = 2; for (int i = 2; i < n; i++) { steps[i] = steps[i - 1] + steps[i - 2]; } return steps[n - 1]; }}四、总结小记2022/6/14 开启动静布局的题目

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/minimum-height-trees 树是一个无向图，其中任何两个顶点只通过一条门路连贯。 换句话说，一个任何没有简略环路的连通图都是一棵树。 给你一棵蕴含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 示意树中节点 ai 和 bi 之间存在一条无向边。 可抉择树中任何一个节点作为根。当抉择节点 x 作为根节点时，设后果树的高度为 h 。在所有可能的树中，具备最小高度的树（即，min(h)）被称为 最小高度树 。 请你找到所有的 最小高度树 并按 任意程序 返回它们的根节点标签列表。 树的 高度 是指根节点和叶子节点之间最长向下门路上边的数量。 示例 1： 输出：n = 4, edges = [[1,0],[1,2],[1,3]]输入：[1]解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是惟一的最小高度树。示例 2： 输出：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]输入：[3,4]提醒： 1 <= n <= 2 * 104edges.length == n - 10 <= ai, bi < nai != bi所有 (ai, bi) 互不雷同给定的输出 保障 是一棵树，并且 不会有反复的边 ...

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/permutations-ii 给定一个可蕴含反复数字的序列 nums ，按任意程序 返回所有不反复的全排列。示例 1： 输出：nums = [1,1,2]输入：[[1,1,2], [1,2,1], [2,1,1]]示例 2： 输出：nums = [1,2,3]输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提醒： 1 <= nums.length <= 8-10 <= nums[i] <= 10 二、解题思路用回溯法解决全排列问题，给定的数组中元素有反复，因而用回溯法执行后的全排列后果中会有反复的，如下图所示。解决办法，先结构一个hashmap，key是元素，value是元素的个数，而后再用回溯法来解决 三、解题办法3.1 Java实现public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); // 结构一个hashmap Map<Integer, Integer> countMap = new HashMap<>(); for (int n : nums) { int count = countMap.getOrDefault(n, 0); countMap.put(n, count + 1); } dfs(countMap, nums.length, new LinkedList<>(), ans); return ans; } void dfs(Map<Integer, Integer> countMap, int total, Deque<Integer> perm, List<List<Integer>> ans) { // 应用双端队列 if (perm.size() == total) { ans.add(new ArrayList<>(perm)); } for (Map.Entry<Integer, Integer> tmp : countMap.entrySet()) { if (tmp.getValue() > 0) { int oldValue = tmp.getValue(); perm.offerFirst(tmp.getKey()); tmp.setValue(tmp.getValue() - 1); dfs(countMap, total, perm, ans); tmp.setValue(oldValue); perm.pollFirst(); } } }}四、总结小记2022/6/12 来记录后果的类型要用双端队列

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/binary-tree-paths 给你一个二叉树的根节点 root ，按 任意程序 ，返回所有从根节点到叶子节点的门路。 叶子节点 是指没有子节点的节点。 示例 1： 输出：root = [1,2,3,null,5]输入：["1->2->5","1->3"]示例 2： 输出：root = [1]输入：["1"]提醒： 树中节点的数目在范畴 [1, 100] 内-100 <= Node.val <= 100二、解题思路dfs解决即可 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> ans = new ArrayList<>(); dfs(root, "", ans); return ans; } void dfs(TreeNode node, String path, List<String> ans) { boolean end = true; if ("".equals(path)) { path = String.valueOf(node.val); } else { path += "->" + node.val; } if (node.left != null) { dfs(node.left, path, ans); end = false; } if (node.right != null) { dfs(node.right, path, ans); end = false; } if (end) { ans.add(path); } }}四、总结小记2022/6/11 做完前几个中等的搜寻题，再做简略的就很简略了

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（160）相交链表一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。哈希法（JS里的Map数据结构）”。// 思路：// 1）状态初始化：resMap = new Map(), resNode = null; 。// 2）外围1：遍历 链表A ，将每个节点存入 哈希resMap 中。// 3）外围2：遍历 链表B 。// 3.1）若 以后节点是否存在于 哈希resMap 中，则 resNode 置为以后节点 并 退出遍历。// 4）返回后果 resNode 。var getIntersectionNode = function(headA, headB) { // 1）状态初始化：resMap = new Map(), resNode = null; 。 let resMap = new Map(), resNode = null; // 2）外围1：遍历 链表A ，将每个节点存入 哈希resMap 中。 while (headA) { resMap.set(headA, 1); headA = headA.next; } // 3）外围2：遍历 链表B 。 while (headB) { // 3.1）若 以后节点是否存在于 哈希resMap 中，则 resNode 置为以后节点 并 退出遍历。 if (resMap.has(headB)) { resNode = headB; break; } headB = headB.next; } // 4）返回后果 resNode 。 return resNode;}2 计划21)代码： ...

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/surrounded-regions 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。 示例 1： 输出：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]输入：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在程度或垂直方向相邻，则称它们是“相连”的。示例 2： 输出：board = [["X"]]输入：[["X"]]提醒： m == board.lengthn == board[i].length1 <= m, n <= 200boardi 为 'X' 或 'O' 二、解题思路找联通重量问题用DFS来做，次要是细节的优化。能够从这个中央动手，任何不在边界上的O都会变成X。也能够反向思维先找没有被突围的。具体的实现思路：从边界登程，去找和边界相连的O，把它标记成一个非凡值，再把网格中其余的O标记成X，最初再把第一步标记成非凡值的O还原 三、解题办法3.1 Java实现public class Solution { public void solve(char[][] board) { this.m = board.length; if (this.m == 0) { return; } this.board = board; this.n = board[0].length; for (int y = 0; y < m; y++) { dfs(0, y); dfs(n - 1, y); } for (int x = 0; x < n; x++) { dfs(x, 0); dfs(x, m - 1); } Map<Character, Character> v = new HashMap<>(); v.put('G', 'O'); v.put('O', 'X'); v.put('X', 'X'); for (int y = 0; y < m; y++) { for (int x = 0; x < n; x++) { switch (board[y][x]) { case 'G': board[y][x] = 'O'; break; case 'O': board[y][x] = 'X'; break; case 'X': board[y][x] = 'X'; } } } } private char[][] board; private int m; private int n; private void dfs(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') { return; } board[y][x] = 'G'; dfs(x - 1, y); dfs(x + 1, y); dfs(x, y - 1); dfs(x, y + 1); }}四、总结小记2022/6/10 联通重量问题用DFS