# leetcode

**Repository Path**: loubobooo/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: leetcode的日积月累
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2019-09-02
- **Last Updated**: 2022-04-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# leetcode
---
#### 介绍
leetcode的日积月累

(Notes: "♥如果喜欢请给个star")

| #题号 | 题目| 解决方案 | 难易程度 |
|---| ----- | -------- | ---------- |
|1|[两数之和](https://leetcode-cn.com/problems/two-sum/) | [Java](./src/main/java/com/example/TwoSum.java)|简单|
|2|[两数相加](https://leetcode-cn.com/problems/add-two-numbers/) | [Java](./src/main/java/com/example/AddTwoNumbers.java)|中等|
|3|[无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/) | [Java](./src/main/java/com/example/LongestSubstringWithoutRepeatingCharacters.java)|中等|
|4|[寻找两个有序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/) | [Java](./src/main/java/com/example/MedianOfTwoSortedArrays.java) |困难|
|5|[最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/) | [Java](./src/main/java/com/example/LongestPalindromicSubstring.java)|中等|
|7|[整数反转](https://leetcode-cn.com/problems/reverse-integer/) | [Java](./src/main/java/com/example/ReverseInteger.java)|简单|
|8|[字符串转换整数 (atoi)](https://leetcode-cn.com/problems/string-to-integer-atoi/) | [Java](./src/main/java/com/example/StringToIntegerAtoi.java)|中等|
|9|[回文数](https://leetcode-cn.com/problems/palindrome-number/) | [Java](./src/main/java/com/example/PalindromeNumber.java)|简单|
|11|[盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/) | [Java](./src/main/java/com/example/ContainerWithMostWater.java)|中等|
|12|[整数转罗马数字](https://leetcode-cn.com/problems/integer-to-roman/) | [Java](./src/main/java/com/example/IntegerToRoman.java)|中等|
|13|[罗马数字转整数](https://leetcode-cn.com/problems/roman-to-integer/) | [Java](./src/main/java/com/example/RomanToInteger.java)|简单|
|14|[最长公共前缀](https://leetcode-cn.com/problems/longest-common-prefix/) | [Java](./src/main/java/com/example/LongestCommonPrefix.java)|简单|
|15|[三数之和](https://leetcode-cn.com/problems/3sum/) | [Java](./src/main/java/com/example/ThreeSum.java)|中等|
|17|[电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/) | [Java](./src/main/java/com/example/LetterCombinationsOfAPhoneNumber.java)|中等|
|18|[四数之和](https://leetcode-cn.com/problems/4sum/) |[Java](./src/main/java/com/example/FourSum.java)|中等|
|19|[删除链表的倒数第N个节点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/) |[Java](./src/main/java/com/example/RemoveNthNodeFromEndOfList.java)|中等|
|20|[有效的括号](https://leetcode-cn.com/problems/valid-parentheses/) |[Java](./src/main/java/com/example/ValidParentheses.java) |简单|
|21|[合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/) |[Java](./src/main/java/com/example/MergeTwoSortedLists.java) |简单|
|22|[括号生成](https://leetcode-cn.com/problems/generate-parentheses/) |[Java](./src/main/java/com/example/GenerateParentheses.java) |中等|
|23|[合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/) |[Java](./src/main/java/com/example/MergeJSortedLists.java) |困难|
|24|[两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/) |[Java](./src/main/java/com/example/SwapNodesInPairs.java) |中等|
|26|[删除排序数组中的重复项](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/) |[Java](./src/main/java/com/example/RemoveDuplicateFromSortedArray.java) |简单|
|27|[移除元素](https://leetcode-cn.com/problems/remove-element/) |[Java](./src/main/java/com/example/ImplementStrstr.java) |简单|
|28|[实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/) |[Java](./src/main/java/com/example/RemoveElement.java) |简单|
|29|[两数相除](https://leetcode-cn.com/problems/divide-two-integers/) |[Java](./src/main/java/com/example/DivideTwoIntegers.java) |中等|
|32|[最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/) |[Java](./src/main/java/com/example/LongestValidParentheses.java) |困难|
|33|[搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/) |[Java](./src/main/java/com/example/SearchInRotatedSortedArray.java)|中等|
|34|[在排序数组中查找元素的第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/) |[Java](./src/main/java/com/example/FindFirstAndLastPositionOfElementInSortedArray.java) |中等|
|35|[搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/) |[Java](./src/main/java/com/example/SearchInsertPosition.java) |简单|
|38|[外观数列](https://leetcode-cn.com/problems/count-and-say/) |[Java]() |中等|
|39|[组合总和](https://leetcode-cn.com/problems/combination-sum/) |[Java](./src/main/java/com/example/CombinationSum.java) |中等|
|40|[组合总和 II](https://leetcode-cn.com/problems/combination-sum-ii/) |[Java](./src/main/java/com/example/CombinationSumIi.java) |中等|
|41|[缺失的第一个正数](https://leetcode-cn.com/problems/first-missing-positive/) |[Java](./src/main/java/com/example/FirstMissingPositive.java) |中等|
|42|[接雨水](https://leetcode-cn.com/problems/trapping-rain-water/) |[Java](./src/main/java/com/example/TrappingRainWater.java) |困难|
|46|[全排列](https://leetcode-cn.com/problems/permutations/) |[Java](./src/main/java/com/example/Permutations.java) |中等|
|47|[全排列II](https://leetcode-cn.com/problems/permutations-ii/) |[Java](./src/main/java/com/example/PermutationsIi.java) |中等|
|49|[字母异位词分组](https://leetcode-cn.com/problems/group-anagrams/) |[Java](./src/main/java/com/example/GroupAnagrams.java) |中等|
|50|[Pow(x, n)](https://leetcode-cn.com/problems/powx-n/) |[Java](./src/main/java/com/example/PowxN.java) |中等|
|51|[N 皇后](https://leetcode-cn.com/problems/n-queens/) |[Java](./src/main/java/com/example/NQueens.java) |困难|
|52|[N皇后 II](https://leetcode-cn.com/problems/n-queens-ii/) |[Java](./src/main/java/com/example/NQueensIi.java) |困难|
|53|[最大子数组和](https://leetcode-cn.com/problems/maximum-subarray/) |[Java](./src/main/java/com/example/MaximumSubarray.java) |简单|
|54|[螺旋矩阵](https://leetcode-cn.com/problems/spiral-matrix/) |[Java](./src/main/java/com/example/SpiralMatrix.java)|中等|
|58|[最后一个单词的长度](https://leetcode-cn.com/problems/length-of-last-word/) |[Java](./src/main/java/com/example/LengthOfLastWord.java) |简单|
|60|[排列序列](https://leetcode-cn.com/problems/permutation-sequence/) |[Java](./src/main/java/com/example/PermutationSequence.java) |困难(回溯超时)|
|61|[排列序列](https://leetcode-cn.com/problems/rotate-list/) |[Java](./src/main/java/com/example/RotateList.java) |中等|
|62|[不同路径](https://leetcode-cn.com/problems/unique-paths/) |[Java](./src/main/java/com/example/UniquePaths.java) |中等|
|63|[不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/) |[Java](./src/main/java/com/example/ValidParentheses.java) |中等|
|66|[加一](https://leetcode-cn.com/problems/plus-one/) |[Java](./src/main/java/com/example/PlusOne.java) |简单|
|67|[二进制求和](https://leetcode-cn.com/problems/add_binary/) |[Java](./src/main/java/com/example/AddBinary.java) |简单|
|69|[x 的平方根](https://leetcode-cn.com/problems/sqrtx/) |[Java](./src/main/java/com/example/Sqrtx.java) |简单|
|70|[爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/) |[Java](./src/main/java/com/example/ClimbingStairs.java) |简单|
|72|[编辑距离](https://leetcode-cn.com/problems/edit-distance/) |[Java](./src/main/java/com/example/EditDistance.java) |困难|
|75|[颜色分类](https://leetcode-cn.com/problems/sort-colors/) |[Java](./src/main/java/com/example/SortColors.java) |中等|
|77|[组合](https://leetcode-cn.com/problems/combinations/) |[Java](./src/main/java/com/example/Combinations.java) |中等|
|78|[子集](https://leetcode-cn.com/problems/subsets/) |[Java](./src/main/java/com/example/Subsets.java) |简单|
|79|[单词搜索](https://leetcode-cn.com/problems/word-search/) |[Java](./src/main/java/com/example/WordSearch.java) |中等|
|82|[删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/) |[Java](./src/main/java/com/example/RemoveDuplicatesFromSortedListIi.java) |中等|
|83|[删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/) |[Java](./src/main/java/com/example/RemoveDuplicatesFromSortedList.java)|简单|
|88|[合并两个有序数组](https://leetcode-cn.com/problems/merge-sorted-array/) |[Java](./src/main/java/com/example/MergeSortedArray.java)|简单|
|90|[子集 II](https://leetcode-cn.com/problems/subsets-ii/) |[Java](./src/main/java/com/example/SubsetsIi.java)|中等|
|92|[反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/) |[Java](./src/main/java/com/example/ReverseLinkedListIi.java)|中等|
|93|[复原 IP 地址](https://leetcode-cn.com/problems/restore-ip-addresses/) |[Java](./src/main/java/com/example/RestoreIpAddresses.java)|中等|
|94|[二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/) |[Java](./src/main/java/com/example/BinaryTreeInorderTraversal.java) |中等|
|99|[验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/) |[Java](./src/main/java/com/example/ValidateBinarySearchTree.java) |中等|
|100|[相同的树](https://leetcode-cn.com/problems/same-tree/) |[Java](./src/main/java/com/example/SameTree.java) |简单|
|101|[对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/) |[Java](./src/main/java/com/example/SymmetricTree.java) |简单|
|102|[二叉树的层次遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/) |[Java](./src/main/java/com/example/BinaryTreeLevelorderTraversal.java) |中等|
|103|[ 二叉树的锯齿形层序遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/) |[Java](./src/main/java/com/example/BinaryTreeZigzagLevelOrderTraversal.java) |中等|
|104|[二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/) |[Java](./src/main/java/com/example/MaximumDepthOfBinaryTree.java) |简单|
|107|[二叉树的层序遍历 II](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/) |[Java](./src/main/java/com/example/BinaryTreeLevelOrderTraversalIi.java) |中等|
|111|[二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/) |[Java](./src/main/java/com/example/MinimumDepthOfBinaryTree.java) |简单|
|112|[路径总和](https://leetcode-cn.com/problems/path-sum/) |[Java](./src/main/java/com/example/PathSum.java) |简单|
|114|[二叉树展开为链表](https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/) |[Java](./src/main/java/com/example/FlattenBinaryTreeToLinkedList.java) |中等|
|118|[杨辉三角](https://leetcode-cn.com/problems/pascals-triangle/) |[Java](./src/main/java/com/example/PascalsTriangle.java) |简单|
|119|[杨辉三角 II](https://leetcode-cn.com/problems/pascals-triangle-ii/) |[Java](./src/main/java/com/example/PascalsTriangleIi.java) |简单|
|121|[买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/) |[Java](./src/main/java/com/example/BestTimeToBuyAndSellStock.java) |简单|
|125|[验证回文串](https://leetcode-cn.com/problems/valid-palindrome/) |[Java](./src/main/java/com/example/ValidPalindrome.java) |简单|
|131|[验证回文串](https://leetcode-cn.com/problems/palindrome-partitioning/) |[Java](./src/main/java/com/example/PalindromePartitioning.java) |中等|
|136|[只出现一次的数字](https://leetcode-cn.com/problems/single-number/) |[Java](./src/main/java/com/example/SingleNumber.java) |简单|
|137|[只出现一次的数字 II](https://leetcode-cn.com/problems/single-number-ii/) |[Java](./src/main/java/com/example/SingleNumberIi.java) |中等|
|141|[环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) |[Java](./src/main/java/com/example/LinkedListCycle.java) |简单|
|142|[环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/) |[Java](./src/main/java/com/example/LinkedListCycleIi.java) |中等|
|144|[二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/) |[Java](./src/main/java/com/example/BinaryTreePreorderTraversal.java) |简单|
|145|[二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/) |[Java](./src/main/java/com/example/BinaryTreePostorderTraversal.java) |简单|
|146|[LRU 缓存](https://leetcode-cn.com/problems/lru-cache/) |[Java](./src/main/java/com/example/LRUCache.java) |中等|
|148|[排序链表](https://leetcode-cn.com/problems/sort-list/) |[Java](./src/main/java/com/example/SortList.java) |中等|
|151|[翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/) |[Java](./src/main/java/com/example/ReverseWordsInAString.java) |中等|
|152|[乘积最大子数组](https://leetcode-cn.com/problems/maximum-product-subarray/) |[Java](./src/main/java/com/example/MaximumProductSubarray.java) |中等|
|164|[最大间距](https://leetcode-cn.com/problems/maximum-gap/) |[Java](./src/main/java/com/example/MaximumGap.java) |困难|
|167|[两数之和 II - 输入有序数组](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/) |[Java](./src/main/java/com/example/TwoSumIiInputArrayIsSorted.java) |中等|
|160|[相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/) |[Java](./src/main/java/com/example/IntersectionOfTwoLinkedLists.java) |简单|
|169|[多数元素](https://leetcode-cn.com/problems/majority-element/) |[Java](./src/main/java/com/example/MajorityElement.java) |简单|
|172|[阶乘后的零](https://leetcode-cn.com/problems/factorial-trailing-zeroes/) |[Java](./src/main/java/com/example/FactorialTrailingZeroes.java) |中等|
|174|[地下城游戏](https://leetcode-cn.com/problems/dungeon-game/) |[Java](./src/main/java/com/example/DungeonGame.java) |困难|
|179|[最大数](https://leetcode-cn.com/problems/largest-number/) |[Java](./src/main/java/com/example/LargestNumber.java) |中等|
|190|[颠倒二进制位](https://leetcode-cn.com/problems/reverse-bits/) |[Java](./src/main/java/com/example/ReverseBits.java) |简单|
|191|[位1的个数](https://leetcode-cn.com/problems/number-of-1-bits/) |[Java](./src/main/java/com/example/NumberOf1Bits.java) |简单|
|199|[二叉树的右视图](https://leetcode-cn.com/problems/binary-tree-right-side-view/) |[Java](./src/main/java/com/example/BinaryTreeRightSideView.java) |中等|
|202|[快乐数](https://leetcode-cn.com/problems/happy-number/) |[Java](./src/main/java/com/example/HappyNumber.java) |简单|
|203|[移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements/) |[Java](./src/main/java/com/example/RemoveLinkedListElements.java) |简单|
|206|[反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) |[Java](./src/main/java/com/example/ReverseLinkedList.java) |简单|
|208|[实现 Trie (前缀树)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/) |[Java](./src/main/java/com/example/Trie.java) |中等|
|215|[数组中的第K个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/) |[Java](./src/main/java/com/example/KthLargestElementInAnArray.java) |中等|
|217|[存在重复元素](https://leetcode-cn.com/problems/contains-duplicate/) |[Java](./src/main/java/com/example/ContainsDuplicate.java) |简单|
|221|[最大正方形](https://leetcode-cn.com/problems/maximal-square//) |[Java](./src/main/java/com/example/MaximalSquare.java) |中等|
|222|[完全二叉树的节点个数](https://leetcode-cn.com/problems/count-complete-tree-nodes/) |[Java](./src/main/java/com/example/CountCompleteTreeNodes.java) |中等|
|225|[用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/) |[Java](./src/main/java/com/example/MyStack.java) |简单|
|226|[翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/) |[Java](./src/main/java/com/example/InvertBinaryTree.java) |简单|
|227|[基本计算器 II](https://leetcode-cn.com/problems/basic-calculator-ii/) |[Java]() |中等|
|228|[汇总区间](https://leetcode-cn.com/problems/summary-ranges/) |[Java](./src/main/java/com/example/SummaryRanges.java) |简单|
|229|[求众数 II](https://leetcode-cn.com/problems/majority-element-ii/) |[Java](./src/main/java/com/example/MajorityElementIi.java) |中等|
|231|[2 的幂](https://leetcode-cn.com/problems/power-of-two/) |[Java](./src/main/java/com/example/PowerOfTwo.java) |简单|
|232|[用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/) |[Java](./src/main/java/com/example/ImplementQueueUsingStacks.java) |简单|
|237|[删除链表中的节点](https://leetcode-cn.com/problems/delete-node-in-a-linked-list/) |[Java](./src/main/java/com/example/DeleteNodeInALinkedList.java) |简单|
|234|[回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/) |[Java](./src/main/java/com/example/PalindromeLinkedList.java) |简单|
|236|[二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/) |[Java](./src/main/java/com/example/LowestCommonAncestorOfABinaryTree.java) |中等|
|258|[各位相加](https://leetcode-cn.com/problems/add-digits/) |[Java](./src/main/java/com/example/AddDigits.java) |简单|
|347|[前 K 个高频元素](https://leetcode-cn.com/problems/top-k-frequent-elements/) |[Java](./src/main/java/com/example/TopKFrequentElements.java) |中等|
|443|[压缩字符串](https://leetcode-cn.com/problems/string-compression/) |[Java](./src/main/java/com/example/StringCompression.java) |中等|


## 刷题套路总结
### 动态规划模板(5部曲)
```
特征：连续类的题目
```
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式dp[i]
3. dp数组的初始化
4. 确定遍历顺序
5. 举例推导dp数组

### 回溯算法模板(3部曲)
1. 递归函数参数
2. 递归终止条件
3. 单层搜索的逻辑
```
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
```
注意：要有startIndex记录一个起始位置，组合问题循环遍历for从startIndex开始，排列问题循环遍历for从0开始

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，**那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！**

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。

**那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！**

有同学问了，什么时候for可以从0开始呢？

求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。

首先排列是有序的，也就是说[1,2] 和[2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

以示例中nums = [1,2,3]为例把求子集抽象为树型结构

## 二叉树的非递归遍历模板
```
TreeNode cur = root;
while( 栈非空 || cur 非空)
{
if( cur 非空)
{

}
else
{

}
}
```