livingsu-CSDN博客

原创暑期实习笔记

一、springboot二、git

2021-09-09 16:28:20 309 1

一、题目给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。二、解法解法一：位操作遍历0表示不取，1表示取，那么全集就是111…11，空集就是00…00，一共有2n−12^n-12n−1个元素class Solution {public: vector<vector<int>> subsets(vector<int>& nums) {

2021-06-07 10:07:20 252 1

原创 leetcode 76. 最小覆盖子串

一、题目给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。输入：s = “ADOBECODEBANC”, t = “ABC”输出：“BANC”二、解法思路：滑动窗口用两个指针lll，rrr构成一个滑动窗口，维护这个窗口里面的数据保证是符合答案的。过程是：首先不断右移rrr直至满足答案（扩张窗口），然后不断左移lll同时保证窗口也满足（

2021-06-06 11:11:08 208

原创 leetcode 56. 合并区间

一、题目以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].输入：intervals = [[1,4],[4,5]]输出：

2021-05-31 17:31:26 141

原创 leetcode 39. 组合总和

一、题目给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。示例 1：输入：candidates = [2,3,6,7], target = 7,所求解集为：[[7],[2,2,3]]二、解法看到组合，就想到回溯法。关键在于回溯法函数，void dfs(

2021-05-31 11:34:59 91 1

原创 leetcode 34. 在排序数组中查找元素的第一个和最后一个位置

一、题目给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]二、解法二分查找：寻找leftIdx（第一个

2021-05-31 11:08:15 75

原创 leetcode 33. 搜索旋转排序数组

一、题目整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你旋转后的数组 nums 和一个

2021-05-31 10:22:52 59

原创 leetcode 32. 最长有效括号

一、题目给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。输入：s = “)()())”输出：4解释：最长有效括号子串是 “()()”二、解法思路：动态规划dp[i]dp[i]dp[i]表示以s[i]s[i]s[i]结尾的有效子串的最长长度。考察s[i]s[i]s[i]和s[i−1]s[i-1]s[i−1]：若s[i]==(s[i]==(s[i]==(，则dp[i]=0dp[i]=0dp[i]=0若s[i]==)s[i]==)s[i]==)，

2021-05-31 00:24:55 68

原创 leetcode 31. 下一个排列

一、题目实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。输入：nums = [1,2,3]输出：[1,3,2]输入：nums = [3,2,1]输出：[1,2,3]二、解法思路：要找到一个尽可能靠右的“较小数”，和一个尽可能靠右的“较大数”，交换两者。方法：从后往前遍历，第一个满足nums[i]<nums[i+1]n

2021-05-30 23:08:55 62

原创 leetcode 23. 合并K个升序链表

一、题目给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[1->4->5,1->3->4,2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6二、解法解法1：暴力数组排序：用一个数组保存所有链

2021-05-29 18:54:37 121

原创 leetcode 22. 括号生成

一、题目数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]二、解法思路：回溯法具体思想：用一个回溯函数，记录当前已经得到的组合，首先判断是否达到边界情况，然后添加组合，继续递归求解，最后回退组合。本题中，有几个关键的地方：使用字符串的长度作为边界情况判断的记录要满足有效的括号组合，需要满足以下情况：左括号数不能超过n右括号

2021-05-29 16:32:00 86

原创 leetcode 19. 删除链表的倒数第 N 个结点

