Leetcode

序本文次要记录一下leetcode树之门路总和 题目给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。阐明: 叶子节点是指没有子节点的节点。示例: 给定如下二叉树，以及指标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在指标和为 22 的根节点到叶子节点的门路 5->4->11->2。起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/path-sum著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return sum - root.val == 0; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}小结这里采纳递归的形式来求解，递归的终止条件就是root为null或者左右节点为null，此时判断是否有符合条件的sum；之后针对root.left或者root.right递归调用hasPathSum，此时sum传参为sum - root.val ...

序本文次要记录一下leetcode链表之宰割链表 题目编写程序以 x 为基准宰割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中蕴含 x，x 只需呈现在小于 x 的元素之后(如下所示)。宰割元素 x 只需处于“右半局部”即可，其不须要被置于左右两局部之间。示例:输出: head = 3->5->8->5->10->2->1, x = 5输入: 3->1->2->10->5->5->8起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/partition-list-lcci著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode partition(ListNode head, int x) { ListNode cursor = head; ListNode previous = head; int tmp; while (cursor != null) { if (cursor.val < x) { tmp = cursor.val; cursor.val = previous.val; previous.val = tmp; previous = previous.next; } cursor = cursor.next; } return head; }}小结这里循环遍历链表，须要应用cursor及previous两个指针，它们开始都指向head，而后判断以后节点的值是否小于x，是的话则以后节点与前一个节点的值进行替换，而后同时更新previous指针及cursor指针。 ...

序本文次要记录一下leetcode链表之环路检测 题目给定一个链表，如果它是有环链表，实现一个算法返回环路的结尾节点。有环链表的定义：在链表中某个节点的next元素指向在它后面呈现过的节点，则表明该链表存在环路。 示例 1：输出：head = [3,2,0,-4], pos = 1输入：tail connects to node index 1解释：链表中有一个环，其尾部连贯到第二个节点。 示例 2：输出：head = [1,2], pos = 0输入：tail connects to node index 0解释：链表中有一个环，其尾部连贯到第一个节点。 示例 3：输出：head = [1], pos = -1输入：no cycle解释：链表中没有环。 进阶：你是否能够不必额定空间解决此题？起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle-lcci著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { break; } } if (fast == null || fast.next == null) { return null; } while (head != fast) { head = head.next; fast = fast.next; } return head; }}小结借助额定空间的话，应用HashSet，遍历链表直到游标指针为null或者找到HashSet中存在的元素；如果不借助额定空间的话，先用快慢指针遍历找到相交的节点，若没有相交的节点间接返回，若有相交的节点，则再次从头遍历，同时挪动头指针与快慢指针相遇的节点指针，若二者相遇则找到入口节点。 ...

@TOC 字符串循环移位蕴含编程之美 3.1 s1 = AABCD, s2 = CDAAReturn : true题解： 给定两个字符串 s1 和 s2，要求断定 s2 是否可能被 s1 做循环移位失去的字符串蕴含。s1 进行循环移位的后果是 s1s1 的子字符串，因而只有判断 s2 是否是 s1s1 的子字符串即可。 字符串循环移位编程之美 2.17 s = "abcd123" k = 3Return "123abcd"题解： 将字符串向右循环挪动 k 位。将 abcd123 中的 abcd 和 123 独自翻转，失去 dcba321，而后对整个字符串进行翻转，失去 123abcd。 字符串中单词的翻转程序员代码面试指南 s = "I am a student"Return "student a am I"题解：将每个单词翻转，而后将整个字符串翻转。 242. 无效的字母异位词* (简略)给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。示例 1: ...

序本文次要记录一下leetcode链表之删除排序链表中的反复元素 题目给定一个排序链表，删除所有反复的元素，使得每个元素只呈现一次。示例 1:输出: 1->1->2输入: 1->2示例 2:输出: 1->1->2->3->3输入: 1->2->3起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } ListNode cursor = head; ListNode next = head.next; while (next != null) { if (cursor.val == next.val) { cursor.next = next.next; } else { cursor = cursor.next; } next = next.next; } return head; }}小结这里应用一个cursor，从head开始，再应用next保留失常遍历时的next，cursor在找到反复节点时批改next为next.next，否则后退一个节点 ...

D122 1154. Day of the Year题目链接1154. Day of the Year 题目剖析这道题目比较简单，给定YYYY-MM-DD格局的日期，返回这一天是这一年的第几天。 思路首先要晓得每个月的天数是不一样的，那么咱们先把它存起来。 而后用array_slice获取当月之前的所有月份天数，并用array_sum函数计算总和。再加上DD局部即可。 须要留神的是，只有当待求月份大于2月时，才须要通过判断是否是平年来加1天。如果待求月份为1月或2月时，不须要思考平年。 最终代码<?phpclass Solution { /** * @param String $date * @return Integer */ public $daysOfMonth = [ 31,28,31,30,31,30, 31,31,30,31,30,31, ]; function dayOfYear($date) { list($year, $month, $day) = explode('-', $date); $year = intval($year); $month = intval($month); $day = intval($day); $isLeap = intval(($month>2) && ($year%4 == 0) && ($year%100!=0)); return array_sum(array_slice($this->daysOfMonth,0,$month-1)) + $day + $isLeap; }}不过这题只战胜了41.67%，有晋升空间。 ...

D121 21. Merge Two Sorted Lists题目链接21. Merge Two Sorted Lists 题目剖析合并两个有序链表。 思路一一遍历两个链表，把小的数字塞入数组里。之后再拼起来。 最终代码<?php/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */class Solution{ private $vals = []; function mergeTwoLists($l1, $l2) { $this->iterate($l1, $l2); $root = $node = NULL; if($this->vals){ $root = $node = new ListNode(array_pop($this->vals)); } while(!empty($this->vals)){ $node->next = new ListNode(array_pop($this->vals)); $node = $node->next; } return $root; } function iterate($l1, $l2){ if(!is_null($l1) && !is_null($l2)){ if($l1->val<=$l2->val){ array_unshift($this->vals, $l1->val); $l1 = $l1->next; } else{ array_unshift($this->vals, $l2->val); $l2 = $l2->next; } } else if(!is_null($l1)){ array_unshift($this->vals,$l1->val); $l1 = $l1->next; } else if(!is_null($l2)){ array_unshift($this->vals,$l2->val); $l2 = $l2->next; } else if (is_null($l1) && is_null($l2)){ return; } $this->iterate($l1, $l2); }}若感觉本文章对你有用，欢送用爱发电赞助。 ...

D120 830. Positions of Large Groups题目链接830. Positions of Large Groups 题目剖析给定一个字符串，返回雷同字母间断呈现次数超过3次的始末值。 解决思路我采纳的是，先放进数组，间断则递增完结的下标。若遇到不同字母，则先判断上一个字母的起点下标减起始下标是否小于3则删除，大于等于3则保留。 在for循环外再判断一次最初一对下标是否也符合要求。因为之前是在当遇到不同字母时判断的，若测试样例中只呈现了同一个字符，那么就进不去判断长度的代码中。 最终代码<?phpclass Solution { /** * @param String $S * @return Integer[][] */ function largeGroupPositions($S) { $largeGroup = [[0,0]]; $S = str_split($S); $prev = ""; $index = 0; foreach($S as $k => $v){ $cur = $largeGroup[$index]; if($v == $prev){ $cur[1]++; $largeGroup[$index] = $cur; } else{ if($cur[1]-$cur[0]<2){ $largeGroup[$index] = [$k,$k]; } else{ $index++; $largeGroup[] = [$k, $k]; } } $prev = $v; } if($largeGroup[$index][1]-$largeGroup[$index][0]<2){ unset($largeGroup[$index]); } return $largeGroup; }}若感觉本文章对你有用，欢送用爱发电赞助。 ...

D119 704. Binary Search题目链接704. Binary Search 题目剖析有序数组的二分查找。 思路这个不必多说了，很根底的题目了。 用三个标记去记录起始地位、两头地位以及开端地位。因为是有序的，所以能够通过判断两头地位的大小来每次缩小一半待查找元素个数。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer */ function search($nums, $target) { $start = 0; $end = count($nums); do{ $mid = floor(($end+$start)/2); var_dump($start.'-'.$mid.'-'.$end); if($nums[$mid] == $target){ return $mid; } if($nums[$mid]<$target){ $start = $mid+1; } else{ $end = $mid-1; } }while($end>=$start); return -1; }}若感觉本文章对你有用，欢送用爱发电赞助。

序本文次要记录一下leetcode链表之两个链表的第一个公共节点 题目输出两个链表，找出它们的第一个公共节点。 如上面的两个链表：在节点 c1 开始相交。 示例 1：输出：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输入：Reference of the node with value = 8输出解释：相交节点的值为 8 （留神，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 示例 2：输出：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1输入：Reference of the node with value = 2输出解释：相交节点的值为 2 （留神，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。 ...

序本文次要记录一下leetcode链表之删除链表的节点 题目给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。留神：此题比照原题有改变示例 1:输出: head = [4,5,1,9], val = 5输入: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2:输出: head = [4,5,1,9], val = 1输入: [4,5,9]解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. 阐明： 题目保障链表中节点的值互不雷同 若应用 C 或 C++ 语言，你不须要 free 或 delete 被删除的节点起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode deleteNode(ListNode head, int val) { ListNode cursor = head; ListNode preNode = null; if (cursor.val == val) { return head.next; } while (cursor.val != val) { preNode = cursor; cursor = cursor.next; } preNode.next = preNode.next.next; return head; }}小结这里的关键在于要设计一个preNode指针保护前一个节点，好进行删除操作 ...

序本文次要记录一下leetcode链表之回文链表 题目请判断一个链表是否为回文链表。示例 1:输出: 1->2输入: false示例 2:输出: 1->2->2->1输入: true进阶：你是否用 O(n) 工夫复杂度和 O(1) 空间复杂度解决此题？起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/palindrome-linked-list著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public boolean isPalindrome(ListNode head) { if (head == null) { return true; } Stack stack = new Stack(); ListNode cursor = head; while(cursor != null) { stack.push(cursor.val); cursor = cursor.next; } cursor = head; while(cursor != null) { int val = (int)stack.pop(); if (val != cursor.val) { return false; } cursor = cursor.next; } return true; }}小结这里应用Stack来解决，先遍历一遍放到Stack中，之后再次遍历，挨个跟stack.pop进去的比拟 ...

216. 组合总和 III题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/combination-sum-iii 题目找出所有相加之和为 n 的 k 个数的组合。组合中只容许含有 1 - 9 的正整数，并且每种组合中不存在反复的数字。 阐明： 所有数字都是正整数。解集不能蕴含反复的组合。示例 1: 输出: k = 3, n = 7输入: [[1,2,4]]示例 2: 输出: k = 3, n = 9输入: [[1,2,6], [1,3,5], [2,3,4]]解题思路思路：回溯因为这篇题解是跟着每日一题去撰写的，最近的每日一题考察点有些反复，这里先放前两天题目的题解： 39. 组合总和40. 组合总和 II其中本题与第 39、40 题雷同的有： 解集不能蕴含反复组合，组合中元素都是正整数。与第 40 题不同的有： 组合不存在反复数字。本题与第 39、40 题都不同的在于： 限度组合的长度；组合元素只含 1~9。因为近期考查的点有些重合，这里就不再赘述，能够查看下面的两篇题解进行理解。至于本题，依据与后面题目的不同点扭转相应的策略，具体的思路可看上面的简略图示： 依据下面图示的思路，编写代码，具体如下。 class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: ans = [] tmp = [] def helper(choice, total): """ Args: choice: 递归每层选取的元素 total: 组合中的元素和 """ # 这里限度组合长度， if len(tmp) == k: if total == n: ans.append(tmp[::]) return # 限度元素和大于 n if total > n: return # 组合中只容许 1-9 的正整数 for i in range(choice, 10): total += i tmp.append(i) # 避免元素反复选取 # 同时防止组合反复 helper(i+1, total) tmp.pop() total -= i total = 0 helper(1, total) return ans欢送关注公众号 【书所集录】 ...

序本文次要记录一下leetcode链表之找出倒数第k个节点 题目输出一个链表，输入该链表中倒数第k个节点。为了合乎大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值顺次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 示例：给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode c1 = head; while (c1 != null && k > 0) { c1 = c1.next; k--; } ListNode c2 = head; while (c1 != null) { c1 = c1.next; c2 = c2.next; } return c2; }}快慢指针，先让快指针走k步，而后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。小结这里采纳了快慢指针的套路，先让快指针走k步，而后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。 ...

40. 组合总和 II题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/combination-sum-ii 题目给定一个数组 candidates 和一个指标数 target ，找出 candidates 中所有能够使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能应用一次。 阐明： 所有数字（包含指标数）都是正整数。解集不能蕴含反复的组合。示例 1: 输出: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]示例 2: 输出: candidates = [2,5,2,1,2], target = 5,所求解集为:[ [1,2,2], [5]]解题思路思路：回溯这道题跟 39. 组合总和 相似，两者不同的中央在于： 【39. 组合总和】，candidates 中的数字能够无限度反复被选取；【40. 组合总和 II】，candidates 中的每个数字在每个组合中只能应用一次。这里还有个隐式的条件就是，这道题中没有强调给定数组元素重复性问题，而在示例中，咱们也能够看到元素在数组中是存在反复的状况，这也是一个不同点。 两者雷同的中央在于： 解集中不能蕴含反复的组合，也就是雷同数字不同排序视为反复。在第 39 题中，因为元素不反复且可屡次选取同个元素，所以采取的策略中只有防止不产生反复组合即可。 在第 40 题，也就是本题当中，咱们次要须要解决的就是数组元素存在反复状况的问题，上面是解决的方法： 首先先将数组进行排序，这样反复的元素地位相邻，能够疾速去重；因为不容许组合反复（雷同数字不同排序视为反复），所以递归每层不能存在反复的元素。为了防止反复抉择同个元素，进入上层递归时，抉择下一个索引地位对应的元素。这里用一个简略图示来加深了解，如下： 这里同样只选取其中一个分支绘制图示，因为其余分支同样是采纳雷同的策略。若不了解，同样可自行补全并加深了解。 依照这样的思路进行书写代码，具体如下。 class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: # 将数组进行升序排序 candidates.sort() # 后果列表 ans = [] # 可能组合 tmp = [] def helper(idx, total): if total == target: ans.append(tmp[::]) return if total > target: return for i in range(idx, len(candidates)): # 这里限度同一层不能抉择值雷同的元素 # 若有雷同的元素，优先选择索引靠前的 if candidates[i-1] == candidates[i] and i-1 >= idx: continue total += candidates[i] tmp.append(candidates[i]) # 这里留神，与 39 题不同，进入递归下一层 # 从以后索引的下一位开始选取，防止反复选取同个元素 helper(i+1, total) # 回溯 tmp.pop() total -= candidates[i] total = 0 helper(0, total) return ans这里将 39. 组合总和 的题解放在这里，能够联合本题加深了解。 ...

