代码拉取完成，页面将自动刷新
Fork 仓库
加载中
确定同步？
同步操作将从 CodeSleep/MyBlog_01 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230
/*
Navicat Premium Data Transfer
Source Server : test
Source Server Type : MySQL
Source Server Version : 80019
Source Host : localhost:3306
Source Schema : blog
Target Server Type : MySQL
Target Server Version : 80019
File Encoding : 65001
Date: 25/10/2020 21:22:57
*/
SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;
-- ----------------------------
-- Table structure for hibernate_sequence
-- ----------------------------
DROP TABLE IF EXISTS `hibernate_sequence`;
CREATE TABLE `hibernate_sequence` (
`next_val` bigint(0) NULL DEFAULT NULL
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of hibernate_sequence
-- ----------------------------
INSERT INTO `hibernate_sequence` VALUES (102);
INSERT INTO `hibernate_sequence` VALUES (102);
INSERT INTO `hibernate_sequence` VALUES (102);
INSERT INTO `hibernate_sequence` VALUES (102);
INSERT INTO `hibernate_sequence` VALUES (102);
-- ----------------------------
-- Table structure for t_blog
-- ----------------------------
DROP TABLE IF EXISTS `t_blog`;
CREATE TABLE `t_blog` (
`id` bigint(0) NOT NULL,
`appreciation` bit(1) NOT NULL,
`commentabled` bit(1) NOT NULL,
`content` longtext CHARACTER SET utf8 COLLATE utf8_bin NULL,
`create_time` datetime(6) NULL DEFAULT NULL,
`first_picture` longtext CHARACTER SET utf8 COLLATE utf8_bin NULL,
`flag` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`published` bit(1) NOT NULL,
`recommend` bit(1) NOT NULL,
`share_statement` bit(1) NOT NULL,
`title` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`update_time` datetime(6) NULL DEFAULT NULL,
`views` int(0) NULL DEFAULT NULL,
`type_id` bigint(0) NULL DEFAULT NULL,
`user_id` bigint(0) NULL DEFAULT NULL,
`description` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE,
INDEX `FK292449gwg5yf7ocdlmswv9w4j`(`type_id`) USING BTREE,
INDEX `FK8ky5rrsxh01nkhctmo7d48p82`(`user_id`) USING BTREE,
CONSTRAINT `FK292449gwg5yf7ocdlmswv9w4j` FOREIGN KEY (`type_id`) REFERENCES `t_type` (`id`) ON DELETE RESTRICT ON UPDATE RESTRICT,
CONSTRAINT `FK8ky5rrsxh01nkhctmo7d48p82` FOREIGN KEY (`user_id`) REFERENCES `t_user` (`id`) ON DELETE RESTRICT ON UPDATE RESTRICT
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of t_blog
-- ----------------------------
INSERT INTO `t_blog` VALUES (22, b'1', b'0', '# 这是本博客第一篇测试用博客\r\n测试了博客评论功能和管理功能、标签选择功能、分类选择功能、推荐功能等\r\n这是本博客第一篇测试用博客；前端页面采用框架；semantic-UI制作，后端采用SpringBoot + SpringMVC + Spring Security + MySQL+ JSP（后续会学习mybatis将持久层改写为mybatis）系统日志采用自定义注解+AOP 方式实现；支持MarkDown编辑博客内容；使用MD5加密密码，感谢网上的老师们\r\n\r\n------------------------------------本博客的起点\r\n```java\r\npublic class HelloBlog {\r\n public static void main(String[] args) {\r\n System.out.println(\"Hello Blog\");\r\n }\r\n}\r\n```', '2020-10-05 07:56:14.779000', 'https://picsum.photos/id/289/800/450', '原创', b'1', b'0', b'0', 'The First Test', '2020-10-06 09:12:11.232000', 111, 2, 1, '这是本博客第一篇测试用博客；前端页面采用框架；semantic-UI制作，后端采用SpringBoot + SpringMVC + Spring Security + MySQL+ JSP（后续会学习mybatis将持久层改写为mybatis）系统日志采用自定义注解+AOP 方式实现；感谢网上的老师们');
INSERT INTO `t_blog` VALUES (92, b'1', b'1', '#### 1、两数之和\r\n\r\n 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。\r\n\r\n 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。\r\n\r\n**示例:**\r\n\r\n> 给定 nums = [2, 7, 11, 15], target = 9\r\n>\r\n> 因为 nums[0] + nums[1] = 2 + 7 = 9\r\n> 所以返回 [0, 1]\r\n\r\n**方法一：暴力法**\r\n\r\n 暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target -x相等的目标元素。\r\n\r\n```java\r\nclass Solution {\r\n public int[] twoSum(int[] nums, int target) {\r\n for (int i = 0; i < nums.length; i++) {\r\n for (int j = i + 1; j < nums.length; j++) {\r\n if (nums[j] == target - nums[i]) {\r\n return new int[] { i, j };\r\n }\r\n }\r\n }\r\n throw new IllegalArgumentException(\"No two sum solution\");\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析：**\r\n\r\n> **时间复杂度：**O(n^2)\r\n> 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n^2)\r\n>\r\n> **空间复杂度：**O(1)。\r\n\r\n**方法二：两遍哈希表**\r\n\r\n 为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。\r\n\r\n 通过以空间换取速度的方式，我们可以将查找时间从 O(n)降低到 O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。\r\n\r\n 一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（`target - nums[i]`）是否存在于表中。注意，该目标元素不能是 `nums[i]`本身！\r\n\r\n```java\r\nclass Solution {\r\n public int[] twoSum(int[] nums, int target) {\r\n Map<Integer, Integer> map = new HashMap<>();\r\n for (int i = 0; i < nums.length; i++) {\r\n map.put(nums[i], i);\r\n }\r\n for (int i = 0; i < nums.length; i++) {\r\n int complement = target - nums[i];\r\n if (map.containsKey(complement) && map.get(complement) != i) {\r\n return new int[] { i, map.get(complement) };\r\n }\r\n }\r\n throw new IllegalArgumentException(\"No two sum solution\");\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析：**\r\n\r\n> **时间复杂度：**O(n)，\r\n> 我们把包含有 nn 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1)，所以时间复杂度为 O(n)。\r\n>\r\n> **空间复杂度**：O(n)，\r\n> 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n个元素。\r\n\r\n**方法三：一遍哈希表**\r\n\r\n 事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。\r\n\r\n```java\r\nclass Solution {\r\n public int[] twoSum(int[] nums, int target) {\r\n Map<Integer, Integer> map = new HashMap<>();\r\n for (int i = 0; i < nums.length; i++) {\r\n int complement = target - nums[i];\r\n if (map.containsKey(complement)) {\r\n return new int[] { map.get(complement), i };\r\n }\r\n map.put(nums[i], i);\r\n }\r\n throw new IllegalArgumentException(\"No two sum solution\");\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析：**\r\n\r\n> **时间复杂度：**O(n)，\r\n> 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。\r\n>\r\n> **空间复杂度：**O(n)，\r\n> 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。\r\n\r\n**方法四：哈希映射**\r\n\r\n**思路**\r\n 标签：哈希映射\r\n 这道题本身如果通过暴力遍历的话也是很容易解决的，时间复杂度在 O(n2)\r\n 由于哈希查找的时间复杂度为 O(1)，所以可以利用哈希容器 map 降低时间复杂度\r\n 遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 `target-nums[i]` 的 key 值\r\n 如果存在则找到了两个值，如果不存在则将当前的 `(nums[i],i)` 存入 map 中，继续遍历直到找到为止\r\n 如果最终都没有结果则抛出异常\r\n 时间复杂度：O(n)\r\n\r\n```java\r\nclass Solution {\r\n public int[] twoSum(int[] nums, int target) {\r\n Map<Integer, Integer> map = new HashMap<>();\r\n for(int i = 0; i< nums.length; i++) {\r\n if(map.containsKey(target - nums[i])) {\r\n return new int[] {map.get(target-nums[i]),i};\r\n }\r\n map.put(nums[i], i);\r\n }\r\n throw new IllegalArgumentException(\"No two sum solution\");\r\n }\r\n}\r\n```\r\n\r\n#### 2、整数反转\r\n\r\n 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。\r\n\r\n**示例 1:**\r\n\r\n> 输入: 123\r\n> 输出: 321\r\n\r\n **示例 2:**\r\n\r\n> 输入: -123\r\n> 输出: -321\r\n\r\n**示例 3:**\r\n\r\n> 输入: 120\r\n> 输出: 21\r\n\r\n**注意:**\r\n\r\n 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。\r\n\r\n**方法：弹出和推入数字 & 溢出前进行检查**\r\n\r\n**思路**\r\n\r\n 我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。\r\n\r\n**算法**\r\n\r\n 反转整数的方法可以与反转字符串进行类比。\r\n\r\n 我们想重复“弹出” `x` 的最后一位数字，并将它“推入”到 `rev` 的后面。最后，`rev` 将与 `x `相反。\r\n\r\n 要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。\r\n\r\n```java\r\n//pop operation:\r\npop = x % 10;\r\nx /= 10;\r\n\r\n//push operation:\r\ntemp = rev * 10 + pop;\r\nrev = temp;\r\n```\r\n\r\n 但是，这种方法很危险，因为当`temp=rev⋅10+pop` 时会导致溢出。\r\n\r\n 幸运的是，事先检查这个语句是否会导致溢出很容易。\r\n\r\n 为了便于解释，我们假设 \\text{rev}rev 是正数。\r\n\r\n 如果 `temp=rev⋅10+pop` 导致溢出，那么一定有 `rev ≥ INTMAX / 10`。\r\n 如果`rev> INTMAX / 10`，那么 `temp=rev⋅10+pop` 一定会溢出。\r\n 如果`rev== INTMAX / 10` ，那么只要`pop>7`，`temp=rev⋅10+pop` 就会溢出。\r\n当 `rev` 为负时可以应用类似的逻辑。\r\n\r\n```java\r\nclass Solution {\r\n public int reverse(int x) {\r\n int rev = 0;\r\n while (x != 0) {\r\n int pop = x % 10;\r\n x /= 10;\r\n if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;\r\n if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;\r\n rev = rev * 10 + pop;\r\n }\r\n return rev;\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析**\r\n\r\n> **时间复杂度：**O(log(x))，x 中大约有log 10(x) 位数字。\r\n> **空间复杂度：**O(1)。\r\n\r\n#### 3、回文数\r\n\r\n 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。\r\n\r\n**示例 1:**\r\n\r\n> 输入: 121\r\n> 输出: true\r\n\r\n**示例 2:**\r\n\r\n> 输入: -121\r\n> 输出: false\r\n> 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。\r\n\r\n**示例 3:**\r\n\r\n> 输入: 10\r\n> 输出: false\r\n> 解释: 从右向左读, 为 01 。因此它不是一个回文数。\r\n\r\n**进阶:**\r\n\r\n 你能不将整数转为字符串来解决这个问题吗？\r\n\r\n**解法一：普通解法**（LeetCode有动画演示）\r\n\r\n 最好理解的一种解法就是先将 **整数转为字符串** ，然后将字符串分割为数组，只需要循环数组的一半长度进行判断对应元素是否相等即可。\r\n\r\n```java\r\n///简单粗暴，看看就行\r\nclass Solution {\r\n public boolean isPalindrome(int x) {\r\n String reversedStr = (new StringBuilder(x + \"\")).reverse().toString();\r\n return (x + \"\").equals(reversedStr);\r\n }\r\n}\r\n```\r\n\r\n**解法二：进阶解法---数学解法**\r\n\r\n 通过取整和取余操作获取整数中对应的数字进行比较。\r\n\r\n举个例子：1221 这个数字。\r\n\r\n 通过计算 1221 / 1000， 得首位1\r\n 通过计算 1221 % 10， 可得末位 1\r\n 进行比较\r\n 再将 22 取出来继续比较\r\n\r\n```java\r\nclass Solution {\r\n public boolean isPalindrome(int x) {\r\n //边界判断\r\n if (x < 0) return false;\r\n int div = 1;\r\n //\r\n while (x / div >= 10) div *= 10;\r\n while (x > 0) {\r\n int left = x / div;\r\n int right = x % 10;\r\n if (left != right) return false;\r\n x = (x % div) / 10;\r\n div /= 100;\r\n }\r\n return true;\r\n }\r\n}\r\n```\r\n\r\n**方法三：反转一半数字**\r\n\r\n**思路**\r\n\r\n 映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。\r\n\r\n 第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。\r\n 但是，如果反转后的数字大于 `int.MAX`，我们将遇到整数溢出问题。\r\n\r\n 按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 \\text{int}int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。\r\n\r\n 例如，输入 `1221`，我们可以将数字 “12**21**” 的后半部分从 “**21**” 反转为 “**12**”，并将其与前半部分 “**12**” 进行比较，因为二者相同，我们得知数字 `1221` 是回文。\r\n\r\n**算法**\r\n\r\n 首先，我们应该处理一些临界情况。所有负数都不可能是回文，例如：`-123` 不是回文，因为` - `不等于 `3`。所以我们可以对所有负数返回 `false`。除了 `0` 以外，所有个位是 `0`的数字不可能是回文，因为最高位不等于 `0`。所以我们可以对所有大于 `0` 且个位是 `0` 的数字返回 `false`。\r\n\r\n 现在，让我们来考虑如何反转后半部分的数字。\r\n\r\n 对于数字 `1221`，如果执行 `1221 % 10`，我们将得到最后一位数字 `1`，要得到倒数第二位数字，我们可以先通过除以 `10` 把最后一位数字从 `1221` 中移除，`1221 / 10 = 122`，再求出上一步结果除以 `10` 的余数，`122 % 10 = 2`，就可以得到倒数第二位数字。如果我们把最后一位数字乘以 `10`，再加上倒数第二位数字，`1 * 10 + 2 = 12`，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。\r\n\r\n 现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？\r\n\r\n 由于整个过程我们不断将原始数字除以 `10`，然后给反转后的数字乘上 `10`，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。\r\n\r\n```java\r\nclass Solution {\r\n public boolean isPalindrome(int x) {\r\n // 特殊情况：\r\n // 如上所述，当 x < 0 时，x 不是回文数。\r\n // 同样地，如果数字的最后一位是 0，为了使该数字为回文，\r\n // 则其第一位数字也应该是 0\r\n // 只有 0 满足这一属性\r\n if (x < 0 || (x % 10 == 0 && x != 0)) {\r\n return false;\r\n }\r\n\r\n int revertedNumber = 0;\r\n while (x > revertedNumber) {\r\n revertedNumber = revertedNumber * 10 + x % 10;\r\n x /= 10;\r\n }\r\n\r\n // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。\r\n // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，\r\n // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。\r\n return x == revertedNumber || x == revertedNumber / 10;\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析**\r\n\r\n> **时间复杂度：**`O(logn)`，对于每次迭代，我们会将输入除以 `10`，因此时间复杂度为 `O(logn)`。\r\n> **空间复杂度：**`O(1)`。我们只需要常数空间存放若干变量。', '2020-10-06 08:27:26.957000', 'https://ss0.bdstatic.com/70cFvHSh_Q1YnxGkpoWK1HF6hhy/it/u=3021978503,3156841697&fm=15&gp=0.jpg', '转载', b'1', b'1', b'1', 'LeetCode算法1-3(难度简单)', '2020-10-06 08:34:19.268000', 5, 88, 1, ' LeetCode算法题；两数之和；在数组中找出和为目标值的那两个整数，并返回他们的数组下标。整数反转；给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。回文数；判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数');
INSERT INTO `t_blog` VALUES (93, b'1', b'1', '#### 4、两数相加\r\n\r\n 给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。\r\n\r\n 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。\r\n\r\n 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。\r\n\r\n**示例：**\r\n\r\n> 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)\r\n> 输出：7 -> 0 -> 8\r\n> 原因：342 + 465 = 807\r\n\r\n**解法1：**\r\n**整体思路：**\r\n 将长度较短的链表在末尾补零使得两个连表长度相等，再一个一个元素对其相加（考虑进位）\r\n\r\n**具体步骤：**\r\n\r\n> 获取两个链表所对应的长度\r\n> 在较短的链表末尾补零\r\n> 对齐相加考虑进位\r\n\r\n**实现代码：**\r\n\r\n```c++\r\n/**\r\n * Definition for singly-linked list.\r\n * struct ListNode {\r\n * int val;\r\n * ListNode *next;\r\n * ListNode(int x) : val(x), next(NULL) {}\r\n * };\r\n */\r\nclass Solution {\r\npublic:\r\n ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {\r\n int len1=1;//记录l1的长度\r\n int len2=1;//记录l2的长度\r\n ListNode* p=l1;\r\n ListNode* q=l2;\r\n while(p->next!=NULL)//获取l1的长度\r\n {\r\n len1++;\r\n p=p->next;\r\n }\r\n while(q->next!=NULL)//获取l2的长度\r\n {\r\n len2++;\r\n q=q->next;\r\n }\r\n if(len1>len2)//l1较长，在l2末尾补零\r\n {\r\n for(int i=1;i<=len1-len2;i++)\r\n {\r\n q->next=new ListNode(0);\r\n q=q->next;\r\n }\r\n }\r\n else//l2较长，在l1末尾补零\r\n {\r\n for(int i=1;i<=len2-len1;i++)\r\n {\r\n p->next=new ListNode(0);\r\n p=p->next;\r\n }\r\n }\r\n p=l1;\r\n q=l2;\r\n bool count=false;//记录进位\r\n ListNode* l3=new ListNode(-1);//存放结果的链表\r\n ListNode* w=l3;//l3的移动指针\r\n int i=0;//记录相加结果\r\n while(p!=NULL&&q!=NULL)\r\n {\r\n i=count+p->val+q->val;\r\n w->next=new ListNode(i%10);\r\n count=i>=10?true:false;\r\n w=w->next;\r\n p=p->next;\r\n q=q->next;\r\n }\r\n if(count)//若最后还有进位\r\n {\r\n w->next=new ListNode(1);\r\n w=w->next;\r\n }\r\n return l3->next; \r\n }\r\n};\r\n```\r\n\r\n**解法2：**\r\n\r\n**整体思路：**\r\n\r\n 不对齐补零，若链表不为空则用sum(代表每个位的和的结果)加上，考虑进位。\r\n\r\n**实现代码：**\r\n\r\n```C++\r\nclass Solution {\r\npublic:\r\n ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {\r\n ListNode* head=new ListNode(-1);//存放结果的链表\r\n ListNode* h=head;//移动指针\r\n int sum=0;//每个位的加和结果\r\n bool carry=false;//进位标志\r\n while(l1!=NULL||l2!=NULL)\r\n {\r\n sum=0;\r\n if(l1!=NULL)\r\n {\r\n sum+=l1->val;\r\n l1=l1->next;\r\n }\r\n if(l2!=NULL)\r\n {\r\n sum+=l2->val;\r\n l2=l2->next;\r\n }\r\n if(carry)\r\n sum++;\r\n h->next=new ListNode(sum%10);\r\n h=h->next;\r\n carry=sum>=10?true:false;\r\n }\r\n if(carry)\r\n {\r\n h->next=new ListNode(1);\r\n }\r\n return head->next;\r\n }\r\n};\r\n```\r\n\r\n**解法3：**\r\n\r\n**思路**\r\n**标签：**链表\r\n 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 00，比如 987 + 23 = 987 + 023 = 1010\r\n 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值\r\n 如果两个链表全部遍历完毕后，进位值为 11，则在新链表最前方添加节点 11\r\n 小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。\r\n\r\n```java\r\n/**\r\n * Definition for singly-linked list.\r\n * public class ListNode {\r\n * int val;\r\n * ListNode next;\r\n * ListNode(int x) { val = x; }\r\n * }\r\n */\r\nclass Solution {\r\n public ListNode addTwoNumbers(ListNode l1, ListNode l2) {\r\n ListNode pre = new ListNode(0);\r\n ListNode cur = pre;\r\n int carry = 0;\r\n while(l1 != null || l2 != null) {\r\n int x = l1 == null ? 0 : l1.val;\r\n int y = l2 == null ? 0 : l2.val;\r\n int sum = x + y + carry;\r\n \r\n carry = sum / 10;\r\n sum = sum % 10;\r\n cur.next = new ListNode(sum);\r\n\r\n cur = cur.next;\r\n if(l1 != null)\r\n l1 = l1.next;\r\n if(l2 != null)\r\n l2 = l2.next;\r\n }\r\n if(carry == 1) {\r\n cur.next = new ListNode(carry);\r\n }\r\n return pre.next;\r\n }\r\n}\r\n```\r\n\r\n#### 5、无重复字符的最长子串\r\n\r\n 给定一个字符串，请你找出其中不含有重复字符的 **最长子串** 的长度。\r\n\r\n**示例 1:**\r\n\r\n> 输入: \"abcabcbb\"\r\n> 输出: 3 \r\n> 解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。\r\n\r\n**示例 2:**\r\n\r\n> 输入: \"bbbbb\"\r\n> 输出: 1\r\n> 解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。\r\n\r\n**示例 3:**\r\n\r\n> 输入: \"pwwkew\"\r\n> 输出: 3\r\n> 解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。\r\n> 请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。\r\n\r\n**方法一：**\r\n\r\n**思路：**\r\n\r\n 这道题主要用到思路是：滑动窗口\r\n\r\n什么是滑动窗口？\r\n\r\n 其实就是一个队列,比如例题中的 `abcabcbb`，进入这个队列（窗口）为 `abc `满足题目要求，当再进入 `a`，队列变成了` abca`，这时候不满足要求。所以，我们要移动这个队列！\r\n\r\n如何移动？\r\n\r\n 我们只要把队列的左边的元素移出就行了，直到满足题目要求！\r\n\r\n 一直维持这样的队列，找出队列出现最长的长度时候，求出解！\r\n\r\n时间复杂度：O(n)\r\n\r\n代码：\r\n\r\n```java\r\nclass Solution {\r\n public int lengthOfLongestSubstring(String s) {\r\n if (s.length()==0) return 0;\r\n HashMap<Character, Integer> map = new HashMap<Character, Integer>();\r\n int max = 0;//最长子串长度\r\n int left = 0;//滑动窗口左下标，i相当于滑动窗口右下标\r\n for(int i = 0; i < s.length(); i ++){\r\n /**1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,\r\n 此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；\r\n 2、如果当前字符 ch 包含在 map中，此时有2类情况：\r\n 1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，\r\n 那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；\r\n 2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，\r\n 而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；\r\n 随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时\r\n 应该不变，left始终为2，子段变成 ba才对。\r\n 为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).\r\n 另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，\r\n 因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！*/\r\n if(map.containsKey(s.charAt(i))){//charAt() 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。\r\n left = Math.max(left,map.get(s.charAt(i)) + 1); //map.get():返回字符所对应的索引，当发现重复元素时，窗口左指针右移\r\n } //map.get(\'a\')=0,因为map中只有第一个a的下标，然后更新left指针到原来left的的下一位，不管是否更新left，都要更新 s.charAt(i) 的位置！\r\n map.put(s.charAt(i),i); //再更新map中a映射的下标\r\n max = Math.max(max,i-left+1); //比较两个参数的大小\r\n }\r\n return max;\r\n }\r\n}\r\n```\r\n\r\n```c++\r\nclass Solution {\r\npublic:\r\n int lengthOfLongestSubstring(string s) {\r\n if(s.size() == 0) return 0;\r\n unordered_set<char> lookup;\r\n int maxStr = 0;\r\n int left = 0;\r\n for(int i = 0; i < s.size(); i++){\r\n while (lookup.find(s[i]) != lookup.end()){\r\n lookup.erase(s[left]);\r\n left ++;\r\n }\r\n maxStr = max(maxStr,i-left+1);\r\n lookup.insert(s[i]);\r\n }\r\n return maxStr;\r\n \r\n }\r\n};\r\n```\r\n\r\n**方法二：**\r\n\r\n滑动窗口思路和算法\r\n\r\n 我们先用一个例子来想一想如何在较优的时间复杂度内通过本题。\r\n\r\n 我们不妨以示例一中的字符串 `abcabcbb` 为例，找出 **从每一个字符开始的，不包含重复字符的最长子串**，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：\r\n\r\n> 以` (a)bcabcbb` 开始的最长字符串为 `(abc)abcbb`；\r\n> 以 `a(b)cabcbb` 开始的最长字符串为 `a(bca)bcbb`；\r\n> 以 `ab(c)abcbb` 开始的最长字符串为 `ab(cab)cbb`；\r\n> 以` abc(a)bcbb` 开始的最长字符串为 `abc(abc)bb`；\r\n> 以` abca(b)cbb `开始的最长字符串为 `abca(bc)bb`；\r\n> 以 `abcab(c)bb` 开始的最长字符串为 `abcab(cb)b`；\r\n> 以 `abcabc(b)b` 开始的最长字符串为 `abcabc(b)b`；\r\n> 以 `abcabcb(b) `开始的最长字符串为 `abcabcb(b)`。\r\n\r\n 发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 **k** 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 **r_k**。那么当我们选择第 **k+1**个字符作为起始位置时，首先从 **k+1** 到 **r_k**的字符显然是不重复的，并且由于少了原本的第 **k** 个字符，我们可以尝试继续增大 **r_k** ，直到右侧出现了重复字符为止。\r\n\r\n 这样以来，我们就可以使用「滑动窗口」来解决这个问题了：\r\n\r\n 我们使用两个指针表示字符串中的某个子串（的左右边界）。其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 **r_k** ；在每一步的操作中，我们会将左指针向右移动一格，表示 **我们开始枚举下一个字符作为起始位置**，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 **以左指针开始的，不包含重复字符的最长子串。**我们记录下这个子串的长度；\r\n\r\n 在枚举结束后，我们找到的最长的子串的长度即为答案。\r\n\r\n**判断重复字符**\r\n\r\n 在上面的流程中，我们还需要使用一种数据结构来判断 **是否有重复的字符**，常用的数据结构为哈希集合（即 `C++ `中的 `std::unordered_set`，`Java` 中的 `HashSet`，`Python` 中的 `set`, `JavaScript` 中的 `Set`）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。\r\n\r\n 至此，我们就完美解决了本题。\r\n\r\n```java\r\nclass Solution {\r\n public int lengthOfLongestSubstring(String s) {\r\n // 哈希集合，记录每个字符是否出现过\r\n Set<Character> occ = new HashSet<Character>();\r\n int n = s.length();\r\n // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动\r\n int rk = -1, ans = 0;\r\n for (int i = 0; i < n; ++i) {\r\n if (i != 0) {\r\n // 左指针向右移动一格，移除一个字符\r\n occ.remove(s.charAt(i - 1));\r\n }\r\n while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {\r\n // 不断地移动右指针\r\n occ.add(s.charAt(rk + 1));\r\n ++rk;\r\n }\r\n // 第 i 到 rk 个字符是一个极长的无重复字符子串\r\n ans = Math.max(ans, rk - i + 1);\r\n }\r\n return ans;\r\n }\r\n}\r\n```\r\n\r\n```c++\r\nclass Solution {\r\npublic:\r\n int lengthOfLongestSubstring(string s) {\r\n // 哈希集合，记录每个字符是否出现过\r\n unordered_set<char> occ;\r\n int n = s.size();\r\n // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动\r\n int rk = -1, ans = 0;\r\n // 枚举左指针的位置，初始值隐性地表示为 -1\r\n for (int i = 0; i < n; ++i) {\r\n if (i != 0) {\r\n // 左指针向右移动一格，移除一个字符\r\n occ.erase(s[i - 1]);\r\n }\r\n while (rk + 1 < n && !occ.count(s[rk + 1])) {\r\n // 不断地移动右指针\r\n occ.insert(s[rk + 1]);\r\n ++rk;\r\n }\r\n // 第 i 到 rk 个字符是一个极长的无重复字符子串\r\n ans = max(ans, rk - i + 1);\r\n }\r\n return ans;\r\n }\r\n};\r\n```\r\n\r\n**复杂度分析**\r\n\r\n> **时间复杂度：**O(N)，其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。\r\n>\r\n> **空间复杂度：**O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。\r\n\r\n#### 6、最长回文子串\r\n\r\n 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。\r\n\r\n**示例 1：**\r\n\r\n> 输入: \"babad\"\r\n> 输出: \"bab\"\r\n> 注意: \"aba\" 也是一个有效答案。\r\n\r\n**示例 2：**\r\n\r\n> 输入: \"cbbd\"\r\n> 输出: \"bb\"\r\n\r\n**说明：**\r\n\r\n 以下解法中「暴力算法」是基础，「动态规划」必须掌握，「中心扩散」方法要会写；\r\n 「Manacher 算法」仅用于扩宽视野，绝大多数的算法面试中，面试官都不会要求写这个方法（除非面试者是竞赛选手）。\r\n\r\n**方法一：暴力匹配 （Brute Force）**\r\n\r\n 根据回文子串的定义，枚举所有长度大于等于 22 的子串，依次判断它们是否是回文；\r\n 在具体实现时，可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”；\r\n 在记录最长回文子串的时候，可以只记录“当前子串的起始位置”和“子串长度”，不必做截取。这一步我们放在后面的方法中实现。\r\n 说明：暴力解法时间复杂度高，但是思路清晰、编写简单。由于编写正确性的可能性很大，**可以使用暴力匹配算法检验我们编写的其它算法是否正确**。优化的解法在很多时候，是基于“暴力解法”，以空间换时间得到的，因此思考清楚暴力解法，分析其缺点，很多时候能为我们打开思路。\r\n\r\n```java\r\npublic class Solution {\r\n\r\n public String longestPalindrome(String s) {\r\n int len = s.length();\r\n if (len < 2) {\r\n return s;\r\n }\r\n\r\n int maxLen = 1;\r\n int begin = 0;\r\n // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组\r\n char[] charArray = s.toCharArray();\r\n\r\n // 枚举所有长度大于 1 的子串 charArray[i..j]\r\n for (int i = 0; i < len - 1; i++) {\r\n for (int j = i + 1; j < len; j++) {\r\n if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {\r\n maxLen = j - i + 1;\r\n begin = i;\r\n }\r\n }\r\n }\r\n return s.substring(begin, begin + maxLen);\r\n }\r\n\r\n /**\r\n * 验证子串 s[left..right] 是否为回文串\r\n */\r\n private boolean validPalindromic(char[] charArray, int left, int right) {\r\n while (left < right) {\r\n if (charArray[left] != charArray[right]) {\r\n return false;\r\n }\r\n left++;\r\n right--;\r\n }\r\n return true;\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析：**\r\n\r\n> **时间复杂度：**O(N^3)，这里 NN 是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串，这三种操作都与 NN 相关；\r\n> **空间复杂度：**O(1)，只使用到常数个临时变量，与字符串长度无关。\r\n\r\n**方法二：动态规划**\r\n\r\n 这道题比较烦人的是判断回文子串。因此需要一种能够快速判断原字符串的所有子串是否是回文子串的方法，于是想到了「动态规划」。\r\n\r\n 「动态规划」的一个关键的步骤是想清楚「状态如何转移」。事实上，「回文」天然具有「状态转移」性质。\r\n\r\n 一个回文去掉两头以后，剩下的部分依然是回文（这里暂不讨论边界情况）；\r\n\r\n依然从回文串的定义展开讨论：\r\n\r\n> 如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；\r\n> 如果一个字符串的头尾两个字符相等，才有必要继续判断下去。\r\n> 如果里面的子串是回文，整体就是回文串；\r\n> 如果里面的子串不是回文串，整体就不是回文串。\r\n\r\n即：**在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质**，这就是状态转移。因此可以把「状态」定义为原字符串的一个子串是否为回文子串。\r\n\r\n**第 1 步：定义状态**\r\n\r\n`dp[i][j]`表示子串 `s[i..j] `是否为回文子串，这里子串 `s[i..j] `定义为左闭右闭区间，可以取到 `s[i] `和 `s[j]`。\r\n\r\n**第 2 步：思考状态转移方程**\r\n\r\n 在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：\r\n\r\n```java\r\ndp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]\r\n```\r\n\r\n说明：\r\n\r\n 「动态规划」事实上是在填一张二维表格，由于构成子串，因此` i `和 `j` 的关系是 `i <= j` ，因此，只需要填这张表格对角线以上的部分。\r\n\r\n 看到 `dp[i + 1][j - 1]` 就得考虑边界情况。\r\n\r\n 边界条件是：表达式 `[i + 1, j - 1]` 不构成区间，即长度严格小于 2，即` j - 1 - (i + 1) + 1 < 2` ，整理得` j - i < 3`。\r\n\r\n 这个结论很显然：`j - i < 3` 等价于` j - i + 1 < 4`，即当子串 `s[i..j] `的长度等于 `2` 或者等于 `3` 的时候，其实只需要判断一下头尾两个字符是否相等就可以直接下结论了。\r\n\r\n 如果子串 `s[i + 1..j - 1]` 只有 1 个字符，即去掉两头，剩下中间部分只有 11 个字符，显然是回文；\r\n 如果子串 `s[i + 1..j - 1]` 为空串，那么子串 `s[i, j] `一定是回文子串。\r\n因此，在 `s[i] == s[j]` 成立和 `j - i < 3` 的前提下，直接可以下结论，`dp[i][j] = true`，否则才执行状态转移。\r\n\r\n**第 3 步：考虑初始化**\r\n\r\n 初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 `true`，即 `dp[i][i] = true` 。\r\n\r\n 事实上，初始化的部分都可以省去。因为只有一个字符的时候一定是回文，dp[i][i] 根本不会被其它状态值所参考。\r\n\r\n**第 4 步：考虑输出**\r\n\r\n 只要一得到 `dp[i][j] = true`，就记录子串的长度和起始位置，没有必要截取，这是因为截取字符串也要消耗性能，记录此时的回文子串的「起始位置」和「回文长度」即可。\r\n\r\n**第 5 步：考虑优化空间**\r\n\r\n 因为在填表的过程中，只参考了左下方的数值。事实上可以优化，但是增加了代码编写和理解的难度，丢失可读和可解释性。在这里不优化空间。\r\n\r\n 注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。\r\n\r\n 大家能够可以自己动手，画一下表格，相信会对「动态规划」作为一种「表格法」有一个更好的理解。\r\n\r\n**参考代码 2：**\r\n\r\n```java\r\npublic class Solution {\r\n\r\n public String longestPalindrome(String s) {\r\n // 特判\r\n int len = s.length();\r\n if (len < 2) {\r\n return s;\r\n }\r\n\r\n int maxLen = 1;\r\n int begin = 0;\r\n\r\n // dp[i][j] 表示 s[i, j] 是否是回文串\r\n boolean[][] dp = new boolean[len][len];\r\n char[] charArray = s.toCharArray();\r\n\r\n for (int i = 0; i < len; i++) {\r\n dp[i][i] = true;\r\n }\r\n for (int j = 1; j < len; j++) {\r\n for (int i = 0; i < j; i++) {\r\n if (charArray[i] != charArray[j]) {\r\n dp[i][j] = false;\r\n } else {\r\n if (j - i < 3) {\r\n dp[i][j] = true;\r\n } else {\r\n dp[i][j] = dp[i + 1][j - 1];\r\n }\r\n }\r\n\r\n // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置\r\n if (dp[i][j] && j - i + 1 > maxLen) {\r\n maxLen = j - i + 1;\r\n begin = i;\r\n }\r\n }\r\n }\r\n return s.substring(begin, begin + maxLen);\r\n }\r\n}\r\n```\r\n\r\n**复杂度分析：**\r\n\r\n> **时间复杂度：**O(N^{2})。\r\n> **空间复杂度：**O(N^{2})，二维 dp 问题，一个状态得用二维有序数对表示，因此空间复杂度是 O(N^{2})。', '2020-10-06 08:31:18.017000', 'https://ss3.bdstatic.com/70cFv8Sh_Q1YnxGkpoWK1HF6hhy/it/u=1739836374,4159281451&fm=26&gp=0.jpg', '转载', b'1', b'1', b'1', 'LeetCode算法4-6(难度中等)', '2020-10-06 08:40:07.296000', 5, 88, 1, 'LeetCode算法题；两数相加；给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。无重复字符的最长子串；给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。最长回文子串；给定一个字符串 s，找到 s 中最长的回文子串');
INSERT INTO `t_blog` VALUES (94, b'1', b'1', '#### 4、Z字形变换\r\n\r\n**题目理解：**\r\n 字符串 `s` 是以 **Z** 字形为顺序存储的字符串，目标是按行打印。\r\n 设 `numRows` 行字符串分别为 `s1,s2 ,..., sn` ，则容易发现：按顺序遍历字符串 `s` 时，每个字符 `c `在 `Z` 字形中对应的 **行索引** 先从 `s1`增大至 `sn`，再从 `sn`减小至 `s1…… `如此反复。\r\n因此，解决方案为：模拟这个行索引的变化，在遍历 `s` 中把每个字符填到正确的行 `res[i] `。\r\n\r\n**算法流程：** 按顺序遍历字符串 `s`；\r\n\r\n `res[i] += c`： 把每个字符 `c` 填入对应行 `si`；\r\n\r\n `i += flag`： 更新当前字符 `c` 对应的行索引；\r\n\r\n `flag = - flag`： 在达到 **Z** 字形转折点时，执行反向。\r\n\r\n**复杂度分析：**\r\n\r\n> **时间复杂度 O(N) ：**遍历一遍字符串 s；\r\n> **空间复杂度 O(N) ：**各行字符串共占用 O(N)额外空间。\r\n\r\n```java\r\nclass Solution {\r\n public String convert(String s, int numRows) {\r\n if(numRows < 2) return s;\r\n List<StringBuilder> rows = new ArrayList<StringBuilder>();\r\n for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());\r\n int i = 0, flag = -1;\r\n for(char c : s.toCharArray()) {\r\n rows.get(i).append(c);\r\n if(i == 0 || i == numRows -1) flag = - flag;\r\n i += flag;\r\n }\r\n StringBuilder res = new StringBuilder();\r\n for(StringBuilder row : rows) res.append(row);\r\n return res.toString();\r\n }\r\n}\r\n```\r\n\r\n#### 5、字符串转换整数（`atoi`）\r\n\r\n请你来实现一个 `atoi` 函数，使其能将字符串转换成整数。\r\n\r\n 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：\r\n\r\n 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。\r\n 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。\r\n 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。\r\n\r\n**注意：**假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。\r\n\r\n 在任何情况下，若函数不能进行有效的转换时，请返回 0 。\r\n\r\n**提示：**\r\n\r\n 本题中的空白字符只包括空格字符 `\' \'` 。\r\n 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。\r\n\r\n**示例 1:**\r\n\r\n> 输入: \"42\"\r\n> 输出: 42\r\n\r\n**示例 2:**\r\n\r\n> 输入: \" -42\"\r\n> 输出: -42\r\n> 解释: 第一个非空白字符为 \'-\', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。\r\n\r\n**示例 3:**\r\n\r\n> 输入: \"4193 with words\"\r\n> 输出: 4193\r\n> 解释: 转换截止于数字 \'3\' ，因为它的下一个字符不为数字。\r\n\r\n**示例 4:**\r\n\r\n> 输入: \"words and 987\"\r\n> 输出: 0\r\n> 解释: 第一个非空字符是 \'w\', 但它不是数字或正、负号。因此无法执行有效的转换。\r\n\r\n**示例 5:**\r\n\r\n> 输入: \"-91283472332\"\r\n> 输出: -2147483648\r\n> 解释: 数字 \"-91283472332\" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。\r\n\r\n**方法一：**\r\n\r\n 这道题目其实出得有点恶心，需要比较仔细才可以通过。当然比这题更恶心的是要需要识别科学计数法，识别二进制(0b01)，八进制（012)，十六进制（0xab），不知道`leetcode`会不会丧心病狂出这样的题目（或者已经有了？）。。\r\n\r\n这题的做法大概是这样：\r\n\r\n 去掉前导空格\r\n 再是处理正负号\r\n 识别数字，注意越界情况。\r\n\r\n这道题目如果只是简单地字符串转整数的话，就是简单地 `ans = ans * 10 + digit`。\r\n 但是注意这道题目可能会超过integer的最大表示！\r\n 也就是说会在某一步 `ans * 10 + digit > Integer.MAX_VALUE`。\r\n`*10` 和 `+digit` 都有可能越界，那么只要把这些都移到右边去就可以了。\r\n`ans > (Integer.MAX_VALUE - digit) / 10` 就是越界。\r\n\r\n 不过我的忠告是，等真正工作以后，尽可能地调用`jdk`的方法，比如`Character.isDigit`。如果没有你想要的`api`，也要尽量使用`guava`，`apache common`等常见的`utils`包，尽量不要自己造轮子，一是这样减少出错的可能，二是比较无脑，保护脑细胞~\r\n\r\n下面是代码：\r\n\r\n```java\r\npublic class Solution {\r\n public int myAtoi(String str) {\r\n char[] chars = str.toCharArray();\r\n int n = chars.length;\r\n int idx = 0;\r\n while (idx < n && chars[idx] == \' \') {\r\n // 去掉前导空格\r\n idx++;\r\n }\r\n if (idx == n) {\r\n //去掉前导空格以后到了末尾了\r\n return 0;\r\n }\r\n boolean negative = false;\r\n if (chars[idx] == \'-\') {\r\n //遇到负号\r\n negative = true;\r\n idx++;\r\n } else if (chars[idx] == \'+\') {\r\n // 遇到正号\r\n idx++;\r\n } else if (!Character.isDigit(chars[idx])) {\r\n // 其他符号\r\n return 0;\r\n }\r\n int ans = 0;\r\n while (idx < n && Character.isDigit(chars[idx])) {\r\n int digit = chars[idx] - \'0\';\r\n if (ans > (Integer.MAX_VALUE - digit) / 10) {\r\n // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE\r\n // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。\r\n return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;\r\n }\r\n ans = ans * 10 + digit;\r\n idx++;\r\n }\r\n return negative? -ans : ans;\r\n }\r\n}\r\n```', '2020-10-06 08:49:51.987000', 'https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1601984371876&di=661d2a4572aae10b1f505c11bdb8307a&imgtype=0&src=http%3A%2F%2Fimg1.imgtn.bdimg.com%2Fit%2Fu%3D2003029766%2C3601196323%26fm%3D214%26gp%3D0.jpg', '转载', b'1', b'1', b'1', 'LeetCode算法7-8(难度中等)', '2020-10-06 08:51:43.183000', 2, 88, 1, 'LeetCode算法：Z字形变换；字符串 `s`是以 Z字形为顺序存储的字符串，目标是按行打印。字符串转换整数（`atoi`）；请你来实现一个 `atoi` 函数，使其能将字符串转换成整数。该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。\r\n');
INSERT INTO `t_blog` VALUES (95, b'1', b'1', '#### 9、寻找两个正序数组的中位数\r\n\r\n 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。\r\n\r\n 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。\r\n\r\n 你可以假设 nums1 和 nums2 不会同时为空。\r\n\r\n**示例 1:**\r\n\r\n> nums1 = [1, 3]\r\n> nums2 = [2]\r\n>\r\n> 则中位数是 2.0\r\n\r\n**示例 2:**\r\n\r\n> nums1 = [1, 2]\r\n> nums2 = [3, 4]\r\n>\r\n> 则中位数是 (2 + 3)/2 = 2.5\r\n\r\n**解法一**\r\n\r\n 简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。\r\n\r\n```java\r\npublic double findMedianSortedArrays(int[] nums1, int[] nums2) {\r\n int[] nums;\r\n int m = nums1.length;\r\n int n = nums2.length;\r\n nums = new int[m + n];\r\n if (m == 0) {\r\n if (n % 2 == 0) {\r\n return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;\r\n } else {\r\n\r\n return nums2[n / 2];\r\n }\r\n }\r\n if (n == 0) {\r\n if (m % 2 == 0) {\r\n return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;\r\n } else {\r\n return nums1[m / 2];\r\n }\r\n }\r\n\r\n int count = 0;\r\n int i = 0, j = 0;\r\n while (count != (m + n)) {\r\n if (i == m) {\r\n while (j != n) {\r\n nums[count++] = nums2[j++];\r\n }\r\n break;\r\n }\r\n if (j == n) {\r\n while (i != m) {\r\n nums[count++] = nums1[i++];\r\n }\r\n break;\r\n }\r\n\r\n if (nums1[i] < nums2[j]) {\r\n nums[count++] = nums1[i++];\r\n } else {\r\n nums[count++] = nums2[j++];\r\n }\r\n }\r\n\r\n if (count % 2 == 0) {\r\n return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;\r\n } else {\r\n return nums[count / 2];\r\n }\r\n}\r\n```\r\n\r\n> **时间复杂度：**遍历全部数组 (m+n)(m+n)\r\n>\r\n> **空间复杂度：**开辟了一个数组，保存合并后的两个数组 O(m+n)O(m+n)\r\n\r\n**解法二**\r\n\r\n 其实，我们不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了。\r\n\r\n 开始的思路是写一个循环，然后里边判断是否到了中位数的位置，到了就返回结果，但这里对偶数和奇数的分类会很麻烦。当其中一个数组遍历完后，出了 `for` 循环对边界的判断也会分几种情况。总体来说，虽然复杂度不影响，但代码会看起来很乱。\r\n\r\n 首先是怎么将奇数和偶数的情况合并一下。\r\n\r\n 用 `len `表示合并后数组的长度，如果是奇数，我们需要知道第 `（len+1）/2 `个数就可以了，如果遍历的话需要遍历 `int(len/2 ) + 1` 次。如果是偶数，我们需要知道第`len/2`和`len/2+1` 个数，也是需要遍历 `len/2+1` 次。所以遍历的话，奇数和偶数都是 `len/2+1` 次。\r\n\r\n 返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量 `left` 和 `right`，`right` 保存当前循环的结果，在每次循环前将 `right` 的值赋给 `left`。这样在最后一次循环的时候，`left` 将得到 `right` 的值，也就是上一次循环的结果，接下来 `right` 更新为最后一次的结果。\r\n\r\n 循环中该怎么写，什么时候 `A` 数组后移，什么时候 `B` 数组后移。用 `aStart` 和 `bStart` 分别表示当前指向 `A` 数组和 `B` 数组的位置。如果 `aStart` 还没有到最后并且此时 `A` 位置的数字小于 `B` 位置的数组，那么就可以后移了。也就是`aStart`＜`m&&A[aStart]`< `B[bStart]`。\r\n\r\n 但如果 `B` 数组此刻已经没有数字了，继续取数字 `B[ bStart ]`，则会越界，所以判断下 `bStart` 是否大于数组长度了，这样 `||` 后边的就不会执行了，也就不会导致错误了，所以增加为 `aStart`＜`m&&(bStart)` >= `n||A[aStart]<B[bStart])` 。\r\n\r\n**代码**\r\n\r\n```java\r\npublic double findMedianSortedArrays(int[] A, int[] B) {\r\n int m = A.length;\r\n int n = B.length;\r\n int len = m + n;\r\n int left = -1, right = -1;\r\n int aStart = 0, bStart = 0;\r\n for (int i = 0; i <= len / 2; i++) {\r\n left = right;\r\n if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {\r\n right = A[aStart++];\r\n } else {\r\n right = B[bStart++];\r\n }\r\n }\r\n if ((len & 1) == 0)\r\n return (left + right) / 2.0;\r\n else\r\n return right;\r\n}\r\n```\r\n\r\n> **时间复杂度：**遍历 `len/2+1` 次，`len=m+n`，所以时间复杂度依旧是 `O(m+n)`。\r\n>\r\n> **空间复杂度：**我们申请了常数个变量，也就是 `m`，`n`，`len`，`left`，`right`，`aStart`，`bStart` 以及 `i`。总共 8 个变量，所以空间复杂度是 `O(1）`。\r\n\r\n#### 10、正则表达式匹配\r\n\r\n给你一个字符串 `s` 和一个字符规律 `p`，请你来实现一个支持` \'.\' `和 `\'*\' `的正则表达式匹配。\r\n\r\n> `\'.\'`匹配任意单个字符\r\n> `\'*\'`匹配零个或多个前面的那一个元素\r\n\r\n所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。\r\n\r\n**说明:**\r\n\r\n> `s` 可能为空，且只包含从 `a-z` 的小写字母。\r\n> `p` 可能为空，且只包含从 `a-z` 的小写字母，以及字符` . `和` *`。\r\n\r\n**示例 1:**\r\n\r\n> 输入:\r\n> s = `\"aa\"`\r\n> p = `\"a\"`\r\n> 输出: false\r\n> 解释: \"a\" 无法匹配 \"aa\" 整个字符串。\r\n\r\n**示例 2:**\r\n\r\n> 输入:\r\n> s = `\"aa\"`\r\n> p = `\"a*\"`\r\n> 输出: true\r\n> 解释: 因为 \'*\' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 \'a\'。因此，字符串 \"aa\" 可被视为 \'a\' 重复了一次。\r\n\r\n**示例 3:**\r\n\r\n> 输入:\r\n> s =` \"ab\"`\r\n> p =` \".*\"`\r\n> 输出: true\r\n> 解释: \".*\" 表示可匹配零个或多个（\'*\'）任意字符（\'.\'）。\r\n\r\n**示例 4:**\r\n\r\n> 输入:\r\n> s = `\"aab\"`\r\n> p =` \"c*a*b\"`\r\n> 输出: true\r\n> 解释: 因为 \'*\' 表示零个或多个，这里 \'c\' 为 0 个, \'a\' 被重复一次。因此可以匹配字符串 \"aab\"。\r\n\r\n**示例 5:**\r\n\r\n> 输入:\r\n> s = `\"mississippi\"`\r\n> p = `\"mis*is*p*.\"`\r\n> 输出: false\r\n\r\n**方法一：动态规划**\r\n\r\n**先明确一点：**\r\n\r\n```java\r\n例子:s=\"a\",p=\"c*a\",返回为true,\r\n因此其实 \"c*\" 是放在一起看的，\r\nc* 可以是无，或者是单个多个c。\r\n而不是 * 可以是无或者是单个多个a。\r\n```\r\n\r\n首先定义状态：\r\n\r\n `dp[i][j] ：s`前i个字符`[0,i)`是否能匹配p的前j个字符`[0,j)`。要明确一点，这里是左闭右开的，因此此时是在比较`s[i-1]与p[i-1]`。\r\n\r\n 确定状态方程之前先明确都会出现什么情况。首先就是`s[i-1]`与`p[j-1]`之间的关系，可能相等，可能不等。不等的情况下有三种情况：（1）`p[j-1]为\'*\'`，（2）`p[j-1]为\'.\'`（3）`p[j-1]`就是普通的一个字符。接下来对这些情况进行具体的解释。\r\n\r\n**完整思路**\r\n\r\n**1.s[i-1]==p[j-1]**\r\n\r\n```java\r\ndp[i][j] = dp[i-1][j-1];\r\n```\r\n\r\n**2.s[i-1]!=p[j-1]**\r\n\r\n**1)p[j-1]==\'.\'**\r\n \'.\'是万能字符，可以直接让\'.\'等于s[i]处的字符\r\n\r\n```java\r\ndp[i][j] = dp[i-1][j-1];\r\n```\r\n\r\n**2)p[j-1]==\'*\'**\r\n `\'*\'`可以匹配零个或多个前面的元素，而是否能取多个或1个字符要看j-2的字符是否和i-1的字符相同。因此首先要判断`p[j-2]==s[i-1]`\r\n\r\n**(1)p[j-2]!=s[i-1]**\r\n\r\n `j-2`的字符不等于`i-1`的字符，那就只能让`*`代表取0个字符。\r\n`dp[i][j] = dp[i][j-2] `(相当于去掉`p[j-1]`和`p[j-2]`)\r\n\r\n**(2)p[j-2]==s[i-1]||p[j-2]==\'.\'**\r\n\r\n 可以让`*`代表0个字符或多个字符，如果`p[j-2]`为`\'.\'`就可以替换为`s[i-1]`的字符\r\n\r\n**`\'*\'`取0个字符**\r\n\r\n 例子：`s:aab,p:aabb*`,虽然`j-2`和`i-1`相等，但是`dp[i][j-2]`已经匹配了，直接删去`j-1`和`j-2`即可（你来之前我们就已经是总冠军了）\r\n\r\n```java\r\ndp[i][j] = dp[i][j-2] (取0个字符)\r\n```\r\n\r\n**`\'*\'`取1个字符**\r\n\r\n 例子：s:aab,p:aab*\r\n\r\n```java\r\ndp[i][j] = dp[i][j-1] (取1个字符，相当于去掉p[j-1])\r\n```\r\n\r\n**`\'*\'`取多个字符**\r\n 例子：`s：aabb,p：aab*`,要判断的是`s:aab`和`aab*` 是否可以匹配，如果可以匹配的话，那么s后面再加上一个b也没关系，因为*可以变成多个b。\r\n\r\n```java\r\ndp[i][j] = dp[i-1][j] (取多个字符)\r\n```\r\n\r\n**3)else（j处就是个普通字符，`dp[i][j]`肯定不能匹配了,其实这里写不写都可以，只不过为了让大家看着思路清晰。）**\r\n\r\n```java\r\ndp[i][j] = false;\r\n```\r\n\r\n**注意**\r\n\r\n最终要确定三点。\r\n1.本题必须初始化第一行。也就是`dp[0][j]`。判断条件为：\r\n\r\n```java\r\n//p[j-1]为*可以把j-2和j-1处的字符删去，只有[0,j-3]也为true才可以让dp[0,j-1]为true。\r\nif(p.charAt(j-1)==\'*\'&&dp[0][j-2])\r\n```\r\n\r\n2.以理解角度两个都是空的字符串肯定互相匹配，以代码角度，当`s=\"a\"`,`p=\"a\"`时，`dp[1][1] `= `dp[0][0]`,因此必须`dp[0`][0]取`true`\r\n\r\n```java\r\ndp[0][0] = true;\r\n```\r\n\r\n3.字符串为空长度为0，只需要判断他们是否为空即可。\r\n\r\n```java\r\n/*\r\ns和p可能为空。空的长度就是0，但是这些情况都已经判断过了，只需要判断是否为null即可\r\nif(p.length()==0&&s.length()==0)\r\n return true;\r\n */\r\n if(s==null||p==null)\r\n return false;\r\n```\r\n\r\n**写在最后（总结出现`‘*’`的情况）**\r\n\r\n 这里最难理解的就是如果`p[j-1]==\'*\'`的情况，上述的描述是把整个情况完全描绘出来了，其实可以简略一些过程。\r\n\r\n*的情况只有两种：\r\n\r\n1.不论`p[j-2]`是否等于`s[i-1]`都可以删除掉`j-1`和`j-2`处字符：\r\n\r\n```java\r\ndp[i][j] = dp[i][j]||dp[i][j-2];\r\n```\r\n\r\n2.只有`p[j-2]`==`s[i-1]`或`p[j-2]`==`‘.’`才可以让*取1个或者多个字符：\r\n\r\n```java\r\nif(nowpLast==nows||nowpLast==\'.\')\r\n dp[i][j] = dp[i-1][j]||dp[i][j-1];\r\n```\r\n\r\n**完整题解**\r\n\r\n```java\r\nclass Solution {\r\n public boolean isMatch(String s, String p) {\r\n /*\r\n s和p可能为空。空的长度就是0，但是这些情况都已经判断过了，只需要判断是否为null即可\r\n if(p.length()==0&&s.length()==0)\r\n return true;\r\n */\r\n if(s==null||p==null)\r\n return false;\r\n int rows = s.length();\r\n int columns = p.length();\r\n boolean[][]dp = new boolean[rows+1][columns+1];\r\n //s和p两个都为空，肯定是可以匹配的，同时这里取true的原因是\r\n //当s=a，p=a，那么dp[1][1] = dp[0][0]。因此dp[0][0]必须为true。\r\n dp[0][0] = true;\r\n for(int j=1;j<=columns;j++)\r\n { \r\n //p[j-1]为*可以把j-2和j-1处的字符删去，只有[0,j-3]都为true才可以\r\n //因此dp[j-2]也要为true，才可以说明前j个为true\r\n if(p.charAt(j-1)==\'*\'&&dp[0][j-2])\r\n dp[0][j] = true;\r\n }\r\n\r\n for(int i=1;i<=rows;i++)\r\n {\r\n for(int j=1;j<=columns;j++)\r\n {\r\n char nows = s.charAt(i-1);\r\n char nowp = p.charAt(j-1);\r\n if(nows==nowp)\r\n {\r\n dp[i][j] = dp[i-1][j-1];\r\n }else{\r\n if(nowp==\'.\')\r\n dp[i][j] = dp[i-1][j-1];\r\n else if(nowp==\'*\')\r\n {\r\n //p需要能前移1个。（当前p指向的是j-1，前移1位就是j-2，因此为j>=2）\r\n if(j>=2){\r\n char nowpLast = p.charAt(j-2);\r\n //只有p[j-2]==s[i-1]或p[j-2]==‘.’才可以让*取1个或者多个字符：\r\n if(nowpLast==nows||nowpLast==\'.\')\r\n dp[i][j] = dp[i-1][j]||dp[i][j-1];\r\n //不论p[j-2]是否等于s[i-1]都可以删除掉j-1和j-2处字符：\r\n dp[i][j] = dp[i][j]||dp[i][j-2];\r\n }\r\n }\r\n else\r\n dp[i][j] = false;\r\n }\r\n }\r\n }\r\n return dp[rows][columns];\r\n }\r\n}\r\n```\r\n', '2020-10-06 08:54:52.274000', 'https://ss1.bdstatic.com/70cFuXSh_Q1YnxGkpoWK1HF6hhy/it/u=3436466062,4078714061&fm=26&gp=0.jpg', '转载', b'1', b'1', b'1', 'LeetCode算法9-10(难度困难)', '2020-10-06 08:54:52.274000', 3, 88, 1, 'LeetCode算法；寻找两个正序数组的中位数；给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。正则表达式匹配给你一个字符串 `s` 和一个字符规律 `p`，请你来实现一个支持` \'.\' `和 `\'*\' `的正则表达式匹配。');
INSERT INTO `t_blog` VALUES (99, b'1', b'1', '#### 1、组合两个表\r\n\r\n**表1：`Person`**\r\n\r\n```\r\n+-------------+---------+\r\n| 列名 | 类型 |\r\n+-------------+---------+\r\n| PersonId | int |\r\n| FirstName | varchar |\r\n| LastName | varchar |\r\n+-------------+---------+\r\nPersonId 是上表主键\r\n```\r\n\r\n**表2：`Address`**\r\n\r\n```\r\n+-------------+---------+\r\n| 列名 | 类型 |\r\n+-------------+---------+\r\n| AddressId | int |\r\n| PersonId | int |\r\n| City | varchar |\r\n| State | varchar |\r\n+-------------+---------+\r\nAddressId 是上表主键\r\n```\r\n\r\n 编写一个 SQL 查询，满足条件：无论 person 是否有地址信息，都需要基于上述两表提供 person 的以下信息：\r\n\r\n```\r\nFirstName, LastName, City, State\r\n```\r\n\r\n**方法一：使用 outer join**\r\n\r\n**算法**\r\n\r\n 因为表 `Address` 中的 `personId` 是表 `Person` 的外关键字，所以我们可以连接这两个表来获取一个人的地址信息。\r\n\r\n 考虑到可能不是每个人都有地址信息，我们应该使用 `outer join` 而不是默认的 `inner join`。\r\n\r\n```mysql\r\nselect FirstName, LastName, City, State\r\nfrom Person left join Address\r\non Person.PersonId = Address.PersonId;\r\n```\r\n\r\n 注意：如果没有某个人的地址信息，使用 `where` 子句过滤记录将失败，因为它不会显示姓名信息。\r\n\r\n#### 2、第二高的薪水\r\n\r\n 编写一个 SQL 查询，获取 `Employee` 表中第二高的薪水（Salary） 。\r\n\r\n```\r\n+----+--------+\r\n| Id | Salary |\r\n+----+--------+\r\n| 1 | 100 |\r\n| 2 | 200 |\r\n| 3 | 300 |\r\n+----+--------+\r\n```\r\n\r\n 例如上述 `Employee` 表，SQL查询应该返回 `200` 作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回 `null`。\r\n\r\n```\r\n+---------------------+\r\n| SecondHighestSalary |\r\n+---------------------+\r\n| 200 |\r\n+---------------------+\r\n```\r\n\r\n**方法一：使用子查询和 `LIMIT` 子句**\r\n\r\n**算法**\r\n\r\n 将不同的薪资按降序排序，然后使用 [`LIMIT`](https://dev.mysql.com/doc/refman/5.7/en/select.html) 子句获得第二高的薪资。\r\n\r\n```MySQL\r\nSELECT DISTINCT\r\n Salary AS SecondHighestSalary\r\nFROM\r\n Employee\r\nORDER BY Salary DESC\r\nLIMIT 1 OFFSET 1\r\n```\r\n\r\n 然而，如果没有这样的第二最高工资，这个解决方案将被判断为 “错误答案”，因为本表可能只有一项记录。为了克服这个问题，我们可以将其作为临时表。\r\n\r\n```MySQL\r\nSELECT\r\n (SELECT DISTINCT\r\n Salary\r\n FROM\r\n Employee\r\n ORDER BY Salary DESC\r\n LIMIT 1 OFFSET 1) AS SecondHighestSalary;\r\n```\r\n\r\n**方法二：使用 IFNULL 和 LIMIT 子句**\r\n\r\n 解决 “NULL” 问题的另一种方法是使用 “IFNULL” 函数，如下所示。\r\n\r\n```MySQL\r\nSELECT\r\n IFNULL(\r\n (SELECT DISTINCT Salary\r\n FROM Employee\r\n ORDER BY Salary DESC\r\n LIMIT 1 OFFSET 1),\r\n NULL) AS SecondHighestSalary\r\n```\r\n\r\n#### 3、超过经理收入的员工\r\n\r\n `Employee` 表包含所有员工，他们的经理也属于员工。每个员工都有一个 Id，此外还有一列对应员工的经理的 Id。\r\n\r\n```\r\n+----+-------+--------+-----------+\r\n| Id | Name | Salary | ManagerId |\r\n+----+-------+--------+-----------+\r\n| 1 | Joe | 70000 | 3 |\r\n| 2 | Henry | 80000 | 4 |\r\n| 3 | Sam | 60000 | NULL |\r\n| 4 | Max | 90000 | NULL |\r\n+----+-------+--------+-----------+\r\n```\r\n\r\n 给定 `Employee` 表，编写一个 SQL 查询，该查询可以获取收入超过他们经理的员工的姓名。在上面的表格中，Joe 是唯一一个收入超过他的经理的员工。\r\n\r\n```\r\n+----------+\r\n| Employee |\r\n+----------+\r\n| Joe |\r\n+----------+\r\n```\r\n\r\n**方法 1：使用 `WHERE` 语句**\r\n\r\n**算法**\r\n\r\n 如下面表格所示，表格里存有每个雇员经理的信息，我们也许需要从这个表里获取两次信息。\r\n\r\n```sql\r\nSELECT *\r\nFROM Employee AS a, Employee AS b;\r\n```\r\n\r\n> 注意：关键词 \'AS\' 是可选的\r\n\r\n```\r\nId Name Salary ManagerId Id Name Salary ManagerId\r\n1 Joe 70000 3 1 Joe 70000 3\r\n2 Henry 80000 4 1 Joe 70000 3\r\n3 Sam 60000 1 Joe 70000 3\r\n4 Max 90000 1 Joe 70000 3\r\n1 Joe 70000 3 2 Henry 80000 4\r\n2 Henry 80000 4 2 Henry 80000 4\r\n3 Sam 60000 2 Henry 80000 4\r\n4 Max 90000 2 Henry 80000 4\r\n1 Joe 70000 3 3 Sam 60000 \r\n2 Henry 80000 4 3 Sam 60000 \r\n3 Sam 60000 3 Sam 60000 \r\n4 Max 90000 3 Sam 60000 \r\n1 Joe 70000 3 4 Max 90000 \r\n2 Henry 80000 4 4 Max 90000 \r\n3 Sam 60000 4 Max 90000 \r\n4 Max 90000 4 Max 90000 \r\n```\r\n\r\n> 前 3 列来自表格 a ，后 3 列来自表格 b\r\n\r\n 从两个表里使用 Select 语句可能会导致产生 笛卡尔乘积 。在这种情况下，输出会产生 4*4=16 个记录。然而我们只对雇员工资高于经理的人感兴趣。所以我们应该用 `WHERE` 语句加 2 个判断条件。\r\n\r\n```sql\r\nSELECT *\r\nFROM Employee AS a, Employee AS b\r\nWHERE a.ManagerId = b.Id AND a.Salary > b.Salary;\r\n```\r\n\r\n```\r\nId Name Salary ManagerId Id Name Salary ManagerId\r\n1 Joe 70000 3 3 Sam 60000 \r\n```\r\n\r\n 由于我们只需要输出雇员的名字，所以我们修改一下上面的代码，得到最终解法：\r\n\r\n```mysql\r\nSELECT a.Name AS \'Employee\'\r\nFROM Employee AS a,Employee AS b\r\nWHERE a.ManagerId = b.Id AND a.Salary > b.Salary;\r\n```\r\n\r\n**方法 2：使用 `JOIN` 语句**\r\n\r\n**算法**\r\n\r\n实际上， `JOIN` 是一个更常用也更有效的将表连起来的办法，我们使用 `ON` 来指明条件。\r\n\r\n```mysql\r\nSELECT a.NAME AS Employee\r\nFROM Employee AS a JOIN Employee AS b\r\n ON a.ManagerId = b.Id\r\n AND a.Salary > b.Salary;\r\n```\r\n\r\n#### 4、查找重复的电子邮箱\r\n\r\n 编写一个 SQL 查询，查找 `Person` 表中所有重复的电子邮箱。\r\n\r\n **示例：**\r\n\r\n```\r\n+----+---------+\r\n| Id | Email |\r\n+----+---------+\r\n| 1 | a@b.com |\r\n| 2 | c@d.com |\r\n| 3 | a@b.com |\r\n+----+---------+\r\n```\r\n\r\n 根据以上输入，你的查询应返回以下结果：\r\n\r\n```\r\n+---------+\r\n| Email |\r\n+---------+\r\n| a@b.com |\r\n+---------+\r\n```\r\n\r\n **说明：**所有电子邮箱都是小写字母。\r\n\r\n**方法一：使用 `GROUP BY` 和临时表**\r\n\r\n**算法**\r\n\r\n 重复的电子邮箱存在多次。要计算每封电子邮件的存在次数，我们可以使用以下代码。\r\n\r\n```mysql\r\nselect Email, count(Email) as num\r\nfrom Person\r\ngroup by Email;\r\n```\r\n\r\n```\r\n| Email | num |\r\n|---------|-----|\r\n| a@b.com | 2 |\r\n| c@d.com | 1 |\r\n```\r\n\r\n 以此作为临时表，我们可以得到下面的解决方案。\r\n\r\n```mysql\r\nselect Email from\r\n(\r\n select Email, count(Email) as num\r\n from Person\r\n group by Email\r\n) as statistic\r\nwhere num > 1;\r\n```\r\n\r\n**方法二：使用 `GROUP BY` 和 `HAVING` 条件**\r\n\r\n 向 `GROUP BY` 添加条件的一种更常用的方法是使用 `HAVING` 子句，该子句更为简单高效。\r\n\r\n 所以我们可以将上面的解决方案重写为：\r\n\r\n```mysql\r\nselect Email\r\nfrom Person\r\ngroup by Email\r\nhaving count(Email) > 1;\r\n```\r\n#### 5、从不订购的客户\r\n\r\n 某网站包含两个表，`Customers` 表和 `Orders` 表。编写一个 SQL 查询，找出所有从不订购任何东西的客户。\r\n\r\n`Customers` 表：\r\n\r\n```\r\n+----+-------+\r\n| Id | Name |\r\n+----+-------+\r\n| 1 | Joe |\r\n| 2 | Henry |\r\n| 3 | Sam |\r\n| 4 | Max |\r\n+----+-------+\r\n```\r\n\r\n`Orders` 表：\r\n\r\n```\r\n+----+------------+\r\n| Id | CustomerId |\r\n+----+------------+\r\n| 1 | 3 |\r\n| 2 | 1 |\r\n+----+------------+\r\n```\r\n\r\n例如给定上述表格，你的查询应返回：\r\n\r\n```\r\n+-----------+\r\n| Customers |\r\n+-----------+\r\n| Henry |\r\n| Max |\r\n+-----------+\r\n```\r\n\r\n**方法：使用子查询和 `NOT IN` 子句**\r\n\r\n**算法**\r\n\r\n 如果我们有一份曾经订购过的客户名单，就很容易知道谁从未订购过。\r\n\r\n 我们可以使用下面的代码来获得这样的列表。\r\n\r\n```sql\r\nselect customerid from orders;\r\n```\r\n\r\n 然后，我们可以使用 `NOT IN` 查询不在此列表中的客户。\r\n\r\n```mysql\r\nselect customers.name as \'Customers\'\r\nfrom customers\r\nwhere customers.id not in\r\n(\r\n select customerid from orders\r\n);\r\n```\r\n\r\n', '2020-10-06 08:59:39.629000', 'https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1601984914896&di=8d2bcad61f33ec732acf678dc11f963b&imgtype=0&src=http%3A%2F%2Fb-ssl.duitang.com%2Fuploads%2Fitem%2F201612%2F03%2F20161203232334_uJTSa.jpeg', '转载', b'1', b'1', b'1', 'LeetCode数据库1-5(简单)', '2020-10-06 09:10:52.925000', 3, 90, 1, 'LeetCode数据库；组合两个表；编写一个 SQL 查询。第二高的薪水；编写一个 SQL 查询，获取 `Employee` 表中第二高的薪水（Salary）。超过经理收入的员工；编写一个 SQL 查询，该查询可以获取收入超过他们经理的员工的姓名。查找重复的电子邮箱；查找 `Person` 表中所有重复的电子邮箱。从不订购的客户；找出所有从不订购任何东西的客户');
INSERT INTO `t_blog` VALUES (100, b'1', b'1', '### 中等\r\n\r\n#### 6、第N高的薪水\r\n\r\n 编写一个 SQL 查询，获取 `Employee` 表中第 *n* 高的薪水（Salary）。\r\n\r\n```\r\n+----+--------+\r\n| Id | Salary |\r\n+----+--------+\r\n| 1 | 100 |\r\n| 2 | 200 |\r\n| 3 | 300 |\r\n+----+--------+\r\n```\r\n\r\n 例如上述 `Employee` 表，*n = 2* 时，应返回第二高的薪水 `200`。如果不存在第 *n* 高的薪水，那么查询应返回 `null`。\r\n\r\n```\r\n+------------------------+\r\n| getNthHighestSalary(2) |\r\n+------------------------+\r\n| 200 |\r\n+------------------------+\r\n```\r\n\r\n**思路1：单表查询**\r\n\r\n 由于本题不存在分组排序，只需返回全局第N高的一个，所以自然想到的想法是用order by排序加limit限制得到。需要注意两个细节：\r\n\r\n 同薪同名且不跳级的问题，解决办法是用group by按薪水分组后再order by\r\n\r\n 排名第N高意味着要跳过N-1个薪水，由于无法直接用limit N-1，所以需先在函数开头处理N为N=N-1。\r\n\r\n **注：**这里不能直接用limit N-1是因为limit和offset字段后面只接受正整数（意味着0、负数、小数都不行）或者单一变量（意味着不能用表达式），也就是说想取一条，limit 2-1、limit 1.1这类的写法都是报错的。\r\n\r\n**注：**这种解法形式最为简洁直观，但仅适用于查询全局排名问题，如果要求各分组的每个第N名，则该方法不适用；而且也不能处理存在重复值的情况。\r\n\r\n**代码1**\r\n\r\n```mysql\r\nCREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT\r\nBEGIN\r\n SET N := N-1;\r\n RETURN (\r\n # Write your MySQL query statement below.\r\n SELECT \r\n salary\r\n FROM \r\n employee\r\n GROUP BY \r\n salary\r\n ORDER BY \r\n salary DESC\r\n LIMIT N, 1\r\n );\r\nEND\r\n```\r\n\r\n**思路2：子查询**\r\n\r\n 排名第N的薪水意味着该表中存在N-1个比其更高的薪水\r\n 注意这里的N-1个更高的薪水是指去重后的N-1个，实际对应人数可能不止N-1个\r\n 最后返回的薪水也应该去重，因为可能不止一个薪水排名第N\r\n 由于对于每个薪水的where条件都要执行一遍子查询，注定其效率低下\r\n\r\n**代码2**\r\n\r\n```mysql\r\nCREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT\r\nBEGIN\r\n RETURN (\r\n # Write your MySQL query statement below.\r\n SELECT \r\n DISTINCT e.salary\r\n FROM \r\n employee e\r\n WHERE \r\n (SELECT count(DISTINCT salary) FROM employee WHERE salary>e.salary) = N-1\r\n );\r\nEND\r\n```\r\n\r\n**思路3：笛卡尔积**\r\n\r\n 当然，可以很容易将思路2中的代码改为笛卡尔积连接形式，其执行过程实际上一致的，甚至MySQL执行时可能会优化成相同的查询语句。\r\n\r\n**代码3**\r\n\r\n```mysql\r\nCREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT\r\nBEGIN\r\n RETURN (\r\n # Write your MySQL query statement below.\r\n SELECT \r\n DISTINCT e1.salary\r\n FROM \r\n employee e1, employee e2 \r\n WHERE \r\n e1.salary <= e2.salary\r\n GROUP BY \r\n e1.salary\r\n HAVING \r\n count(DISTINCT e2.salary) = N\r\n );\r\nEND\r\n```\r\n\r\n#### 7、分数排名\r\n\r\n 编写一个 SQL 查询来实现分数排名。\r\n\r\n 如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。\r\n\r\n```\r\n+----+-------+\r\n| Id | Score |\r\n+----+-------+\r\n| 1 | 3.50 |\r\n| 2 | 3.65 |\r\n| 3 | 4.00 |\r\n| 4 | 3.85 |\r\n| 5 | 4.00 |\r\n| 6 | 3.65 |\r\n+----+-------+\r\n```\r\n\r\n 例如，根据上述给定的 `Scores` 表，你的查询应该返回（按分数从高到低排列）：\r\n\r\n```\r\n+-------+------+\r\n| Score | Rank |\r\n+-------+------+\r\n| 4.00 | 1 |\r\n| 4.00 | 1 |\r\n| 3.85 | 2 |\r\n| 3.65 | 3 |\r\n| 3.65 | 3 |\r\n| 3.50 | 4 |\r\n+-------+------+\r\n```\r\n\r\n **重要提示：**对于 MySQL 解决方案，如果要转义用作列名的保留字，可以在关键字之前和之后使用撇号。例如 **`Rank`**\r\n\r\n**方法一：**\r\n\r\n 最后的结果包含两个部分，第一部分是降序排列的分数，第二部分是每个分数对应的排名。\r\n\r\n**第一部分不难写：**\r\n\r\n```mysql\r\nselect a.Score as Score\r\nfrom Scores a\r\norder by a.Score DESC\r\n```\r\n\r\n 比较难的是第二部分。假设现在给你一个分数X，如何算出它的排名Rank呢？\r\n 我们可以先提取出大于等于X的所有分数集合H，将H去重后的元素个数就是X的排名。比如你考了99分，但最高的就只有99分，那么去重之后集合H里就只有99一个元素，个数为1，因此你的Rank为1。\r\n\r\n**先提取集合H：**\r\n\r\n```mysql\r\nselect b.Score from Scores b where b.Score >= X;\r\n```\r\n\r\n我们要的是集合H去重之后的元素个数，因此升级为：\r\n\r\n```mysql\r\nselect count(distinct b.Score) from Scores b where b.Score >= X as Rank;\r\n```\r\n\r\n而从结果的角度来看，第二部分的Rank是对应第一部分的分数来的，所以这里的X就是上面的a.Score，把两部分结合在一起为：\r\n\r\n```mysql\r\nselect a.Score as Score,\r\n(select count(distinct b.Score) from Scores b where b.Score >= a.Score) as Rank\r\nfrom Scores a\r\norder by a.Score DESC\r\n```\r\n\r\n#### 8、连续出现的数字\r\n\r\n 编写一个 SQL 查询，查找所有至少连续出现三次的数字。\r\n\r\n```\r\n+----+-----+\r\n| Id | Num |\r\n+----+-----+\r\n| 1 | 1 |\r\n| 2 | 1 |\r\n| 3 | 1 |\r\n| 4 | 2 |\r\n| 5 | 1 |\r\n| 6 | 2 |\r\n| 7 | 2 |\r\n+----+-----+\r\n```\r\n\r\n 例如，给定上面的 `Logs` 表， `1` 是唯一连续出现至少三次的数字。\r\n\r\n```\r\n+-----------------+\r\n| ConsecutiveNums |\r\n+-----------------+\r\n| 1 |\r\n+-----------------+\r\n```\r\n\r\n**解法一：**\r\n\r\n**思路：**\r\n1、由于要获取至少连续三次出现的数字，看到这个题肯定是会变的，如果是至少连续出现四次呢(100次呢)，咱们连接四个表(连接一千个?)？这种方法肯定是不可取的。\r\n\r\n2、找规律，找出这连续起来的数字有什么规律呢，我们会发现连续的数字是相同的数字，但是id有可能不是连续的，我们就需要通过对结果集进行再次编号，让其变成连续的。\r\n\r\n**原始数据:**\r\n\r\n```\r\nid Num\r\n1 1\r\n2 1\r\n3 1\r\n4 2\r\n5 2\r\n8 3\r\n9 3\r\n10 3\r\n11 3\r\n12 2\r\n```\r\n\r\n3、首先我们获取到对每条数据编号从1开始使用row_number()函数使用id来排序既`row_number() over(order by id)`\r\n\r\n```mysql\r\nselect id,num,row_number() over (order by id) AS orde\r\nfrom logs\r\n```\r\n\r\n结果为:\r\n\r\n```\r\nid Num orde\r\n1 1 1\r\n2 1 2\r\n3 1 3\r\n4 2 4\r\n5 2 5\r\n8 3 6\r\n9 3 7\r\n10 3 8\r\n11 3 9\r\n12 2 10\r\n```\r\n\r\n4、然后我们通过另一种方式排序将，这些num值一样的进行排序，然后对其编号同样使用`row_bumber()`使用`num`来分组使用id排序 `over(partition by num order by id)`\r\n\r\n```mysql\r\nselect id, num, row_number() over (partition by num order by id) AS orde\r\nfrom logs\r\n```\r\n\r\n结果为：\r\n\r\n```\r\nid Num orde\r\n1 1 1\r\n2 1 2\r\n3 1 3\r\n4 2 1\r\n5 2 2\r\n8 3 3\r\n9 3 1\r\n10 3 2\r\n11 3 3\r\n12 2 4\r\n```\r\n\r\n5、通过3、4步骤我们能得到什么呢，两个相减之后我们可以得到，只要是相等的，则相减的值是一样的。而且如果不连续的话相减值也不一样。\r\n\r\n```mysql\r\nselect id,num,row_number() over(order by id)-row_number() over(partition by num order by id) AS orde\r\nfrom logs\r\n```\r\n\r\n结果为：\r\n\r\n```\r\nid Num orde\r\n1 1 0\r\n2 1 0\r\n3 1 0\r\n4 2 3\r\n5 2 3\r\n12 2 7\r\n8 3 5\r\n9 3 5\r\n10 3 5\r\n11 3 5\r\n```\r\n\r\n 这样是不是一目了然呢，最后在通过`num`和`orde`两个共同分组找到一样的一共有几个，我们就可以找到连续的了。\r\n\r\n```mysql\r\nselect distinct Num AS consecutiveNums\r\nfrom(\r\n select num,count(*) num_count\r\n from(\r\n select id,num row_number() over(order by id)-row_number over (partition by num order by id) AS orde\r\n from logs)AS W\r\n group by num,orde)AS S\r\nwhere num_count >=3\r\n```\r\n\r\n结果为：\r\n\r\n```\r\nConsecutiveNums\r\n1\r\n3\r\n```\r\n\r\n#### 9、部门工资最高的员工\r\n\r\n`Employee` 表包含所有员工信息，每个员工有其对应的 Id, salary 和 department Id。\r\n\r\n```\r\n+----+-------+--------+--------------+\r\n| Id | Name | Salary | DepartmentId |\r\n+----+-------+--------+--------------+\r\n| 1 | Joe | 70000 | 1 |\r\n| 2 | Henry | 80000 | 2 |\r\n| 3 | Sam | 60000 | 2 |\r\n| 4 | Max | 90000 | 1 |\r\n+----+-------+--------+--------------+\r\n```\r\n\r\n`Department` 表包含公司所有部门的信息。\r\n\r\n```\r\n+----+----------+\r\n| Id | Name |\r\n+----+----------+\r\n| 1 | IT |\r\n| 2 | Sales |\r\n+----+----------+\r\n```\r\n\r\n 编写一个 SQL 查询，找出每个部门工资最高的员工。例如，根据上述给定的表格，Max 在 IT 部门有最高工资，Henry 在 Sales 部门有最高工资。\r\n\r\n```\r\n+------------+----------+--------+\r\n| Department | Employee | Salary |\r\n+------------+----------+--------+\r\n| IT | Max | 90000 |\r\n| Sales | Henry | 80000 |\r\n+------------+----------+--------+\r\n```\r\n\r\n**方法：使用 JOIN 和 IN 语句**\r\n\r\n**算法**\r\n\r\n因为 **Employee** 表包含` Salary `和 `DepartmentId` 字段，我们可以以此在部门内查询最高工资。\r\n\r\n```\r\nSELECT\r\n DepartmentId, MAX(Salary)\r\nFROM\r\n Employee\r\nGROUP BY DepartmentId;\r\n```\r\n\r\n> 注意：有可能有多个员工同时拥有最高工资，所以最好在这个查询中不包含雇员名字的信息。\r\n\r\n```\r\n| DepartmentId | MAX(Salary) |\r\n|--------------|-------------|\r\n| 1 | 90000 |\r\n| 2 | 80000 |\r\n```\r\n\r\n然后，我们可以把表 **Employee** 和 **Department** 连接，再在这张临时表里用 `IN` 语句查询部门名字和工资的关系。\r\n\r\n```mysql\r\nSELECT\r\n Department.name AS \'Department\',\r\n Employee.name AS \'Employee\',\r\n Salary\r\nFROM\r\n Employee\r\n JOIN\r\n Department ON Employee.DepartmentId = Department.Id\r\nWHERE\r\n (Employee.DepartmentId , Salary) IN\r\n ( SELECT\r\n DepartmentId, MAX(Salary)\r\n FROM\r\n Employee\r\n GROUP BY DepartmentId\r\n );\r\n```\r\n\r\n```\r\n| Department | Employee | Salary |\r\n|------------|----------|--------|\r\n| Sales | Henry | 80000 |\r\n| IT | Max | 90000 |\r\n```\r\n\r\n### 困难\r\n\r\n#### 10、部门工资前三高的所有员工\r\n\r\n`Employee` 表包含所有员工信息，每个员工有其对应的工号 `Id`，姓名 `Name`，工资 `Salary` 和部门编号 `DepartmentId` 。\r\n\r\n```\r\n+----+-------+--------+--------------+\r\n| Id | Name | Salary | DepartmentId |\r\n+----+-------+--------+--------------+\r\n| 1 | Joe | 85000 | 1 |\r\n| 2 | Henry | 80000 | 2 |\r\n| 3 | Sam | 60000 | 2 |\r\n| 4 | Max | 90000 | 1 |\r\n| 5 | Janet | 69000 | 1 |\r\n| 6 | Randy | 85000 | 1 |\r\n| 7 | Will | 70000 | 1 |\r\n+----+-------+--------+--------------+\r\n```\r\n\r\n`Department` 表包含公司所有部门的信息。\r\n\r\n```\r\n+----+----------+\r\n| Id | Name |\r\n+----+----------+\r\n| 1 | IT |\r\n| 2 | Sales |\r\n+----+----------+\r\n```\r\n\r\n编写一个 SQL 查询，找出每个部门获得前三高工资的所有员工。例如，根据上述给定的表，查询结果应返回：\r\n\r\n```\r\n+------------+----------+--------+\r\n| Department | Employee | Salary |\r\n+------------+----------+--------+\r\n| IT | Max | 90000 |\r\n| IT | Randy | 85000 |\r\n| IT | Joe | 85000 |\r\n| IT | Will | 70000 |\r\n| Sales | Henry | 80000 |\r\n| Sales | Sam | 60000 |\r\n+------------+----------+--------+\r\n```\r\n\r\n**解释：**\r\n\r\nIT 部门中，Max 获得了最高的工资，Randy 和 Joe 都拿到了第二高的工资，Will 的工资排第三。销售部门（Sales）只有两名员工，Henry 的工资最高，Sam 的工资排第二。\r\n\r\n**解题思路：**\r\n\r\n回忆一下 count 函数\r\n\r\n```mysql\r\ncount(字段名) # 返回表中该字段总共有多少条记录\r\n```\r\n\r\n回忆一下 DISTINCT 关键字\r\n\r\n```mysql\r\nDISTINCT 字段名 # 过滤字段中的重复记录\r\n```\r\n\r\n我们先找出公司里前 3 高的薪水，意思是不超过三个值比这些值大\r\n\r\n```mysql\r\nSELECT e1.Salary \r\nFROM Employee AS e1\r\nWHERE 3 > \r\n (SELECT count(DISTINCT e2.Salary) \r\n FROM Employee AS e2 \r\n WHERE e1.Salary < e2.Salary AND e1.DepartmentId = e2.DepartmentId) ;\r\n```\r\n\r\n举个栗子：\r\n当 `e1 = e2 = [4,5,6,7,8]`\r\n\r\n`e1.Salary = 4`，`e2.Salary` 可以取值 `[5,6,7,8]`，`count(DISTINCT e2.Salary) = 4`\r\n\r\n`e1.Salary = 5`，`e2.Salary` 可以取值 `[6,7,8]`，`count(DISTINCT e2.Salary) = 3`\r\n\r\n`e1.Salary = 6`，`e2.Salary` 可以取值 `[7,8]`，`count(DISTINCT e2.Salary) = 2`\r\n\r\n`e1.Salary = 7`，`e2.Salary` 可以取值 `[8]`，`count(DISTINCT e2.Salary) = 1`\r\n\r\n`e1.Salary = 8`，`e2.Salary` 可以取值 `[]`，`count(DISTINCT e2.Salary) = 0`\r\n\r\n最后 `3 > count(DISTINCT e2.Salary)`，所以 `e1.Salary` 可取值为 `[6,7,8]`，即集合前 3 高的薪水\r\n\r\n再把表 Department 和表 Employee 连接，获得各个部门工资前三高的员工。\r\n\r\n```mysql\r\nSELECT\r\n Department.NAME AS Department,\r\n e1.NAME AS Employee,\r\n e1.Salary AS Salary \r\nFROM\r\n Employee AS e1,Department \r\nWHERE\r\n e1.DepartmentId = Department.Id \r\n AND 3 > (SELECT count( DISTINCT e2.Salary ) \r\n FROM Employee AS e2 \r\n WHERE e1.Salary < e2.Salary AND e1.DepartmentId = e2.DepartmentId ) \r\nORDER BY Department.NAME,Salary DESC;\r\n```\r\n\r\n**方法二：使用 `JOIN` 和子查询**\r\n\r\n**算法**\r\n\r\n公司里前 3 高的薪水意味着有不超过 3 个工资比这些值大\r\n\r\n```mysql\r\nselect e1.Name as \'Employee\', e1.Salary\r\nfrom Employee e1\r\nwhere 3 >\r\n(\r\n select count(distinct e2.Salary)\r\n from Employee e2\r\n where e2.Salary > e1.Salary\r\n);\r\n```\r\n\r\n在这个代码里，我们统计了有多少人的工资比 `e1.Salary` 高，所以样例的输出应该如下所示。\r\n\r\n```mysql\r\n| Employee | Salary |\r\n|----------|--------|\r\n| Henry | 80000 |\r\n| Max | 90000 |\r\n| Randy | 85000 |\r\n```\r\n\r\n然后，我们需要把表 **Employee** 和表 **Department** 连接来获得部门信息。\r\n\r\n```mysql\r\nSELECT\r\n d.Name AS \'Department\', e1.Name AS \'Employee\', e1.Salary\r\nFROM\r\n Employee e1\r\n JOIN\r\n Department d ON e1.DepartmentId = d.Id\r\nWHERE\r\n 3 > (SELECT\r\n COUNT(DISTINCT e2.Salary)\r\n FROM\r\n Employee e2\r\n WHERE\r\n e2.Salary > e1.Salary\r\n AND e1.DepartmentId = e2.DepartmentId\r\n );\r\n```\r\n\r\n```\r\n| Department | Employee | Salary |\r\n|------------|----------|--------|\r\n| IT | Joe | 70000 |\r\n| Sales | Henry | 80000 |\r\n| Sales | Sam | 60000 |\r\n| IT | Max | 90000 |\r\n| IT | Randy | 85000 |\r\n```\r\n\r\n', '2020-10-06 09:10:31.416000', 'https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1601985499155&di=bd307d484445bb8cb2d7d42b0010feed&imgtype=0&src=http%3A%2F%2Fb.zol-img.com.cn%2Fdesk%2Fbizhi%2Fimage%2F3%2F960x600%2F1367976837494.jpg', '转载', b'1', b'1', b'1', 'LeetCode数据库6-10(中等+困难)', '2020-10-06 09:10:31.416000', 0, 90, 1, 'LeetCode数据库；第N高的薪水；编写一个 SQL 查询，获取 `Employee` 表中第 n 高的薪水（Salary）。分数排名；编写一个 SQL 查询来实现分数排名。连续出现的数字；编写一个 SQL 查询，查找所有至少连续出现三次的数字。部门工资最高的员工；找出每个部门工资最高的员工。部门工资前三高的所有员工；找出每个部门获得前三高工资的所有员工。');
-- ----------------------------
-- Table structure for t_blog_tags
-- ----------------------------
DROP TABLE IF EXISTS `t_blog_tags`;
CREATE TABLE `t_blog_tags` (
`blogs_id` bigint(0) NOT NULL,
`tags_id` bigint(0) NOT NULL,
INDEX `FK5feau0gb4lq47fdb03uboswm8`(`tags_id`) USING BTREE,
INDEX `FKh4pacwjwofrugxa9hpwaxg6mr`(`blogs_id`) USING BTREE,
CONSTRAINT `FK5feau0gb4lq47fdb03uboswm8` FOREIGN KEY (`tags_id`) REFERENCES `t_tag` (`id`) ON DELETE RESTRICT ON UPDATE RESTRICT,
CONSTRAINT `FKh4pacwjwofrugxa9hpwaxg6mr` FOREIGN KEY (`blogs_id`) REFERENCES `t_blog` (`id`) ON DELETE RESTRICT ON UPDATE RESTRICT
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of t_blog_tags
-- ----------------------------
INSERT INTO `t_blog_tags` VALUES (92, 63);
INSERT INTO `t_blog_tags` VALUES (92, 67);
INSERT INTO `t_blog_tags` VALUES (92, 69);
INSERT INTO `t_blog_tags` VALUES (92, 72);
INSERT INTO `t_blog_tags` VALUES (93, 63);
INSERT INTO `t_blog_tags` VALUES (93, 67);
INSERT INTO `t_blog_tags` VALUES (93, 69);
INSERT INTO `t_blog_tags` VALUES (93, 72);
INSERT INTO `t_blog_tags` VALUES (94, 63);
INSERT INTO `t_blog_tags` VALUES (94, 67);
INSERT INTO `t_blog_tags` VALUES (94, 69);
INSERT INTO `t_blog_tags` VALUES (94, 72);
INSERT INTO `t_blog_tags` VALUES (95, 63);
INSERT INTO `t_blog_tags` VALUES (95, 67);
INSERT INTO `t_blog_tags` VALUES (95, 69);
INSERT INTO `t_blog_tags` VALUES (95, 72);
INSERT INTO `t_blog_tags` VALUES (100, 72);
INSERT INTO `t_blog_tags` VALUES (100, 74);
INSERT INTO `t_blog_tags` VALUES (100, 75);
INSERT INTO `t_blog_tags` VALUES (99, 62);
INSERT INTO `t_blog_tags` VALUES (22, 62);
-- ----------------------------
-- Table structure for t_comment
-- ----------------------------
DROP TABLE IF EXISTS `t_comment`;
CREATE TABLE `t_comment` (
`id` bigint(0) NOT NULL,
`avatar` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`content` longtext CHARACTER SET utf8 COLLATE utf8_bin NULL,
`create_time` datetime(6) NULL DEFAULT NULL,
`email` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`nickname` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`blog_id` bigint(0) NULL DEFAULT NULL,
`parent_comment_id` bigint(0) NULL DEFAULT NULL,
`new_column` int(0) NULL DEFAULT NULL,
`admin_comment` bit(1) NOT NULL,
PRIMARY KEY (`id`) USING BTREE,
INDEX `FKke3uogd04j4jx316m1p51e05u`(`blog_id`) USING BTREE,
INDEX `FK4jj284r3pb7japogvo6h72q95`(`parent_comment_id`) USING BTREE,
CONSTRAINT `FK4jj284r3pb7japogvo6h72q95` FOREIGN KEY (`parent_comment_id`) REFERENCES `t_comment` (`id`) ON DELETE RESTRICT ON UPDATE RESTRICT,
CONSTRAINT `FKke3uogd04j4jx316m1p51e05u` FOREIGN KEY (`blog_id`) REFERENCES `t_blog` (`id`) ON DELETE RESTRICT ON UPDATE RESTRICT
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of t_comment
-- ----------------------------
INSERT INTO `t_comment` VALUES (37, '/images/avatar.jpg', '测试评论', '2020-10-06 02:59:06.738000', '1059339010@qq.com', 'CodeSleep', 22, NULL, NULL, b'0');
INSERT INTO `t_comment` VALUES (38, '/images/avatar.jpg', '测试第二次', '2020-10-06 02:59:16.328000', '1059339010@qq.com', 'CodeSleep', 22, 37, NULL, b'0');
INSERT INTO `t_comment` VALUES (39, '/images/avatar.jpg', '测试第三次', '2020-10-06 03:00:46.786000', '123456@qq.com', 'Xayah', 22, 38, NULL, b'0');
INSERT INTO `t_comment` VALUES (40, '/images/avatar.jpg', '测试第四次', '2020-10-06 03:01:35.235000', '1234567@qq.com', 'Xayah12138', 22, 37, NULL, b'0');
INSERT INTO `t_comment` VALUES (41, '/images/avatar.jpg', '测试第五次', '2020-10-06 03:01:49.128000', '12345678@qq.com', 'Xayah12138', 22, NULL, NULL, b'0');
INSERT INTO `t_comment` VALUES (42, '/images/avatar.jpg', '测试第六次', '2020-10-06 03:06:12.996000', '123213@qq.com', '芜湖起飞', 22, NULL, NULL, b'0');
INSERT INTO `t_comment` VALUES (43, '/images/avatar.jpg', '测试第七次', '2020-10-06 03:06:30.568000', '123213@qq.com', '起飞咯', 22, NULL, NULL, b'0');
INSERT INTO `t_comment` VALUES (44, 'https://picsum.photos/id/1027/100/100', '第八次测试', '2020-10-06 03:11:45.849000', '1059339010@qq.com', '管理员', 22, 43, NULL, b'1');
-- ----------------------------
-- Table structure for t_tag
-- ----------------------------
DROP TABLE IF EXISTS `t_tag`;
CREATE TABLE `t_tag` (
`id` bigint(0) NOT NULL,
`name` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of t_tag
-- ----------------------------
INSERT INTO `t_tag` VALUES (62, '测试');
INSERT INTO `t_tag` VALUES (63, 'JAVA');
INSERT INTO `t_tag` VALUES (64, 'JavaScript');
INSERT INTO `t_tag` VALUES (65, 'JavaWeb');
INSERT INTO `t_tag` VALUES (66, 'Web');
INSERT INTO `t_tag` VALUES (67, 'C');
INSERT INTO `t_tag` VALUES (68, 'CSS');
INSERT INTO `t_tag` VALUES (69, 'C++');
INSERT INTO `t_tag` VALUES (70, 'SpringBoot');
INSERT INTO `t_tag` VALUES (71, 'SpringMVC');
INSERT INTO `t_tag` VALUES (72, 'LeetCode');
INSERT INTO `t_tag` VALUES (73, 'Linux');
INSERT INTO `t_tag` VALUES (74, '数据库');
INSERT INTO `t_tag` VALUES (75, 'MYSQL');
INSERT INTO `t_tag` VALUES (76, 'IDEA');
INSERT INTO `t_tag` VALUES (77, 'eclipse');
INSERT INTO `t_tag` VALUES (78, '虚拟机');
INSERT INTO `t_tag` VALUES (101, 'AJAX');
-- ----------------------------
-- Table structure for t_type
-- ----------------------------
DROP TABLE IF EXISTS `t_type`;
CREATE TABLE `t_type` (
`id` bigint(0) NOT NULL,
`name` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of t_type
-- ----------------------------
INSERT INTO `t_type` VALUES (2, '测试');
INSERT INTO `t_type` VALUES (79, 'Linux');
INSERT INTO `t_type` VALUES (80, '虚拟机');
INSERT INTO `t_type` VALUES (81, '前端');
INSERT INTO `t_type` VALUES (83, '自学笔记');
INSERT INTO `t_type` VALUES (84, 'BUG');
INSERT INTO `t_type` VALUES (85, '面试题');
INSERT INTO `t_type` VALUES (86, 'JAVA框架');
INSERT INTO `t_type` VALUES (87, 'JAVA');
INSERT INTO `t_type` VALUES (88, '数据结构与算法');
INSERT INTO `t_type` VALUES (89, '教程');
INSERT INTO `t_type` VALUES (90, '数据库');
INSERT INTO `t_type` VALUES (91, '其他');
-- ----------------------------
-- Table structure for t_user
-- ----------------------------
DROP TABLE IF EXISTS `t_user`;
CREATE TABLE `t_user` (
`id` bigint(0) NOT NULL,
`avatar` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`create_time` datetime(6) NULL DEFAULT NULL,
`email` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`nickname` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`password` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
`type` int(0) NULL DEFAULT NULL,
`update_time` datetime(6) NULL DEFAULT NULL,
`username` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of t_user
-- ----------------------------
INSERT INTO `t_user` VALUES (1, 'https://picsum.photos/id/1027/100/100', '2020-10-03 21:44:28.000000', '1059339010@qq.com', '管理员', '123456', 1, '2020-10-03 21:45:44.000000', 'admin');
INSERT INTO `t_user` VALUES (2, 'https://picsum.photos/id/1027/100/100', '2024-09-19 17:02:00.000000', 'niuhaideng@163.com', '牛海登', '123456', 1, '2024-09-19 17:02:25.000000', 'niuhaideng');
SET FOREIGN_KEY_CHECKS = 1;
Loading...
举报
请认真填写举报原因，尽可能描述详细。
请选择举报类型
误判申诉
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化