leetcode刷题记录

旨在了解一点基本的算法基础，期待稍微提高一点逻辑思维。

直接把刷题记录搬运过来了，且放在这里把，原项目地址；大概的时间应该是2020年下半年左右吧。

一 class类命名规则

java 复制代码

/**
 *
 *  class命名规则如下：'J' + number + '_' + level +  '_' + describe
 *  1. 以字母J开头
 *  2. numbern 表示题目的序号，四位数
 *  3. leverl表示题目的难度级别：E：easy；M:middle; H:hard
 *  4. describe 题目的大概描述，详见class注释
 */

二已做的题目目录

0001.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

0002.两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
复制代码
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

0003.无重复的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

0004. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

0005.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

0006.Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

这不是明明是N型转换吗....

0007.整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

0008.字符串转换整数（atoi）

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

0009.回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

进阶:

你能不将整数转为字符串来解决这个问题吗？

0010.正则表达式匹配▲ TODO 动态规划

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

0011.盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

0012.整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

https://leetcode-cn.com/problems/integer-to-roman/

0013.罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

https://leetcode-cn.com/problems/roman-to-integer/

0014.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

0015.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解决方案：排序 + 双指针

0016.最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

解决方案：排序 + 双指针

和15题类似，只是要在遍历的时候记录下最接近的数

0017.电话号码的字母组合 ▲ 递归

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

递归查

复制代码

 各个位置的字符直接罗列即可

0018.四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

参见三数之和依然是双指针，变成两数之和

指针 i, j=i+1; 确认下来之后，变成两数之和left = j+1；right = len-1；

0019.删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

**进阶：**你能尝试使用一趟扫描实现吗？

这里我使用的是用Map保存一遍节点

0020.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

用栈直接解决

0021.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

暴力遍历
递归两两合并

0022.括号生成 ▲回溯dfs（减枝）

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

0023.合并K个升序链表 ▲ 分治算法TODO

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

听说适合用分治算法，但是我不会TODO
暴力遍历，两两合并

0024.两两交换链表中的节点递归

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

暴力遍历
递归调用：终止条件-没有节点或就一个节点

0025.K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

区间判断略，我先是通过栈的方式反转的

直接反转区间链表的方式：图例如下

复制代码

/**
 * 反转区间链表[start, end) 前包含 后不包含:反转过程如下：
 * 1-2-3-4        5
 * 2-3-4        1-5
 * 3-4        2-1-5
 * 4        3-2-1-5
 * 		  4-3-2-1-5
 */

0026.删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

没什么方法，拿起键盘就是干，用新的下标表示不重复的数组的下标，然后返回j+1

0027.移除元素项

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

同26题，却更简单

0028.实现 strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

既然是简单，那么我 haystack.indexOf(needle) 多简单
匹配到开头的时候，双指针往下匹配
循环haystack 然后substring(i,i+needle.length()) .equals (needle)

0029.两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

智商有限写起来真费劲啊最终还是忽略了边界，直接用long走起：

解题思路：

js 复制代码

网上的代码看的不大懂 只好自己瞎写了
58/3=19...1
58/48=1...10   3左移了四次得到48   1<<4 = 16   找到48 这个数，因为下一个96 已经大于58 了
58 - 48 = 10;
10/3=3...1    3 位移1次得到6       1<<1 = 2
10 - 6 = 4
4> 3 ,但是不需要位移              1<< 0 = 1
结果 = 16 + 2 + 1 = 19

总体就是小学的试试学的除法算法 但是改为二进制的：
      _19___
    3) 58
      _30_
       28
      _27_
        1

0030.串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

不知道这个题目为什么定位是困难级别，只是单纯的截取总words长度的子串，然后把子串分割为小的子串和words的元素匹配即可，用到了HashMap；

应该有更好的算法

0031.下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。

题解：

题目读起来有点别扭；

从后往前找到一个降序，然后这个位置后面最小的数和这个位置交换后，重排序其后的