/** * 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 reverseKGroup(ListNode head, int k) { if(k <= 1) return head; ListNode dummy = new ListNode(0, head); ListNode tail = dummy; while(tail.next != null) { int count = k; ListNode temp = tail; tail = tail.next; ListNode temp2 = tail; while(temp2 != null && count > 0) { temp2 = temp2.next; count--; } if(count > 0) return dummy.next; count = k-1; while(count > 0) { ListNode cur = tail.next; tail.next = cur.next; cur.next = temp.next; temp.next = cur; count--; } } return dummy.next; }}

序本文次要记录一下leetcode链表之合并两个排序的链表 题目输出两个递增排序的链表，合并这两个链表并使新链表中的节点依然是递增排序的。示例1：输出：1->2->4, 1->3->4输入：1->1->2->3->4->4限度：0 <= 链表长度 <= 1000起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode newHead = new ListNode(-1); ListNode cursor = newHead; while(l1 != null && l2 != null) { if (l1.val <= l2.val) { cursor.next = l1; l1 = l1.next; } else { cursor.next = l2; l2 = l2.next; } cursor = cursor.next; } if (l1 == null) { cursor.next = l2; } if (l2 == null) { cursor.next = l1; } return newHead.next; }}这里先创立一个newHead节点来示意合并后链表的头指针，而后创立一个cursor，其初始值为newHead；之后同时遍历l1及l2，取最小的作为cursor.next，同时该链表后退一个节点，并且cursor跟着后退；最初再将cursor.next指向尚未遍历完的链表的残余节点；之后返回头指针指向的节点小结合并两个有序链表的基本思路就是设置一个cursor以及新链表的头指针，而后同时遍历两个链表，取小的节点作为cursor的next，而后该链表往后退，cursor也跟着往后退，最初再将cursor.next指向尚未遍历完的链表的残余节点 ...

/** * 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 swapPairs(ListNode head) { if(head == null || head.next == null) return head; ListNode temp = head.next; head.next = temp.next; temp.next = head; head = temp; ListNode pre = head.next; if (pre.next == null) return head; ListNode cur = pre.next; while(cur != null && cur.next != null) { temp = cur.next; pre.next = temp; cur.next = temp.next; temp.next = cur; pre = cur; cur = pre.next; } return head; }}

/** * 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 mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; ListNode head = new ListNode(); ListNode tail = head; PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val)); for(ListNode node : lists) { if(node!=null) { pq.add(node); } } while (!pq.isEmpty()) { tail.next = pq.poll(); tail = tail.next; if (tail.next != null) { pq.add(tail.next); } } return head.next; }}

class Solution { public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<>(); if(n == 0){ ans.add(""); return ans; } if(n == 1){ ans.add("()"); return ans; } generator(ans, n, 0, 0, ""); return ans; } void generator(List<String> ans, int n, int left, int right, String prefix) { if(prefix.length() == 2*n) { ans.add(prefix); return; } if(left > right) { generator(ans, n, left, right+1, prefix+")"); } if(left < n) { generator(ans, n, left+1, right, prefix+"("); } }}

39. 组合总和题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/combination-sum 题目给定一个无反复元素的数组 candidates 和一个指标数 target ，找出 candidates 中所有能够使数字和为 target 的组合。 candidates 中的数字能够无限度反复被选取。 阐明： 所有数字（包含 target）都是正整数。解集不能蕴含反复的组合。示例 1： 输出：candidates = [2,3,6,7], target = 7,所求解集为：[ [7], [2,2,3]]示例 2： 输出：candidates = [2,3,5], target = 8,所求解集为：[ [2,2,2,2], [2,3,3], [3,5]]提醒： 1 <= candidates.length <= 301 <= candidates[i] <= 200candidate 中的每个元素都是举世无双的。1 <= target <= 500解题思路思路：回溯先审题，题目给定无反复元素数组和目标值 target，要求找出数组中所有能够使数组元素和为 target 的组合。 其中数组中的元素都为正整数，能够重复使用数组中的元素，然而解集中不能存在反复的组合。 这里能够看示例 1： 输出：candidates = [2,3,6,7], target = 7,所求解集为：[ [7], [2,2,3]]这里答案并没有 [2,3,2] 或 [3,2,2]，因为这两者就被视为与 [2,2,3] 为反复的组合，这里须要特地留神。 ...

序本文次要记录一下leetcode链表之反转链表 题目定义一个函数，输出一个链表的头节点，反转该链表并输入反转后链表的头节点。 示例:输出: 1->2->3->4->5->NULL输入: 5->4->3->2->1->NULL 限度：0 <= 节点个数 <= 5000起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseList(ListNode head) { ListNode current = head; ListNode previous = null; ListNode next = null; while (current != null) { next = current.next; current.next = previous; previous = current; current = next; } return previous; }}这里应用了current、previous、next来保留小结这里应用了current、previous、next来保留，初始化的时候previous及next都设置为null ...

77. 组合题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/combinations 题目给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输出: n = 4, k = 2输入:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]解题思路思路：组合数先审题，题目要求给定 n，返回 1...n 中所有可能的 k 个数组合。咱们能够发现，这其实就是高中数学概念上的组合数问题。 组合的定义： 从 n 个不同元素中，任取 m（$m \leq n$）个不同元素组成一组，称为组合。 组合数的定义： 从 n 个不同元素中，任取 m（$m \leq n$）个不同元素的所有组合的个数，叫做组合数，记为 $C_{n}^{m}$。 组合数有这样一个性质： $$C_{n+1}^{m} = C_{n}^{m} + C_{n}^{m-1}$$ 这里咱们令 n' = n+1，那么下面的式子则会变成： $$C_{n'}^{m} = C_{n'-1}^{m} + C_{n'-1}^{m-1}$$ 其实也就等同于： $$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$$ ...

60. 第k个排列题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/permutation-sequence 题目给出汇合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小程序列出所有排列状况，并一一标记，当 n = 3 时, 所有排列如下： "123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。 阐明： 给定 n 的范畴是 [1, 9]。给定 k 的范畴是[1, n!]。示例 1: 输出: n = 3, k = 3输入: "213"示例 2: 输出: n = 4, k = 9输入: "2314"解题思路思路：DFS + 剪枝先审题，题目中阐明，给定汇合 [1, 2, 3, ..., n] 有 n! 中排列。按大小程序列出所有排列状况，进行标记，而后返回第 k 个排列。 那么依照题意，咱们最容易想到的就是列出 [1, 2, 3 ..., n] 个元素全排列，而后返回第 k 个排列，然而这样效率可能会非常低，而且咱们也没有必要去求得所有的全排列。 ...

160. 相交链表编写一个程序，找到两个单链表相交的起始节点。如上面的两个链表：在节点 c1 开始相交。示例 1：输出：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输入：Reference of the node with value = 8输出解释：相交节点的值为 8 （留神，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 留神： 如果两个链表没有交点，返回 null.在返回后果后，两个链表仍须放弃原有的构造。可假定整个链表构造中没有循环。程序尽量满足 O(n) 工夫复杂度，且仅用 O(1) 内存。题解办法一：用两个指针别离获取两个链表得长度，失去长度差n。长链表的指针从头结点跑n步，短链表的指针指向短链表头指针，之后两个指针同步向后跑，直到两个指针相交。 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //1. 计算两个链表的长度之差 ListNode p1 = headA; ListNode p2 = headB; int n = 0; while (p1!=null){ p1 = p1.next; n++; } while (p2!=null){ p2 = p2.next; n--; } //p1指向长链，p2指向短链 if (n>0){ p1 = headA; p2 = headB; }else { p1 = headB; p2 = headA; } n = Math.abs(n); //长链先走n步 for (int i = 0; i<n; i++){ p1 = p1.next; } //p1,p2一起走 while(p1!=p2){ p1 = p1.next; p2 = p2.next; } return p1; }}办法二：更简洁的办法先使得长链表指针达到离末端的间隔与短链表长度雷同。p1, p2别离指向链表headA和headB，若p1先跑完，则p1指向headB, 若p2跑完，则将p2指向headA，直到p1与p2雷同。例如对于链表:A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9, 两个链表长度相差为2. 那么链表B少跑两个结点。指针p2在链表B先跑完，将p2重置向A, p1,p2持续同步向后跑，指针p1在A中会跑完多的两个结点，同时p2在B中也会同步跑2个结点，此时p2指向的地位正好是比链表A比链表B长出的那一部分。最初p1指向headB，p1和p2此时离开端的间隔雷同，只须要同步向后走直到遇到交点。 ...

841. 钥匙和房间题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/keys-and-rooms 题目有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。 在模式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 roomsi 由 [0,1，...，N-1] 中的一个整数示意，其中 N = rooms.length。 钥匙 roomsi = v 能够关上编号为 v 的房间。 最后，除 0 号房间外的其余所有房间都被锁住。 你能够自在地在房间之间来回走动。 如果能进入每个房间返回 true，否则返回 false。 示例 1： 输出: [[1],[2],[3],[]]输入: true解释: 咱们从 0 号房间开始，拿到钥匙 1。之后咱们去 1 号房间，拿到钥匙 2。而后咱们去 2 号房间，拿到钥匙 3。最初咱们去了 3 号房间。因为咱们可能进入每个房间，咱们返回 true。示例 2： 输出：[[1,3],[3,0,1],[2],[0]]输入：false解释：咱们不能进入 2 号房间。提醒： 1 <= rooms.length <= 10000 <= rooms[i].length <= 1000所有房间中的钥匙数量总计不超过 3000。解题思路思路：DFS、BFS先看题目，题目要求从 0 号房间开始，问是否可能进入每个房间？其中，0 号房间最开始是关上的，而其余的房间则全副锁住。实践上，每个房间外面都有钥匙（但依据 提醒 2 可能无）对应其余房间的钥匙（包含以后房间，如示例 2 的 1 号房间）。 ...

557. 反转字符串中的单词 III题目给定一个字符串，你须要反转字符串中每个单词的字符程序，同时仍保留空格和单词的初始程序。 示例： 输出："Let's take LeetCode contest"输入："s'teL ekat edoCteeL tsetnoc"提醒： 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额定的空格。解题思路应用辅助列表先看题目，给定字符串，其中字符串含有空格，要求反转被空格隔开的单词，然而保留空格和单词的初始程序。 再看前面的提醒，字符串每个单词只有单个空格分隔，字符串不会有其余额定的空格。 因为只有单个空格分隔，那么这里，咱们能够思考将给定的字符串依照空格进行宰割，这里应用字符串的 split() 函数，具体的做法： 依照空格对字符串进行宰割；定义辅助列表，而后将分割部分的单词进行翻转，依照程序增加到辅助列表中；最初将反转之后单词进行拼接，增加空格距离。具体代码实现如下： class Solution: def reverseWords(self, s: str) -> str: # 依照空格进行切割 s = s.split(' ') # 而后将切割后的每局部都进行翻转 ans = [] for part in s: part = part[::-1] ans.append(part) # 最初拼接 return ' '.join(ans)后面的办法应用字符串的 split() 办法，这里再说一种在不应用宰割的办法如何实现： 遍历字符串，定义变量 left, right 别离指向单词开始和结尾，定义辅助列表；挪动 right，查找空格，当遇到空格时，开始逆序将单词增加到辅助列表中；而后遇到空格，也将空格增加到辅助列表，再次挪动 right，反复后面的步骤，直至 right 达到字符串开端。具体的代码实现如下。 class Solution: def reverseWords(self, s: str) -> str: ans = [] length = len(s) right = 0 while right < length: left = right # 先寻得空格，而后对空格后面进行替换 while right < length and s[right] != ' ': right += 1 # 逆序增加到辅助列表中 for i in range(right-1, left-1, -1): ans.append(s[i]) # 遇到空格也将空格也增加到列表中，而后继续移动 while right < length and s[right] == ' ': ans.append(' ') right += 1 # 返回 return ''.join(ans)欢送关注公众号 【书所集录】 ...

1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。   示例: 给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] def twoSum(nums: List[int], target: int) -> List[int]: if not nums or len(nums) < 2: return prefix_sum = {} n = len(nums) for i in range(n): if nums[i] in prefix_sum: return [prefix_sum[nums[i]], i] prefix_sum[target-nums[i]] = i工夫复杂度为$O(n)$, 工夫复杂度为$O(n)$ 15. 三数之和给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不反复的三元组。 ...

657. 机器人是否返回原点题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/robot-return-to-origin 题目在二维立体上，有一个机器人从原点 (0, 0) 开始。给出它的挪动程序，判断这个机器人在实现挪动后是否在 (0, 0) 处完结。 挪动程序由字符串示意。字符 move[i] 示意其第 i 次挪动。机器人的无效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在实现所有动作后返回原点，则返回 true。否则，返回 false。 留神：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右挪动一次，“L” 将始终向左挪动等。此外，假如每次移动机器人的挪动幅度雷同。 示例 1: 输出: "UD"输入: true解释：机器人向上挪动一次，而后向下挪动一次。所有动作都具备雷同的幅度，因而它最终回到它开始的原点。因而，咱们返回 true。示例 2: 输出: "LL"输入: false解释：机器人向左挪动两次。它最终位于原点的左侧，距原点有两次 “挪动” 的间隔。咱们返回 false，因为它在挪动完结时没有返回原点。解题思路思路：模仿先看题目，题目要求，在给定挪动程序后，机器人从原点 (0， 0) 登程，挪动结束后是否可能回到原点。 其中，机器人能够挪动范畴为四个方位，以下字母别离对应四个方位： R（右）L（左）U（上）D（下）最初留神局部也额定阐明，机器人回到原点无论面向哪个方位都能够。 那么，咱们的思路就是模仿机器人行走。在二维立体上。定义 x，y 轴，机器人从原点（0,0）登程。当指令为 R,U 示意机器人别离往 x，y 轴的正方向挪动，L,D 示意机器人别离往 x，y 轴的负方向挪动。图示如下： 当初，定义变量 x，y，遍历字符串 moves，依据字符串中的指令移动机器人，挪动结束，判断机器人是否回到原点。做法如下： 定义变量 x，y；遇到以下指令，更新 x，y： 遇到 'R'，x += 1；遇到 'L'，x -= 1；遇到 'U'，y += 1；遇到 'D'，y -= 1；挪动结束，判断是否回到原点，也就是 x，y 是否都为 0。具体代码实现如下。 ...

class Solution { public List<String> letterCombinations(String digits) { Map<Character, String> phone = new HashMap<Character, String>(); phone.put('2', "abc"); phone.put('3', "def"); phone.put('4', "ghi"); phone.put('5', "jkl"); phone.put('6', "mno"); phone.put('7', "pqrs"); phone.put('8', "tuv"); phone.put('9', "wxyz"); List<String> output = new ArrayList<String>(); for(int i = 0; i < digits.length(); i++) { String letter = phone.get(digits.charAt(i)); List<String> temp = new ArrayList<String>(); for(int j = 0; j < letter.length(); j++) { if(output.size() == 0) { temp.add(letter.substring(j, j+1)); } else { for(String s : output) { temp.add(s+letter.substring(j, j+1)); } } } output.clear(); output.addAll(temp); temp.clear(); } return output; }}

This problem is a variation of 3Sum. The main difference is that the sum of a triplet is not necessarily equal to the target. Instead, the sum is in some relation with the target, which is closest to the target for this problem. In that sense, this problem shares similarities with 3Sum Smaller. Before jumping in, let's check solutions for the similar problems: 3Sum fixes one number and uses either the two pointers pattern or a hash set to find complementary pairs. Thus, the time complexity is \mathcal{O}(n^2)O(n2).3Sum Smaller, similarly to 3Sum, uses the two pointers pattern to enumerate smaller pairs. Note that we cannot use a hash set here because we do not have a specific value to look up.For the same reason as for 3Sum Smaller, we cannot use a hash set approach here. So, we will focus on the two pointers pattern and shoot for \mathcal{O}(n^2)O(n2) time complexity as the best conceivable runtime (BCR). ...

141. 环形链表题目给定一个链表，判断链表中是否有环。 为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 示例 1： 输出：head = [3,2,0,-4], pos = 1输入：true解释：链表中有一个环，其尾部连贯到第二个节点。 示例 2： 输出：head = [1,2], pos = 0输入：true解释：链表中有一个环，其尾部连贯到第一个节点。 示例 3： 输出：head = [1], pos = -1输入：false解释：链表中没有环。 进阶： 你能用 O(1)（即，常量）内存解决此问题吗？解题思路思路：哈希表、快慢指针在这里，咱们间接看示例，如果链表存在环，那么某一个结点被拜访的次数将不止一次。 哈希表那么，咱们应用哈希表来存储拜访的节点，判读根据如下： 当某个结点在被拜访时，发现存在于哈希表中，那么咱们能够判断该链表为环形链表。否则持续拜访，直至结点为空。具体的代码见【代码实现 # 哈希表】 快慢指针题目最初进阶局部，提出是否可能用常量空间复杂度解决问题。因为后面的办法，定义哈希表存储须要额定的空间。 在这里，咱们用快慢指针的思路来解决。具体如下： 定义两个指针 p、q，其中一个快指针 p 每次挪动两步，慢指针 q 每次挪动一步；如果不存在环，那么快指针会先一步达到尾部，那么咱们就能够返回 False；如果存在环，那么快指针将会再次达到链表的某个结点，最终快慢指针将会重合，返回 True。具体的代码见【代码实现 # 快慢指针】 代码实现# 哈希表# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def hasCycle(self, head: ListNode) -> bool: hash_map = {} # 结点非空时 while head: # 先判断结点是否曾经存在于哈希表中 # 存在，则示意存在环 if head in hash_map: return True # 记录拜访的节点，拜访过都标记为 1 hash_map[head] = 1 head = head.next return False# 快慢指针# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def hasCycle(self, head: ListNode) -> bool: # 定义快慢指针 # 快指针 p 每次挪动两步，慢指针 q 每次挪动一步 p = head q = head while p and p.next: q = q.next p = p.next.next if p == q: return True return False实现后果 ...

查找35. 搜寻插入地位给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。 你能够假如数组中无反复元素。 示例 1: 输出: [1,3,5,6], 5输入: 2示例 2: 输出: [1,3,5,6], 2输入: 1示例 3: 输出: [1,3,5,6], 7输入: 4示例 4: 输出: [1,3,5,6], 0输入: 0首先来回顾一下二分搜寻的代码 def search(nums -> list[int], target -> int) -> int: """ Params: nums(list): sorted array target(int): int """ # 如果数组为空 if not nums: return -1 def helper(left -> int, right -> int): # 循环完结条件: left = right + 1 while left <= right: # 防止数值过大导致溢出 mid = left + (right - left) // 2 # 向左膨胀 if nums[mid] < target: right = mid -1 # 向右膨胀 elif nums[mid] > target: left = mid + 1 # 找到了, 间接返回 elif nums[mid] == target: return mid n = len(nums) idx = helper(0, n-1) return idx if idx else -1def searchInsert(nums -> list[int], target -> int) -> int: if not nums: return 0 def helper(left, right): while left <= right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: right = right - 1 return left return helper(0, len(nums)-1)202. 高兴数编写一个算法来判断一个数 n 是不是高兴数。 ...

459. 反复的子字符串题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/repeated-substring-pattern 题目给定一个非空的字符串，判断它是否能够由它的一个子串反复屡次形成。给定的字符串只含有小写英文字母，并且长度不超过10000。 示例 1: 输出: "abab"输入: True解释: 可由子字符串 "ab" 反复两次形成。示例 2: 输出: "aba"输入: False示例 3: 输出: "abcabcabcabc"输入: True解释: 可由子字符串 "abc" 反复四次形成。 (或者子字符串 "abcabc" 反复两次形成。)解题思路思路：枚举先审题，题目中要求某个字符串是否是由某个子串反复屡次形成。 这里咱们假如字符串 cur_string 是由某个子串 sub_string 反复屡次形成。联合示例，尝试剖析外面的法则。 如果依照 sub_string 的长度去划分 cur_string 字符串，这里肯定是可能残缺划分的，也就是说： sub_string 的长度是 cur_string 长度的倍数；同样的，每个划分局部的子串都是同样的。令 m = len(sub_string)，也就说相隔长度 m，前后两个子串对应的字符是雷同的。（后续子串局部同样成立）如下列图示： 以子串的长度划分给定字符串 相隔长度 m（子串长度），对应的字符雷同 然而这里须要留神，这里反复次数至多有 1 次，那么子串的长度不会大于给定字符串长度的一半。那么咱们枚举的时候，只有在 [1, n/2] （n：给定字符串的长度）的范畴内查看是否有符合条件的状况。 那么，依据下面的剖析，当初咱们说下枚举的具体方法（上面局部 n 示意给定字符串的长度）： 在 [1, n/2] 开始遍历，先查找能被 n 整除的数字 i；当找到 i 时， i 也就是此时子串的长度。此时判断子串是否能反复屡次形成给定的字符串。从 [i, n] 开始判断，依据后面剖析的状况二，相隔长度 i（子串长度），对应的字符是雷同的。具体代码实现如下。 ...

ARTSARTS 是陈浩（网名左耳朵耗子）在极客工夫专栏里发动的一个流动，目标是通过分享的形式来保持学习。 每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。本周内容本周的 ARTS 你将看到: LeetCode 516 最长回文子序列.来自 Uber 的 Golang 编程标准.Algorithm本周的算法题是 LeetCode 516.longest-palindromic-subsequence, 最长回文子序列. 回文序列和会问字符串的最大区别就是序列是能够不间断的, 然而串必须是间断的. 所以这道题和之前第 5 题最长回文子串的区别就很显著了, 或者说这道题要求更加宽泛一些. // 没错我就是抄答案的 https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/// dp[i][j] 代表 s 的下标冲 i 到 j 范畴内的回文子序列长度// base case: dp[i][i] 代表一个字符肯定是回文子序列func longestPalindromeSubseq(s string) int { l := len(s) dp := make([][]int, l) for i := range dp { dp[i] = make([]int, l) } for i := 0; i < l; i++ { dp[i][i] = 1 } for i := l - 1; i >= 0; i-- { for j := i + 1; j < l; j++ { if s[i] == s[j] { dp[i][j] = dp[i+1][j-1] + 2 } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1]) } } } return dp[0][l-1]}func max(a, b int) int { if a > b { return a } return b} Review 文章举荐本周举荐的英文文章是 Uber 公开的外部 Golang编程标准. ...

679. 24 点游戏题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/24-game 题目你有 4 张写有 1 到 9 数字的牌。你须要判断是否能通过 *，/，+，-，(，) 的运算失去 24。 示例 1: 输出: [4, 1, 8, 7]输入: True解释: (8-4) * (7-1) = 24示例 2: 输出: [1, 2, 1, 2]输入: False留神: 除法运算符 / 示意实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。每个运算符对两个数进行运算。特地是咱们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输出时，表达式 -1 - 1 - 1 - 1 是不容许的。你不能将数字连贯在一起。例如，输出为 [1, 2, 1, 2] 时，不能写成 12 + 12 。解题思路思路：回溯抛开本题，先说一下，咱们平时玩 24 点游戏个别程序是： ...

529. 扫雷游戏题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/minesweeper 题目让咱们一起来玩扫雷游戏！ 给定一个代表游戏板的二维字符矩阵。 M 代表一个未挖出的地雷，E 代表一个未挖出的空方块，B 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）示意有多少地雷与这块已挖出的方块相邻，X 则示意一个已挖出的地雷。 当初给出在所有未挖出的方块中（M或者E）的下一个点击地位（行和列索引），依据以下规定，返回相应地位被点击后对应的面板： 如果一个地雷（M）被挖出，游戏就完结了- 把它改为 X。如果一个没有相邻地雷的空方块（E）被挖出，批改它为（B），并且所有和其相邻的未挖出方块都应该被递归地揭发。如果一个至多与一个地雷相邻的空方块（E）被挖出，批改它为数字（'1'到'8'），示意相邻地雷的数量。如果在此次点击中，若无更多方块可被揭发，则返回面板。示例 1： 输出:[['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'M', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'E', 'E', 'E']]Click : [3,0]输入:[['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]解释: 示例 2： 输出:[['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]Click : [1,2]输入:[['B', '1', 'E', '1', 'B'], ['B', '1', 'X', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]解释: ...

647. 回文子串题目起源：力扣（LeetCode）[https://leetcode-cn.com/probl...](https://leetcode-cn.com/probl...) 题目给定一个字符串，你的工作是计算这个字符串中有多少个回文子串。 具备不同开始地位或完结地位的子串，即便是由雷同的字符组成，也会被视作不同的子串。 示例 1： 输出："abc"输入：3解释：三个回文子串: "a", "b", "c"示例 2： 输出："aaa"输入：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"提醒： 输出的字符串长度不会超过 1000 。解题思路思路：动静布局先看题目，题目要求在给定的字符串中，求得字符串中有多少个回文子串。其中提及，不同开始或完结地位的子串，即使雷同也视为不同子串。 其实看完题目，咱们想到最间接的想法就是，先枚举字符的组合，判断这些字符组合成的子串是否是回文串即可。 当初咱们来看看，用这种间接的办法代码实现： class Solution: def countSubstrings(self, s: str) -> int: def is_palindrome(string): """判断传入字符串是否是回文串 """ left = 0 right = len(string) - 1 while left < right: if string[left] != string[right]: return False left += 1 right -= 1 return True # 计数 count = 0 # 枚举字符组合 for i in range(len(s)): for j in range(i, len(s)): # 判断字符组合是否是回文串 # 若是计数 +1，否则跳过 sub_string = s[i:j+1] if is_palindrome(sub_string): count += 1 return count下面的办法中，假如字符串长度为 n，咱们枚举所有子串须要 $O(n^2)$ 的工夫，而判断子串是否回文串须要 $O(S)$ 的工夫，S 是子串的长度，所以整个算法的工夫是 $O(n^3)$。 ...

110. 均衡二叉树题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/balanced-binary-tree 题目给定一个二叉树，判断它是否是高度均衡的二叉树。 本题中，一棵高度均衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回 true 。示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4返回 false 。解题思路思路：递归（自顶向下，自底向上）审题，题目要求给定的二叉树是否是高度均衡二叉树。对于高度均衡二叉树，题目给的定义是：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 也就是说，只有所有子树都是均衡二叉树的条件下，整个二叉树才是均衡二叉树。那么咱们用递归的思维来解决这个问题。 递归（自顶向下）在这里，咱们先用自顶向下的思路来去解决这个问题。 下面说了，要判断一个二叉树是否是均衡二叉树？要看所有子树是否都是均衡二叉树，那么这里须要比拟每个节点左右子树的高度差绝对值，不能超过 1。 那么，首先思考计算节点的高度 height，会有以下状况： 若以后节点为空节点，那么返回高度 0；若以后节点为非空节点，那么这里返回左右子树中的最大高度 + 1。而后，要思考的是如何去判断是否均衡？状况如下： 先解决非凡状况，如果根节点为空，间接返回 True；根节点非空，那么这里用先序遍历递归，对上面三种状况进行判断： 判断以后子树是否是均衡二叉树；判断以后子树的左子树是否是均衡二叉树；判断以后子树的右子树是否是均衡二叉树。具体的代码见【代码实现 # 递归（自顶向下）】 递归（自底向上）在下面 递归（自顶向下） 的办法中，会产生大量反复计算，工夫复杂度较高。 这里具体的做法如下： 设定终止条件： 越过叶子节点时，返回高度 0；若左右子树任一高度为 -1 的状况下，代表左右子树不均衡，间接返回 -1。（这里左右子树高度由上面的左右子树高度差绝对值是否超过 1 决定）如果以后节点左右子树的高度差的绝对值不超过 1 时，那么返回左右子树最大高度 +1；如果以后节点左右子树的高度差的绝对值超过 1 时，返回 -1，示意子树不均衡。具体的代码见【代码实现 # 递归（自底向上）】 ...

之前我做了一个视频， 介绍我的刷题浏览器扩大插件，视频地址：https://www.bilibili.com/vide...。 明天我在上次的根底上减少了局部公司的显示以及优化了若干体验性能。 这个刷题插件能做什么？当你在任意非题目详情页或者我还没有收录的题目详情页的时候， 我都会列出以后我总结的所有题解。 其实我给比拟经典的题目做了题解，因而这个题目数目不是很多，目前是 173 道题。另外有时候我间接写了专题，没有独自给每道题写题解，因而数量上要比 173 多很多。当你进到一个我写了题解的题目详情页的时候， 你就能够正式应用我的插件了。 它能够： 给出这道题目的前置常识。换句话说就是我须要先把握什么能力做出这道题。这个题目的关键点。哪些公司出了这道题。我切实不会了，给我看看题解吧。好，满足你。题解我就不看了，间接 show me code 吧。好，满足你。 我怎么能力获取呢？公众号《力扣加加》后盾回复刷题插件即可。 后盾收到的文件该如何装置呢？将下载的压缩包解压在 Chrome 浏览器的地址栏输出 chrome://extensions/点击 load uppack不晓得中文是什么名字，反正就是下面三个按钮最右边的。抉择你解压之后的文件夹 呈现上面这个就阐明你装置胜利了，点一下试试吧。 前期的布局是怎么样的？前期的性能打算先对 91 流动的用户开发。对于 91 流动，大家能够关注我的公众号《力扣加加》理解详情。更多公司信息。 继续欠缺题目的公司信息，这个过程须要大家的帮忙，大家能够把本人面试遇到的问题发给我（附带公司和岗位信息），我能够收费提供咨询服务。依据公司，查找题目。面试突击必备。岗位信息。 这个过程同样须要大家的帮忙，大家能够把本人面试遇到的问题发给我（附带公司和岗位信息），我能够收费提供咨询服务。 可视化调试。 可视化展现你的代码容许状况。 （一个双指针题目的可视化调试过程） 主动制订复习计划。AI 智能提醒。即新的提醒也能够依据题目信息揣测可能的解法。等等关注更新大家能够关注我的公众号， 如果插件有更新，会第一工夫在公众号同步的哦~ 想看题解能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858... 。 目前曾经 35K star 啦。 关注公众号力扣加加，致力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你辨认套路，高效刷题。 感激感激张震的爬虫脚本。感激羽飞 和 肠粉提供的公司信息

733. 图像渲染题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/flood-fill 题目有一幅以二维整数数组示意的图画，每一个整数示意该图画的像素值大小，数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 示意图像渲染开始的像素值（行 ，列）和一个新的色彩值 newColor，让你从新上色这幅图像。 为了实现上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标雷同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标雷同的相连像素点，……，反复该过程。将所有有记录的像素点的色彩值改为新的色彩值。 最初返回通过上色渲染后的图像。 示例 1: 输出:image = [[1,1,1],[1,1,0],[1,0,1]]sr = 1, sc = 1, newColor = 2输入: [[2,2,2],[2,2,0],[2,0,1]]解析:在图像的正中间，(坐标(sr,sc)=(1,1)),在门路上所有符合条件的像素点的色彩都被更改成2。留神，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。留神: image 和 image[0] 的长度在范畴 [1, 50] 内。给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。imagei 和 newColor 示意的色彩值在范畴 [0, 65535]内。解题思路思路：DFS、BFS先审题，题目要求是将某些符合条件的坐标点进行从新上色。这里这些坐标点合乎的定义为：间接或间接相邻的与起始坐标点色彩雷同的局部。 在题目中，明确说了从给定的初始坐标开始，往坐标点四个方位进行扩散，标记与初始坐标点色彩雷同的坐标，而后以这些标记的点持续扩散，反复直至完结，将所有标记的点都从新上色。 那么，咱们这里采纳深度优先搜寻和广度优先搜寻的模式来解决这个问题。 深度优先搜寻（DFS）首先，先看深度优先搜寻如何解决。具体的做法如下： 首先从给定的初始坐标点开始向四个方位扩散，进行遍历；每搜寻一个坐标，确定是否与初始坐标点色彩雷同。如果雷同，那么从新上色，避免从新搜寻陷入死循环；如果不同，不解决。反复直至所有符合条件的点都从新上色，返回从新上色后的图像。这里有个须要留神的中央，进行扩散的时候，依照下面的做法，会将初始坐标点进行从新上色。这个时候色彩的变动会影响后续。所以开始前用一个遍历存储初始坐标点的色彩。还有，给定的初始坐标点色彩，可能与新给定的色彩雷同，这样间接调用会先入死循环。这也是测试用例没通过留神到的。┑(￣ ￣)┍具体的代码见【代码实现 # 深度优先搜寻】 广度优先搜寻（BFS）在这里，咱们同样能够应用广度优先搜寻的思路来解决这个问题。上面看应用此办法的思路： 申明辅助队列，从初始坐标点开始，先将初始坐标点入队；出队，开始搜寻，当遇到与初始坐标点色彩雷同的点时，入队，同时将从新上色；循环直至队列为空，返回从新上色后的图像。同样留神初始坐标点色彩可能会被笼罩的问题。具体的代码见【代码实现 # 广度优先搜寻】 代码实现# 深度优先搜寻class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: # 先存储初始坐标点色彩 init_color = image[sr][sc] # 边界 m = len(image) n = len(image[0]) # 四个方位 directions = [(0, 1), (0, -1), (-1, 0),(1, 0)] def dfs(x, y): """进行深度优先搜寻 Args: x: 像素值（行） y: 像素值（列） """ if image[x][y] == init_color: # 如果遇到与初始坐标点色彩雷同的点，从新上色，开始扩散 image[x][y] = newColor for dx, dy in directions: nx = x + dx ny = y + dy # 限定边界 if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == init_color: dfs(nx, ny) # 留神: # 有可能一开始给定的初始坐标点的色彩与前面给定的新色彩是雷同的 # 间接调用会先入死循环，直至超出递归深度 if init_color != newColor: dfs(sr, sc) return image# 广度优先搜寻class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: # 先存储初始坐标点色彩 init_color = image[sr][sc] # 边界 m = len(image) n = len(image[0]) # 四个方位 directions = [(0, 1), (0, -1), (-1, 0),(1, 0)] def bfs(sr, sc): """进行深度优先搜寻 Args: sr: 像素值（行） sc: 像素值（列） """ # 申明辅助队列 from collections import deque queue = deque() # 入队 queue.append([sr, sc]) # 从新上色 image[sr][sc] = newColor # 出队，开始搜寻 while queue: x, y = queue.popleft() for dx, dy in directions: nx = x + dx ny = y + dy if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == init_color: # 当遇到与初始坐标点色彩雷同的，入队，并从新上色 queue.append([nx, ny]) image[nx][ny] = newColor if init_color != newColor: bfs(sr, sc) return image实现后果 ...

546. 移除盒子题目给出一些不同色彩的盒子，盒子的色彩由数字示意，即不同的数字示意不同的色彩。你将通过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你能够移除具备雷同色彩的间断 k 个盒子（k >= 1），这样一轮之后你将失去 k*k 个积分。当你将所有盒子都去掉之后，求你能取得的最大积分和。 示例： 输出：boxes = [1,3,2,2,2,3,4,3,1]输入：23解释：[1, 3, 2, 2, 2, 3, 4, 3, 1]----> [1, 3, 3, 4, 3, 1] (3*3=9 分)----> [1, 3, 3, 3, 1] (1*1=1 分)----> [1, 1] (3*3=9 分)----> [] (2*2=4 分)提醒： 1 <= boxes.length <= 1001 <= boxes[i] <= 100解题思路思路：动静布局首先先看题目，题目给定一组序列，外面不同的数字代表着不同色彩的盒子。题目要求移除盒子，求得序列为空，也就是移除掉所有盒子时能取得的最大积分。 在这里，积分的计算形式如下（移除盒子的操作次数不限）： 当移除的盒子是具备雷同色彩的，假如为 k（k>=1） 个，那么此时取得得积分为 k * k。 当初，咱们联合例子来看， 输出：boxes = [1,3,2,2,2,3,4,3,1]输入：23解释：[1, 3, 2, 2, 2, 3, 4, 3, 1]----> [1, 3, 3, 4, 3, 1] (3*3=9 分)----> [1, 3, 3, 3, 1] (1*1=1 分)----> [1, 1] (3*3=9 分)----> [] (2*2=4 分)这里大抵说下解释中的局部： ...

241 为运算表达式设计优先级给定一个含有数字和运算符的字符串，为表达式增加括号，扭转其运算优先级以求出不同的后果。你须要给出所有可能的组合的后果。无效的运算符号蕴含 +, - 以及 * 。示例 1: 输出: "2-1-1"输入: [0, 2]解释: ((2-1)-1) = 0 (2-(1-1)) = 2示例 2: 输出: "2*3-4*5"输入: [-34, -14, -10, -10, 10]解释: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10题解：分治 class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> res = new ArrayList<>(); if (input == null || input.length() == 0){ return res; } // 字符串全为数字时转化为数字并返回 int num = 0; // 思考是全数字的状况 int index = 0; while (index < input.length() && !isOperation(input.charAt(index))) { num = num * 10 + input.charAt(index) - '0'; index ++; } // 将全数字的状况间接返回 if (index == input.length()) { res.add(num); return res; } for(int i=0; i<input.length(); i++){ if (isOperation(input.charAt(i))){ List<Integer> res1 = diffWaysToCompute(input.substring(0,i)); List<Integer> res2 = diffWaysToCompute(input.substring(i+1)); for (int j = 0; j < res1.size(); j++){ for (int k = 0; k < res2.size(); k++){ num = calculate(res1.get(j), input.charAt(i), res2.get(k)); res.add(num); } } } } return res; } // 计算两个数的运算值 public int calculate(int num1, char op, int num2){ switch(op){ case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; } return -1; } public boolean isOperation(char ch){ return ch == '+' || ch == '-' || ch == '*'; }}递归分治优化：Map保留计算过的后果 ...

241 为运算表达式设计优先级给定一个含有数字和运算符的字符串，为表达式增加括号，扭转其运算优先级以求出不同的后果。你须要给出所有可能的组合的后果。无效的运算符号蕴含 +, - 以及 * 。示例 1: 输出: "2-1-1"输入: [0, 2]解释: ((2-1)-1) = 0 (2-(1-1)) = 2示例 2: 输出: "2*3-4*5"输入: [-34, -14, -10, -10, 10]解释: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10题解：分治 class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> res = new ArrayList<>(); if (input == null || input.length() == 0){ return res; } // 字符串全为数字时转化为数字并返回 int num = 0; // 思考是全数字的状况 int index = 0; while (index < input.length() && !isOperation(input.charAt(index))) { num = num * 10 + input.charAt(index) - '0'; index ++; } // 将全数字的状况间接返回 if (index == input.length()) { res.add(num); return res; } for(int i=0; i<input.length(); i++){ if (isOperation(input.charAt(i))){ List<Integer> res1 = diffWaysToCompute(input.substring(0,i)); List<Integer> res2 = diffWaysToCompute(input.substring(i+1)); for (int j = 0; j < res1.size(); j++){ for (int k = 0; k < res2.size(); k++){ num = calculate(res1.get(j), input.charAt(i), res2.get(k)); res.add(num); } } } } return res; } // 计算两个数的运算值 public int calculate(int num1, char op, int num2){ switch(op){ case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; } return -1; } public boolean isOperation(char ch){ return ch == '+' || ch == '-' || ch == '*'; }}递归分治优化：Map保留计算过的后果 ...

43. 字符串相乘题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/multiply-strings 题目给定两个以字符串模式示意的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也示意为字符串模式。 示例 1: 输出: num1 = "2", num2 = "3"输入: "6"示例 2: 输出: num1 = "123", num2 = "456"输入: "56088"阐明： num1 和 num2 的长度小于110。num1 和 num2 只蕴含数字 0-9。num1 和 num2 均不以零结尾，除非是数字 0 自身。不能应用任何规范库的大数类型（比方 BigInteger）或间接将输出转换为整数来解决。解题思路思路：竖式运算首先审题，题目要求的是乘积，那么咱们能够模仿竖式乘法来计算乘积。 这里先要留神一种状况，当 num1 和 num2 任意一个为 0 时，间接返回 0。 如果 num1 和 num2 都不为 0，那么咱们能够遍历 num2 每一位和 num1 进行相乘，而后将每次相乘的后果进行累加。（这其实就是咱们竖式乘法运算的思维）如下图示： 之前咱们曾遇到过 415. 字符串相加，咱们在后续的累加的局部能够间接应用此题的思维。还有一个须要留神的，除了 num2 最低位与 num1 的运算除外，其余位与 num1 的乘积都应该补 0。 ...

43. 字符串相乘题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/multiply-strings 题目给定两个以字符串模式示意的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也示意为字符串模式。 示例 1: 输出: num1 = "2", num2 = "3"输入: "6"示例 2: 输出: num1 = "123", num2 = "456"输入: "56088"阐明： num1 和 num2 的长度小于110。num1 和 num2 只蕴含数字 0-9。num1 和 num2 均不以零结尾，除非是数字 0 自身。不能应用任何规范库的大数类型（比方 BigInteger）或间接将输出转换为整数来解决。解题思路思路：竖式运算首先审题，题目要求的是乘积，那么咱们能够模仿竖式乘法来计算乘积。 这里先要留神一种状况，当 num1 和 num2 任意一个为 0 时，间接返回 0。 如果 num1 和 num2 都不为 0，那么咱们能够遍历 num2 每一位和 num1 进行相乘，而后将每次相乘的后果进行累加。（这其实就是咱们竖式乘法运算的思维）如下图示： 之前咱们曾遇到过 415. 字符串相加，咱们在后续的累加的局部能够间接应用此题的思维。还有一个须要留神的，除了 num2 最低位与 num1 的运算除外，其余位与 num1 的乘积都应该补 0。 ...

133. 克隆图题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/clone-graph 题目给你无向 连通 图中一个节点的援用，请你返回该图的 深拷贝（克隆）。 图中的每个节点都蕴含它的值 val（int） 和其街坊的列表（list[Node]）。 class Node { public int val; public List<Node> neighbo rs;}测试用例格局： 简略起见，每个节点的值都和它的索引雷同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中应用邻接列表示意。 邻接列表 是用于示意无限图的无序列表的汇合。每个列表都形容了图中节点的街坊集。 给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的援用返回。 示例 1： 输出：adjList = [[2,4],[1,3],[2,4],[1,3]]输入：[[2,4],[1,3],[2,4],[1,3]]解释：图中有 4 个节点。节点 1 的值是 1，它有两个街坊：节点 2 和 4 。节点 2 的值是 2，它有两个街坊：节点 1 和 3 。节点 3 的值是 3，它有两个街坊：节点 2 和 4 。节点 4 的值是 4，它有两个街坊：节点 1 和 3 。示例 2： ...

133. 克隆图题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/clone-graph 题目给你无向 连通 图中一个节点的援用，请你返回该图的 深拷贝（克隆）。 图中的每个节点都蕴含它的值 val（int） 和其街坊的列表（list[Node]）。 class Node { public int val; public List<Node> neighbo rs;}测试用例格局： 简略起见，每个节点的值都和它的索引雷同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中应用邻接列表示意。 邻接列表 是用于示意无限图的无序列表的汇合。每个列表都形容了图中节点的街坊集。 给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的援用返回。 示例 1： 输出：adjList = [[2,4],[1,3],[2,4],[1,3]]输入：[[2,4],[1,3],[2,4],[1,3]]解释：图中有 4 个节点。节点 1 的值是 1，它有两个街坊：节点 2 和 4 。节点 2 的值是 2，它有两个街坊：节点 1 和 3 。节点 3 的值是 3，它有两个街坊：节点 2 和 4 。节点 4 的值是 4，它有两个街坊：节点 1 和 3 。示例 2： ...

130. 被围绕的区域题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/surrounded-regions 题目给定一个二维的矩阵，蕴含 'X' 和 'O'（字母 O）。 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。 示例: X X X XX O O XX X O XX O X X运行你的函数后，矩阵变为： X X X XX X X XX X X XX O X X解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在程度或垂直方向相邻，则称它们是“相连”的。 解题思路思路：DFS、BFS首先先看题目，给定的二维矩阵中，蕴含 'X' 和 'O'（字母 O）。再看解释局部，任何边界上的 'O' 不会被填充为 'X'，那么当初也就是说，其实有三个局部： 可造成突围的 'X'；被 'X' 突围的 'O'；未被 'X' 突围的 'O'。当初题目的要求是将被突围的 'O'，转变为 'X'。后面也说了，未被突围的 'O'，是处于边界上的，同时侧面阐明与边界 'O' 相连的 'O' 又不会被 'X' 填充。 ...

二叉搜寻树广告： 最近github上新开了一个仓库May-Nodes，包含但不限于之前面试遇到的相干数据库,计算机操作系统,Java基础知识，计算机网络以及LeetCode等算法题解等常识。届时也会整顿学习应用的PDF文档与资源。有须要的小伙伴 能够点个关注和star。在继续更新中，总会遇到你想要的。前言首先明确二叉搜寻树系列的特殊性：二叉搜寻树(Binary Search Tree 简称为BST)，对于其的特点是任意节点的值都要大等于左子树所有节点的值，且要小于等于左边子树的所有节点的值。其左右子树的个性也就奠定了其在操作过程中就是有迹可循的。 两个根底的框架局部首先是二叉搜寻树的总的设计理念： void BinarySearch(TreeNode root){ if(root ...) // 进行系列的操作； BinarySearch(root.left); BinarySearch(root.right);}当然这个设计理念的思维就是说，咱们只管进行具体的递归操作，具体的操作咱们就能够参见是先序，中序还是后续而后做具体的操作，举个栗子：对于700-二叉搜寻树的搜寻，咱们只管进行左右子数的循环，其余的交给root去解决： public TreeNode searchBST(TreeNode root, int val) { if(root == null) return root; if(root.val == val) return root; else if(root.val> val) return searchBST(root.left,val); else return searchBST(root.right,val); }其上就是对二叉树只进行查问的操作，然而不波及到任何的批改操作，只须要简略判断即可，然而对于还有一部分的二叉搜寻树而言，咱们须要对左右子数进行简略的解决和判断： 举个栗子：判断一棵二叉树是否是对称的对称的二叉树，就须要对节点值进行判断解决（以下的思维也是在很多中央都可能用到的思维） 对于这类的题目来说，能够将逻辑块分成一个具体的函数，因为有的时候，咱们的逻辑块可能并没有具体的返回值，也有的时候，想要的最初的返回值喝逻辑块在运行中的返回值不同。对于这类的题目，个别都是判断是否相等，判断两颗树是否是相等的等，都是须要对树中的值进行对应的判断解决。 public boolean isSymmetric(TreeNode pRoot) { if(pRoot==null) return true; return issys(pRoot.left,pRoot.right); } private boolean issys(TreeNode l,TreeNode r){ if(l==null && r==null){ return true; // 次要是判断对于两颗树来说对应的节点是否都不存在，都不存在时候 示意不必比拟，就能够返回正常值。 } if(l==null ||r==null){ return false; // 示意本该对应的节点上，一个是null 一个却不是null 时候，返回一个谬误的值。 } if(l.val!=r.val) { return false; // 留神 这里该判断两者不相等 返回一个谬误值，而不是两者相等返回正确值 // 因为 若是呈现左右子数雷同时候 以后是正确的 然而若是咱们间接返回正确值 // 上面的状况 就有可能没方法失去正确的判断。 } return issys(l.left,r.right)&& issys(l.right,r.left); }具体示例简略实现版：以上就是具体的框架局部，一个实用于对值具体查找的判断，一个应用于节点的等值判断。 ...

93. 还原IP地址题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/restore-ip-addresses 题目给定一个只蕴含数字的字符串，还原它并返回所有可能的 IP 地址格局。 无效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。 示例: 输出: "25525511135"输入: ["255.255.11.135", "255.255.111.35"]解题思路思路： 回溯 先看题目，题目要求的是给定一个只蕴含数字的字符串，还原返回所有可能的 IP 地址格局。至于 IP 地址的无效格局，是由 4 个整数（0~255），整数间用 '.' 分隔组成。 首先，依据题目，借助示例来看下： s = "25525511135"假如，给定的字符串如下面示例，那么咱们在第一个片段中，咱们有三种抉择的可能： 选 '2'；选 '25'；选 '255'。当第一片段抉择结束后，后续的三个片段，也以同样的模式去抉择。然而咱们在抉择的过程中可能会出错，如果出错的话，此时咱们就须要撤销这项抉择，转而去尝试另外一个抉择。 同样的，这里咱们的抉择是有根据的，并非随便抉择。由题目，咱们也能够发现，每个片段可抉择的数字区间在 [0, 255] 之间，这里也示意长度不能超过 3。 这里还有个须要留神的，题目中并没有明确指出。每个片段中抉择的数字是不能有前导 0 的，0 能够作为一个抉择，然而不能呈现 '0...' 这样的模式，这个也是在测试用例没过的时候发现的。╮(╯▽╰)╭后面说了抉择以及限度，那咱们如何能力确认，当抉择结束之后，抉择组成的片段就是无效的？ 首先，要在后面所述的限度条件下进行抉择；再来，题目要求还原，也就是，咱们抉择完 4 个片段之后，必须是要用完所有字符的。如果抉择结束，然而没有用完字符，示意此项抉择不合乎，返回，回溯；如果先用完字符，然而没有找齐 4 个片段，同样回溯。因为还原的后果可能不止一种，当找到无效的组合，存入返回列表中，持续搜寻直至所有可能的抉择都尝试一次。具体的代码实现如下（含正文）。 代码实现class Solution: def restoreIpAddresses(self, s: str) -> List[str]: res = [] # 这里初始化长度为 4 的列表，别离存储对应 4 个片段 sub_res = [0] * 4 def dfs(seg_id, seg_first): # 先看找到 4 个片段的状况 # 这里可能呈现字符齐全应用，以及未应用齐全的状况 if seg_id == 4: # 应用齐全则增加到列表后返回 if seg_first == len(s): res.append('.'.join(str(seg)for seg in sub_res)) # 未齐全应用则间接返回 return # 若未找到 4 个片段，则持续查找 # 这里要留神未找到 4 个片段却应用完字符的状况 if seg_first == len(s): return # 不能存在前导 0，如果有 0，那么以后片段只能为独自 0 if s[seg_first] == "0": sub_res[seg_id] = 0 dfs(seg_id+1, seg_first+1) addr = 0 # 每个片段抉择的状况 for seg_last in range(seg_first, len(s)): # 这里用整型来示意，前面再转换为字符串类型，防止过于频繁的切片 addr = addr * 10 + (ord(s[seg_last]) - ord('0')) # 大于 0，但小于等于 255 的状况 if 0 < addr <= 255: sub_res[seg_id] = addr dfs(seg_id+1, seg_last+1) # 其余状况间接跳出循环 else: break dfs(0, 0) return res 实现后果 ...

93. 还原IP地址题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/restore-ip-addresses 题目给定一个只蕴含数字的字符串，还原它并返回所有可能的 IP 地址格局。 无效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。 示例: 输出: "25525511135"输入: ["255.255.11.135", "255.255.111.35"]解题思路思路： 回溯 先看题目，题目要求的是给定一个只蕴含数字的字符串，还原返回所有可能的 IP 地址格局。至于 IP 地址的无效格局，是由 4 个整数（0~255），整数间用 '.' 分隔组成。 首先，依据题目，借助示例来看下： s = "25525511135"假如，给定的字符串如下面示例，那么咱们在第一个片段中，咱们有三种抉择的可能： 选 '2'；选 '25'；选 '255'。当第一片段抉择结束后，后续的三个片段，也以同样的模式去抉择。然而咱们在抉择的过程中可能会出错，如果出错的话，此时咱们就须要撤销这项抉择，转而去尝试另外一个抉择。 同样的，这里咱们的抉择是有根据的，并非随便抉择。由题目，咱们也能够发现，每个片段可抉择的数字区间在 [0, 255] 之间，这里也示意长度不能超过 3。 这里还有个须要留神的，题目中并没有明确指出。每个片段中抉择的数字是不能有前导 0 的，0 能够作为一个抉择，然而不能呈现 '0...' 这样的模式，这个也是在测试用例没过的时候发现的。╮(╯▽╰)╭后面说了抉择以及限度，那咱们如何能力确认，当抉择结束之后，抉择组成的片段就是无效的？ 首先，要在后面所述的限度条件下进行抉择；再来，题目要求还原，也就是，咱们抉择完 4 个片段之后，必须是要用完所有字符的。如果抉择结束，然而没有用完字符，示意此项抉择不合乎，返回，回溯；如果先用完字符，然而没有找齐 4 个片段，同样回溯。因为还原的后果可能不止一种，当找到无效的组合，存入返回列表中，持续搜寻直至所有可能的抉择都尝试一次。具体的代码实现如下（含正文）。 代码实现class Solution: def restoreIpAddresses(self, s: str) -> List[str]: res = [] # 这里初始化长度为 4 的列表，别离存储对应 4 个片段 sub_res = [0] * 4 def dfs(seg_id, seg_first): # 先看找到 4 个片段的状况 # 这里可能呈现字符齐全应用，以及未应用齐全的状况 if seg_id == 4: # 应用齐全则增加到列表后返回 if seg_first == len(s): res.append('.'.join(str(seg)for seg in sub_res)) # 未齐全应用则间接返回 return # 若未找到 4 个片段，则持续查找 # 这里要留神未找到 4 个片段却应用完字符的状况 if seg_first == len(s): return # 不能存在前导 0，如果有 0，那么以后片段只能为独自 0 if s[seg_first] == "0": sub_res[seg_id] = 0 dfs(seg_id+1, seg_first+1) addr = 0 # 每个片段抉择的状况 for seg_last in range(seg_first, len(s)): # 这里用整型来示意，前面再转换为字符串类型，防止过于频繁的切片 addr = addr * 10 + (ord(s[seg_last]) - ord('0')) # 大于 0，但小于等于 255 的状况 if 0 < addr <= 255: sub_res[seg_id] = addr dfs(seg_id+1, seg_last+1) # 其余状况间接跳出循环 else: break dfs(0, 0) return res 实现后果 ...

给定一个蕴含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 形成的组合，这里的「相邻」要求两个 1 必须在程度或者竖直方向上相邻。你能够假如 grid 的四个边缘都被 0（代表水）突围着。 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。) 示例 1: [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]对于下面这个给定矩阵应返回 6。留神答案不应该是 11 ，因为岛屿只能蕴含程度或垂直的四个方向的 1 。 示例 2: [[0,0,0,0,0,0,0,0]]对于下面这个给定的矩阵, 返回 0。 留神: 给定的矩阵grid 的长度和宽度都不超过 50。 剖析： 咱们想晓得网格中每个连通形态的面积，而后取最大值。 如果咱们在一个土地上，以 4 个方向摸索与之相连的每一个土地（以及与这些土地相连的土地），那么摸索过的土地总数将是该连通形态的面积。 为了确保每个土地拜访不超过一次，咱们每次通过一块土地时，将这块土地的值置为 0。这样咱们就不会屡次拜访同一土地。 1.遍历grid失去每个地位岛屿????面积的最大值，返回一个maxArea2.搜寻函数-递归实现dfs函数3.判断边界，若不在边界内，返回0;否则为1，递归计算上下左右是否为1，area计算岛屿面积；4.判断完每个地位须要将其置0(gridi=0) 实现解法：var maxAreaOfIsland = function (grid) { var maxArea = 0; //记录保持者 for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) { if (grid[i][j] === 1) { maxArea = Math.max(maxArea, dfs(grid, i, j)); //更新记录 } } } function dfs(grid, i, j) { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) { return 0; //递归进口边界 } grid[i][j] = 0; //防止反复计算，沉岛策略 var area = 1; area += dfs(grid, i + 1, j); //下面的1 area += dfs(grid, i - 1, j); //上面的1 area += dfs(grid, i, j + 1); //右面的1 area += dfs(grid, i, j - 1); //右面的1 return area } return maxArea //返回最大面积};

给定一个蕴含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 形成的组合，这里的「相邻」要求两个 1 必须在程度或者竖直方向上相邻。你能够假如 grid 的四个边缘都被 0（代表水）突围着。 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。) 示例 1: [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]对于下面这个给定矩阵应返回 6。留神答案不应该是 11 ，因为岛屿只能蕴含程度或垂直的四个方向的 1 。 示例 2: [[0,0,0,0,0,0,0,0]]对于下面这个给定的矩阵, 返回 0。 留神: 给定的矩阵grid 的长度和宽度都不超过 50。 剖析： 咱们想晓得网格中每个连通形态的面积，而后取最大值。 如果咱们在一个土地上，以 4 个方向摸索与之相连的每一个土地（以及与这些土地相连的土地），那么摸索过的土地总数将是该连通形态的面积。 为了确保每个土地拜访不超过一次，咱们每次通过一块土地时，将这块土地的值置为 0。这样咱们就不会屡次拜访同一土地。 1.遍历grid失去每个地位岛屿????面积的最大值，返回一个maxArea2.搜寻函数-递归实现dfs函数3.判断边界，若不在边界内，返回0;否则为1，递归计算上下左右是否为1，area计算岛屿面积；4.判断完每个地位须要将其置0(gridi=0) 实现解法：var maxAreaOfIsland = function (grid) { var maxArea = 0; //记录保持者 for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) { if (grid[i][j] === 1) { maxArea = Math.max(maxArea, dfs(grid, i, j)); //更新记录 } } } function dfs(grid, i, j) { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) { return 0; //递归进口边界 } grid[i][j] = 0; //防止反复计算，沉岛策略 var area = 1; area += dfs(grid, i + 1, j); //下面的1 area += dfs(grid, i - 1, j); //上面的1 area += dfs(grid, i, j + 1); //右面的1 area += dfs(grid, i, j - 1); //右面的1 return area } return maxArea //返回最大面积};

99. 复原二叉搜寻树题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/recover-binary-search-tree 题目二叉搜寻树中的两个节点被谬误地替换。 请在不扭转其构造的状况下，复原这棵树。 示例 1: 输出: [1,3,null,null,2] 1 / 3 \ 2输入: [3,1,null,null,2] 3 / 1 \ 2示例 2: 输出: [3,1,4,null,null,2] 3 / \1 4 / 2输入: [2,1,4,null,null,3] 2 / \1 4 / 3进阶: 应用 O(n) 空间复杂度的解法很容易实现。你能想出一个只应用常数空间的解决方案吗？解题思路思路：中序遍历（递归），Morris算法题目中阐明，二叉搜寻树中的两个节点被谬误地替换，须要在不扭转构造的状况下复原二叉搜寻树。 咱们晓得，应用中序遍历二叉搜寻树时，失去的序列必然是递增的。如果二叉搜寻树的节点被谬误替换，那么应用中序遍历，就可能定位到谬误的节点。 假如有一个递增的序列 [1, 2, 3, 4]，如果咱们替换相邻的地位，比方 2 和 3，那么序列就会变为 [1, 3, 2, 4]。此时，这里会呈现一处谬误点，因为 3 > 2 不满足序列递增。如果咱们替换不相邻的地位，例如 1 和 4，那么序列就会变为 [4, 2, 3, 1]，此时，会呈现两个谬误点，4 > 2 和 3 > 1 不满足序列递增。 ...

99. 复原二叉搜寻树题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/recover-binary-search-tree 题目二叉搜寻树中的两个节点被谬误地替换。 请在不扭转其构造的状况下，复原这棵树。 示例 1: 输出: [1,3,null,null,2] 1 / 3 \ 2输入: [3,1,null,null,2] 3 / 1 \ 2示例 2: 输出: [3,1,4,null,null,2] 3 / \1 4 / 2输入: [2,1,4,null,null,3] 2 / \1 4 / 3进阶: 应用 O(n) 空间复杂度的解法很容易实现。你能想出一个只应用常数空间的解决方案吗？解题思路思路：中序遍历（递归），Morris算法题目中阐明，二叉搜寻树中的两个节点被谬误地替换，须要在不扭转构造的状况下复原二叉搜寻树。 咱们晓得，应用中序遍历二叉搜寻树时，失去的序列必然是递增的。如果二叉搜寻树的节点被谬误替换，那么应用中序遍历，就可能定位到谬误的节点。 假如有一个递增的序列 [1, 2, 3, 4]，如果咱们替换相邻的地位，比方 2 和 3，那么序列就会变为 [1, 3, 2, 4]。此时，这里会呈现一处谬误点，因为 3 > 2 不满足序列递增。如果咱们替换不相邻的地位，例如 1 和 4，那么序列就会变为 [4, 2, 3, 1]，此时，会呈现两个谬误点，4 > 2 和 3 > 1 不满足序列递增。 ...

在一个由 0 和 1 组成的二维矩阵内，找到只蕴含 1 的最大正方形，并返回其面积。示例:输出: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输入: 4动静布局法分析：咱们用 dp(i,j)dp(i, j)dp(i,j) 示意以 (i,j)(i, j)(i,j) 为右下角，且只蕴含 111 的正方形的边长最大值。如果咱们能计算出所有 dp(i,j)dp(i, j)dp(i,j) 的值，那么其中的最大值即为矩阵中只蕴含 111 的正方形的边长最大值，其平方即为最大正方形的面积。 如果该地位的值是 000，则 dp(i,j)=0dp(i, j) = 0dp(i,j)=0，因为以后地位不可能在由 111 组成的正方形中； 如果该地位的值是 111，则 dp(i,j)dp(i, j)dp(i,j) 的值由其上方、左方和左上方的三个相邻地位的 dpdpdp 值决定。具体而言，以后地位的元素值等于三个相邻地位的元素中的最小值加 111，状态转移方程如下： dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1 dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1 js解法： /** * @param {character[][]} matrix * @return {number} */var maximalSquare = function (matrix) { if (!matrix.length || !matrix[0].length) return 0 var maxSlideLen = 0, //记录最长边 dp = Array(matrix.length); //构建dp数组 for (var i = 0; i < matrix.length; i++) { dp[i] = Array(matrix[0].length).fill(0); //填充每一位为0 for (let j = 0; j < matrix[0].length; j++) { if (matrix[i][j] === 1) { if (i === 0 || j === 0) { dp[i][j] = 1; // 第一列和第一行的dp值为1 } else { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 //判断左上，左下，右上是否有0 } maxSlideLen = Math.max(maxSlideLen, dp[i][j]) //更新最大边长 } } } return maxSlideLen ** 2 //求最大边长面积};

在一个由 0 和 1 组成的二维矩阵内，找到只蕴含 1 的最大正方形，并返回其面积。示例:输出: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输入: 4动静布局法分析：咱们用 dp(i,j)dp(i, j)dp(i,j) 示意以 (i,j)(i, j)(i,j) 为右下角，且只蕴含 111 的正方形的边长最大值。如果咱们能计算出所有 dp(i,j)dp(i, j)dp(i,j) 的值，那么其中的最大值即为矩阵中只蕴含 111 的正方形的边长最大值，其平方即为最大正方形的面积。 如果该地位的值是 000，则 dp(i,j)=0dp(i, j) = 0dp(i,j)=0，因为以后地位不可能在由 111 组成的正方形中； 如果该地位的值是 111，则 dp(i,j)dp(i, j)dp(i,j) 的值由其上方、左方和左上方的三个相邻地位的 dpdpdp 值决定。具体而言，以后地位的元素值等于三个相邻地位的元素中的最小值加 111，状态转移方程如下： dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1 dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1 js解法： /** * @param {character[][]} matrix * @return {number} */var maximalSquare = function (matrix) { if (!matrix.length || !matrix[0].length) return 0 var maxSlideLen = 0, //记录最长边 dp = Array(matrix.length); //构建dp数组 for (var i = 0; i < matrix.length; i++) { dp[i] = Array(matrix[0].length).fill(0); //填充每一位为0 for (let j = 0; j < matrix[0].length; j++) { if (matrix[i][j] === 1) { if (i === 0 || j === 0) { dp[i][j] = 1; // 第一列和第一行的dp值为1 } else { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 //判断左上，左下，右上是否有0 } maxSlideLen = Math.max(maxSlideLen, dp[i][j]) //更新最大边长 } } } return maxSlideLen ** 2 //求最大边长面积};

本题次要在于对树这种数据结构的考查，以及深度优先遍历的应用，优化时能够采取空间换工夫的策略。<!-- more --> 原题给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0  到 n - 1 的 n 个节点组成，且恰好有 n - 1 条 edges 。树的根节点为节点 0 ，树上的每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ） 边数组 edges 以 edges[i] = [ai, bi] 的模式给出，该格局示意节点 ai 和 bi 之间存在一条边。 返回一个大小为 n 的数组，其中 ans[i] 示意第 i 个节点的子树中与节点 i 标签雷同的节点数。 树 T 中的子树是由 T 中的某个节点及其所有后辈节点组成的树。 示例 1： 输出：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"输入：[2,1,1,1,1,1,1]解释：节点 0 的标签为 'a' ，以 'a' 为根节点的子树中，节点 2 的标签也是 'a' ，因而答案为 2 。留神树中的每个节点都是这棵子树的一部分。节点 1 的标签为 'b' ，节点 1 的子树蕴含节点 1、4 和 5，然而节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点自身）。示例 2： ...

统计所有小于非负整数 n 的质数的数量。示例:输出: 10输入: 4解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。js暴力解法：/** * @param {number} n * @return {number} */var countPrimes = function(n) { var count = 0; function isPrime(num){ for(var i=2;i<=Math.sqrt(num);i++){ if(num%i===0) return false } return true } for(var j=2;j<n;j++){ if(isPrime(j)){ count++ } } return count};js埃拉托斯特尼筛法/** * @param {number} n * @return {number} */var countPrimes = function(n) { var count = 0; var times = Array(n).fill(0); for(var i =2;i<times.length;i++){ if(!times[i-1]){ count++; for(var j=i*i;j<=n;j+=i){ times[j-1]=true } } } return count};

100. 雷同的树题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/same-tree 题目给定两个二叉树，编写一个函数来测验它们是否雷同。 如果两个树在结构上雷同，并且节点具备雷同的值，则认为它们是雷同的。 示例 1: 输出: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3]输入: true示例 2: 输出: 1 1 / \ 2 2 [1,2], [1,null,2]输入: false示例 3: 输出: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2]输入: false解题思路由题意可知，若两个二叉树雷同，那么两个树在结构上雷同，并且节点具备雷同的值。那么，咱们能够通过深度优先搜寻（DFS）、广度优先搜寻（BFS）去判断两个二叉树是否雷同。 思路：DFS、BFS深度优先搜寻（DFS）应用深度优先搜寻，遇到的状况及剖析如下： 当两个二叉树都空时，那么能够断定两个二叉树雷同，返回 True；当两个二叉树其中一个为空，而另外一个不为空时，那么两个二叉树肯定不同的，返回 False；当两个二叉树都不为空的状况下，要对节点的值进行判断。别离对两个二叉树的根节点，以及根节点的左右子树的值进行判断。若呈现不同，则示意两个二叉树不同，返回 False，否则返回 True。具体的代码见【代码实现 # 深度优先搜寻】 广度优先搜寻（BFS）同样的，咱们也能够应用广度优先搜寻的办法来解决这个问题，这里咱们要借助辅助队列，算法具体的过程如下： 判断两个二叉树是否同时为空，若是，返回 True；判断两个二叉树是否其中一个为空，另一个不为空，若是，返回 False；当两个二叉树都不为空时，开始广度优先搜寻，这里应用队列，别离存储两个二叉树的节点： 初始先将两个二叉树的根节点别离放入队列中；出队，对出队的两个节点的值进行比拟： 当两个节点值不同，那么二叉树肯定不同；当两个节点值雷同，持续判断二叉树的构造是否雷同，也就是以后节点的子节点是否存在为空的状况。同时为空，断定为雷同，但当两个节点的子节点仅有一个为空，那么二叉树不同。当两个节点值雷同，构造也雷同时，将两个节点的非空子节点别离存入队列中。这里须要留神的是，存储时，如果子节点不为空，那么思考的程序都为从左到右。当后面的算法执行完结后，如果队列都为空，那么示意两个二叉树是雷同的；如果队列不都为空，那么表明二叉树的构造不同，也就是说两个二叉树不同。 具体的代码见【代码实现 # 广度优先搜寻】 代码实现# 深度优先搜寻# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: def dfs(p, q): # 两个二叉树都为空的状况 if p == None and q == None: return True # 两个二叉树只有一个为空的状况 elif p == None or q == None: return False # 二叉树都不为空的状况，比拟值 elif p.val == q.val: # 当根节点的值雷同时，往下持续判断左右子树的值 return dfs(p.left, q.left) and dfs(p.right, q.right) # 值不同，返回 False return False return dfs(p, q)# 广度优先搜寻# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: from collections import deque # 判断两个二叉树是否为空的状况 if not p and not q: return True elif not p or not q: return False # 都不为空的状况，应用队列，存储二叉树的节点 # 先将两个根节点入队 queue_p = deque([p]) queue_q = deque([q]) while queue_p and queue_q: node_p = queue_p.popleft() node_q = queue_q.popleft() # 比拟值 if node_p.val != node_q.val: return False # 比拟构造 left_p, right_p = node_p.left, node_p.right left_q, right_q = node_q.left, node_q.right # 这里应用异或，直接判断两个为空以及其中一个为空的状况 # ^ 雷同返回 0，否则返回 1 # 只有返回 1 的状况才会执行语句，也就是不同返回 False if (not left_p) ^ (not left_q): return False if (not right_p) ^ (not right_q): return False # 值与构造雷同时，当子节点非空，将子节点依照从左到右的程序入队 if left_p: queue_p.append(left_p) if right_p: queue_p.append(right_p) if left_q: queue_q.append(left_q) if right_q: queue_q.append(right_q) # 最初须要判断队列是否为空 # 如果队列不都为空，那么表明二叉树构造不同 return not queue_p and not queue_q实现后果 ...

