LeetCode百题【实现前缀树】
题目描述 Trie （发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
1234567891011121314输入["Trie", "insert", "search", "search", "startsWith", "insert", "search&q ...
LeetCode百题【目标和】
题目描述给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
12345678输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3
示例 2：
12输入：nums = [1], target = 1输出：1
提示：
1 <= nums.length <= ...
LeetCode百题【和为 K 的子数组】
题目描述给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
12输入：nums = [1,1,1], k = 2输出：2
示例 2：
12输入：nums = [1,2,3], k = 3输出：2
提示：
1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7
解法
前缀和+哈希表
定义pre[i]为[0.....i]里所有数的和 则有递推公式pre[i]=pre[i-1]+nums[i]
那么[j....i]和为k的的子数组条件可以转化为pre[i]-pre[j-1]=k
简单移项得:pre[j-1]=pre[i]-k
所以我们考虑以i结尾的和为k的连续子数组个数时只要统计有多少个前缀和为 pre[i]-k的pre[j]即可
我们建立哈希表以和为键，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新哈希表边计算答案
123456789101112131415 ...
MySql高级
索引索引概述索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。 这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现高级查找算法 。
优点
（1）类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本 ，这也是创建索引最主要的原因。
（2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。
（3）在实现数据的 参考完整性方面，可以加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时， 可以提高查询速度。
（4）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时 间 ，降低了CPU的消耗。
缺点
（1）创建索引和维护索引要耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。
（2）索引需要占磁盘空间 ，除了数据表占数据空间之 外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文 件更快达到最大文件尺寸。
（3）虽然索引大大提高了查询速度，同时却会降低更新表的速度 。当对表 中的数据进行增加、删除和修改的时候，索 ...
LeetCode百题【每日温度】
题目描述给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
12输入: temperatures = [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0]
示例 2:
12输入: temperatures = [30,40,50,60]输出: [1,1,1,0]
示例 3:
12输入: temperatures = [30,60,90]输出: [1,1,0]
提示：
1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100
解法
单调栈
维护递减栈，后入栈的元素总比栈顶元素小。
若当前元素 < 栈顶元素：入栈
若当前元素 > 栈顶元素：弹出栈顶元素，记录两者下标差值即为所求天数，这里用栈记录的是 T 的下标。
12345678910 ...
LeetCode百题【字符串解码】
题目描述给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
12输入：s = "3[a]2[bc]"输出："aaabcbc"
示例 2：
12输入：s = "3[a2[c]]"输出："accaccacc"
示例 3：
12输入：s = "2[abc]3[cd]ef"输出："abcabccdcdcdef"
示例 4：
12输入：s = "abc3[cd]xyz"输出："abccdcdcdxyz"
提示：
1 <= s.length & ...
LeetCode百题【前 K 个高频元素】
题目描述给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
12输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]
示例 2:
12输入: nums = [1], k = 1输出: [1]
提示：
1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶： 你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
解法
堆
首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」
建立一个小顶堆，然后遍历「出现次数数组」：
如果堆的元素个数小于 k，就可以直接插入堆中。
如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 k个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
当每次弹出最小的数,剩下的就是最 ...
LeetCode百题【零钱兑换】
题目描述给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
123输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1
示例 2：
12输入：coins = [2], amount = 3输出：-1
示例 3：
12输入：coins = [1], amount = 0输出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
解法
动态规划
定义dp[i]为组成金额 i 所需最少的硬币数量
动态转移方程为
即我们枚举最后一枚硬币面额是coin，那么需要从dp[i-coin]这个金额的状态转移过来,再算上枚举的这枚硬币数量1的贡献
由于要硬币数量最少，所以dp[i]为前 ...
LeetCode百题【最长递增子序列】
题目描述给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
123输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
12输入：nums = [0,1,0,3,2,3]输出：4
示例 3：
12输入：nums = [7,7,7,7,7,7,7]输出：1
提示：
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
解法
动态规划
定义dp[i]为考虑前 i个元素，以第 i 个数字结尾的最长上升子序列的长度
那么有动态转移方程
$$dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]$ ...
LeetCode百题【寻找重复数】
题目描述给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
12输入：nums = [1,3,4,2,2]输出：2
示例 2：
12输入：nums = [3,1,3,4,2]输出：3
提示：
1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
解法
排序
1234567891011121314class Solution { public int findDuplicate(int[] nums) { ...