0032.最长有效括号动态规划 ▲ 栈

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
(() → 2
)()()) → 4

题解：

我首先通过栈的方式记录每个位置是否匹配，然后找出结果中的连续最大匹配——这是我第一个不看题解写出来的hard
后来网上看了看题解，又用动态规划写出了答案，效率果然更高

又一次写了写动态规划，希望熟能生巧

0033. 搜索旋转排序数组二分法查找

给你一个整数数组 nums ，和一个整数 target 。
该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

要求算法时间复杂度必须是 O(logn)

题解：

复制代码

 原本是有序的 升序    要求算法时间复杂度必须是 O(logn)
1. 旋转后必定存在0-mid-end 有一部分有序
2. 有序的直接判断 start 和end
3. 不在有序中 在无序中继续二分重复上述步骤

0034. 34. 在排序数组中查找元素的第一个和最后一个位置二分法查找

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

题解：

又是一个二分法查找，

原本我的是想法是先通过二分法找到开始位置，再从开始位置为起点二分法查找结束位置。结果写起来就细节判断不好，

最终折中：先通过二分法查找到target的位置，再向两边滑动找开始和结束的位置

0035. 搜索插入位置二分法查找

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

题解：

又是一个二分法查找，

一看就会一写就废。

二分发找到mid 则返回；

不然的话返回 left值

0036. 有效的数独把数存在对应的位上面

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 '.' 表示。

题解：

定义三个size=9的数组，其中每个元素，分别存储某行、某列、某个小九宫格的全部元素
按位存储，nums[xIndex] = nums[xIndex] | 1 << n;
判断是否包含：(nums[xIndex] >> n & 1) == 1;
某个九宫格的下标计算：int boxIndex = i / 3 * 3 + j / 3;
详见代码

0037. 解数独困难▲ 回溯

编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

提示：
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

题解：

这一题我居然慢慢写的情况下，写成功了

这一题主要用到回溯的解题思路，就是不断的是错，行不通则减枝回退，同时利用上一题（36题）的校验某个位置元素是否合法的方法；

定义三个size=9的数组，其中每个元素，分别存储某行、某列、某个小九宫格的全部元素
先把非’.‘元素初始化到对应的三个数组中
然后开始通递归回溯的方式填充'.'，每次从1-9逐一尝试，如果通过校验，就同步更新上述三个数组的对应元素的对应位，然后继续尝试填充下一个’.‘
如果填充的数字没有通过校验，则回溯当前位，同时回溯三个数组中的对应元素的对应位
终止条件为，最后一位[8-8]填充完毕
详细见代码

0038. 38. 外观数列

给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
复制代码
前五项如下：
1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

题解：

这一题很简单，没啥可说的，相见代码即可

定义好初始条件 1 的时候就是“1”

0039. 组合总和中等回溯

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

题解：

这又是一道典型的回溯，我来试试看

每个元素可重复使用
先把数组排序，这样只要探测到当前元素比target小，就可以直接终止往下搜索
为了防止重复结果集，在某个元素的全部组合探测完毕后，下一次探测就不再使用它
另外结果集有set去重
见代码

0040. 组合总和 II 中等回溯

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

题解：

这依然是是一道典型的回溯，和上一题基本差不多，甚至更简单，解题思路参见上一题

0041. 缺失的第一个正数困难

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

题解：

难在难在额外的要求，时间和空间复杂度的要求；不然老夫一梭子下去就是暴力求解：隐含的条件是：缺失的数字必定是在1到长度+1中间

我看了网上的题解思路，代码虽然不完全一致，但是也实现了效果
确实的数字必定在1 —— len + 1
确定1 在不在数组内，不在则直接返回1
把数组内超标的数字全部换成1
把每个数字对应的小标的数字置为 - X，当下一次遍历当这个数字为负数时候表示这个下标对应的数字是存在的
从前往后变量数字（此时当前元素若为负数则表示当前下标对应的元素是存在的，比如nums[0] == -2:表示正数1是存在的），此时第一个不为负数的元素对应的下标即为第一个缺失的最小正整数

