1、求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6示例 2：
输入: n = 9
输出: 45解题思路
不使用for、if，使用递归进行相加，当n=10
10 +sumNums(10-1)
9 + sumNums(9-1)
8 + sumNums(8-1)
+到1就停止递归，即(10 +9+... +2 +1)class Solution {
public int sumNums(int n) {
if(n == 1) {
return 1;
}
return n +sumNums(n-1);
}
}但是不允许使用if，可以使用&&替代
代码
class Solution {
public int sumNums(int n) {
int sumOr1 = n;
//n > 1就能继续递归，否则终止递归，返回sumOr1（此时sumOr1 = n = 1）
boolean flag = n>1 && (sumOr1 += sumNums(n-1)) >0;
return sumOr1;
}
}2、数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1解题思路
一、map
直接使用map，key为数字，value为出现的次数，遍历数组，如果map存在则value+1，否则添加，value为1。
HashMap<Integer, Integer> map = new HashMap<>();
int currentNum = 0;
int currentCount = 0;
// 存入map
for(int i = 0; i < nums.length; i++) {
// 存在
currentNum = nums[i];
if(map.get(currentNum) != null) {
map.put(currentNum, map.get(currentNum) +1 ); // 数量加一
} else {
map.put(currentNum, 1);
}
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
if(entry.getValue() == 1) {
return entry.getKey();
}
}
// Set<Integer> keySet = map.keySet();
// for (Integer key : keySet) {
// currentCount = map.get(key);
// if(currentCount == 1) {
// return key;
// }
// }二、数组计算各二进制位和
数字的各个二进制位相加%3就会多出唯一的数字的当前位的值
比如 1 +1 +1 +2，二进制位为：
0001
0001
0001
0010
各个位相加结果：0 0 1 3，
各个位%3即为多出的数的二进制位： 0 0 1 0 => 2获取每一位：
num & 1即可获取当前最低位，通过循环num = num >>>1无符号右移，配合num & 1可以逐个获取所有二进制位，并与二进制数组进行相加恢复二进制位：
0 0 1 3 => 0 0 1 0 => 2从二进制位数组最高位开始，sum = sum<<1 + (currentBinary%3)即可
int[] sumArr = new int[32];
int currentNum;
for(int i = 0; i < nums.length; i++ ) {
currentNum = nums[i];
for(int j = 31; j >=0; j--) {
sumArr[j] += currentNum & 1; // 获取最后一位，并添加到对应位数
currentNum = currentNum >>> 1; // 右移一位
}
}
int realNum = 0;
// 恢复十进制
for(int i = 0; i <32 ; i++ ) {
realNum = realNum << 1;
realNum += sumArr[i]%3; // 结果只可能是1或者0
}
return realNum;三、有限状态机
在第二种方法我们知道，各个数二进制位的和%3即可得到所求数的当前位数。
每个位1出现的次数为0、1、2，当出现次数为3次时，变为0，循环后，为1的二进制位一定是要求的数的每一位（因为每一位3次重复就为0），如何实现呢。
因为每个二进制位有三种状态，重复0、1、2次，可以使用00,01,10记录三种状态，高位为1表示重复两次，低位为1表示重复一次，重复三次变为00，令a为高位，b为低位，c为当前要测试的数组中的数。
数字逻辑电路学的逻辑函数化简。
~为取反
newA = a~b~c + ~abc
newB = ~ab~c + ~a~bc = ~a(b~c + ~bc) = ~a(b^c) 其中b~c + ~bc为异或
循环后得到的newB即为所求结果（因为低位b为只重复一次的数）
代码
class Solution {
public int singleNumber(int[] nums) {
// 3.状态机 0 1 2
int a = 0, b = 0, preA;
for(int num : nums) {
preA = a;
a = (a & ~b & ~num) | (~a & b & num);
b = ~preA & ( b ^ num );
}
return b;
}
}3、链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5./**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/第一种
存入LinkedList，根据size直接get取即可
LinkedList<ListNode> list = new LinkedList<>();
ListNode currentNode = head;
while(currentNode != null) { // 当前节点不为空
list.add(currentNode); // 将当前的node添加进list
currentNode = currentNode.next; // 跳到下一个节点
}
return list.get(list.size() - k); // 获取倒数第k个第二种
直接计算长度，再遍历到所求节点。
int length = 0;
ListNode currentNode;
currentNode = head;
while(currentNode != null) {
length++;
currentNode = currentNode.next;
}
currentNode = head;
// System.out.print(currentNode);
for(int i = 0; i < length -k; i++) {
currentNode = currentNode.next;
}
return currentNode;第三种
双指针，两指针相差k-1个；
ListNode demandNode = head;
ListNode currentNode = head;
int countStep = 0;
// 开始遍历节点
while(currentNode != null) {
countStep++;
if(countStep == k) { // k=1，不相差
demandNode = head;
}
currentNode = currentNode.next; // 跳到下一个
if(countStep > k) {
demandNode = demandNode.next; // 目标指针跳下一个
}
}
return demandNode;
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode demandNode = head;
ListNode currentNode = head;
int countStep = 1;
// 将当前指针摆到对应位置
while(countStep != k) { // k倒数第一个，指针应该同位
currentNode = currentNode.next;
countStep++;
}
// 两指针同进退
while(currentNode.next != null) {
currentNode = currentNode.next;
demandNode = demandNode.next;
}
return demandNode;
}
}4、二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7返回它的最大深度 3 。
dfs：深度优先遍历
bfs：层序优先遍历
树的深度，为根节点的左子树深度 与 右子树深度 最大值 +1，递归结束为，节点为空。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/DFS
后序遍历
class Solution {
public int maxDepth(TreeNode root) {
return root == null? 0: Math.max( maxDepth(root.left), maxDepth(root.right) ) +1;
}
}BFS
层序优先遍历，一层一层的存入Queue中，根据queue.size获取当前层的节点。
- Queue
- poll 删除首部
- offer 添加到尾部
注意queue.size会实时变化。
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>(); // 队列
if(root != null) {
queue.offer(root); // 添加第一个
}
int depth = 0;
TreeNode currentNode = null;
while(queue.size() != 0) {
int size = queue.size();
for(int i = 0; i < size; i++) { // 有坑！！！
currentNode = queue.poll(); // 弹出该节点
if(currentNode.left != null) {
queue.offer(currentNode.left);
}
if(currentNode.right != null) {
queue.offer(currentNode.right);
}
}
depth++;
}
return depth;
}5、二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4思路
- 将树dfs遍历存入list，
Collections.sort( list )从大到小进行排序，直接获取。
public void getNum(TreeNode treeNode) {
if(treeNode == null ) {
return;
}
// 右
if(treeNode.right != null) {
getNum(treeNode.right);
}
// 中
list.add(treeNode.val);
// 左
if(treeNode.left != null) {
getNum(treeNode.left);
}- 该树是二叉搜索树，通过中序遍历可以按规律排序，使用右、中、左即为从大到小排序，通过全局k–计算已经获取的节点，当等于0时即为要找的节点。
public void getNum(TreeNode treeNode) {
if(treeNode == null || k == 0) {
return;
}
// 右
if(treeNode.right != null) {
getNum(treeNode.right);
}
// 中
k--;
if(k == 0) {
needNum = treeNode.val;
}
// 左
if(treeNode.left != null) {
getNum(treeNode.left);
}
}6、两个栈组成队列
Stack stack = new Stack();
思路： 栈的内容存入另一个栈，取出则是最先的一个。
所以，存入时，只需存入第一个栈即可
取出时，需要遍历栈1存入栈2，栈2pop即可得到最先的一个，再重新存入栈1
注意点：在pop前需要确保size != 0
7、和为s的连续正数序列
双重循环
一重：1~target
二重：加起来能==target，则存入List中
遍历List存入数组
简单优化
List<int[]>
双重循环
一重：1~target/2
二重：加起来能 == target，则从 x ~ y 存入int中
Arrays.toArray(new int[list.size()][]);
8、二叉树的最近公共祖先
看不懂
思路：
使用中序遍历，（判空结束）push 中左右 pop，查找出指定节点的路径，缺点是需要用全局变量控制递归的结束
使用for倒叙遍历找出先相同的节点就停止双重循环
实际上只需要从下标0开始，下标一致，找到最后一个不同即可（因为路径是有一段是一样的）。
搜索二叉树
不能用static变量？为啥
简单的左右子树找到路径即可，递归 or for
9、从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
思路：
使用广度优先遍历，使用队列1来保存当前的层级，队列2来保存下一层的层级，使用boolean来控制目前遍历哪个层级，当当前队列为空则需要替换并且添加进入数组。
问题极大
实际上应该使用队列的长度来进行遍历保存！
10、数组中出现次数超过一半的数字
每一个存入map，超过一半的长度就返回。
排序后中间的那个
摩尔投票，多个候选人id在数组中，遍历
- 第一个人，写在黑板上，票数为1
- 第二个人，同一个人，票数+1，不同人，票数-1
11、数组中重复的数字
- 直接使用hashmap
- 使用hashset
- 一个萝卜一个坑，进行原地置换，
12、和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^6
不能两个for
- 遍历中，使用二分法查找是否存在另一个补值，但是需要注意4=2+2的情况，如果有两个一样的，二分法只能查找出一个，
Arrays.binarySearch(arr, destination)查找不到将返回负数 - 使用HashMap更方便
- 使用双指针，分别在数组两端，和比taget大则lastIndex–，小则firstIndex++;
13、圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
1 <= n <= 10^51 <= m <= 10^6
使用list、删除指定下标的数据（指针会指向下一个数据，移动数量为 （ nowIndex + 报数限制 - 1 ） % size ），直到还有最后一个，用linklist会超时，因为查找十分需要时间
正确的不会
14、调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
- 直接判断奇偶存到两个list，合并后，使用==list.stream().mapToInt(Integer.intValue).toArray()==;应该学一下流的操作
15、最长回文子串
https://leetcode-cn.com/problems/longest-palindromic-substring/
给你一个字符串 s，找到 s 中最长的回文子串。
暴力破解法
双重for使用substring进行爆破
中心扩展法
每一个字母当做中间，分成odd、even两种
编码时间很长的原因：没想清楚每个变量的用途，没想清楚怎么解题就编码
动态规划
a[i][j]是回文串：
- 字符串头尾相等
- AND 依赖于
a[i+1][j-1]是回文串（去头和去尾） OR 子串区间长度 j -i >= 3（长度小于2，只需保证头尾相等即可）
- AND 依赖于
16、二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，判断数组中是否含有该整数
一、每行看头尾，是否在数字两侧，在则二分
二、从右上顶点开始，太大则向左，太小则向右
17、二叉搜索树的后序遍历序列
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
根据后序遍历的特点
- 最后一个肯定是根节点
- 根据大小划分左右子数，小的都在左边
- 遍历其他的（划为右子树），必须比根节点大
注意判空，数组边界
优化
二叉搜索树的特点
左子树节点的值 < 根节点的值
右子树的值 > 根节点的值
public boolean verifyPostorder(int[] postorder) {
return this.verifyPostorder(postorder, 0, postorder.length - 1);
}
private boolean verifyPostorder(int[] postorder, int start, int end) {
// 任意两个节点都能构成
if( end - start <= 1) {
return true;
}
int i = start;
int endVal = postorder[end];
// 左子树，倒数第二个
while( postorder[i] < endVal ) { // i < end && 等于的时候就是最后一个了，可以省略
i++;
}
int leftIndex = i;
// 右子树，倒数第二个
while( postorder[i] > endVal) {
i++;
}
if(i == end) {
return verifyPostorder(postorder, start, leftIndex - 1) && verifyPostorder(postorder, leftIndex, end - 1);
}
return false;
}18、包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.
一个栈用来正常操作，另一个辅助栈用来min操作
知识点：要知道new Stack<>()的操作，push、pop、peek
辅助栈只需要插入等于或小于其peek的，其他不会影响到min
只需要pop出相等的
private Stack<Integer> A,B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.push(x);
if(B.isEmpty() || B.peek() != null && B.peek() >= x) {
B.push(x);
}
}
public void pop() {
if(A.pop().equals(B.peek())) {
B.pop();
}
}