Moon

题目描述题目链接 给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。 字符串中只包含大小写英文字母和数字。 输入格式第一行包含整数 n 和 m，表示字符串长度和询问次数。 第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。 接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。 注意，字符串的位置从 1 开始编号。 输出格式对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。 每个结果占一行。 输入样例： 123458 3aabbaabb1 3 5 71 3 6 81 2 1 2 输出样例： 123YesNoYes 算法1(字符串哈希) $O(n)$字符串匹配类型的题目可以考虑使用 KMP 算法，但是KMP算法是 $O(n^2)$ 的时间复杂度，在面对较大数据范围时，将会超时，因此在此题中应该考虑使用另外的解题方法 由于题目需要求两个范围内的字符串是否相等，那么很 ...

题目描述题目链接 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 123输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 123输入: nums = [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 算法1(暴力 + 前缀积优化) $O(n^2)$如果使用通常的暴力算法，那么需要枚举区间的左端点，再枚举长度，这样的话需要的时间、空间复杂度都很高 那么此时可以想到，使用前缀积的思想来进行优化 与前缀和类似，可以预先处理出来数组的前缀积，再依次枚举区间的长度、端点就可以优化掉一维 算法2（DP） $O(n)$利用动态规划的思想： 很容易从题目描述中看出，选择每个点作为子数组终点时，代表的是一系列选择的结果，因此需要使用动态规划来表示一系列结果 由于本题中是求子数组的最大乘积，而乘法有着负负得正的性质，因此在每次更新状态时 ...

题目描述题目链接 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1： 1234567891011输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 示例 2： 12输入：nums = [1], k = 1输出：[1] 算法1(单调队列) $O(n)$题目要求我们维护 ...

题目描述题目链接 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。 如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。   示例 1： 123456输入：nums = [1,5,2]输出：false解释：一开始，玩家 1 可以从 1 和 2 中进行选择。如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。因此，玩家 1 永远不会成为赢家， ...

题目描述题目链接 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足： 每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。sk == endWord给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。 示例 1： 12345输入：beginWord = "hit", endWord = "cog", wordList ...

题目描述题目链接 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例： 123456789101112131415161718输入["LRUCache", "put", "put", "get", "put", "get", "put", "ge ...

题目描述题目链接 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 进阶： 你可以设计一个只使用常数额外空间的算法来解决此问题吗？ 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 算法1(遍历一遍链表) $O(n)$ 创建 dummy 节点来保存头结点 k 个一组翻转链表： 首先判断接下来是否有 k 个节点，如果没有的话直接退出 类似于直接反转链表，两个一组，翻转即可，因此只需要翻转 k - 1 次 翻转结束，处理一些边界 123456789101112131415161718192021222324252627282930313233343536373839404142/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), n ...

题目描述 题目链接 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。 示例1： 123输入：root = [1,2,3]输出：6解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 示例2： 123输入：root = [-10,9,20,null,null,15,7]输出：42解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42 算法1 (遍历) O(n2)O(n^2)O(n2) 对于这道问题，我们需要思考的是： 一个节点的最大路径和到底如何计算？ 根据树的递归特性，我们可以知道：一个节点的最大路径，一定是经过其左子树、右子树的最大路径，在加上当前路径大小的值 需要注意的是： 当左、右子树某个最大路径为负数时，我们可以不走这条路径，那么可以将路径与 0 取最大值 这样， ...

数据库基础知识 数据库范式 1NF: 属性不可再分割 2NF：1NF基础之上，消除非主属性对于码的部分函数依赖 3NF：2NF基础之上，消除了非主属性对于码的传递函数依赖 drop、delete、truncate区别 用法不同 drop(丢弃数据)：drop table 表名，直接删除整张表 truncate(清空数据)：truncate table 表名，清空表中的数据 delete(删除数据)：delete from 表名 where 列名=值， 删除某一列数据，如果不加 where 字句的话，与 truncate 类似 truncate 和不带 where 子句的 delete、以及 drop 都会删除表内的数据，但是 truncate 和 delete 只删除数据不删除表的结构(定义)，执行 drop 语句，此表的结构也会删除，也就是执行 drop 之后对应的表不复存在 属于不同的数据库语言 trucate 和 drop 属于 DDL(数据定义语言)，语句，操作立即生效，原数据不放到 rollback segment中，不可回滚，操作不触发 trigger ...

题目描述题目链接 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。   示例 1： 123输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。 示例 2： 1234输入: s = "applepenapple", wordDict = ["apple", "pen"]输出: true解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。  注意，你可以重复使用字典中 ...