题目:
思想:
分割每个单词,然后拼接到一起(123
拼接成123123
),再直接判断每个单词对应的下一个单词是否满足首尾相同即可。
代码:
1 | class Solution: |
分割每个单词,然后拼接到一起(123
拼接成123123
),再直接判断每个单词对应的下一个单词是否满足首尾相同即可。
1 | class Solution: |
一开始又读错题了,以为是将colsum
分成upper
和 lower
两个数组,
结果是将将colsum[i]
分成upper[i]
和 lower[i]
两个数。
并且upper[i]
和lower[i]
的和等于colsum[i]
。
在每一次的循环里,获取colsum
的值,然后判断0,1,2仨种情况,0直接不管,2的话平均分配。
1的话,直接给当前最小的那个数组。(这里我用的upper
和lower
本身的参数来记录剩余数字)。
在最开始的时候判断if sum(colsum) != upper + lower
, 最后判断if upper + lower != 0
。
At first, I misunderstood the question again, thinking that it was about dividing colsum
into two arrays, upper
and lower
. However, it turned out that it was about dividing colsum[i]
into two numbers, upper[i]
and lower[i]
. Additionally, the sum of upper[i]
and lower[i]
should be equal to colsum[i]
.
In each iteration, the value of colsum
is obtained, and then three scenarios, 0, 1, and 2, are considered. If it’s 0, it is ignored. If it’s 2, the values are evenly distributed. If it’s 1, it is assigned to the array with the current minimum value (using the remaining numbers in upper and lower than parameters).
At the beginning, it is checked whether if sum(colsum) != upper + lower
, and finally, it is checked whether if upper + lower != 0
.
1 | class Solution: |
“””
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node
的新值等于原树中大于或等于 node.val
的值之和。
提醒一下,二叉搜索树满足下列约束条件:
注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1:
输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:
输入:root = [0,null,1] 输出:[1,null,1]
示例 3:
输入:root = [1,0,2] 输出:[3,3,2]
示例 4:
输入:root = [3,2,4,1] 输出:[7,9,4,10]
提示:
0
和 104
之间。-104
和 104
之间。方法一:反序中序遍历
思路及算法
本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树,记录过程中的节点值之和,并不断更新当前遍历到的节点的节点值,即可得到题目要求的累加树。
方法二:Morris 遍历
思路及算法
有一种巧妙的方法可以在线性时间内,只占用常数空间来实现中序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出,因此被称为 Morris 遍历。
我们以一个简单的二叉树为例进行说明。假设我们要进行中序遍历的 Morris 遍历。
1 | 1 |
初始化当前节点为根节点(current = 1)。
当前节点不为空时,执行以下步骤:
当前节点的左子节点不为空。我们找到当前节点的前驱节点,也就是左子树中的最右节点。在这个例子中,前驱节点为节点5。
前驱节点的右子节点为空,将其右子节点指向当前节点(5 -> 1)。
将当前节点移动到其左子节点(current = 2)。
1 | 1 |
当前节点的左子节点不为空。我们找到当前节点的前驱节点,也就是左子树中的最右节点。在这个例子中,前驱节点为节点4。
前驱节点的右子节点为空,将其右子节点指向当前节点(4 -> 2)。
将当前节点移动到其左子节点(current = 4)。
1 | 1 |
当前节点的左子节点为空。输出当前节点的值(4)。
将当前节点移动到其右子节点(current = 5)。
当前节点的左子节点为空。输出当前节点的值(5)。
将当前节点移动到其右子节点(current = 2)。
1 | 1 |
当前节点的左子节点为空。输出当前节点的值(2)。
将当前节点移动到其右子节点(current = 1)。
1 | 1 |
当前节点的左子节点为空。输出当前节点的值(1)。
将当前节点移动到其右子节点(current = 3)。
1 | 1 |
当前节点的左子节点为空。输出当前节点的值(3)。
将当前节点移动到其右子节点(current = null)。
当前节点为空,遍历结束。
根据上述步骤,通过修改节点之间的指针关系,我们完成了对二叉树的中序遍历。
1 | class Solution: |
1 | class Solution: |
这类链表题目一般都是使用双指针法解决的,例如寻找距离尾部第 K 个节点、寻找环入口、寻找公共尾部入口等。
双指针第一次相遇: 设两指针 fast,slow 指向链表头部 head,fast 每轮走 2 步,slow 每轮走 1 步;
a. 第一种结果: fast 指针走过链表末端,说明链表无环,直接返回 null;
.TIPS: 若有环,两指针一定会相遇。因为每走 1 轮,fast 与 slow 的间距 +1,fast 终会追上 slow;
b. 第二种结果: 当fast == slow时, 两指针在环中 第一次相遇 。下面分析此时fast 与 slow走过的 步数关系 :
.设链表共有 a+b 个节点,其中 链表头部到链表入口 有 a 个节点(不计链表入口节点), 链表环 有 b 个节点(这里需要注意,a 和 b 是未知数,例如图解上链表 a=4 , b=5);设两指针分别走了 f,s 步,则有:
a. fast 走的步数是slow步数的 2 倍,即 f=2s;(解析: fast 每轮走 2 步)
b.fast 比 slow多走了 n 个环的长度,即 f=s+nb;( 解析: 双指针都走过 a 步,然后在环内绕圈直到重合,重合时 fast 比 slow 多走 环的长度整数倍 );
.以上两式相减得:f=2nb,s=nb,即fast和slow 指针分别走了 2n,n 个 环的周长 (注意: n 是未知数,不同链表的情况不同)。
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1 输出:[]
示例 3:
输入:head = [1,2], n = 1 输出:[1]
提示:
sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶:你能尝试使用一趟扫描实现吗?
采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。
我们可以设想假设设定了双指针 p 和 q 的话,当 q 指向末尾的 NULL,p 与 q 之间相隔的元素个数为 n 时,那么删除掉 p 的下一个指针就完成了要求。
设置虚拟节点 dummyHead 指向 head
设定双指针 p 和 q,初始都指向虚拟节点 dummyHead
移动 q,直到 p 与 q 之间相隔的元素个数为 n
同时移动 p 与 q,直到 q 指向的为 NULL
将 p 的下一个节点指向下下个节点
1 | class Solution: |
1 | class Solution { |
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
提示:
[0, 100]
内0 <= Node.val <= 100
用 head 表示原始链表的头节点,新的链表的第二个节点,用 newHead 表示新的链表的头节点,原始链表的第二个节点,则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next),表示将其余节点进行两两交换,交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head,即完成了所有节点的交换。最后返回新的链表的头节点 newHead。
1 | class Solution: |
1 | class Solution { |
给你一个整数 n
,以二进制字符串的形式返回该整数的 负二进制(base -2
)表示。
注意,除非字符串就是 "0"
,否则返回的字符串中不能含有前导零。
示例 1:
输入:n = 2 输出:"110" 解释:(-2)2 + (-2)1 = 2
示例 2:
输入:n = 3 输出:"111" 解释:(-2)2 + (-2)1 + (-2)0 = 3
示例 3:
输入:n = 4 输出:"100" 解释:(-2)2 = 4
提示:
0 <= n <= 109
我们可以判断 n 从低位到高位的每一位,如果该位为 1,那么答案的该位为 1,否则为 0。如果该位为 1,那么我们需要将 n 减去 k。接下来我们更新 n=⌊n/2⌋, k=−k。继续判断下一位。
最后,我们将答案反转后返回即可。
时间复杂度 O(logn),其中 n 为给定的整数。忽略答案的空间消耗,空间复杂度 O(1)。
1 | class Solution: |
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
已按 非递减顺序 排序
进阶:
O(n)
的算法解决本问题本来打算每一次计算完平方数后都自己写个插排的,结果超时了。忽略了sort的牛逼。
1 | class Solution: |
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其和 ≥ target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3]
是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4] 输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
O(n)
时间复杂度的解法, 请尝试设计一个 O(n log(n))
时间复杂度的解法。本来打算用双指针做,但是我的双指针超时了。
1 | class Solution: |
6351. 标记所有元素后数组的分数.md
给你一个数组 nums ,它包含若干正整数。
一开始分数 score = 0 ,请你按照下面算法求出最后分数:
从数组中选择最小且没有被标记的整数。如果有相等元素,选择下标最小的一个。
将选中的整数加到 score 中。
标记 被选中元素,如果有相邻元素,则同时标记 与它相邻的两个元素 。
重复此过程直到数组中所有元素都被标记。
请你返回执行上述算法后最后的分数。
示例 1:
输入:nums = [2,1,3,4,5,2]
输出:7
解释:我们按照如下步骤标记元素:
1 | class Solution: |
1 | class Solution: |