336. 回文对题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/palindrome-pairs 题目给定一组惟一的单词， 找出所有不同的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j]，可拼接成回文串。 示例 1: 输出: ["abcd","dcba","lls","s","sssll"]输入: [[0,1],[1,0],[3,2],[2,4]]解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]示例 2: 输出: ["bat","tab","cat"]输入: [[0,1],[1,0]]解释: 可拼接成的回文串为 ["battab","tabbat"]解题思路思路：枚举，哈希表首先先看题目，题目中阐明给定的列表中单词惟一，判断是否存在不同索引的单词可能组成回文串？ 在示例中，咱们发现组成回文串的字符串长度并非肯定相等的。那么假如，当存在这样的两个字符串单词 a、b 时，a + b 是一个回文串，记录此时两个字符串的长度别离为 a_len、b_len。依据示例，咱们来分状况进行剖析： 当 a_len = b_len 时，那么 a 肯定是 b 的翻转；当 a_len > b_len 时，因为 b 的长度较小，那么这个时候要组成回文串，a 中必定有局部曾经是回文串。那么将 a 划分为前后 a1 和 a2 两局部，后面 a1 局部是 b 的翻转，而 a2 本身是回文串；当 a_len < b_len 时，这个状况其实是下面一种的背面。同样将 b 划分为前后 b1 和 b2 两个局部，b1 本身是回文串，而 b2 是 a 的翻转。从下面的剖析，咱们能够发现，拆解的都是长度较长的字符串。那么，咱们当初能够尝试枚举每个字符串 i，将其认为是较长的字符串，那么咱们当初将其拆分 i1 和 i2。那么这里将会有两种状况： ...

