LeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)
Home Page: https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/
License: Other
如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K（K 为非负整数）。
给定两个字母异位词 A 和 B ，返回 A 和 B 的相似度 K 的最小值。
示例 1：
输入：A = "ab", B = "ba"
输出：1
示例 2：
输入：A = "abc", B = "bca"
输出：2
示例 3：
输入：A = "abac", B = "baca"
输出：2
示例 4：
输入：A = "aabc", B = "abca"
输出：2
提示：
1 <= A.length == B.length <= 20
A 和 B 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-similar-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定一个长度为N的整数数组，只允许乘法，不能用除法。计算任意 N - 1 个数的组合中乘积最大的一组，并写出算法的时间复杂度。
In this problem, your solution has bug! When result contains index 0， if (visited[target - element]) will not be true!
I think you should update the code to below:
var twoNums = function(nums, target) {
const visited = {} // 记录出现的数字， 空间复杂度N
for (let index = 0; index < nums.length; index++) {
const element = nums[index];
if (visited[target - element] !== void 0) {
return [visited[target - element], index]
}
visited[element] = index;
}
return []
}
在思路的heading下, 现在有思路概要和图形演示,
提议分成三个部分:
1, 思路概要
2, 图形演示
3, pseudocodes
从序列的第一个元素依次相加，记作tmpSum，每当tmpSum<0，则清零。
tmpSum的最大值即为问题的解。
大概这样：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int tmpSum = 0;
for (int i = 0; i< nums.size(); i ++){
tmpSum += nums[i];
if (tmpSum > ans) ans = tmpSum;
if (tmpSum < 0) tmpSum = 0;
}
return ans;
}
};给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。
一个点的坐标（x，y）由一个有两个整数的整数数组表示。
示例:
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
注意:
所有输入整数都在 [-10000，10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角（90度角）。
输入点没有顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
今日的每日一题来一个leetcode题目， 《105. 从前序与中序遍历序列构造二叉树》
题目描述：
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
题目链接： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
left_str = ['(','[','{']
right_str = [')',']','}']
arr = []
input = input('请输入字符串:')
for i in input:
if i in left_str:
arr.append(i)
elif i in right_str:
if len(arr) > 0 and arr.pop() == left_str[right_str.index(i)]:
msg = 'ok'
continue
else:
msg = 'error'
else:
msg = 'wrong chacter'
break;
print(msg)
求取数组中最大连续子序列和，例如给定数组为 A = [1， 3， -2， 4， -5]， 则最大连续子序列和为 6，即 1 + 3 +（-2）+ 4 = 6。
去
首先我们来明确一下题意。
比如：
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。
输出：按升序排列的输入整数的列表。
约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。
一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/relative-sort-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
下面的问题，可以用小学三年级的方法解决，也可以使用初中方程式的方法解决，还可以使用大学的高级编程语言解决。请尝试使用所有方法解决，并进行比较。
有这样一个乘法算式：
人过大佛寺 * 我 = 寺佛大过人
这里的每一个字代表一个数字，不同的字代表不同的数字，你能把这些数字都找出来么？
输入N，利用random()函数，生成一个1至N的全排列。
例如：当输入N = 4,生成结果可以为1324或3214等等，并保证等概率
要求：
空间复杂度 o(n)
时间复杂度越少越好。
一次只需要生成一次随机的全排列，每次可能都不一样。
来源 算法导论
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：
N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/friend-circles
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
虽然所有题目都给出了解法，但是时间-空间复杂度都有待进一步优化。希望能共同努力。
In the file: leetcode/problems/169.majority-element.md
"假如没有题干中约束“majority”出现的次数小于2/n，投票算法就失效了"
改为
“majority”出现的次数大于n/2”？
能不能找出一个九位数，这个数包含了1-9这九个数字，并且这九个数的前n位能被n整除，若这个数为abcdefghi，则ab可以被2整除，abc可以被3整除... abcdefghi可以被9整除。
请尽量优化你的复杂度，包括但不限于剪枝
编程语言有C/C++版的吗? 老哥
输入为
nums1: [1,2,3,0,0,0]
nums2: [2,5,6]
结果应该为：[1,2,2,3,5,6] , 而不是 [1,2,3,3,5,6]，图片有误
另外，题目中说的 nums1 的 size is greater or equal to m + n , 所以 current 初始值应该为 m + n - 1 而不是 nums1.length - 1，leetcode能跑过应该是没有 greater 的测试用例
可以方便留个微信号什么的吗？这是我的邮箱[email protected]
What is the difference between a Dictionary data structure and a HashTable?
大佬，我看了这个“2.addTwoNumbers”的JS解法，感觉比较绕，所以自己重写了一下，自己感觉更直白一点。总之，谢谢大佬的辛苦劳动，让我受益匪浅。tks。
let addTwoNumbers = function(l1, l2) {
if (l1 === null || l2 === null) return null
let dummyHead = new ListNode(0)
let cur1 = l1
let cur2 = l2
let cur = dummyHead
let carry = 0
while (cur1 !== null || cur2 !== null) {
let val1 = cur1 !== null ? cur1.val : 0
let val2 = cur2 !== null ? cur2.val : 0
let sum = val1 + val2 + carry
let newNode = new ListNode(sum % 10)
carry = sum >= 10 ? 1 : 0
cur.next = newNode
cur = cur.next
if (cur1 !== null) {
cur1 = cur1.next
}
if (cur2 !== null) {
cur2 = cur2.next
}
}
if (carry > 0) {
cur.next = new ListNode(carry)
}
return dummyHead.next
}Top Linked questions -> Top Liked questions
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
输出坐标的顺序不重要
m 和 n 都小于150
示例：
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
返回:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
今天的题编程之美和lc都有，这道题有多种解答，请尽量使用多种方法解决。
判断一个 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 形式的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。
如题
难度： 中等
标签 数组，动态规划
题目描述：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
求一个字符串首尾相等的最长子串，例如abcba，最长就是abcba
辅助栈不再只是一个中转站。
push时，先入栈。之后如果辅助栈为空，则依次把栈中元素弹出并放入辅助栈。
pop时，如果辅助栈不为空，则直接从辅助栈中弹出。反之如果辅助栈为空，则依次把栈中元素弹出放入辅助栈，然后再从辅助栈中弹出。
peek时，如果辅助栈不为空，则直接取辅助栈的栈顶元素。反之如果辅助栈为空，则依次把栈中元素弹出放入辅助栈，然后再取辅助栈的栈顶元素。
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
self.stack_helper = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack.append(x)
if not self.stack_helper:
while self.stack:
self.stack_helper.append(self.stack.pop())
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if not self.stack_helper:
while self.stack:
self.stack_helper.append(self.stack.pop())
return self.stack_helper.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if not self.stack_helper:
while self.stack:
self.stack_helper.append(self.stack.pop())
return self.stack_helper[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return not (self.stack or self.stack_helper)
视频连接打不开呀，三种括号那个问题
比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。
你可以假设版本字符串非空，并且只包含数字和 . 字符。
. 字符不代表小数点，而是用于分隔数字序列。
例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。
你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。
示例 1:
输入: version1 = "0.1", version2 = "1.1"
输出: -1
示例 2:
输入: version1 = "1.0.1", version2 = "1"
输出: 1
示例 3:
输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1
示例 4：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，“01” 和 “001” 表示相同的数字 “1”。
示例 5：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有第三级修订号，这意味着它的第三级修订号默认为 “0”。
提示：
版本字符串由以点 （.） 分隔的数字字符串组成。这个数字字符串可能有前导零。
版本字符串不以点开始或结束，并且其中不会有两个连续的点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/compare-version-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）
例如：
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
121.best-time-to-buy-and-sell-stock.md 是不是不对？
低点买入，高点卖出？
不是应该 1点买入；6点卖出么？
还是我理解错了？
一个K位的数N
(K≤2000，N≤1020)
找出一个比N大且最接近的数，这个数的每位之和与N相同，用代码实现之。
例如：0050 所求书数字为0104；112 所求数为121；
so that the problems order by this number
给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
回想一下：
叶节点 是二叉树中没有子节点的节点
树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
示例 1：
输入：root = [1,2,3]
输出：[1,2,3]
示例 2：
Explanation:
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".
输入：root = [1,2,3,4]
输出：[4]
示例 3：
输入：root = [1,2,3,4,5]
输出：[2,4,5]
提示：
给你的树中将有 1 到 1000 个节点。
树中每个节点的值都在 1 到 1000 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。请设计程序算出结果，那种计算机语言不限。
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
某种药方要求非常严格，你每天需要同时服用A、B两种药片各一颗，不能多也不能少。这种药非常贵，你不希望有任何一点的浪费。一天，你打开装药片A的药瓶，倒出一粒药片放在手心;然后打开另一个药瓶，但不小心倒出了两粒药片。现在，你手心上有一颗药片A，两颗药片B，并且你无法区别哪个是A，哪个是B。你如何才能严格遵循药方服用药片，并且不能有任何的浪费?
提示：药片可以破坏，比如二等分，三等分。。。
我们经常碰到一个问题，就是需要在一个数组中求最大值或者最小值。如果我们要同时取出最大最小值呢？
常见的做法是扫描一次数字，然后分别和当然最大值和当前最小值进行比对，因此总的比较次数是2N，
其中N为数组的长度。
那么有没有办法减少比较次数呢？
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.