- 博客(108)
- 收藏
- 关注
RSS订阅原创 git多账户跨平台管理
git 的配置分system, global, local三个等级，global在用户目录 ～/.gitconfig里面，可以配置当前用户的所有仓库，local在某个仓库的repository/.git/config里面，只对当前repository有效。Windows系统里面，每行结尾用回车(CR)+换行(LF)，Linux系统中每行结尾用换行(LF)，这样会出现本来代码没有动，但是git显示有改动的情况。另外，我们通常一台电脑只有一个用户，这个时候你可以设置global 用户和邮箱。
2023-06-13 18:03:32
134
原创 leetcode 917 仅仅反转字母
s 仅由 ASCII 值在范围 [33, 122] 的字符组成。输入：s = “Test1ng-Leet=code-Q!输出：“Qedo1ct-eeLg=ntse-T!输入：s = “a-bC-dEf-ghIj”所有英文字母（小写或大写）位置反转。输出：“j-Ih-gfE-dCba”所有非英文字母保留在原有位置。输入：s = “ab-cd”s 不含 ‘"’ 或 ‘\’输出：“dc-ba”
2023-04-07 11:57:09
370
原创 leetcode 1092. 最短公共超序列
当 f[i][j]=f[i−1][j−1]+1 且 s1[i-1]=s2[j-1] 时，此时它们为 LCS 中的字符，将其追加到具体方案，并让 i 和 j 同时前移；当 f[i][j]=f[i-1][j-1]，s1[i-1]或s2[j-1] 随便一个追加到答案中，令i j同时前移；当 f[i][j]=f[i−1][j]，s1[i-1]为特有字符，将 s1[i-1] 追加到答案中，令 i 前移；当 f[i][j]=f[i][j-1]，s2[j-1]为特有字符，将 s2[j-1] 追加到答案中，令 j 前移；
2023-03-20 14:18:24
403
原创 leetcode 2111 使数组K递增的最少操作次数
但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]），对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4]。输入：arr = [4,1,5,2,6,2], k = 2。
2023-03-20 14:05:53
289
原创 leetcode 1458 两个子序列的最大点积
在选择了这一对数字之后，前面还有[0:i]和[0:j]可以选择，前面的元素的最大点积即为 f[i−1][j−1]， 因此目前为 f[i−1][j−1]+xij。如果我们没有都选择nums1[i] 以及nums2[j] ，如果扔掉nums1[i], 则最大点积即为 f[i−1][j], 如果扔掉nums2[j], 则最大点积即为 f[i][j-1], 如果都扔掉，则最大点积就是 f[i-1][j-1]f[0][0] 和 f[0][] 和 f[][0]时间复杂度和空间复杂度都是O(mn)
2023-03-20 13:51:10
260
原创 leetcode 1911 最大子序列交替和
1.1 如果选择nums[i]且形成偶数长度的子序列，即对应even[i]，那么不选的时候就是奇数，要让even[i]呈现出最大交替和，不选的时候的奇数子序列最大交替和也必须是最大的，即even[i] = odd[i-1] - nums[i]1.2 如果选择nums[i]且形成奇数长度的子序列，即对应odd[i]，那么不选的时候就是偶数，要让odd[i]呈现出最大交替和，不选的时候的偶数子序列最大交替和也必须是最大的，即odd[i] = even[i-1] + nums[i]
2023-03-18 23:07:27
392
原创 leetcode 583 两个字符串的删除操作
为了使删除操作的次数最少，剩下的字符应尽可能多。因此 dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1)假设字符串word1和word2的长度分别为m 和 n，创建dp, dp[i][j] 表示使word1前面i个字符word[0:i] 和 word2前面j个字符word2[0:j] 相同的最少删除操作次数。word1[0:i−1] 和 word2[0:j−1] 相同的最少删除操作次数，增加一个公共字符之后，最少删除操作次数不变，因此 dp[i][j]=dp[i−1][j−1]
2023-03-18 12:08:19
400
原创 leetcode 1218 最长定差子序列
令 dp[i] 表示以 arr[i] 为结尾的最长的等差子序列的长度，我们可以在 arr[i] 左侧找到满足 arr[j]=arr[i]−d 的元素，将 arr[i] 加到以 arr[j] 为结尾的最长的等差子序列的末尾，这样可以递推地从 dp[j] 计算出 dp[i]。输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2。输入：arr = [1,2,3,4], difference = 1。输入：arr = [1,3,5,7], difference = 1。
2023-03-17 16:28:59
376
原创 leetcode 673 最长递增子序列的个数
定义dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。dp[i]=max(dp[j])+1,其中0≤j
2023-03-17 14:35:14
238
原创 leetcode151 翻转字符串里的单词
给你一个字符串 s ，逐个翻转字符串中的所有 单词 。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。说明：输入字符串 s 可以在前面、后面或者单词间包含多余的空格。翻转后单词间应当仅用一个空格分隔。翻转后的字符串中不应包含额外的空格。示例 1：输入：s = “the sky is blue”输出：“blue is sky the”示例 2：输入：s = " hello world "输出：“worl
2022-06-09 18:14:16
78
原创 leetcode491 递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。示例 1：输入：nums = [4,6,7,7]输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2：输入：nums = [4,4,3,2,1]输出：[[4,4]]
2022-06-01 16:38:31
84
原创 leetcode 300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例 1：输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：输入：nums = [0,1,0,3,2,3]输出：4示例 3：输入：nums = [7,7,7,7,7,7,7
2022-05-31 17:31:59
92
原创 leetcode 718 最长公共子串
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。示例 1：输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]输出：3解释：长度最长的公共子数组是 [3,2,1] 。示例 2：输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]输出：5和子序列不一样的是‘abc’ 与’abd’最长公共子串为’ab’，长度为2，但是添加一位以后，‘abcd’与’abdd’即便最后一位相同，
2022-05-31 16:39:09
496
原创 leetcode 647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。示例 1：输入：s = “abc”输出：3解释：三个回文子串: “a”, “b”, “c”示例 2：输入：s = “aaa”输出：6解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”状态：dp[i][j] 表示字
2022-05-31 15:24:16
69
原创 leetcode 1143 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。示例 1：输入：text1 = “abcde”, text2 = “ace”
2022-05-20 13:35:55
141
1
原创 堆的python实现
from binary_tree import Nodeclass PerfectBinaryTree(Node): def is_empty(self): if not self.item: return True def add_one(self, data): if self.is_empty(): self.item = data return queue
2022-05-20 09:55:08
197
原创 二叉树的python实现
二叉class Node(object): def __init__(self, item=None, lchild=None, rchild=None): self.item = item self.lchild = lchild self.rchild = rchilddef build_tree1(preorder, inorder): if len(preorder) == 0: return None
2022-05-20 09:51:42
272
原创 leetcode392 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。进阶：如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？致谢：特别感谢 @pbrother 添加此问题并且创建所有测试用例。示例 1：输入：s = “abc”, t
2022-05-19 14:57:32
98
原创 leetcode 125 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: “A man, a plan, a canal: Panama”输出: true解释：“amanaplanacanalpanama” 是回文串示例 2:输入: “race a car”输出: false解释：“raceacar” 不是回文串class Solution(object): def isPalindrome(self, s)
2022-05-19 11:28:00
76
原创 单链表的python实现_无头结点
无头结点的单链表class ListNode(object): def __init__(self, value=0, next=None): self.value = value self.next = nextdef BuildListNode(l: list): if not l: return None head = ListNode(l[0]) temp = head for elem in l[1:]
2022-05-18 19:00:52
283
原创 链表的python实现_带头结点
单链表的增删改查class ListNode(object): def __init__(self, value=0, next=None): self.value = value self.next = nextdef BuildListNode(l: list): head = ListNode() temp = head for elem in l: temp.next = ListNode(elem)
2022-05-18 18:56:53
430
原创 插入排序算法
def insertion_sort_v2(nums): n = len(nums) # 从第二个数开始往后遍历 for i in range(1, n, 1): # 加速方法： 既然i-1之前的所有元素都是有序的，如果i比i-1的大，则不用多次一举从前到后了 # 只有i比i-1对应的元素小，才需要与前面的比较 if nums[i-1] <= nums[i]: continue temp
2022-04-21 09:45:38
318
原创 leetcode 1 twosum
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]使用查找表记录元素的值与...
2022-03-31 09:14:46
44
原创 二分查找法
由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是O（logN） ，二分查找的条件是查找范围不为空，即left<=right 。class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 while left <= right: mid = (rig
2022-03-26 16:43:30
5509
原创 leetcode 230 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。输入：root = [3,1,4,null,2], k = 1输出：1因为二叉搜索树和中序遍历的性质，所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是，我们可以通过中序遍历找到第 k 个最小元素。# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, lef
2022-03-26 16:28:40
700
原创 leetcode112 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。叶子节点 是指没有子节点的节点。输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true解释：等于目标和的根节点到叶节点路径如上图所示。广度优先记录从根节点到当前节点的路径和
2022-03-22 15:45:21
523
原创 leetcode 111 二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。首先可以想到使用后序深度优先搜索的方法，对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。时间复杂度O(n)， n为节点个数， 空间复杂度O(logn）取决于栈空间# Definition for a binary tree node.# class TreeNode:# def __in
2022-03-21 22:49:11
502
原创 leetcode231 2的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。示例 1：输入：n = 1输出：true解释：20 = 1示例 2：输入：n = 16输出：true解释：24 = 16示例 3：输入：n = 3输出：false示例 4：输入：n = 4输出：true示例 5：输入：n = 5输出：false思路与算法一个数n是 2的幂，当且仅当 n是正整
2022-03-16 12:56:06
307
原创 leetcode394 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。示例 1：输入：s = “3[a]2[bc]”输出：“aaabcbc”示例 2：输入：s = “3[
2022-03-16 10:31:43
92
原创 leetcode 680 验证回文字符串II
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: s = “aba”输出: true示例 2:输入: s = “abca”输出: true解释: 你可以删除c字符。示例 3:输入: s = “abc”输出: false首先判断原始字符串是否是回文串，如果是，就返回 True, 用双指针的时间复杂度O(n)；如果不是，则枚举每一个位置作为被删除的位置，再判断剩下的字符串是否是回文串。这种做法的渐进时间复杂度是n-1 + n-2+ …1=n(n-1)/2
2022-03-15 21:57:32
67
原创 leetcode 147 对链表进行插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。输入: head = [4,2,1,3]输出: [1,2,3,4]插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 ，直到全部元素都
2022-03-13 22:49:14
108
原创 leetcode 148 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。输入：head = [4,2,1,3]输出：[1,2,3,4]插入排序的时间复杂度是 O（n2），这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度，时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序，其中最适合链表的排序算法是归并排序。归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的
2022-03-13 17:39:01
833
原创 leetcode 83 删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。输入：head = [1,1,2]输出：[1,2]由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。具体地，我们用指针 cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur与 cur.next 对应的元素相同，那么我们就将cur.next从链表中移除, 但是注意这个时候cur位置没有变，继续判断cur与cur
2022-03-12 17:38:30
233
原创 leetcode 227 基本计算器II
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。示例 1：输入：s = “3+2*2”输出：7示例 2：输入：s = " 3/2 "输出：1示例 3：输入：s = " 3+5 / 2 "输出：5首先 s一定是个正确的表达式，不存在4 / 0这样的式子由于乘除优先于加减计算，因此不妨考虑先进行所有乘除运算，并将这些乘除运算后的整数值放回原表达式的相应位置，则随后整个表达式的值，就等于一系列整数加减后的值。基于此，我们可以用一个栈，保存这些（
2022-03-12 13:44:36
248
原创 leetcode 844 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。如果相等，返回 true ；否则，返回 false 。注意：如果对空文本输入退格字符，文本继续为空。示例 1：输入：s = “ab#c”, t = “ad#c”输出：true解释：S 和 T 都会变成 “ac”。示例 2：输入：s = “ab##”, t = “c#d#”输出：true解释：s 和 t 都会变成 “”。示例 3：输入：s = “a##c”, t = “#a#c”
2022-03-11 19:41:48
362
原创 leetcode155 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。示例:输入：[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,
2022-03-11 18:37:35
83
原创 leetcode 82 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。输入：head = [1,2,3,3,4,4,5]输出：[1,2,5]输入：head = [1,1,1,2,3]输出：[2,3]思路与算法由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。具体地，我们用 c
2022-03-10 21:47:21
312
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人