337. 打家劫舍 III题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/house-robber-iii 题目在上次打劫完一条街道之后和一圈屋宇后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，咱们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪慧的小偷意识到“这个中央的所有屋宇的排列相似于一棵二叉树”。 如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警。 计算在不触动警报的状况下，小偷一晚可能盗取的最高金额。 示例 1: 输出: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1输入: 7 解释: 小偷一晚可能盗取的最高金额 = 3 + 3 + 1 = 7.示例 2: 输出: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1输入: 9解释: 小偷一晚可能盗取的最高金额 = 4 + 5 = 9.解题思路这道题是 【198. 打家劫舍】、【213. 打家劫舍 II】 的后续思路：递归、动静布局在这道题当中，偷窃的对象不再是一条街或者围成圈的屋宇。而是看似二叉树排布的屋宇。在这里，咱们会用动静布局的办法来解决。 不过在此之前，咱们先看题目，【如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警】，这里的意思是，不可能偷窃相连的两个节点，也就是不能同时偷窃属于父子关系的节点。 题目给定的二叉树中，节点上的权值也就是要偷窃的金额，依照下面的条件，也就是说，每个节点都有两种状态：已偷取、未偷取。因为不能同时偷窃属于父子关系的节点，求该条件限定下，能偷取的金额最大值为多少。 递归在这里，咱们先用递归的办法来解决，这里依据下面的剖析，分状况来探讨，具体思路如下（基于三层的二叉树形容）： 当偷窃根节点时，则无奈偷窃根节点下的左右子节点，然而能够抉择投左右子节点下的子树。当不偷窃根节点时，则能够思考偷窃根节点下的左右子节点。那么，大抵的代码如下： # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def rob(self, root: TreeNode) -> int: if not root: return 0 # 分状况 # 偷窃根节点 与 不偷窃根节点 in_root = root.val if root.left: # 偷窃根节点时，无奈偷取子节点，那么偷窃子孙节点 in_root += self.rob(root.left.left) +self. rob(root.left.right) if root.right: in_root += self.rob(root.right.left) +self. rob(root.right.right) # 不偷取根节点，那么收益就是左右子节点权值的总和 not_in_root = self.rob(root.left) + self.rob(root.right) # 返回大值 return max(in_root, not_in_root)下面这段代码执行后超时，因为在计算子孙节点的时候，计算了根节点下的左右子树，而后续计算又反复计算了子孙节点。在这里，咱们来进行优化，将计算后的后果存储到哈希表中，遇到须要反复计算的局部，间接拿过去，不须要再次递归计算。 ...