一、题目给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]二、解法解法1：遍历两次，第一次遍历得到链表的长度 lengthlengthlength，第二次遍历到第 length−nlength-nlength−n 个节点即可要注意删除虚拟节点dummy，避免出现内存泄漏问题（c++会出现该问题）/** * Definition for singly-

2021-05-29 13:15:41 52

原创 leetcode 17. 电话号码的字母组合

一、题目给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。输入：digits = “23”输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]输入：digits = “”输出：[]二、解法本题与全排列那题很类似，使用回溯法。回溯法函数原型void backtrace(vector<T>& ans,T&

2021-05-29 12:45:52 133

原创 leetcode 15. 三数之和

一、题目给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。二、解法要使答案不包含重复的三元组，思路是将nums进行排序，并且每次拿出来的元素都不能和上一次的相同。比如[-1,-1,0,1]，如果第一次迭代拿出了两个-1，那么答案中就会有重复。对于三重循环 i,j,ki,j,ki,j,k ，如果固定了 iii ，随着 nums[j]num

2021-05-29 11:08:20 60

原创 leetcode 46. 全排列

一、题目给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]二、解法思路：回溯法（本质就是dfs）全排列就是要将n个数字填入n个空格中。如果我们已知前面k个空格已经填好，现在需要填一个数，那么只需要在后面n-k个数中间选一个即可。回溯的意思是，每一次选就是简单的将后面的元素和前面的元素进行交换，然后继续进行下

2021-05-27 10:52:50 85 1

原创 leetcode 10. 正则表达式匹配

一、题目给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。输入：s = “aa” p = “a*”输出：true解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。二、解法动态规划：dp[i][j]dp[i][j]dp[i][j

2021-05-26 16:07:41 60

原创 leetcode 5. 最长回文子串

一、题目给你一个字符串 s，找到 s 中最长的回文子串。输入：s = “babad”输出：“bab”解释：“aba” 同样是符合题意的答案。二、解法思路：动态规划dp[i][j]dp[i][j]dp[i][j] 表示下标从 iii 至 jjj 的子串是否是回文串。显然 dpdpdp 是一个半三角型，因为 i>ji>ji>j 时字符串无意义。可以列出转移方程：dp[i][j]=dp[i+1][j−1]&&S[i]==S[j]dp[i][j]=d

2021-05-26 10:09:34 45

原创 leetcode 4. 寻找两个正序数组的中位数

一、题目给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5输入：nums1 = [], nums2 = [1]输出：1.00000二、解法问题实际上是求两个正序数组的第k小的数。简单的思路是双指针一个一个往后移动，时间复杂度是 O(m+n)O(

2021-05-26 09:16:07 44

原创 leetcode 993. 二叉树的堂兄弟节点

一、题目在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。输入：root = [1,2,3,4], x = 4, y = 3输出：false二、解法思路：显然用深度优先搜索（dfs）。要得到结果，

2021-05-17 10:10:31 95

原创 leetcode 1734. 解码异或后的排列

一、题目给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个奇数。它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。输入：encoded = [3,1]输出：[1,2,3]解释：如果 perm = [1,2,3]

2021-05-11 09:09:48 117 1

原创 leetcode 938. 二叉搜索树的范围和

一、题目给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。输入：root = [10,5,15,3,7,null,18], low = 7, high = 15输出：32二、解法2.1 dfs深度优先搜索思路是用递归/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeN

2021-04-27 08:24:57 61

原创 leetcode 3. 无重复字符的最长子串

一、题目给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。二、解法思路：滑动窗口滑动窗口的本质就是在暴力（双重for循环）下面进行优化，通过维护一个有序的数据结构

2021-04-24 21:43:48 37

原创 leetcode 1. 两数之和

一、题目给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 二、解法解法一：直接暴力枚举，时间复杂度为O(N2)O(N^2)O(N2)解法二：用

2021-04-24 17:00:17 57

原创 leetcode 377. 组合总和 Ⅳ

一、题目给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。输入：nums = [1,2,3], target = 4输出：7解释：所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。二、解法思路：动态规划该问题本质上是

2021-04-24 16:29:08 75

原创 leetcode 剑指 Offer 25. 合并两个排序的链表

一、题目输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。输入：1->2->4, 1->3->4输出：1->1->2->3->4->4二、解法思路：引入一个虚拟头结点，然后用双指针遍历两个链表，如果一个链表已经结束，则遍历结束/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *

2021-04-22 11:30:10 44

原创 leetcode 91. 解码方法

一、题目一条包含字母 A-Z 的消息通过以下映射进行了编码：A->'0'B->'1'...Z->'26' 要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：“AAJF” ，将消息分组为 (1 1 10 6)“KJF” ，将消息分组为 (11 10 6)注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。给你一个

2021-04-21 21:55:25 112

原创 leetcode 146. LRU 缓存机制

一、题目运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之

2021-04-21 21:28:30 68

原创 leetcode 26. 删除有序数组中的重复项

一、题目给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。输入：nums = [1,1,2]输出：2, nums = [1,2]解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。二、思路2.1 STL自带的unique思路：unique可以返回数组两个迭

2021-04-18 14:00:34 82

原创 leetcode 220. 存在重复元素 III

一、题目给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。输入：nums = [1,2,3,1], k = 3, t = 0输出：true输入：nums = [1,5,9,1,5,9], k = 2, t = 3输出：false二、解法2.1 滑动窗口+set思路：

2021-04-17 16:51:19 64

原创 leetcode 213. 打家劫舍 II（c++）

一、题目你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。输入：nums = [2,3,2]输出：3解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）,因为他们是相邻的。

2021-04-15 08:47:23 106

原创 leetcode 208. 实现 Trie (前缀树)

一、题目Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现 Trie 类：Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsW

2021-04-14 08:51:44 65

原创 leetcode 783. 二叉搜索树节点最小距离

一、题目给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。输入：root = [4,2,6,1,3]输出：1提示：树中节点数目在范围 [2, 100] 内0 <= Node.val <= 105二、解法解法一：递归遍历、求左右子树的最值思路：对于root，找到它左子树的最大值和右子树的最小值，进行比较/** * Definition for a binary tree node. * struct TreeNode { *

2021-04-13 08:38:00 81

原创 leetcode 179. 最大数

一、题目给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。输入：nums = [3,30,34,5,9]输出：“9534330”输入：nums = [0,0,0,0]输出：“0”二、解法思路：显然就是将nums进行排序，然后再拼接起来，所以主要问题是排序规则。排序规则：给定字符串a,b，当a+b>b+a时即可也可以用一个long类型，存放拼接的a+b和b+a进行比较

2021-04-12 11:23:52 164

原创 leetcode 264. 丑数 II

一、题目给你一个整数 n ，请你找出并返回第 n 个丑数。丑数就是只包含质因数 2、3 和/或 5 的正整数。输入：n = 10输出：12解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。输入：n = 1输出：1解释：1 通常被视为丑数。二、解法思路：动态规划设dp[i]表示第i个丑数，dp[1]=1，题目求dp[n]由于丑数=前一个较小的丑数乘以因子（2或3或5），故可以用3指针法，每一个指针指向前一个较小丑

2021-04-11 11:56:34 177

原创 leetcode 154. 寻找旋转排序数组中的最小值 II

一、题目已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。给你一个可能存在重复元素值的数

2021-04-09 10:36:30 50

原创 leetcode 153. 寻找旋转排序数组中的最小值

一、题目已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。输入：nums = [3,4,5,1,2]输出：1解释：原数组为 [1,2,3,4,5

2021-04-08 09:23:16 79

原创 leetcode 81. 搜索旋转排序数组 II

一、题目已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]

2021-04-07 08:32:43 112

原创 leetcode 88. 合并两个有序数组

一、题目给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3输出：[1,2,2,3,5,6]二、解法解法1：使用临时数组+双指针思路：用

2021-04-05 10:12:41 51

原创 leetcode 781. 森林中的兔子

一、题目森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。返回森林中兔子的最少数量。示例:输入: answers = [1, 1, 2]输出: 5解释: 两只回答了 “1” 的兔子可能有相同的颜色，设为红色。之后回答了 “2” 的兔子不会是红色，否则他们的回答会相互矛盾。设回答了 “2” 的兔子为蓝色。此外，森林中还应有另外 2只蓝色兔子的回答没有包含在数组中。因此森林中兔子的最少数量是 5:

2021-04-04 10:22:11 116

原创 leetcode 1143. 最长公共子序列

一、题目给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。输入：text1 = “abcde”, text2 = “ace”

2021-04-03 13:32:45 86

OpenGL glfw模拟仿真车削

空空如也