- *代表需要重视的程度
- 重视的题型：排列组合
求数组内=target的元素下标，HashMap
使用boolean[] 256做hash桶，使用双指针，前指针往前移填充hash，发现重复的话（更新结果），后指针前移，擦除hash，循环检查前指针指向的字符是否重复，重复就后指针前移，不重复就前指针前移。
DP, 二维DP，填左半边，从下往上，从左往右 子串 dp[i, j] = (char_i == char_j) && dp[i+1, j-1]
for (int i = len-1; i >= 0; i--) {
for (int j = i+1; j < len; j++) {
if (s.charAt(i) == s.charAt(j) && (i+1 > j-1 || dp[i+1][j-1])) {
dp[i][j] = true;
if (j-i+1 > longest) {
longest = j - i + 1;
start = i;
}
}
}
}Z字形（从上到下，从左到右排列字符串，然后按行收集），关键：控制打印方向 flag
直接使用取余即可，不用区分正数负数，负数对10取余，是末尾的数字加个负号（Java是截断除法），判断溢出可以判断在ret*10+last前面判断与MAX_VALUE/10的关系。
溢出需要全面考虑
不将整数转化成字符串，按照第7题，将数字反转，看看是否和原数字一样。
双指针，头尾各一个指针，一开始宽是最长的，所以移动短的那一端，高才有可能增加，进而面积才有可能增加。
字符串数组中的最长公共前缀。很简单，索引从0开始到 最短字符串的长度len，然后遍历每个串，求当前索引位置的字符是否都相等，遇到不相等的，直接返回（公共前缀就到此）。
固定一个数字，然后就转化成了两数之和问题，可以使用排序+双指针写法；或者使用Hash方法。
双指针，和上题基本一样，固定一个数字，然后头尾双指针移动，双指针移动的方法也一样，只不过就是在内部要更新一下接近值。
三数之和升级版，就是在三数之和的基础之上多加了一层循环，前面循环两个数，然后最后变成两数之和。
一个指针先走N步，然后另一个指针开始走，第一个指针走到头，第二个指针指向的位置就是倒数第N个结点。不用非得
while (fast.next != null) {
if (n <= 0) slow = slow.next;
fast = fast.next;
n--;
}
slow.next = slow.next.next;使用栈，遍历当前字符，是)]}时候，pop出栈顶元素，查看是否匹配；是([{括号入栈。
归并算法
生成n对合法的括号字符串（括号匹配），可以组成有效括号重点是：左右括号的数目
非常优秀的一道回溯、DFS类题目，对于排列组合类的回溯，还需多练习。
private void dfs(int n, int l, int r, String cur, List<String> ret) {
if (cur.length() == 2*n) {
ret.add(cur);
return;
}
if (l < n) {
dfs(n, l+1, r, cur+'(', ret);
}
if (r < l) {
dfs(n, l, r+1, cur+')', ret);
}
}使用大小为K的堆，找到最小的点，链接到结果链表，然后此节点的下一个节点加入堆（此处也是以前没有想到的地方）
有一个指向前面的p, 然后q 和 q.next是要交换的两个，但是也要注意p要指向q.next。
public ListNode swapPairsNew(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode p = dummy, q = head;
while (q != null && q.next != null) {
p.next = q.next;
q.next = q.next.next;
p.next.next = q;
// 更新 p 和 q
p = q;
q = q.next;
}
return dummy.next;
}
// 不要和 字符串翻转 代码搞混了
public ListNode swapPairsRecursive(ListNode head) {
if(head == null || head.next == null) return head;
ListNode nextNode = head.next;
head.next = swapPairsRecursive(nextNode.next);
nextNode.next = head;
return nextNode;
}// 翻转链表 递归写法
private ListNode reverse2(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverse2(head.next);
head.next.next = head;
head.next = null;
return newHead;
}数组，去除重复项后,原地修改数组，前面都是非重复的元素，返回长度。 这种重复的要考虑相邻的元素是否相等。
- 删除排序数组中的重复项2
- 要移除的元素多 保留的少，那么就挑选出要保留的元素，从前往后放置
public int removeElement(int[] nums, int val) {
int ans = 0;
for(int num: nums) {
if(num != val) {
nums[ans] = num;
ans++;
}
}
return ans;
}- 要移除的元素少 保留的多，那么就将要移除的挪到后面去，要保留的从后往前挪到前面去。
class Solution {
public int removeElement(int[] nums, int val) {
int ans = nums.length;
for (int i = 0; i < ans;) {
if (nums[i] == val) {
// 不用找特定的位置再挪，一个一个挪过去就行，也可以循环找到位置
nums[i] = nums[--ans];
} else {
i++;
}
}
return ans;
}
}Sunday算法
数组数字序列，下一个更大的排列。 思路：从后往前找到arr[i-1] < arr[i]的位置，然后找到后面第一个比arr[i-1]大的位置，两个位置交换，然后 i-1往后的元素（从大到小排列的），逆序即可.
根据num[l] 与num[m]的关系
相关题目：81
二分查找，注意初始值（和边界值有关），以及如何判断边界值
判断一个数独（没有数字的部分使用'.'来填充）是否有效（三种规则行1-9、列1-9，3X3格子1-9）。 解法：使用三个hash表（Hash表使用长度为10的boolean数组），一次遍历即可，特别要注意的是3X3格子的下标转换。
从前往后读前一个字符串连续数目、数字，追加到结果中。 求连续的数目，最好的办法是判断 j == j+1 是否成立.
一个数组能组成target的所有组合，不要重复，每个数字可以用多次。 典型的回溯，因为要求所有组合！是一个枚举所有情况的过程。
在39题的基础之上，每个数字只能使用一次。 难点：如何去重。方案：排序，判断数组中当前（要添加到结果集）的元素和前一个是否是相等的？ 回溯中有两个逻辑
给你一个未排序的整数数组（可能存在负整数），请你找出其中没有出现的最小的正整数。 思路：最小整数是 <= 数组的长度n的，，并且还是正整数，所以就想到了数组的下标，在数组下标身上进行标记。将数组中<=0的数字使用n+1进行替换，然后遍历数组，绝对值<=n的，数组中对应的元素（若为正）换成负数。
木桶原理，每一个柱体可以接雨水，由它的左边和右边的最大值的最小值来决定的。我们可以求每一个柱体的这个值，左遍历一遍，右遍历一遍即可。 我们可以使用双指针进行优化, 小的那一边进行移动，然后不断的更新小的那一边的max值，最终结果不断的累加max-cur的。
竖式模拟乘法，可以找规律：最终结果最多 len1+len2位；str1[i] * str2[j]，获得的局部结果在第ret[i+j]和ret[i+j+1]位置。 难点：如何将这些局部的值加在一起? 就是从后往前计算，在计算每个局部和 sum = str1[i] * str2[j]+ret[i+j+1]， ret[i+j+1] = sum % 10; ret[i+j] += sum /10; 注意去除前导0，和结果仅为0的情况。
问至少多少次可以跳到末尾，贪心算法，每次跳到所能触及到的最远位置，
求没有重复的数组的去排列。 回溯，还有used数组，套模板即可。
和上题一样，但是难点：如何解决重复? 对数组预先排序，对于重复的元素，只使用第一个元素。
if (i > 0 && num[i] == num[i-1] && !used[i-1]) continue;
如果used[i-1]没有被使用，那么后续肯定会被使用，就会导致重复。
原地顺时针旋转90度，左上和右下进行交换，然后再上下交换。
原地修改的算法，一般思路是：交换、做标记（�加正负号、bit位做标记）
将排序后的字符串作为识别的key，添加到map的集合中。 如何避免排序，可以自己统计每种字母的情况，然后组成特殊的字符串当成map的key
char[] chars = str.toCharArray();
Arrays.sort(chars);快速幂算法
数组最大的子序列的和。思路：遍历，碰见 当前值+sum < 当前值时候，让sum= 当前值
螺旋打印矩阵，控制边界即可。
数组值代表能跳的距离，从第一个位置判断能否走到最后一个位置。每一个位置，都有一个能走的最远位置，判断这个位置是否大于等于当前位置。
排序，前一个区间的s 和 e 关系：(1)e < nextS, 加入结果集 (2) e > nextS, e 与 nextE的关系，去较小值
区间类型的题目，一般都需要排序，然后找相邻区间的关系，或者类似于括号似的，计一下数
有序的无重叠区间。插入一个新的区间，使得所有新区间不重叠。 考的是逻辑思路：右区间小于当前新区间的左区间，直接加入结果集，然后是处理重叠部分，最后将剩下的（左区间大于新区间的右区间）加入结果集。
从后往前遍历，去除前导 空格，�从不是空格的位置开始，再次从后往前遍历，计数，碰见空格停止。
阶乘先保存在数组里面 找规律，注意k是从第1个数字开始的，所以K要先减去1， 然后 k / (n-1)! k = k % (n-1)!
计算链表长度len与k的关系，能整除，不用旋转；否则 找到倒数第k+1个节点和倒数第一个节点，然后改变指针指向即可
机器人位于棋盘的左上角，只能往下或者往右走，问到右下角有多少走法。 63题，方格上有障碍物。 解法：DP，按列进行，从上到下，从左往右
和62、63一样，只不过是找一条路径,路径和最小，和前面两题思路一样。
初始进位为1，从后往前加这个进位，如果进位==0，break, 查看最终进位是否为0，如果不是，说明结果位数增加。
使用两个下标，分别从两个串的尾部到头。一开始写的时候特别费劲，总想用一个索引来控制两个串，在下标的转换中遇到了不少问题。 这题和快慢指针，求链表的长度差思想一致。这种对不起的，有距离差的，使用两个指针更方便，更好控制。
m * m >= x 注意m*m可能会溢出，要进行强制类型转换。
dp[n] = dp[n-1] + dp[n-2];
将路径根据”/”split成数组，对于“..”且栈不为空的时候，弹出栈中的元素，其他的不等于"", ".", “..”
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 可以对一个单词进行如下三种操作：插入一个字符；删除一个字符；替换一个字符。 DP:
- dp[i][j]中存的是什么？ word1的前i个字符和word2的前j个字符的编辑距离。
使用原地算法，将元素为0的数组，行、列全置为0. 如何不使用额外的空间? 使用第一行第一列做标记（所以要注意不能修改第一行和第一列的数据）
矩阵的每一行的第一个数大于上一行的最后一个数。很典型的二分法，注意下标的切换。
- 搜索二维矩阵2 每一行、每一列都升序。从矩阵的右上角或者左下角，就和二叉搜索树似的，往左是减小，往下是增大，减治的思想。target > matrix[row][col] row++, target < matrix[row][col] col--
荷兰国旗问题，如果使用一次遍历，就将三类数据分类。分成两类很简单，交换就行了。分成三类，也是需要交换，往两边交换。
难点：细节，交换的时候，指针的变化。
public void sortColors(int[] nums) {
// p0左侧是0区，p2右侧是2区
int p0 = 0, p2 = nums.length-1, cur = 0;
while (cur <= p2) { // [2,0,1]
if (nums[cur] == 0) {
swap(nums, cur++, p0++);
} else if (nums[cur] == 2) {
swap(nums, cur, p2--);
} else {
cur++;
}
}
}在S串中找到包含T串所有字母的最小子串。
使用int[]作为map，双指针，前指针去减map中的元素(并统计count), 当count==0时候，说明map内的元素都包括在前后指针之间了，此时移动后指针，map中的元素累加，value大于0的时候count++，说明有元素没有包括在前后指针之间。
亮点： 使用数字作为map，使用计数替代contain
和26题一样的要求，只不过要求排序数组内的元素最多2个。
// i是符合要求的元素，num[i-2]避免出现2次
public int removeDuplicates(int[] nums) {
int i = 0;
for (int num : nums) {
if (i < 2 || num > nums[i-2]) {
nums[i++] = num;
}
}
return i;
}// [1,3,1,1,1] [1,1,1,3,1]
public boolean search(int[] nums, int target) {
if (nums.length == 0) return false;
int left = 0, right = nums.length - 1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
// if (target == nums[mid]) return true;
// 和33题不同的地方
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
} else if (nums[left] <= nums[mid]) { // 左边有序（旋转点在右边）
if (nums[left] <= target && target <= nums[mid]) right = mid;
else left = mid + 1;
} else { // 右边有序（旋转点在左边）
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid;
}
}
return nums[left] == target;
}- 重复元素保留一个（简单，碰见当前和下一个相等，就把下一个隔过去）
if (p.val == p.next.val) {
p.next = p.next.next;
} else {
p = p.next;
}- ***一个都不保留（较难） pre, cur, 当cur.val == cur.next.val的时候，cur++， 发现不等时候（或者cur.next == null），判断此时pre.next == cur ? 不等于说明，cur是重复元素，pre.next = cur.next, 否则pre = cur
暴力思维：每一列为高，向左右两边扩散，看看能扩散多远（宽）。扩散的时候，只能找周围连续的、比自己高的列，碰见比自己低的列，就要停下。
优化：这很显然是一个下一个更小问题，就想到了单调递增栈。咱们可以往一边去扩散，以peek为高，往右找，不断的拓宽。碰到递减的元素pop出peek，便可以计算以peek为高的 矩形。还一个要注意的点：w如何求，必须得用当前的w = i - stack.peek -1(stack.isEmpty, w = i)
解法1：和84题一样的思路，把每一行当成一个84题的柱形图
解法2：每一个点，都求一个h l r, 然后求面积
给定一个target，分隔成比target小的和大于等于target的两个链表，然后再连接起来
迭代做法，分两部分： 前一批格雷码 + 前一批倒序(头部补1)
一个串的最长有效括号子串。
- 栈的做法: 栈中保存下标"("入栈， ")"出栈（然后当前下标-栈顶下标作为长度，若栈为空，当前下标入栈，作为分隔点，这也是初始栈中放-1的原因）
- DP做法，两大类情况 "()" "))"，其余的情况都为0
- i-1和i为"()"情况 dp[i] = dp[i-2]+2
- i-1和i为 "))" 要看i-1位置的")" 匹配了多少, 且要看 i-dp[i-1]-1位置是否为 "(" 则 dp[i] = dp[i-1]（内部） + 2+ dp[i-dp[i-1]-1-1]（外部）
- 其余为0
难点：如何移动到下一个位置。j每次+1 当j == col的时候，i+1, 当i == row的时候，整个函数返回。
// 判断 3 X 3 下标
x = 3 * (row / 3) + i / 3;
y = 3 * (col / 3) + i % 3;求N皇后的方案或者方案数目。
回溯典型题： 按row回溯，每一row有col种放法。 难点，如何剪枝（判断是否有效）：同行、同列、主、副对角线
对角线 行 + 列 == 常数 行 - 列 == 常数
画出状态转移图，使用有限状态自动机很简单。 状态转移，表驱动：将char转换成下标，在二维数组间转移，碰见无效状态、无效操作直接返回。
题目大意：每一行单词在指定宽度内对齐，单词间的空格从左到右要均匀分布 考察的就是逻辑和字符串的操作，还有更重要的是，收尾处理（循环内没有处理完，跳出循环了，要在循环外）