337. 打家劫舍 III题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/house-robber-iii 题目在上次打劫完一条街道之后和一圈屋宇后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，咱们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪慧的小偷意识到“这个中央的所有屋宇的排列相似于一棵二叉树”。 如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警。 计算在不触动警报的状况下，小偷一晚可能盗取的最高金额。 示例 1: 输出: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1输入: 7 解释: 小偷一晚可能盗取的最高金额 = 3 + 3 + 1 = 7.示例 2: 输出: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1输入: 9解释: 小偷一晚可能盗取的最高金额 = 4 + 5 = 9.解题思路这道题是 【198. 打家劫舍】、【213. 打家劫舍 II】 的后续思路：递归、动静布局在这道题当中，偷窃的对象不再是一条街或者围成圈的屋宇。而是看似二叉树排布的屋宇。在这里，咱们会用动静布局的办法来解决。 不过在此之前，咱们先看题目，【如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警】，这里的意思是，不可能偷窃相连的两个节点，也就是不能同时偷窃属于父子关系的节点。 题目给定的二叉树中，节点上的权值也就是要偷窃的金额，依照下面的条件，也就是说，每个节点都有两种状态：已偷取、未偷取。因为不能同时偷窃属于父子关系的节点，求该条件限定下，能偷取的金额最大值为多少。 递归在这里，咱们先用递归的办法来解决，这里依据下面的剖析，分状况来探讨，具体思路如下（基于三层的二叉树形容）： 当偷窃根节点时，则无奈偷窃根节点下的左右子节点，然而能够抉择投左右子节点下的子树。当不偷窃根节点时，则能够思考偷窃根节点下的左右子节点。那么，大抵的代码如下： # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def rob(self, root: TreeNode) -> int: if not root: return 0 # 分状况 # 偷窃根节点 与 不偷窃根节点 in_root = root.val if root.left: # 偷窃根节点时，无奈偷取子节点，那么偷窃子孙节点 in_root += self.rob(root.left.left) +self. rob(root.left.right) if root.right: in_root += self.rob(root.right.left) +self. rob(root.right.right) # 不偷取根节点，那么收益就是左右子节点权值的总和 not_in_root = self.rob(root.left) + self.rob(root.right) # 返回大值 return max(in_root, not_in_root)下面这段代码执行后超时，因为在计算子孙节点的时候，计算了根节点下的左右子树，而后续计算又反复计算了子孙节点。在这里，咱们来进行优化，将计算后的后果存储到哈希表中，遇到须要反复计算的局部，间接拿过去，不须要再次递归计算。 ...

