## Leetcode-70 爬楼梯问题（DP）

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

$stairs(n) = stairs(n-1) + stairs(n-2)$，只需要初始化好退出递归的条件就算写完了。

## leetcode-242 重排校验

Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true

## leetcode-104 二叉树最大深度

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Given binary tree [3,9,20,null,null,15,7],return its depth = 3.

## leetcode-160 链表交集

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

begin to intersect at node c1.

1. 指针顺序遍历，解决一个问题就是2个链表长度不同，所以第一步要遍历得到2个链表的长度（这块可能空间复杂度开销比较大）。将长链表向前移动至剩余链表长度与短链表一致。

2. 最大的障碍是2个链表长度不同，所以有一个巧妙的办法来补齐。就是当一个链表先行到达链表尾部时，将Next指针去指向另一个链表的头部，同理另一个链表也同样如此，这样就保证了在O（m+n）内一定能找到结果。举个例子：
ListNodeA = 0, 9, 1, 2, 4
LIstNodeB = 3, 2, 4
Path of A -> B = 0, 9, 1, 2, 4, 3, 2, 4
Path of B -> A = 3, 2, 4, 0, 9, 1, 2, 4
这样只需要遍历一次，如果遍历结束2个指针仍然不同都指向None，也就没有交集.

## Leetcode-204 质数个数

Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

1. 创建一个数组，长度为n个True，第0，1个位置设置为False，即0和1不是质数。
2. 从2开始（True，初始化），用2举例，以2*2作为起点开始迭代，迭代的终点是n，步长为2，将满足的都标记为False。
3. 同理3，4由于已经被2标记了跳过，5同理，6被标记，7同理，循环的终点就是$\sqrt{n}$。这里解释一下，因为一共有n个数，每次的起点是i*i，这是因为避免了重复的计算，比如3是从3*3开始的，因为32已经计算过了，$\sqrt{n} \sqrt{n}$作为终点也是保证了不重复计算。总的遍历从2到$\sqrt{n}$，次数下降了指数级别。
4. 这里又借助了python list的可以设置变步长的性质 [i*i : n : i]，也不需要额外开辟更大的空间，可以说是时间复杂度和空间复杂度都做到了极致。
5. AC了，但是凭空我肯定是想不到的。

## Leetcode-17 Letter Combinations of a Phone Number 字母组合

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

(letters = {‘2’: ‘abc’, ‘3’: ‘def’, ‘4’: ‘ghi’, ‘5’: ‘jkl’,
‘6’: ‘mno’, ‘7’: ‘pqrs’, ‘8’: ‘tuv’, ‘9’: ‘wxyz’})
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 2:
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

AC了，也可以借助双指针，主指针是饼干，从动的那个指针是小孩，这样就可以省去异常值也放进去循环了，差不多的思想，排序之后其实优化方法还有很多，感觉排序就是一个能让天空放晴的办法，借助while和指针，大概写了一下：

## Leetcode-416 Partition Equal Subset Sum 分割相等子集

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

• 首先，题目要求2个子数组和相等，因此，只有大数组的和为偶数，才可能使得2个子数组和是相等，所以一旦和为奇数就可以立即排除输出False
• 其次对于和为偶数的情况，可以将总和除2作为每个子数组的目标和，所以问题就转化为找出子数组和为$target = sum / 2$。
• DP问题就是要借助DP的思想，就要写一下状态转移方程，作为写代码的指导思想。动态规划都是借助一个2维或者1维的表格来建立整个过程，于是我们借一个例子来画一下表格：

]处已经满足，那加上nums[i]也同样会满足，显示了DP的递推性。这样主体就搭建好了。

## Leetcode-215 第K个最大的数

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

## Leetcode-46 Permutations 排列

Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

AC了，看到另外的解法，避免了在循环中进行判断，而是在传入下层递归的时候，就只传入除去当次循环的那个元素后的剩余元素，要巧妙的多。

## Leetcode-647 Palindromic Substrings 回文子串个数

Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

AC了，看了个大神的方法，用了for嵌套while的结构，看着还是挺清楚的，我承认我之前非要写个递归，其实就是想自己练练写递归，也没什么特别的道理哈哈。这里用了一个技巧来一步实现奇数偶数的判断，left = center / 2, right = center / 2 + center % 2. 实现如下：

## Leetcode-230 Kth Smallest Element in a BST BST树中第k个最小值

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:
Input: root = [3,1,4,null,2], k = 1. Output: 1
3
/ \
1 4
\
2