0042. 接雨水困难中间过程用到动态规划

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

题解：

看了写别人的思路，然后自己居然写出来了还击败了99%；

果然孰能生巧

java 复制代码

	/**
     * 1. 总体思路:计算每一个列能盛放的雨水
     * 2. 某列左边最高，右边最高，然后取两者中间低的，减去当前 就是当前列能盛放的雨水
     * 3. 如果每次动态的去寻找左右最高 就变成了 O(n^2) 消耗较大
     * 4. 可以转化先分别求每一列[i]的左边最大，右边最大， 这会不会是个动态规划呢？
     * 5. 以求左边做大状态记录为例：
     *   动态规划三步走：
     *   a. 定义dpMaxLeft[i],记录第i列左边做大的值
     *   b. 初始状态 [0] = 0; 可省略
     *   c. 状态转移关系: [i] = max(dpMaxLeft[i-1],[i-1])
     * 6. 右边的最大值求发类似
     */

0043. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解：

直接把竖式相乘用代码表达出来，然后注意细节即可；

详见代码

0044.通配符匹配困难动态规划

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

题解

2020年11月3日的时候刚接触动态规划这一题我没写出来，
现在是2020年12月8日，已经刷题一段时间，并且已经做过一些简单的动态规划，再次尝试写这一道题试试（主要还是因为之前看了别人题解有记忆）：
动态规划三步走：

复制代码

      1. 状态记录数组 dp[i+1] [j+1] 字符串[0,i] 和字符模式[0,j]的匹配情况
      2. 初始状态： [0] [0] 空和空是匹配的  第一行 和第一列 的匹配需要额外的初始
      3. 状态转移：
            - a.字符串和字符串不匹配 则false,匹配则是true 则看上一个位置[i-1] [j-1]
            - b.字符串和? 是匹配的  则看上一个位置是否匹配[i-1] [j-1]
            -  c.字符串和*是匹配的，且可长可短，则*
              - *c1.当前* 没有匹配任何一个字符串()：[ i] [j-1]
              - c2 当前*匹配当前字符，类似？ 则：[i-1] [ j-1]*
              - c3. 当前*匹配当前字符且继续往前匹配，则[i-1] [j]

0045. 跳跃游戏 II 困难贪心

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

题解

隐含条件：总是可以到达最后一个位置：省去了额外的判断
在位置1时候，可以达到的最远距离是max = 1+nums[1]
继续下一步在区间[2， max]中，找出能跳到的最大距离max2,当区间内的每一个位置都尝试完毕，则更新最远距离为max2，并且步数+1
重复上述步骤，在区间[max+1， max2]中找出能挑到的最大距离，直到最远距离大于等于数组

0046. 全排列回溯

给定一个没有重复数字的序列，返回其所有可能的全排列。

题解

就是一个回溯算法，罗列所有的选项即可

0047. 全排列 II 回溯

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

题解

和46题一样，如果有Set去重就一样
个人觉得还是应该做好减枝的判断才是正解
同一层的选择不能出现重复 nums[i-1] == nums[i] && used[i-1]

0048. 旋转图像

90度原地旋转n*n 矩阵

题解

可以一圈一圈向内旋转，圈数：n/2
每圈需要走多少步：step = n-1；以后每圈-2
每一圈做好四个点的依次转换，对我这样没有空间想象力的人来说简直是灾难:

i：当前圈数

j:每一圈的初始位置：如第一圈的第一个位置是(0,0)

下面是四个点：
java 复制代码
```
int p1 = matrix[i][i+j];
int p2 = matrix[i+j][step+i];
int p3 = matrix[step+i][step-j+i];
int p4 = matrix[step-j+i][i];
```

0049. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

题解

把每个字符串按照字符顺序重新排序，相等的就放在一组即可

0050. 实现N次幂分治