207. 课程表题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/course-schedule 题目你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。 在选修某些课程之前须要一些先修课程。 例如，想要学习课程 0 ，你须要先实现课程 1 ，咱们用一个匹配来示意他们：[0,1] 给定课程总量以及它们的先决条件，请你判断是否可能实现所有课程的学习？ 示例 1: 输出: 2, [[1,0]]输入: true解释: 总共有 2 门课程。学习课程 1 之前，你须要实现课程 0。所以这是可能的。示例 2: 输出: 2, [[1,0],[0,1]]输入: false解释: 总共有 2 门课程。学习课程 1 之前，你须要先实现课程 0；并且学习课程 0 之前，你还应先实现课程 1。这是不可能的。提醒： 输出的先决条件是由 边缘列表 示意的图形，而不是 邻接矩阵 。详情请参见图的表示法。你能够假设输出的先决条件中没有反复的边。1 <= numCourses <= 10^5解题思路思路：拓扑排序（BFS，DFS）其实，这是一道经典的【拓扑排序】问题。首先先审题，联合示例 1 和示例 2，咱们其实能够看到，其实题目问的是给定输出先决条件示意的图形（也就是课程表）是否是有向无环图。也是说，当确定先决条件之后，图形不能存在环，否则不成立。 有向无环图（DAG）：指的一个有向图从任意顶点登程无奈通过若干条边回到该点，则该图是一个有向无环图。 有向无环图，详细信息可由下方入口进行理解https://en.wikipedia.org/wiki/Directed_acyclic_graph （维基百科：有向无环图）https://baike.baidu.com/item/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE/10972513?fr=aladdin （百度百科：有向无环图）那么当要求课程安顿图是否是有向无环图时，咱们用拓扑排序来判断。拓扑排序：将图所有顶点进行排序成线性序列，使得图中任意一个有向边 uv，u 在线性序列中呈现在 v 后面。 拓扑排序，详细信息可由下方入口进行理解https://en.wikipedia.org/wiki/Topological_sorting （维基百科：拓扑排序）https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807?fr=aladdin （百度百科：拓扑排序）在题目中的提醒中有阐明，输出的先决条件时由 边缘列表 示意，在这里，咱们要将此转换为 邻接表。 ...

207. 课程表题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/course-schedule 题目你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。 在选修某些课程之前须要一些先修课程。 例如，想要学习课程 0 ，你须要先实现课程 1 ，咱们用一个匹配来示意他们：[0,1] 给定课程总量以及它们的先决条件，请你判断是否可能实现所有课程的学习？ 示例 1: 输出: 2, [[1,0]]输入: true解释: 总共有 2 门课程。学习课程 1 之前，你须要实现课程 0。所以这是可能的。示例 2: 输出: 2, [[1,0],[0,1]]输入: false解释: 总共有 2 门课程。学习课程 1 之前，你须要先实现课程 0；并且学习课程 0 之前，你还应先实现课程 1。这是不可能的。提醒： 输出的先决条件是由 边缘列表 示意的图形，而不是 邻接矩阵 。详情请参见图的表示法。你能够假设输出的先决条件中没有反复的边。1 <= numCourses <= 10^5解题思路思路：拓扑排序（BFS，DFS）其实，这是一道经典的【拓扑排序】问题。首先先审题，联合示例 1 和示例 2，咱们其实能够看到，其实题目问的是给定输出先决条件示意的图形（也就是课程表）是否是有向无环图。也是说，当确定先决条件之后，图形不能存在环，否则不成立。 有向无环图（DAG）：指的一个有向图从任意顶点登程无奈通过若干条边回到该点，则该图是一个有向无环图。 有向无环图，详细信息可由下方入口进行理解https://en.wikipedia.org/wiki/Directed_acyclic_graph （维基百科：有向无环图）https://baike.baidu.com/item/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE/10972513?fr=aladdin （百度百科：有向无环图）那么当要求课程安顿图是否是有向无环图时，咱们用拓扑排序来判断。拓扑排序：将图所有顶点进行排序成线性序列，使得图中任意一个有向边 uv，u 在线性序列中呈现在 v 后面。 拓扑排序，详细信息可由下方入口进行理解https://en.wikipedia.org/wiki/Topological_sorting （维基百科：拓扑排序）https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807?fr=aladdin （百度百科：拓扑排序）在题目中的提醒中有阐明，输出的先决条件时由 边缘列表 示意，在这里，咱们要将此转换为 邻接表。 ...

114. 二叉树开展为链表题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 题目给定一个二叉树，原地将它开展为一个单链表。 例如，给定二叉树 1 / \ 2 5 / \ \3 4 6将其开展为： 1 \ 2 \ 3 \ 4 \ 5 \ 6解题思路思路： 递归，非递归递归咱们先察看例子，能够发现，左子树开展成链表连贯在根节点，而右子树开展链表是紧跟在左子树开展的链表前面。这里应用递归的办法来解决。 应用后序遍历（递归）的具体做法： 先找到左子树的最右节点；当找到左子树的最右节点时，令其指向根的右子树；此时，再让根的右子树，指向根节点的左子树；最初，令根节点的左子树为 None，循环直至右子树为空。具体的代码见【代码实现 # 递归】 非递归在后面咱们晓得，其实递归的思路，应用了额定的空间。这里，咱们应用非递归的办法来尝试解决。（具体做法同上） 具体的代码见【代码实现 # 非递归】 代码实现# 递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ def unflod(node): if not node: return None unflod(node.left) unflod(node.right) # 后序遍历 if node.left: pre = node.left # 找到左子树的最右子节点，用以连贯根的右子树 while pre.right: pre = pre.right # 当找到左子树的最右子节点，令其指向根的右子树 pre.right = node.right # 而后令根的右子树指向根的左子树，令根的左子树为空 node.right = node.left node.left = None # 循环 node = node.right unflod(root)# 非递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ while root: if root.left: pre_node = root.left # 同样先找到左子树的最右节点 while pre_node.right: pre_node = pre_node.right # 最右节点指向根节点的右子树 pre_node.right = root.right # 根的右子树指向根的左子树，同时置空左子树 root.right = root.left root.left = None root = root.right实现后果实现后果 | 递归 ...

114. 二叉树开展为链表题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 题目给定一个二叉树，原地将它开展为一个单链表。 例如，给定二叉树 1 / \ 2 5 / \ \3 4 6将其开展为： 1 \ 2 \ 3 \ 4 \ 5 \ 6解题思路思路： 递归，非递归递归咱们先察看例子，能够发现，左子树开展成链表连贯在根节点，而右子树开展链表是紧跟在左子树开展的链表前面。这里应用递归的办法来解决。 应用后序遍历（递归）的具体做法： 先找到左子树的最右节点；当找到左子树的最右节点时，令其指向根的右子树；此时，再让根的右子树，指向根节点的左子树；最初，令根节点的左子树为 None，循环直至右子树为空。具体的代码见【代码实现 # 递归】 非递归在后面咱们晓得，其实递归的思路，应用了额定的空间。这里，咱们应用非递归的办法来尝试解决。（具体做法同上） 具体的代码见【代码实现 # 非递归】 代码实现# 递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ def unflod(node): if not node: return None unflod(node.left) unflod(node.right) # 后序遍历 if node.left: pre = node.left # 找到左子树的最右子节点，用以连贯根的右子树 while pre.right: pre = pre.right # 当找到左子树的最右子节点，令其指向根的右子树 pre.right = node.right # 而后令根的右子树指向根的左子树，令根的左子树为空 node.right = node.left node.left = None # 循环 node = node.right unflod(root)# 非递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ while root: if root.left: pre_node = root.left # 同样先找到左子树的最右节点 while pre_node.right: pre_node = pre_node.right # 最右节点指向根节点的右子树 pre_node.right = root.right # 根的右子树指向根的左子树，同时置空左子树 root.right = root.left root.left = None root = root.right实现后果实现后果 | 递归 ...

面试题 08.03. 魔术索引题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/magic-index-lcci 题目魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种办法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。 示例1: 输出：nums = [0, 2, 3, 4, 5] 输入：0 阐明: 0下标的元素为0示例2: 输出：nums = [1, 1, 1] 输入：1阐明: nums长度在[1, 1000000]之间此题为原书中的 Follow-up，即数组中可能蕴含反复元素的版本解题思路思路：剪枝，分治 这里先提一下，只是看本题的话，可能会有些争议，前面再解释。当初先审题，理清其中的关键点： 给定的数组是有序的（题目中只说有序，并未说是升序还是降序，这里联合示例，先默认是升序）；题目要求的魔术索引，即是满足条件 A[i] = i；数组中可能存在多个魔术索引，存在时，返回索引值最小的；不存在魔术索引，则返回 -1。当初，联合下面列举的关键点，能够发现数组有序（后面说了先默认升序），即便存在多个魔术索引，返回的也是最小索引的一个。那么当初能间接想到的就是间接遍历数组，当满足条件 nums[i]==i，间接返回即可，没有就返回 -1。相干代码大抵如下： class Solution: def findMagicIndex(self, nums: List[int]) -> int: for i in range(len(nums)): if nums[i] == i: return nums[i] return -1就后面开篇说的争议，略微吐槽下，当写完下面段代码时，总感觉事件没那么简略。前面去翻阅了官网题解下的评论，确实有很大的争议。这里大抵说下，只看本题的话，最直观的就是间接遍历，暴力法解决。能够回顾下题目，题目最初的阐明中提及到 【此题为原书中的 Follow-up，即数组中可能蕴含反复元素的版本】。 这里说的是此题是可能存在反复元素的版本，所以笔者也去翻阅了原题。查阅的后果是，原题是有两局部： 一个是给定数组升序，元素值各不相同，要求给定的数组中是否存在魔术索引；另一个是给定不降落序列，元素值可能雷同，求是否存在魔术索引。（也就是本题）而且题目中 阐明：思考是否存在一个复杂度优于 O(n) 的办法。 那么就当初就查阅的材料联合本题，进行开展阐明。 这里，在原题第一局部的根底上，从新来看这题。题目中阐明，【有可能存在多个魔术索引，元素可能反复】。那咱们将状况离开探讨： ...

343. 整数拆分题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/integer-break 题目给定一个正整数 n，将其拆分为至多两个正整数的和，并使这些整数的乘积最大化。 返回你能够取得的最大乘积。 示例 1: 输出: 2输入: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例 2: 输出: 10输入: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。阐明: 你能够假如 n 不小于 2 且不大于 58。解题思路思路：推导 这里，咱们用数学推导的办法，来尝试解决这个问题。先审题，题目中要咱们将数字 n 进行拆分，而后求拆分后数字乘积最大值。这里须要留神：题目中阐明 n 至多拆分为两个正整数。 由后面所述的题意，咱们可知，目前的问题就是如何拆分，能力使得乘积最大？这里举个例子，若将 1 个数拆分为 2 个数求乘积（均为正整数），咱们晓得，拆分的两个数字越靠近，那么乘积会越大。比拟合乎后面这段话的有：求矩形面积。咱们晓得，矩形当中，正方形面积最大。 那么，咱们先依照这个思路往下思考（后续在推导）。后面举例说的拆分为 2 个数字，这道题当中说的是至多两个正整数，那么依照后面所得出的推论，将数字 n 进行拆分，可能会呈现以下状况： 数字 n 进行拆分时，不肯定均分（因为题目要的拆分之后还是正整数）当下面的状况肯定存在时，那么将数字 n 进行拆分时，拆分的数字应该为多少最合适。下面的状况中，第一种比拟好了解。第二种状况，这里举个例子，例如给定的数字 n 为 6，那么： ...

343. 整数拆分题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/integer-break 题目给定一个正整数 n，将其拆分为至多两个正整数的和，并使这些整数的乘积最大化。 返回你能够取得的最大乘积。 示例 1: 输出: 2输入: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例 2: 输出: 10输入: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。阐明: 你能够假如 n 不小于 2 且不大于 58。解题思路思路：推导 这里，咱们用数学推导的办法，来尝试解决这个问题。先审题，题目中要咱们将数字 n 进行拆分，而后求拆分后数字乘积最大值。这里须要留神：题目中阐明 n 至多拆分为两个正整数。 由后面所述的题意，咱们可知，目前的问题就是如何拆分，能力使得乘积最大？这里举个例子，若将 1 个数拆分为 2 个数求乘积（均为正整数），咱们晓得，拆分的两个数字越靠近，那么乘积会越大。比拟合乎后面这段话的有：求矩形面积。咱们晓得，矩形当中，正方形面积最大。 那么，咱们先依照这个思路往下思考（后续在推导）。后面举例说的拆分为 2 个数字，这道题当中说的是至多两个正整数，那么依照后面所得出的推论，将数字 n 进行拆分，可能会呈现以下状况： 数字 n 进行拆分时，不肯定均分（因为题目要的拆分之后还是正整数）当下面的状况肯定存在时，那么将数字 n 进行拆分时，拆分的数字应该为多少最合适。下面的状况中，第一种比拟好了解。第二种状况，这里举个例子，例如给定的数字 n 为 6，那么： ...

LCP 13. 寻宝题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/xun-bao 题目咱们失去了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。 迷宫是一个二维矩阵，用一个字符串数组示意。它标识了惟一的入口（用 'S' 示意），和惟一的宝藏地点（用 'T' 示意）。然而，宝藏被一些荫蔽的机关爱护了起来。在地图上有若干个机关点（用 'M' 示意），只有所有机关均被触发，才能够拿到宝藏。 要放弃机关的触发，须要把一个重石放在下面。迷宫中有若干个石堆（用 'O' 示意），每个石堆都有有限个足够触发机关的重石。然而因为石头太重，咱们一次只能搬一个石头到指定地点。 迷宫中同样有一些墙壁（用 '#' 示意），咱们不能走入墙壁。残余的都是可随便通行的点（用 '.' 示意）。石堆、机关、终点和起点（无论是否能拿到宝藏）也是能够通行的。 咱们每步能够抉择向上/向下/向左/向右挪动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从终点开始，咱们起码须要多少步能力最初拿到宝藏呢？如果无奈拿到宝藏，返回 -1 。 示例 1： 输出： ["S#O", "M..", "M.T"]输入：16解释： 最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 咱们须要持续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。 示例 2： 输出： ["S#O", "M.#", "M.T"]输入：-1解释：咱们无奈搬到石头触发机关示例 3： 输出： ["S#O", "M.T", "M.."]输入：17解释：留神起点也是能够通行的。限度： ...

104. 二叉树的最大深度题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 题目给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长门路上的节点数。 阐明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。解题思路思路：递归、广度优先搜寻 题目中提醒，【二叉树的深度为根节点到最远叶子节点的最长门路上的节点数】。那么在这里，咱们思考从递归和广度优先搜寻的思路去解决此问题。上面先从递归的思路，对问题进行剖析解决。 递归依据题目的提醒，咱们晓得，二叉树的深度是跟它的左右子树的深度无关。 后面说，二叉树的深度是根节点到最远叶子节点的最长门路上的节点数，那么也就说当咱们失去左子树和右子树的最大深度时，只有取两者中较大深度的加上根节点的深度就是整个二叉树的深度。那么也就是说：二叉树的最大深度 = 左右子树最大深度较大的深度 + 根节点的高度。如上面的式子： max_depth = max(left_tree_depth, right_tree_depth) + 1 那么当初的问题就是如何去求左右子树的最大深度，在这里，两者的计算形式是雷同的。咱们能够递归去计算左右子树的最大深度，当遇到叶子节点时，退出递归。 具体的代码见【代码实现 # 递归】 广度优先搜寻这里，咱们也能够应用广度优先搜寻的思路来解决问题。在这里，咱们须要增加一个辅助队列。咱们将以后层的所有节点都存入这个辅助队列中。 在这里须要留神一点，当咱们筹备搜寻下一层时，这里须要将队列中以后层的所有节点都进行出队，而后让这些节点往上层搜寻。 那么，如果以后层的所有节点都入列，队列还非空，那么阐明下一层还有节点。循环直至队列为空，定义变量 depth，每层搜寻的时候保护更新该值，那么最终，depth 就是咱们要求的二叉树最大深度。 具体的代码见【代码实现 # 广度优先搜寻】 代码实现# 递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def maxDepth(self, root: TreeNode) -> int: # 终止条件 if not root: return 0 # 递归计算左右子树的最大深度 left_tree_depth = self.maxDepth(root.left) right_tree_depth = self.maxDepth(root.right) return max(left_tree_depth, right_tree_depth) + 1# 广度优先搜寻# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def maxDepth(self, root: TreeNode) -> int: # 解决非凡状况 if not root: return 0 from collections import deque # 辅助队列 queue = deque() # 记录二叉树深度，保护更新， depth = 0 queue.append(root) while queue: # 以后层所有节点出列，往下搜寻 size = len(queue) for i in range(size): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth += 1 return depth实现后果实现后果 # 递归 ...

104. 二叉树的最大深度题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 题目给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长门路上的节点数。 阐明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。解题思路思路：递归、广度优先搜寻 题目中提醒，【二叉树的深度为根节点到最远叶子节点的最长门路上的节点数】。那么在这里，咱们思考从递归和广度优先搜寻的思路去解决此问题。上面先从递归的思路，对问题进行剖析解决。 递归依据题目的提醒，咱们晓得，二叉树的深度是跟它的左右子树的深度无关。 后面说，二叉树的深度是根节点到最远叶子节点的最长门路上的节点数，那么也就说当咱们失去左子树和右子树的最大深度时，只有取两者中较大深度的加上根节点的深度就是整个二叉树的深度。那么也就是说：二叉树的最大深度 = 左右子树最大深度较大的深度 + 根节点的高度。如上面的式子： max_depth = max(left_tree_depth, right_tree_depth) + 1 那么当初的问题就是如何去求左右子树的最大深度，在这里，两者的计算形式是雷同的。咱们能够递归去计算左右子树的最大深度，当遇到叶子节点时，退出递归。 具体的代码见【代码实现 # 递归】 广度优先搜寻这里，咱们也能够应用广度优先搜寻的思路来解决问题。在这里，咱们须要增加一个辅助队列。咱们将以后层的所有节点都存入这个辅助队列中。 在这里须要留神一点，当咱们筹备搜寻下一层时，这里须要将队列中以后层的所有节点都进行出队，而后让这些节点往上层搜寻。 那么，如果以后层的所有节点都入列，队列还非空，那么阐明下一层还有节点。循环直至队列为空，定义变量 depth，每层搜寻的时候保护更新该值，那么最终，depth 就是咱们要求的二叉树最大深度。 具体的代码见【代码实现 # 广度优先搜寻】 代码实现# 递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def maxDepth(self, root: TreeNode) -> int: # 终止条件 if not root: return 0 # 递归计算左右子树的最大深度 left_tree_depth = self.maxDepth(root.left) right_tree_depth = self.maxDepth(root.right) return max(left_tree_depth, right_tree_depth) + 1# 广度优先搜寻# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def maxDepth(self, root: TreeNode) -> int: # 解决非凡状况 if not root: return 0 from collections import deque # 辅助队列 queue = deque() # 记录二叉树深度，保护更新， depth = 0 queue.append(root) while queue: # 以后层所有节点出列，往下搜寻 size = len(queue) for i in range(size): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth += 1 return depth实现后果实现后果 # 递归 ...

