LouisLan的学习简记 👋🏼

题目地址 https://leetcode.com/problems/unique-binary-search-trees-ii/ 题目描述 Given an integer n , generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 思路 这道题是之前的 Unique Binary Search Trees 的延伸，之前那个只要求算出所有不同的二叉搜索树的个数，这道题让把那些二叉树都建立出来。这种建树问题一....

题目地址 https://leetcode.com/problems/binary-tree-inorder-traversal/ 题目描述 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 思路 二叉树的中序遍历顺序为左-根-右，可以有递归和非递归来解，其中非递归解法又分为两种，一种是使用栈来接，另一种不需要使用栈。我们先来看递归方法，十分直接，对左子结点调用递归函数，根节点访问值，右子节点再调用递归函数，代码如下： 解法一： class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> res; inorder(....

题目地址 https://leetcode.com/problems/restore-ip-addresses/ 题目描述 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 思路 这道题要求是复原 IP 地址，IP 地址对我们并不陌生，就算我们不是学 CS 的，只要我们是广大网友之一，就应该对其并不陌生。IP 地址由 32 位二进制数组成，为便于使用，常以 XXX.XXX.XXX.XXX 形式表现，每组 XXX 代表小于或等于 255 的 10 进制数。所以说 IP 地址总共有四段，每一段可能有一位，两位或者三位，范围是[0, 255]，题目明确指出输入字符串只含有数字，所以当某段是三位时，我们要判断其是否越界（>255)，还有一点很重要的是，当只有一位时，0 可以成某....

题目地址 https://leetcode.com/problems/reverse-linked-list-ii/ 题目描述 Reverse a linked list from position m to n. Do it in one-pass. **Note: **1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 思路 很奇怪为何没有倒置链表之一，就来了这个倒置链表之二，不过猜也能猜得到之一就是单纯的倒置整个链表，而这道作为延伸的地方就是倒置其中的某一小段。对于链表的问题，根据以往的经验一般都是要建一个 dummy node，连上原链表的头结点，这样的话就算头结点变动了，我们还可以通过 dummy->next 来获得新链表的头结点。这道题的要求是只通过一次遍历完成，就拿题目中的例子来说，变换的是 2,3,4 这三个点，我们需要找到第一个开始变换结点的前....

题目地址 https://leetcode.com/problems/decode-ways/ 题目描述 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). 思路 ....

题目地址 https://leetcode.com/problems/subsets-ii/ 题目描述 Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 思路 这道子集合之二是之前那道 Subsets 的延伸，这次输入数组允许有重复项，其他条件都不变，只需要在之前那道题解法的基础上稍加改动便可以做出来，我们先来看非递归解法，拿题目中的例子 [1 2 2] 来分析，根据之前 Subsets 里的分析可知，当处理到第一个 2 时，此时的子集合为 [], [1], [2], [1, 2]，而这时再处理第二个 2 时，如果在 [] 和 [1] 后直接加 2 会产....

题目地址 https://leetcode.com/problems/gray-code/ 题目描述 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. Example 1: Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2 For a given n, a gray code sequence may not be uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence....

题目地址 https://leetcode.com/problems/merge-sorted-array/ 题目描述 Given two sorted integer arrays nums1 and nums2 , merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n ) to hold additional elements from nums2. Example: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] 思路 混合插入有序数组，由于两个数组都是有序的，所有只要按顺序比较大小即可。题目中说....

题目地址 https://leetcode.com/problems/scramble-string/ 题目描述 Given a string s1 , we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great": great / \ gr eat / \ / \ g r e at / \ a t To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat". rgeat / \ rg eat / \ / \ r g e at / \....

题目地址 https://leetcode.com/problems/partition-list/ 题目描述 Given a linked list and a value x , partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. 思路 这道题要求我们划分链表，把所有小于给定值的节点都移到前面，大于该值的节点顺序不变，相当于一个局部排序的问题。那么可以想到的一种解法是首先找到第一个大于或等于给定值的节点，用题目中给的例子来说就是先找到 4，然后再找小于 3 的值，每找到一个....