实现 pow(x, n) ，即计算 x 的 n 次幂函数。
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

题解

暴力循环当然是不可以的
使用分治算法，每次干掉一半 : xx = x乘以x 每次xx乘以xx
偷懒用long替换int，不考虑边界问题，次幂n为负数时候，则1.0/res即可

0051. N 皇后困难回溯

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

题解

当前已经能比较用回溯法较为顺畅的解决这样的问题了(2020年12月14日)
主要是是否可放皇后的判断：4个Set解决
1. 行Set: row
2. 列Set:column
3. 右(往左)斜线Set：row - column
4. 左(往右)斜线Set: row + column
详见代码

0053. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

题解

虽然这是一道简单的题目，但是可以运用到贪心或者动态规划的思想
至于分治，不知道从何处分。。。。。

0054. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，
返回矩阵中的所有元素。

题解

注意边界条件：行的start小于等于end；列的start小于等于end
在上述条件(while)中，分别从左到右，上到下，右到左，下到上，四组操作，每组操作完毕之后，修改边界条件；另外在自减操作后，需要额外的判断边界条件，不然可能存在还没回到while就出现边界

0055. 跳跃游戏 ▲ 递归 | 动态规划 | 贪心

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

题解

这一题和45题差不多
初看到这一题，心中窃喜，是时候展示到当前(20201216)的刷题效果了,让我先来个递归，再来个动态规划，然后一个贪心算法收尾，美滋滋。
结果刚一个递归提交，就啪啪啪打脸，测试用例74/75，有一个超长数据的测试用例超时，我赶紧修改一下代码：缓存历史判断以及修改前进方式为先大后效，还是不能通过，应该是入栈太深了。
赶紧换个动态压压惊，效果还不错，超过82%,代码还非常简洁
动态规划
1. dp[] 数组记录当前位置能到达的最大下标
2. 初始条件：dp[0] = nums[0];
3. 状态转移：dp[i] = Math.max(dp[i - 1], nums[i] + i);
  
  （如果dp[i - 1] < i 直接返回false 因为连当前位置都达不到）
然后再换个贪心算法，其实原理和动态规划差不多

当前能达到的最远距离max

记录当前位置和最远位置中间区域能到达的最大距离temMax

当区域结束时候（i==max）更新最大距离max
详细见代码

0056. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

题解

就是暴力干，后来看题解不少都写的较复杂，可能效率更好吧，没有细看

先按照区间的首位升序排列
把二维数组中的第一位作为临时数据temp
遍历二维数组，如果current[0]的temp[1]大. 则不合并，把temp = current
如果current[0]<= temp[1],则判断temp[1] = Math.max(current[1], temp[1]);因为可能存在全包含的现象

0057.插入区间困难

给出一个无重叠的，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

题解

我也不知道为什么是困难级别的题目。感觉不至于啊。

一个简单的做法就是直接合并数组，然后使用56题的解题思路，合并区间。

但是总觉得这样的效率不高，题中已经给定了有序的无重叠的区间了。

于是我开始直接判断各种区间重叠的关系

判断原区间为空，则返回插入区间的二维数组
如果插入区间还没达到原来区间的最左端，则直接插入到开始位置
如果插入区间超过原来区间的最右端，则直接插入原区间的结尾位置
遍历原区间，判断各种重叠情况：

在左，在右，前节点在中间，后节点在中间，包含当前区间等等
虽然判断起来比较啰嗦，但是效率还可以：99.48%

0058. 最后一个单词的长度

给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

题解

这一题不愧是简单的级别，那是真的简单，100%

0059. 螺旋矩阵 II

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

题解

这一题思路和54题一样，分别上右下左的顺序一圈一圈的存如数字，效率也还可以100%

详见代码

0060. 排列序列困难回溯效率太低找规律

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

1 <= n <= 9
1 <= k <= n!

题解

这一题可以考虑使用回溯法找出到第k个数的时候退出，毕竟n最大为9；但是效率太低，我提交了一般只有15%；