题目要求 思路： 遍历字符串，遇到空格替换因为字符串s长度可变，所以应用的是while循环，实时更新字符串的长度残缺代码：class Solution: def replaceSpace(self, s: str) -> str: cur, lenth = 0, len(s) while cur < lenth: if s[cur] == " ": s = s[:cur] + "%20" + s[cur + 1:] cur += 1 lenth = len(s) return s

392. 判断子序列题目起源：https://leetcode-cn.com/problems/is-subsequence/ 题目给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 你能够认为 s 和 t 中仅蕴含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 字符串的一个子序列是原始字符串删除一些（也能够不删除）字符而不扭转残余字符绝对地位造成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 示例 1: s = "abc", t = "ahbgdc"返回 true.示例 2: s = "axc", t = "ahbgdc"返回 false.后续挑战 : 如果有大量输出的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你须要顺次查看它们是否为 T 的子序列。在这种状况下，你会怎么扭转代码？ 解题思路思路：双指针、动静布局 在这里，先理清题目所提出的问题，题目要问的是，s 是否是 t 的子序列？而题目中定义这个子序列，是指不扭转绝对地位在原字符串中删除一些（或者不删除）字符残余的字符。 那么也就是说，只有能找到 s 在 t 中存在（绝对地位程序对应），那么能够认定 s 是 t 的子序列。例如，题目中所给出的示例，"ace" 是 "abcde" 的一个子序列，而 "aec" 不是。因为 "aec" 扭转了绝对地位的程序。 ...

392. 判断子序列题目起源：https://leetcode-cn.com/problems/is-subsequence/ 题目给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 你能够认为 s 和 t 中仅蕴含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 字符串的一个子序列是原始字符串删除一些（也能够不删除）字符而不扭转残余字符绝对地位造成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 示例 1: s = "abc", t = "ahbgdc"返回 true.示例 2: s = "axc", t = "ahbgdc"返回 false.后续挑战 : 如果有大量输出的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你须要顺次查看它们是否为 T 的子序列。在这种状况下，你会怎么扭转代码？ 解题思路思路：双指针、动静布局 在这里，先理清题目所提出的问题，题目要问的是，s 是否是 t 的子序列？而题目中定义这个子序列，是指不扭转绝对地位在原字符串中删除一些（或者不删除）字符残余的字符。 那么也就是说，只有能找到 s 在 t 中存在（绝对地位程序对应），那么能够认定 s 是 t 的子序列。例如，题目中所给出的示例，"ace" 是 "abcde" 的一个子序列，而 "aec" 不是。因为 "aec" 扭转了绝对地位的程序。 ...

19. 删除链表的倒数第N个节点141. 环形链表142. 环形链表 II160. 相交链表 19. 删除链表的倒数第N个节点题目形容 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.阐明：给定的 n 保障是无效的。 进阶：你能尝试应用一趟扫描实现吗？ 思路 设置两个指针, 第一个向走n步, 而后两个指针一起往前走, 当第一个指针达到链表开端时, 第二个指针刚好指向倒数第n个元素 def removeNthFromEnd(head, n): if n < 1 or head == None: return head p_fast = p_slow = head # 快指针先往前挪动n步 for i in range(n): p_fast = p_fast.next # 如果此时fast指针为None, 则要删除的节点为头节点 if p_fast == None: return head.next # 快慢指针同时后退 while p_fast.next != None: p_fast = p_fast.next p_slow = p_slow.next p_slow.next = p_slow.next.next return head工夫复杂度为$O(n)$, 空间复杂度为$O(1)$ ...

15. 三数之和16. 最靠近的三数之和18. 四数之和26. 删除排序数组中的反复项27. 移除元素75. 色彩分类88. 合并两个有序数组21. 合并两个有序链表剑指 Offer 21. 调整数组程序使奇数位于偶数后面 15. 三数之和给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不反复的三元组。 留神：答案中不能够蕴含反复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组汇合为：[ [-1, 0, 1], [-1, -1, 2]] 咱们仍然应用与两数之和相似的想法, 将三数之和转换为两数之和, 即首先须要固定第一个数, 而后去挪动其余两个数, 并且为了不便, 首先将数组进行排序. 具体思路如下 排序固定第一个数, 用p0示意. 应用另外两个指针p1, p2, 别离指向第一个数前面的元素和最初一个元素.当p0, p1, p2指向的元素之和大于0时, p2左移, 小于0时, p1右移, 否则, 将以后的3个元素增加到后果中. 当p1 = p2时, 完结循环. 回到第2步.依照上述的思路, 能够写出如下的代码 ...

15. 三数之和16. 最靠近的三数之和18. 四数之和26. 删除排序数组中的反复项27. 移除元素75. 色彩分类88. 合并两个有序数组21. 合并两个有序链表剑指 Offer 21. 调整数组程序使奇数位于偶数后面 15. 三数之和给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不反复的三元组。 留神：答案中不能够蕴含反复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组汇合为：[ [-1, 0, 1], [-1, -1, 2]] 咱们仍然应用与两数之和相似的想法, 将三数之和转换为两数之和, 即首先须要固定第一个数, 而后去挪动其余两个数, 并且为了不便, 首先将数组进行排序. 具体思路如下 排序固定第一个数, 用p0示意. 应用另外两个指针p1, p2, 别离指向第一个数前面的元素和最初一个元素.当p0, p1, p2指向的元素之和大于0时, p2左移, 小于0时, p1右移, 否则, 将以后的3个元素增加到后果中. 当p1 = p2时, 完结循环. 回到第2步.依照上述的思路, 能够写出如下的代码 ...

15. 三数之和16. 最靠近的三数之和18. 四数之和26. 删除排序数组中的反复项27. 移除元素75. 色彩分类88. 合并两个有序数组21. 合并两个有序链表剑指 Offer 21. 调整数组程序使奇数位于偶数后面 15. 三数之和给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不反复的三元组。 留神：答案中不能够蕴含反复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组汇合为：[ [-1, 0, 1], [-1, -1, 2]] 咱们仍然应用与两数之和相似的想法, 将三数之和转换为两数之和, 即首先须要固定第一个数, 而后去挪动其余两个数, 并且为了不便, 首先将数组进行排序. 具体思路如下 排序固定第一个数, 用p0示意. 应用另外两个指针p1, p2, 别离指向第一个数前面的元素和最初一个元素.当p0, p1, p2指向的元素之和大于0时, p2左移, 小于0时, p1右移, 否则, 将以后的3个元素增加到后果中. 当p1 = p2时, 完结循环. 回到第2步.依照上述的思路, 能够写出如下的代码 ...

力扣对于均衡二叉树的题目还是有一些的，并且都十分经典，举荐大家练习。明天给大家精选了 4 道题，如果你彻底搞明确了这几道题，碰到其余的均衡二叉树的题目应该不至于没有思路。当你体会了我的思路之后， 倡议再找几个题目练手，坚固一下学习成绩。 110. 均衡二叉树（简略）最简略的莫过于判断一个树是否为均衡二叉树了，咱们来看下。 题目形容给定一个二叉树，判断它是否是高度均衡的二叉树。本题中，一棵高度均衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例 1:给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4返回 false思路因为均衡二叉树定义为就是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。用伪代码形容就是： if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是均衡二叉树 and root.right 也是均衡二叉树: print('是均衡二叉树')else: print('不是均衡二叉树')而 root.left 和 root.right 如何判断是否是二叉均衡树就和 root 是一样的了，能够看出这个问题有显著的递归性。 因而咱们首先须要晓得如何计算一个子树的高度。这个能够通过递归的形式轻松地计算出来。计算子树高度的 Python 代码如下： def dfs(node, depth): if not node: return 0 l = dfs(node.left, depth + 1) r = dfs(node.right, depth + 1) return max(l, r) + 1代码代码反对： Python3 ...

力扣对于均衡二叉树的题目还是有一些的，并且都十分经典，举荐大家练习。明天给大家精选了 4 道题，如果你彻底搞明确了这几道题，碰到其余的均衡二叉树的题目应该不至于没有思路。当你体会了我的思路之后， 倡议再找几个题目练手，坚固一下学习成绩。 110. 均衡二叉树（简略）最简略的莫过于判断一个树是否为均衡二叉树了，咱们来看下。 题目形容给定一个二叉树，判断它是否是高度均衡的二叉树。本题中，一棵高度均衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例 1:给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4返回 false思路因为均衡二叉树定义为就是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。用伪代码形容就是： if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是均衡二叉树 and root.right 也是均衡二叉树: print('是均衡二叉树')else: print('不是均衡二叉树')而 root.left 和 root.right 如何判断是否是二叉均衡树就和 root 是一样的了，能够看出这个问题有显著的递归性。 因而咱们首先须要晓得如何计算一个子树的高度。这个能够通过递归的形式轻松地计算出来。计算子树高度的 Python 代码如下： def dfs(node, depth): if not node: return 0 l = dfs(node.left, depth + 1) r = dfs(node.right, depth + 1) return max(l, r) + 1代码代码反对： Python3 ...

力扣对于均衡二叉树的题目还是有一些的，并且都十分经典，举荐大家练习。明天给大家精选了 4 道题，如果你彻底搞明确了这几道题，碰到其余的均衡二叉树的题目应该不至于没有思路。当你体会了我的思路之后， 倡议再找几个题目练手，坚固一下学习成绩。 110. 均衡二叉树（简略）最简略的莫过于判断一个树是否为均衡二叉树了，咱们来看下。 题目形容给定一个二叉树，判断它是否是高度均衡的二叉树。本题中，一棵高度均衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例 1:给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4返回 false思路因为均衡二叉树定义为就是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。用伪代码形容就是： if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是均衡二叉树 and root.right 也是均衡二叉树: print('是均衡二叉树')else: print('不是均衡二叉树')而 root.left 和 root.right 如何判断是否是二叉均衡树就和 root 是一样的了，能够看出这个问题有显著的递归性。 因而咱们首先须要晓得如何计算一个子树的高度。这个能够通过递归的形式轻松地计算出来。计算子树高度的 Python 代码如下： def dfs(node, depth): if not node: return 0 l = dfs(node.left, depth + 1) r = dfs(node.right, depth + 1) return max(l, r) + 1代码代码反对： Python3 ...

1. 两数之和560. 和为K的子数组1248. 统计「柔美子数组」437. 门路总和 III 1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] 题目难度: Easy 对于第一次接触这种类型的题目的人而言, 最能想到的形式就是相似冒泡排序的暴力算法, 工夫复杂度为$O(n^2)$, 空间复杂度为$O(1)$. 但题目要求每一个元素只能应用一次, 显然下面的做法并不能满足要求, 那么怎么才能够每个元素只应用一次呢 回到最直观的想法, 咱们须要两两元素进行判断: nums[i] + nums[j] = target?, 如果每个元素只能应用一次, 换一种思路, nums[j] = target - nums[i], 能够想到将target - nums[i]提前保留下来 因为本题返回的是索引, 于是天然想到应用字典来保留, 后续只有判断nums[j]是否在字典中就能够了. 顺着思路, 能够写出如下的代码 def twoSum(self, nums: List[int], target: int) -> List[int]: if not nums or len(nums) < 2: return # 应用字典保留target - nums[i] prefix_sum = {} n = len(nums) for i in range(n): if nums[i] in prefix_sum: return [prefix_sum[nums[i]], i] prefix[target-nums[i]] = i工夫复杂度$O(n)$, 空间复杂度$O(n)$ ...

1025. 除数博弈题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/divisor-game 题目爱丽丝和鲍勃一起玩游戏，他们轮流口头。爱丽丝先手开局。 最后，黑板上有一个数字 N 。在每个玩家的回合，玩家须要执行以下操作： 选出任一 x，满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无奈执行这些操作，就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假如两个玩家都以最佳状态参加游戏。 示例 1： 输出：2输入：true解释：爱丽丝抉择 1，鲍勃无奈进行操作。示例 2： 输出：3输入：false解释：爱丽丝抉择 1，鲍勃也抉择 1，而后爱丽丝无奈进行操作。提醒： 1 <= N <= 1000解题思路思路：递推 在这里，咱们要从题目外面中找出法则。这里先将题目中游戏规则列举进去： 给定数字 N，任取一数 x（0 < x < N），且 N % x == 0；入选定后，用 N - x 代替本来的 N。在这里，依据下面的游戏规则，咱们先列举 N （1 <= N <= 1000） 不同取值状况下，会呈现怎么的后果： ...

64. 最小门路和题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/minimum-path-sum 题目给定一个蕴含非负整数的 m x n 网格，请找出一条从左上角到右下角的门路，使得门路上的数字总和为最小。 阐明：每次只能向下或者向右挪动一步。 示例: 输出:[ [1,3,1], [1,5,1], [4,2,1]]输入: 7解释: 因为门路 1→3→1→1→1 的总和最小。解题思路思路：动静布局 先审题，因为题目中阐明【每次只能向下或者向右挪动一步】。那么要达到起点，只能是从起点的上方或者左方达到。 状态定义设 dp[i][j] 为左上角登程达到地位 (i, j) 的最小门路和 状态转移方程后面提到，每次挪动只能是向下或者向右。对于第一行元素而言（也就是 i = 0 时），只能是从左往右进行挪动；对于每一列而言（也就是 j = 0 时），只能是从上往下挪动。此时状态转移方程为： $$\begin{aligned} dp[0][j] = dp[0][j-1] + grid[0][j], \qquad (i = 0\; and\; j > 0) \\ dp[i][0] = dp[i-1][0] + grid[i][0], \qquad (i > 0\; and\; j = 0)\end{aligned}$$ 对于不在第一行第一列的元素，达到地位 (i, j) 只能是从左方向右挪动达到或者上方向下挪动达到，此时转移方程为： $$\begin{aligned} dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j], \qquad (i > 0 \; and \; j > 0)\end{aligned}$$ ...

剑指 Offer 11. 旋转数组的最小数字题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 题目把一个数组最开始的若干个元素搬到数组的开端，咱们称之为数组的旋转。输出一个递增排序的数组的一个旋转，输入旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。   示例 1： 输出：[3,4,5,1,2]输入：1示例 2： 输出：[2,2,2,0,1]输入：0留神：本题与主站 154 题雷同：https://leetcode-cn.com/probl... 解题思路思路：二分查找 先审题，反复一下【旋转数组】的概念。在这里，旋转数组指的是将升序排列数组的后面若干个元素放到数组开端。 那么，依照这个概念，咱们能够发现。数组旋转后，会将原数组 nums 拆分成两个升序排序的数组，设为 nums1、nums2，而且被搁置在开端局部的数组 nums2 的元素会小于或等于后面局部的数组 nums1 的元素（这里会呈现等于，是因为元素可能反复，待会再剖析）。那么当初的问题就是如何找到旋转后两个升序的数组？因为只有找到旋转后的两个数组，nums2 数组中的首元素就是要求的答案。 那么，在这里，咱们能够思考应用二分查找的办法，找到一个分界点（这个分界点为搁置在开端升序数组的首元素），分界点右边的数组为 nums1，分界点左边（含分界点）的数组为 nums2。 具体的思路如下（上面内容中，呈现 nums1 示意旋转后右边升序数组， nums2 示意旋转后搁置开端的左边升序数组）： 首先，定义指针 left,right 别离指向 nums 数组的首尾两端，而 mid 为每次二分查找的中点；开始进行比拟（nums1 的元素大于或等于 nums2 的元素），这里会呈现以下三种状况： 如果 nums[mid] > nums[right] 时，那么 mid 肯定是 nums1 这个数组当中，此时分界点落在区间 (mid, right]，令 left=mid+1；如果 nums[mid] < nums[right] 时，那么 mid 则在 nums2 数组当中，此时分界点落在区间 [left, mid]，令 right=mid;如果 nums[mid] == nums[right]（这里是因为容许元素反复），这里就会呈现边界含糊的状况，先说论断（前面剖析），让 right 指针往前挪动，令 right -= 1。这里就 nums[mid] == nums[right] 的状况进行剖析，假如给定数组为 [1, 1, 0, 1] 和 [1, 0, 1, 1, 1]，那么会有如下的状况 ...