## Leetcode-69 Sqrt(x) 开根号

Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:
Input: 4
Output: 2

## Leetcode-226 Invert Binary Tree 翻转二叉树

Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9

Output:
4
/ \
7 2
/ \ / \
9 6 3 1

## Leetcode-435 Non-overlapping Intervals 不重复交集

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

AC了，这个题没什么特别的，就是要一开始想清楚。

## Leetcode-51 N-Queens N皇后

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example:
Input: 4
Output: [
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],
[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

• 判断模块，3个情况，不在同一行，不在同一列，不在同一个斜线。这里的斜线要考虑2个方向：abs(r1-r2) == abs(c1 - c2)以及 r1+c1 == r2+c2 （checkValid()）。
• 主模块，递归加遍历，这里我比较优先采用DFS来收集(dfs())。
• 打印结果模块 (trans_print())。

## Leetcode-19 Remove Nth Node From End of List 末尾移除节点

Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

## Leetcode-235 Lowest Common Ancestor of a Binary Search Tree BST最低公共祖先

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

## Leetcode-207 Course schedule

There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.

1. 入度为0的顶点的集合（每次遍历图，如果图顶点的后继节点不存在，那就移入入度为0的集合）
2. 遍历过已经放入的结果集（遍历过的放入结果中）
3. 当前图（字典，当移除入度为0的顶点，同步也要将图中的边进行更新，同步移除包含该入度为0顶点对应的边，再进行判断，如果移除后顶点本身同样没有进入的边了即值为空数组，便也要将其更新到入度为0顶点的集合中，以便继续遍历结束）。

## Leetcode-309 Best Time to Buy and Sell Stock with Cooldown 股票买卖

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

Input: [1,2,3,0,2]
Output: 3

1. hold[i] = max(hold[i-1], reset[i-1] - price[i])
持有状态的价值 = max(前一时刻持有的价值，当前时刻买入的价值)，由于买入之前一定要有cooldown，所以会产生第二种状态转变，注意买入的话是花钱，所以是减去当前股价。
2. sold[i] = hold[i-1] + price[i]
卖出状态的价值 = 前一时刻的持有和当前卖出加钱的和，这里hold[i-1]因为是买入花钱，就一定是负数，所以是求和。
3. rest[i] = max(rest[i-1], sold[i-1])
空仓状态的价值 = max(前一时刻空仓价值，卖出之后的价值）。因为卖出后必须要cooldown，所以这里的sold[i-1]也可以理解了。

## Leetcode-64 Minimum Path Sum 最小路径和

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

## Leetcode-763 Partition Labels 分割字符

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Output: [9,7,8]

Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.

## Leetcode-232 Implement Queue using Stacks 用堆栈实现队列

Implement the following operations of a queue using stacks.

push(x) — Push element x to the back of queue.
pop() — Removes the element from in front of queue.
peek() — Get the front element.
empty() — Return whether the queue is empty.
Example:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

## Leetcode-975 Odd Even Jump 奇偶跳

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:
During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)
A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

（对于某些索引 i，可能无法进行合乎要求的跳跃。）

odd[i] = even[j]
even[i] = odd[j]

odd[i] = even[odd_next[i]]
even[i] = odd[even_next[i]]

## Leetcode-486 Predict the Winner 预测胜者

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
1 5 233 8

## Leetcode-551 Student Attendance Record I 学生出席率

You are given a string representing an attendance record for a student. The record only contains the following three characters:
‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.
A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:
Input: “PPALLP”
Output: True
Example 2:
Input: “PPALLL”
Output: False

## Leetcode-1 2SUM 2数求和

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

## Leetcode-15 3SUM 3数求和

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

## Leetcode-18 4SUM 4数求和

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

4数求和啦，一路从2个做到4个，这里也是一样的意思，4数就是4个指针喽（噗~(oﾟ▽ﾟ)o）。一样也是会遇到很恶心的重复问题，我这里先自己丑陋的实现了一遍，思路是外层2个指针，内部做2SUM，去重我借助了一个字典，因为重复的情况很多很复杂，所以借助字典可以照顾到所有的情况，内外一旦发现重复，就启动指针的移位，最后输出结果中的每一个都先排了个序，再set去重，再转成list输出，哈哈哈，发现居然AC了。代码如下：

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

[
[7],
[2,2,3]
]

[
[2,2,2,2],
[2,3,3],
[3,5]
]

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

[
[1,2,2],
[5]
]