考虑通过找规律的方式是比较靠谱的。

例如n=5,k=20;

nums = [1, 2, 3, 4, 5] 数字个数对应的阶乘关系： [1, 2, 6, 24, 120]

第一位(n=5)：(20-1)/4! = 0 ，第一位是nums[0] = 1, 此时nums中去掉1 [2,3,4,5]； k = k - 0 * 4! = 10;

第二位(n=4)：(10-1)/3!= 1 ，第二位是num[1] = 3,此时nums中去掉3 [2,4,5] k = k - 13! = 4

第三位(n=3)：(4-1)/2! = 1, 第三位是nums[1] = 4,此时nums中去掉4 [2,5] k = k-12! = 2

第四位(n=2): (2-1)/1! = 1, 第四位是nums[1] = 5 ,此时nums中去掉4 [2] k = k-1*1! = 1

第五位(n=1): (1-1)/0! = 0, 第五位是nums[0] = 2 ,此时nums中去掉2 []

详见代码

0061. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

题解

先得到链表的长度，计算出偏移量，计算出新尾部节点的位置
把原链表尾首相连
遍历原来的链表，到新尾部的时候，把它的后面的节点作为头节点返回，并把此尾节点的next置为空
详见代码

0062. 不同路径动态规划

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

题解

这是一个典型的简单的动态规划问题
状态记录[m,n] 记录到m,n的唯一路径个数
初始状态，第一行第一列步数只能是1
状态转移：[m,n] = [m-1,n] + [m,n-1]
详见代码

0063. 不同路径II 动态规划

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

题解

这是一个典型的简单的动态规划问题,和62题几乎一模一样
唯一的区别是需要判断当前网格是否有障碍物，有的话，把当前网格的路径数量置为0
详见代码

0064. 最小路径和动态规划

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

题解

这还是一个简单的动态规划
记录每个网格点的最小路径即可
详见代码

0065. 有效数字困难

验证给定的字符串是否可以解释为十进制数字。

例如:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

题解

我不知道这样的题目为什么是困难，可能就是判断条件多了一点而已

判空和trim
判断e
判断是小数或者整数：判断符号，判断点前后
判断是整数
详见代码

0066. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

题解：

方法1：可以末尾加1，然后判断进位，结尾继续判断进位
方法2：只有99,999之类的数字才能进位，所以加的过程中不进位直接返回，若没有提前return，则直接返回arr[len+1];arr[0] = 1,即返回100，或者1000等
详见代码

0067. 二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

题解：

一个for循环搞定，实在不知道怎么说

详见代码

0068. 文本左右对齐困难

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

题解：

我也不知道这样的题目为什么是困难，一开始的时候我理解错了空格分布

判断好换行的时机
判断好行内的空格分布
判断好最后一行的处理
详见代码

0069. x 的平方根二分

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

题解

我一直不大会二分法中的边界判断，看着简单，一写就错

判断mid的平方，不断二分，知道left <=x
mid的平方需要转为long，不然可能超过int边界
详见代码

0070. 爬楼梯动态规划

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

题解

最初级的动态规划

详见代码

0071. 简化路径

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

题解

利用栈的特性处理路径

以"/"分割路径，然后入栈
忽略空格和一个点
遇到两个点则弹出栈顶
其他情况入栈
以“/”反向连接栈中的元素即可(sb.insert(0, deque.pop()).insert(0, "/");)
详见代码

0406.根据身高重建队列

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对 (h, k) 表示，其中 h 是这个人的身高，k 是应该排在这个人前面且身高大于或等于 h 的人数。例如：[5,2] 表示前面应该有 2 个身高大于等于 5 的人，而 [5,0] 表示前面不应该存在身高大于等于 5 的人。

编写一个算法，根据每个人的身高 h 重建这个队列，使之满足每个整数对 (h, k) 中对人数 k 的要求。

先排序，身高降序，身高相同，则根据k升序
按照k作为下标顺序插入ArrayList，