1.概述这篇blog来源于leetcode。加入了第198场周赛，后果比前几次周赛惨很多。不过没关系，及时发现了本人很菜，路漫漫其修远兮！这边blog次要是针对周赛第四题衍收回来的思考。次要包含RMQ问题以及本人思考题目标过程。价值不是很大，轻易写写。 2.RMQ问题RMQ（Range Minimum / Maximum Query ）次要是用来求区间最值问题钻研进去的算法。对于RMQ问题有很多办法能够求解，比方线段树，或者应用动静布局。对于动态区间的RMQ问题，应用DP是十分好了解的。上面咱们就来聊聊。举个简略的例子比方给定一个无序数组arr。求数组所有区间的最值。如果通过暴力枚举，必定会TLE。然而咱们很容易想到。对于一个大的区间[0,1]，咱们能够将其分为两个子区间:[0,1]和[2,3]。那么大区间的最值，其实能够通过两个子区间失去。 应用动静布局的思维大问题的后果依赖若干个子问题。 既然应用动静布局，咱们就须要列出状态转移方程。咱们令dpi示意：以第i个数为终点，间断2^j个数 的区间最值。比方dp2就是区间[2,3]的最值。3怎么来。其实就是2+2^1-1 ，减1时减掉第一个数。 接下来咱们考虑一下边界条件（对于动静布局，边界条件是解决问题的突破口）根据下面定义：dpi代表数组第i个数开始，间断一个数的区间的最值。间断一个数，其实就只有一个，就是他自身。 所以咱们失去,这里咱们假如数组arr 是从1开始。 dp[i][0]=arr[i];推导转移方程对于dpi，咱们如何做求值？ 其实能够将这个区间分为2局部。第一部分为dpi，第二局部为dpi+(1<<(j-1))。而后依赖两个区间的后果再求大区间的最值。大家看到这两个区间可能很懵逼。不焦急看，咱们一个一个来剖析。 首先是dpi，这个区间咱们应该很容易了解。就是以i开始，共2^(j-1)个数。其实就是以i开始，2^j的前半部分。因为2^(j-1)是2^j的一半。其次是dpi+(1<<(j-1))。这个看起来简单。但从上可知，这个示意的就是残余半个区间的最值。咱们依据dp的定义来推到一下。后半局部区间就是从前半个区间最初一个元素的后一个元素到区间开端。那么咱们就须要计算一下后半个区间的开始地位。其实就是大区间初始地位i+区间长度的一半。长度计算依赖j。所以就能够失去是i+(1<<(j-1))。这里的思维就是一分为2。前提是分进去的区间的后果是提前晓得的。 所以咱们能够失去状态转移方程(以区间最大值举例)： dp[i][j]= max {dp[i][j-1],dp[i+(1<<(j-1)][j-1]} 查问最值通过下面过程，咱们将最值计算出来，然而咱们如何获取后果呢？ 咱们假如len为要查问区间的长度。咱们log(len)也就是咱们dpi中j的长度。然而咱们并不能保障2^log(len)==len。因为len不肯定是2的整数幂。所以咱们并不能保障区间的完整性。 如果该长度正好是2的幂。那么没故障，后果为dpi，否则咱们会脱漏一些区间，如下图。那么如何解决问题呢？大家能够看到咱们能够应用dpi和dpr-(1<<k)+1。应用后者是为了补充咱们的脱漏。然而大家可能会放心有反复。然而如果是求最值问题，反复是不会影响后果的。所以，很ok。 3.较量题目剖析题目链接：https://leetcode-cn.com/probl... 题目剖析：咱们对函数剖析后，发现对于l<=r，他的后果是一个递加的序列。因为与运算。与的越多最终值越小。如果一个区间[l,r]按上述函数进行与。后果必定小于等于区间最小值。 既然是一个有序序列，咱们就能够应用二分。咱们枚举右边界。而后通过二分对区间求值并记录后果。工夫简单为nlog(n) 没错，开始我就是这么做的，然而： 看到这个，我就开始定位耗时。应该是在进行区间与运算的时候浪费时间。所以咱们须要进行优化。于是我想到了区间最值问题。与运算其实和其是一样的。比方同一个大的区间的与运算后果，咱们能够通过两个小区间的后果再进行与操作。 并且对于反复与雷同数字，后果是不会受影响的，这个比拟要害，因为咱们在查问区间最值的时候，会反复计算。 于是我用动静布局构建区间后果。最终解决了问题。 贴出代码RMQ动静布局代码实现 //RMQ问题代码type RMQ struct { Dp [][]int}func (rmq *RMQ) init(arr []int) { dp := make([][]int, len(arr)) rmq.Dp = dp for i := 0; i < len(arr); i++ { dp[i] = make([]int, 20) } //初始化条件。从i起的一个数（2^0）的最小值 就是该数。 for i := 1; i < len(arr); i++ { dp[i][0] = arr[i] } // for j := 1; (1 << j) < len(arr); j++ { for i := 1; i+(1<<(j-1)) < len(arr); i++ { //这里须要留神 为什么临界条件为i+(1<<(j-1)) < len(arr)。 //因为i会被j限度。 j越大。i能取的就越小。咱们只须要保障从i开始到完结的元素全笼罩就能够了。 //这里将范畴分成了两局部。 因为咱们基于2的幂。 其实就是参考二进制的性质。通过移位运算符能够进行二分。 dp[i][j] = rmq.withStrategy(i, j) } }}func (rmq *RMQ) withStrategy(i int, j int) int { return rmq.Dp[i][j-1] & rmq.Dp[i+(1<<(j-1))][j-1]}func (rmq *RMQ) withStrategyQuery(l int, r int, k int) int { return rmq.Dp[l][k] & rmq.Dp[r-(1<<k)+1][k]}func (rmq *RMQ) query(l int, r int) int { k := 0 for ; (1 << (k + 1)) <= r-l+1; k++ { } return rmq.withStrategyQuery(l, r, k)}算法逻辑（二分） ...

题目要求： 思路： 从左往右遍历两个字符串，如果遇到不同的字符，break从右往左遍历两个字符串，如果遇到不同的字符，break用左边不雷同的字符的下标-右边不雷同的字符的下标如果这两个字符串失去的两个差都小于1，返回True，否则返回False外围代码：left1 = 0 left2 = 0 while left1 < len(first) and left2 < len(second): if first[left1] == second[left2]: left1 += 1 left2 += 1 else: break right1 = len(first) - 1 right2 = len(second) - 1 while right1 >= 0 and right2 >= 0: if first[right1] == second[right2]: right1 -= 1 right2 -= 1 else: break return right1 - left1 < 1 and right2 - left2 < 1残缺代码：如果两个字符串雷同，间接返回Trueclass Solution: def oneEditAway(self, first: str, second: str) -> bool: if first == second: return True left1 = 0 left2 = 0 while left1 < len(first) and left2 < len(second): if first[left1] == second[left2]: left1 += 1 left2 += 1 else: break right1 = len(first) - 1 right2 = len(second) - 1 while right1 >= 0 and right2 >= 0: if first[right1] == second[right2]: right1 -= 1 right2 -= 1 else: break return right1 - left1 < 1 and right2 - left2 < 1

36. 无效的数独题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/valid-sudoku 题目判断一个 9x9 的数独是否无效。只须要依据以下规定，验证曾经填入的数字是否无效即可。 数字 1-9 在每一行只能呈现一次。数字 1-9 在每一列只能呈现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能呈现一次。 上图是一个局部填充的无效的数独。 数独局部空格内已填入了数字，空白格用 '.' 示意。 示例 1: 输出:[ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]]输入: true示例 2: 输出:[ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]]输入: false解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其余数字均与 示例1 雷同。 但因为位于左上角的 3x3 宫内有两个 8 存在, 因而这个数独是有效的。阐明: 一个无效的数独（局部已被填充）不肯定是可解的。只须要依据以上规定，验证曾经填入的数字是否无效即可。给定数独序列只蕴含数字 1-9 和字符 '.' 。给定数独永远是 9x9 模式的。解题思路思路：迭代，哈希表 先看数独无效的规定： 数字 1-9 在每一行只能呈现一次。数字 1-9 在每一列只能呈现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能呈现一次。那么咱们能够依据这个规定，遍历给定的数独三次，别离去判断每行，每列，每个 3x3 宫内是否有反复的数字。如果有反复的数字，能够间接返回 False；否则，直至遍历完结，返回 True。 ...

题目要求： 思路： 遍历数组，每当遇见一块海洋，把统计的海洋数量加一，并把这块海洋所有的1都变为0外围代码：res = 0cur = []# 遍历数组for i in range(len(grid)): for j in range(len(grid[0])): # 如果以后为海洋，把以后海洋变为0 if grid[i][j] == '1': # 留神是字符串 grid[i][j] = '0' # 把以后海洋的坐标退出到cur当中，因为要把这块海洋所有相邻的1都找到并变为0 cur.append((i,j)) while cur: # 取到这个点的下标 cur_i, cur_j = cur.pop(0) # 找它的上下左右 for x, y in [(1,0),(0,1),(-1,0),(0,-1)]: tmp_i = cur_i + x tmp_j = cur_j + y # 如果上下左右没有越界 if tmp_i >= 0 and tmp_i < len(grid) and tmp_j >= 0 and tmp_j < len(grid[0]): # 并且上下左右有是海洋的状况 if grid[tmp_i][tmp_j] == '1': # 把海洋变为0，并把这个海洋的下标退出到cur数组中，一会查看这个海洋四周是否还有海洋 grid[tmp_i][tmp_j] = '0' cur.append((tmp_i,tmp_j)) # 把统计的岛屿数量加一 res += 1 return res残缺代码：class Solution: def numIslands(self, grid: List[List[str]]) -> int: res = 0 cur = [] for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': grid[i][j] = '0' cur.append((i,j)) while cur: cur_i, cur_j = cur.pop(0) for x, y in [(1,0),(0,1),(-1,0),(0,-1)]: tmp_i = cur_i + x tmp_j = cur_j + y if tmp_i >= 0 and tmp_i < len(grid) and tmp_j >= 0 and tmp_j < len(grid[0]): if grid[tmp_i][tmp_j] == '1': grid[tmp_i][tmp_j] = '0' cur.append((tmp_i,tmp_j)) res += 1 return res

题目要求： 思路： 保护一个cur用来保留以后的烂橘子遍历一遍给定的数组，如果是烂橘子，把横纵坐标append到cur数组中定义一个time用来保留工夫应用while循环遍历cur，当cur中还有元素时，持续循环，cur中寄存的是烂橘子的数组下标，遍历这些烂橘子，遍历每个烂橘子的时候再遍历这个烂橘子的上下左右四个格子，如果有陈腐的橘子，把这个陈腐的橘子变为烂橘子，把这个新的烂橘子append到nex数组中遍历完结后，把nex数组赋给cur数组，把工夫+1，这时候cur中还有元素，所以持续while循环当cur中没有元素的时候，遍历grid数组，看数组中是否还有陈腐橘子，如果有，返回-1，如果没有，返回工夫time外围代码：cur = []for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 2: cur.append((i, j))# 初始化为-1，因为cur中最初一次遍历的时候保留了数组中最初有好橘子变成烂橘子的那些橘子，这些橘子还有遍历一次，然而曾经不会腐烂其余的橘子了time = -1while cur: nex = [] for i, j in cur: for x, y in [(0, -1), (-1, 0), (1, 0), (0, 1)]: tmp_i = i + x tmp_j = j + y # 判断一下边界 if tmp_i >= 0 and tmp_i < len(grid) and tmp_j >= 0 and tmp_j < len(grid[0]): if grid[tmp_i][tmp_j] == 1: grid[tmp_i][tmp_j] = 2 nex.append((tmp_i,tmp_j)) time += 1 cur = nexfor i in grid: if 1 in i: return -1return time残缺代码： ...

leetcode高级算法(字符串篇)注：点题目能够查看对应的题目，本文代码均应用Javascript编写。代码不肯定是最优解，仅供参考，如仁兄有更好的实现，欢送交换。 反转字符串解析：要原地扭转数组，第一次循环替换第一个和数组最初一个值，第二次替换第二个和数组倒数第二个值，顺次类推。每次替换两个值，循环数组长度的1/2次即可。其实用javascript内置办法reverse，一行代码就搞定了，然而这毕竟是算法题，不本人想进去也没啥必要练了。 代码： /** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */var reverseString = function(s) { var len = s.length; for(var i = 0; i < len / 2; i++){ var temp = s[i]; s[i] = s[len - 1 - i]; s[len - 1 - i] = temp; }};整数反转解析： 个位数，间接返回。十位数及以上，转换为字符串翻转后，判断是否溢出，不溢出加上符号位返回，溢出返回0。代码： /** * @param {number} x * @return {number} */var reverse = function(x) { var absX = Math.abs(x); // 取绝对值 // 个位数间接返回 if(absX >= 0 && absX <= 9){ return x; } var reverse = absX.toString().split('').reverse().join(''); // 转换成字符串数组，反转数字，在变回字符串 if(+reverse > 2 ** 31 - 1){ // 溢出返回0 return 0; }else{ // 加上原来的符号返回 if(x > 0){ return +reverse; }else{ return -reverse; } }};字符串中的第一个惟一字符解析：每次取一个字符和其余字符进行比拟，比拟完没有反复则返回索引，所有字符都比拟完都没有呈现不反复的，则返回-1。 ...

题目要求： 思路： 递归走到底，如果以后节点存在，那么把以后节点的左节点右节点调换返回上一层代码：# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def invertTree(self, root: TreeNode) -> TreeNode: self.helper(root) return root def helper(self, node): if node: self.helper(node.left) self.helper(node.right) node.left, node.right = node.right, node.left

题目要求： 思路： 构建一个二叉树，节点有以下属性：self.left = Noneself.right = Noneself.val = val # 节点值self.nodecount = 1 # 以后节点值呈现了多少次self.leftcount = 0 # 左子树节点数量从后往前遍历数组元素，如果以后的数组元素值与以后树节点值相等，那么把以后节点呈现的次数加一如果以后元素的值大于树节点的值，如果以后节点有右节点，持续比拟右节点，如果以后节点没有右节点，用以后的数组元素创立新的节点，插入到树中如果以后元素的值小于节点的值，如果以后节点有左节点，持续比拟左节点，如果以后的节点没有左节点，用以后的数组元素创立新的节点，插入到树中代码：class TreeNode(object): def __init__(self, val): self.left = None self.right = None self.val = val # 节点值 self.nodecount = 1 # 以后节点值呈现了多少次 self.leftcount = 0 # 左子树节点数量class Solution: def countSmaller(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n if n == 0 or n == 1: return res root = TreeNode(nums[-1]) for i in range(n - 2, -1, -1): res[i] = self.insertNode(root, nums[i]) return res # 往二叉搜寻树中插入新的节点 def insertNode(self, root, val): cur = root res = 0 while cur: if cur.val == val: cur.nodecount += 1 res += cur.leftcount break elif cur.val < val: res += cur.leftcount + cur.nodecount if cur.right: cur = cur.right else: cur.right = TreeNode(val) break else: cur.leftcount += 1 if cur.left: cur = cur.left else: cur.left = TreeNode(val) break return res残缺代码：class TreeNode(object): def __init__(self, val): self.left = None self.right = None self.val = val self.nodecount = 1 self.leftcount = 0 class Solution: def countSmaller(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n if n == 0 or n == 1: return res root = TreeNode(nums[-1]) for i in range(n - 2, -1, -1): res[i] = self.insertNode(root, nums[i]) return res def insertNode(self, root, val): cur = root res = 0 while cur: if cur.val == val: cur.nodecount += 1 res += cur.leftcount break elif cur.val < val: res += cur.leftcount + cur.nodecount if cur.right: cur = cur.right else: cur.right = TreeNode(val) break else: cur.leftcount += 1 if cur.left: cur = cur.left else: cur.left = TreeNode(val) break return res参考视频：LeetCode315 计算右侧小于以后元素的个数 BST解法

112. 路径总和题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/path-sum 题目给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 解题思路思路：递归、广度优先搜索 在这里先讲 递归，这个解法的思路是从根节点往下找，找到叶子节点。 先假设跟节点到当前节点的路径和为 val，那么将问题转变一下，是否能够找到从当前节点到叶子节点的路径和为 sum - val，这符合递归的性质。 那么也就是说从根节点往下找到叶子节点，如果确定当前节点是叶子节点，那么判断 sum 是否等于当前节点的 val 值即可。如果不是叶子节点，那么将继续向下查找。 具体的代码实现见【代码实现 # 递归】 同样的这道题中，我们也可以使用 广度优先搜索 的思路来解决。在这里我们使用队列，存储节点以及根节点到某个节点的路径和。 以题目所给示例，具体的实现过程如下图所示： 具体实现代码见【代码实现 # 广度优先搜索】 代码实现# 递归# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False if not root.left and not root.right: return sum == root.val return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)# 广度优先搜索# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False from collections import deque # 队列存储节点和路径和 queue = deque() queue.append((root, root.val)) while queue: # 出队，开始搜索 node, path = queue.popleft() # 如果叶子节点，路径和等于目标值时，直接返回 True if not node.left and not node.right and path == sum: return True if node.left: queue.append((node.left, path + node.left.val)) if node.right: queue.append((node.right, path + node.right.val)) return False实现结果递归 ...

题目要求： 思路： 如果抢第一个房屋，就不能抢最后一个房屋，抢最后一个房屋，就不能抢第一个房屋，所以把nums分为两种情况，一部分是nums[:-1]和nums[1:]，遍历这两个数组，再比较抢来的最高金额到达当前房屋能抢到的最大金额是，（抢当前房屋，那么就不能抢前一个房屋）和（不抢当前房屋，可以抢前一个房屋）也就是（当前房屋的金额+到前前个房屋抢来的最高金额）和（到前一个为止，抢到的最大金额）核心代码：pre1, cur1 = 0, 0for i in nums[:-1]: pre1, cur1 = cur1, max(pre1 + i, cur1)pre2, cur2 = 0, 0for j in nums[1:]: pre2, cur2 = cur2, max(pre2 + j, cur2)return max(cur1, cur2)完整代码： 如果数组为空，抢来的最高金额为0如果数组长度为1，那么抢来的最高金额为nums[0]class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) == 1: return nums[0] pre1, cur1 = 0, 0 for i in nums[:-1]: pre1, cur1 = cur1, max(pre1 + i, cur1) pre2, cur2 = 0, 0 for j in nums[1:]: pre2, cur2 = cur2, max(pre2 + j, cur2) return max(cur1, cur2)

题目要求： 思路： 递归把（sum - 当前节点的val）传给当前节点的左子树和右子树如果当前节点没有左子树，也没有右子树，而且sum为0，说明到达了一个叶子节点，而且到达这个叶子节点的路径中，有一条路径，这条路径上的所有节点值相加等于sum，返回True核心代码：# 如果root为空，说明yaoif not root: return Falseif root.val == sum and not root.left and not root.right: return True# 递归left = self.hasPathSum(root.left, sum - root.val)right = self.hasPathSum(root.right, sum - root.val)# left和right有一个为True，结果就为Truereturn left or right完整代码：# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False if root.val == sum and not root.left and not root.right: return True left = self.hasPathSum(root.left, sum - root.val) right = self.hasPathSum(root.right, sum - root.val) return left or right

题目给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 个人分析拿到题目的第一反应就是这是一个 regex 表达式解析引擎，但是过于复杂。 于是可以按照一定的顺序去实现。 下面来逐步看一下这个题目的解答过程。 v1 标准库实现版本代码public boolean isMatch(String s, String p) { return s.matches(p);}性能Runtime: 64 ms, faster than 24.57% of Java online submissions for Regular Expression Matching.Memory Usage: 40.3 MB, less than 7.95% of Java online submissions for Regular Expression Matching.虽然实现了，但是对于我们个人基本没有任何收益。 ...