比如数组排序好之后为：

[7, 0]->[7, 1]->[6, 1]->[5, 0]->[5, 2]->[4, 4]

则往ArrayList中循环插入list.add(item(1), item)每步结果如下

[7,0]
[7,0] [7,1]
[7,0] [6,1] [7,1]
[5,0] [7,0] [6,1] [7,1]
[5,0] [7,0] [5,2] [6,1] [7,1]
[5,0] [7,0] [5,2] [6,1] [4,4] [7,1]
[5, 0]->[7, 0]->[5, 2]->[6, 1]->[4, 4]->[7, 1]
- 因为高的先插入，所以后面身高矮的插入到前面，也不会影响到k对应的顺序；
- 很重要的隐含条件是：原来是有序的，k也是对的

0941. 有效的山脉数组

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

A.length >= 3
在 0 < i < A.length - 1 条件下，存在 i 使得：
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]

分别两个循环，从前往后从后往前，得到上行和下行趋势的最后的下标判断二者是否相等

1207. 独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

复制代码

//每个数字的出现次数
Map<Integer, Integer> map = new HashMap<>();
for (int item : arr) {
map.put(item, map.getOrDefault(item, 0)+1);
}
//不同的次数的集合
Set<Integer> countSet = new HashSet<>(new ArrayList<>(map.values()));
return map.size() == countSet.size();

leetcode刷题记录

一 class类命名规则

二 已做的题目目录

0010.正则表达式匹配▲ TODO 动态规划

0017.电话号码的字母组合 ▲ 递归

0022.括号生成 ▲回溯dfs（减枝）

0023.合并K个升序链表 ▲ 分治算法TODO

0024.两两交换链表中的节点 递归

0032.最长有效括号 动态规划 ▲ 栈

0033. 搜索旋转排序数组 二分法查找

0034. 34. 在排序数组中查找元素的第一个和最后一个位置 二分法查找

0035. 搜索插入位置 二分法查找

0036. 有效的数独 把数存在对应的位上面

0037. 解数独 困难▲ 回溯

0039. 组合总和 中等 回溯

0040. 组合总和 II 中等 回溯

0041. 缺失的第一个正数 困难

0042. 接雨水 困难 中间过程用到动态规划

0044.通配符匹配 困难 动态规划

0045. 跳跃游戏 II 困难 贪心

0046. 全排列 回溯

0047. 全排列 II 回溯

0050. 实现N次幂 分治

0051. N 皇后 困难 回溯

0055. 跳跃游戏 ▲ 递归 | 动态规划 | 贪心

0057.插入区间 困难

0060. 排列序列 困难 回溯效率太低 找规律

0062. 不同路径 动态规划

0063. 不同路径II 动态规划

0064. 最小路径和 动态规划

0065. 有效数字 困难

0068. 文本左右对齐 困难

0069. x 的平方根 二分

0070. 爬楼梯 动态规划

评论区

二已做的题目目录

0024.两两交换链表中的节点递归

0032.最长有效括号动态规划 ▲ 栈

0033. 搜索旋转排序数组二分法查找

0034. 34. 在排序数组中查找元素的第一个和最后一个位置二分法查找

0035. 搜索插入位置二分法查找

0036. 有效的数独把数存在对应的位上面

0037. 解数独困难▲ 回溯

0039. 组合总和中等回溯

0040. 组合总和 II 中等回溯

0041. 缺失的第一个正数困难

0042. 接雨水困难中间过程用到动态规划

0044.通配符匹配困难动态规划

0045. 跳跃游戏 II 困难贪心

0046. 全排列回溯

0050. 实现N次幂分治

0051. N 皇后困难回溯

0057.插入区间困难

0060. 排列序列困难回溯效率太低找规律

0062. 不同路径动态规划

0064. 最小路径和动态规划

0065. 有效数字困难

0068. 文本左右对齐困难

0069. x 的平方根二分

0070. 爬楼梯动态规划