概述
LeetCode-剑指offer-全
1、03数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
/*
我的思路：
1、暴力解答，两层for循环，直接超时警告 n^2
2、使用额外的数组来模拟哈希/直接用HashSet 时间O(n)空间O(n)
3、*原地哈希（交换） 时间O(N) 空间O(1)
4、排序之后判断前后相等 时间O(NlogN) 空间O(1)
*/
//2、使用额外数组
// 用一个数组来计数
//已知在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
// public int findRepeatNumber(int[] nums) {
// int[] arr = new int[nums.length];
// for(int i = 0; i < nums.length; i++){
// arr[nums[i]]++;
// if(arr[nums[i]] > 1) return nums[i];
// }
// return -1;
// }
//哈希表 效率双低
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for (int num : nums) {
if (!set.add(num)) {
return num;
}
}
return -1;
}
/**
*3、原地哈希 时间n空间1
如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture
**/
public int findRepeatNumber(int[] nums){
for(int i = 0;i < nums.length;i++){
while(nums[i] != i){
if(nums[nums[i]] == nums[i]) return nums[i];
//交换
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
2、05替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：
0 <= s 的长度 <= 10000
/**
*1、遍历一遍，使用StringBuilder更快一些
**/
public String replaceSpace(String s){
StringBuilder sb = new StringBuilder();
for(int i = 0;i < s.length();i++){
if(s.charAt(i) == ' '){
sb.append("%20");
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
/**
*2、评论区说，原题的意思是不使用额外空间，在原地修改
先统计空格数量x,字符串后边+2x个空格
从后往前遍历修改，从原来的长度尾巴开始
**/
public String replaceSpace(String s) 但是字符串没法修改 还是得借助其他的空间？
// 3、无重复字符的最长子串 搞错了 不是剑指的
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//使用类似滑动窗口？的思想
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<>();
int max = 0;//不重复字符串的最大长度
int left = 0;//重新开始的字符串最左边起点
for(int i = 0;i < s.length();i++){
if(map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i)) + 1);//更新起点
}
map.put(s.charAt(i),i);
max = Math.max(max,i - left + 1);//更新最大长度
}
return max;
}
}
//优化，用数组模拟哈希表
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) return 0;
int[] last = new int[128];//记录字符最新出现的位置，每个坐标对应唯一字符
for(int i = 0;i < 128;i++){
last[i] = Integer.MIN_VALUE;//数组赋初值方便比较
}
int max = 0;//最大值
int left = 0;//滑动窗口/新计算字符串的最左端
for(int i = 0;i < s.length();i++){
int index = s.charAt(i);
left = Math.max(left,last[index] + 1);
max = Math.max(max,i - left + 1);
last[index] = i;
}
return max;
}
3、06从头到尾打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
//1、使用出栈入栈
public int[] reversePrint(ListNode head) {
if(head == null) return new int[0];
Stack<Integer> stack = new Stack<>();
//int len = 0;
while(head != null){
stack.push(head.val);
head = head.next;
//len++;
}
int len = stack.size();
int[] res = new int[len];
for(int i = 0;i < len;i++){
res[i] = stack.pop();
}
return res;
}
//2、遍历链表得知大小，反向赋值给数组，更快速
public int[] reversePrint(ListNode head) {
ListNode temp = head;
int size = 0;
while(temp != null){
size++;
temp = temp.next;
}
int[] res = new int[size];
temp = head;
for(int i = size-1;i>=0;i--){
res[i] = temp.val;
temp = temp.next;
}
return res;
}
4、07重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。设输入的前序遍历和中序遍历的结果中都不含重复的数字
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
/**
*学习建树的过程也是对两种遍历结果规律的复习，放在明天学习吧！
*前序遍历【根节点|左子树|右子树】
*中序遍历【左子树|根节点|右子树】
*--由此可以确定三个节点：1、树的根节点 2、左子树的根节点 3、右子树的根节点
考虑通过递归对所有的子树进行划分
递推的参数：根节点在前序遍历的索引root、子树在中序遍历的左边界left、子树在中序遍历的右边界right
终止条件：left > right return null;
如何递推：
1、建立根节点node = preorder[root];
2、划分左右子树，查找根节点在中序遍历的索引i
3、构建左右子树
左子树：根节点=前序遍历preoder[root+1]、中序遍历的左边界left、右边界i-1
右子树：根节点=前序遍历preoder[i-left+root+1](左根索引+长度)、中序遍历的左边界i+1、右边界right
**/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int[] preorder;
private Map<Integer,Integer> dic = new HashMap<>();//用作搜索前序中的根节点在中序中的位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;//减少recur函数的参数数量
for(int i = 0;i < inorder.length;i++) dic.put(inorder[i],i);
return recur(0,0,inorder.length - 1);
}
private TreeNode recur(int root,int left,int right){
if(left > right) return null;
TreeNode node = new TreeNode(preorder[root]);
int i = dic.get(preorder[root]);//在中序遍历中的索引位置
node.left = recur(root + 1,left,i - 1);
node.right = recur(root + 1 + i - left,i + 1,right);
return node;
}
}
5、09用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
/**
*尾部插入和头部删除，就是FIFO
*已知单个栈的规则是FILO，即先进后厨
我们可以用两个栈来模拟队列.新加入的元素放在栈底
如何放在栈底？先出栈保存在另一个栈，加入元素后再倒回去
使用一个全局变量来监测该模拟队列的长度
**/
class CQueue {
int size;//全放到成员变量上
Stack<Integer> stack1;
Stack<Integer> stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
stack1.push(value);//加入栈底
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
size++;
}
public int deleteHead() {
if(size == 0) return -1;
size--;
return stack1.pop();
}
}
/**
*Stack继承了Vector接口，Vector接口的底层是一个Object[]数组，考虑空间扩容和移位，速度较慢
*用LinkedList做Stack的容器，因为LinkedList继承了Deque接口，双向链表扩容消耗少
* Stack已经被官方遗弃，不被推荐使用
**/
class CQueue {
LinkedList<Integer> A, B;
public CQueue() {
A = new LinkedList<Integer>();
B = new LinkedList<Integer>();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast();
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
}
6、10-1斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
--答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1
输入：n = 2
输出：1
/**
*标准的动态规划问题（用标准解法解析一下流程
1、先定义状态：dp[i]表示斐波那契数列的第i个数字 (输入n，输出dp[n])
2、建立状态转移方程：dp[i] = dp[i - 1] + dp[i -2] (对应已经给出的公式)
3、初始状态：已知dp[0]=0,dp[1]=1;
4、返回值：return dp[n]
这里只涉及到三个变量，因此不用数组而是只定义三个整形变量来储存三个数据
**/
public int fib(int n){
if(n == 0) return 0;
if(n == 1) return 1;
int res = 0;
int fib1 = 0,fib2 = 1;//保存两个中间值
for(int i = 2;i <= n;i++){
res = (fib1 + fib2) % 1000000007;
fib1 = fib2 % 1000000007;
fib2 = res % 1000000007;
}
return res % 1000000007;
}
//边算边取模和最后再取模结果一样
//证明： 要证（a+b）%c = （a%c+b%c）%c 即证a+b与a%c+b%c对c同余 则有c能整除(a+b-a%c-b%c) 设a=mc+p b=nc+q 则(a+b-a%c-b%c)=(m+n)c+p+q-p-q=(m+n)c 则证a+b与a%c+b%c对c同余，证毕
7、10-2青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
/**
*斐波那契问题
设跳上n级台阶有f(n)种跳法，最后一步只有两种情况：跳上1级台阶/跳上2级台阶
此时：1、跳上1级台阶：还剩下n-1个台阶。f(n-1)
2、跳上2级台阶:还剩下n-2个台阶。f(n-2)
f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)
和上一道题一样，只是初始化条件发生了变化
**/
public int numWays(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
int first = 1;
int second = 1;
int res = 0;
for(int i=2;i<=n;i++){
res = (first + second) % 1000000007;
first = second % 1000000007;
second = res % 1000000007;
}
return res;
}
8、11旋转数组种的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
/**
*使用遍历一遍的方法
**/
//100% 98%
class Solution {
public int minArray(int[] numbers){
int res = numbers[0];
for(int i = 1;i < numbers.length;i++){
if(numbers[i] >= numbers[i-1]) {
continue;
}else{
res = numbers[i];
break;
}
}
return res;
}
}
//简化后的代码为什么只有上边的一半排行
class Solution {
public int minArray(int[] numbers){
for(int i = 1;i < numbers.length;i++){
if(numbers[i] >= numbers[i-1]) {
continue;
}else{
return numbers[i];
}
}
return numbers[0];
}
}
//前边加个条件判断就快了 换汤不换药
/**
*题目真正考察的是二分查找 时间复杂度 O(log_2 N) 空间复杂度 O(1)
**/
public int minArray(int[] numbers){
if(numbers == null || numbers.length == 0) return -1;
int left = 0,right = numbers.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
//因为是排序后旋转数组，所以最小数字前边的任意值比后边的都大
//第一种情况是mid取在了后边的有序数组上，此时最小值在left和mid之间
if(numbers[mid] < numbers[right]){
right = mid;
}
//第二种情况mid取在第一段的有序数组，此时最小值在mid + 1和right之间
else if(numbers[mid] > numbers[right]){
left = mid + 1;
}
//mid取在了最后边，那么去个重？进行下一次判断
else{
right--;
}
}
return numbers[left];
}
9、12矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
/**
*深度优先搜索（暴力遍历矩阵中所有的字符串可能性，沿着一个方向搜到底再回溯到上个节点） + 剪枝解决（不匹配就立刻返回结果）
*递归参数：x,y代表当前元素在矩阵board中的位置，u代表在word中的位置
*终止条件：
返回false ： ① 行或列索引越界 或 ② 当前矩阵元素与目标字符不同 或 ③ 当前矩阵元素已访问过 （③ 可合并至 ② ）
返回true ： 字符串 word 已全部匹配，即 k = len(word) - 1 。
递推工作：
标记当前矩阵元素： 将 board[i][j] 值暂存于变量 tmp ，并修改为字符 '/' ，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需一条可行路径） ，并记录结果至 res 。
还原当前矩阵元素： 将 tmp 暂存值还原至 board[i][j] 元素
**/
class Solution {
public boolean exist(char[][] board, String word) {
//回溯法 dfs
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(dfs(board,word,0,i,j)){//这个位置不行就换下一个
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board,String word,int u,int x,int y){
//边界判断 先判断边界后比较 以免越界
if( x >= board.length || x<0 ||
y >= board[0].length || y < 0 ||board[x][y] != word.charAt(u)){
return false;
}
//递归到最后一个且最后一个符合
if(u == word.length() -1) return true;
char temp = board[x][y];
board[x][y] = '*';
//递归遍历,上下左右
boolean res = dfs(board,word,u+1,x-1,y) || dfs(board,word,u+1,x+1,y) ||
dfs(board,word,u+1,x,y-1) || dfs(board,word,u+1,x,y+1);
//恢复，如果有下一次位置判断，避免受影响
board[x][y] = temp;
return res;
}
}
10、13机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。
请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
1 <= n,m <= 100 0 <= k <= 20
/**
*经典的回溯法
回溯dfs：1、条件判断 2、标记已经访问过的 3、根据需求出公式 4、根据需求还原
**/
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];//对已经经过的做一下标记
return dfs(0,0,m,n,k,visited);
}
private int dfs(int i,int j,int m, int n, int k,boolean[][] visited){
if(i < 0 || i >= m || j < 0 || j >= n || (i/10 + i%10 + j/10 + j%10) > k || visited[i][j])
return 0;//已经访问过的也返回0
visited[i][j] = true;
return dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited) +
dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + 1;
}
}
11、14-I剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
/**
*打眼一看是一道典型的动态规划
*但其实是一道数论题：任何大于1的数都可能由2和3构成，3越多得到的积越大
**/
public int cuttingRope(int n) {
if(n<=3) return n-1;
int[] dp = new int[n+1];
dp[2] = 2; dp[3] = 3;//很特殊
for(int i = 4; i <= n; i++){
dp[i] = 2 * dp[i-2] > 3 * dp[i-3] ? 2 * dp[i-2] : 3 * dp[i-3];
}
return dp[n];
}
/**
*复习一下动态规划怎么做
*1、dp数组的含义：dp[i]代表将i拆分至少两个正整数和后的最大乘积
*2、边界条件：dp[0]=dp[1]=1=dp[2]=2
*3、状态转移方程：dp[i] = max(dp[i],max((i-j)*j,j*dp[i-j]))
**/
public int cuttingRope(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i]= Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
12、14-II剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
/**
*要取模，涉及到比较，所有不能用动态规划了
*使用大数避免越界
**/
public int cuttingRope(int n) {
if(n < 4) return n - 1;
long res = 1;
while(n > 4){
res *= 3;
res %= 1000000007;
n -= 3;
}
return (int)(res * n % 1000000007);
}
13、14二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
/**
*比较一位，计数一次，移动一位
*11111111 & 1 = 1(前边补0)
*无符号右移>>> 带符号右移>>
**/
public int hammingWeight(int n) {
int count = 0;
while(n != 0){
count += (n & 1);
n >>>= 1;
}
return count;
}
14、16数值的整数次方
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
/**
*最常规的方法是 x*x*x... 时间复杂度O（n）超出要求
*快速幂：时间复杂度 O(log2 n)
**/、
public double myPow(double x, int n) {
//快速幂 时间复杂度讲到log2(n)
//把n用二进制表示
if(x == 0) return 0;
//n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 转正可能最后一位越界
long b = n;
double res = 1.0;
if(b < 0){//负数的转换逻辑
b = -b;
x = 1 / x;
}
while(b > 0){
if((b & 1) == 1) res *= x;
x *= x;//每次自×一次
b >>= 1;//右移一位
}
return res;
}
15、17打印从一到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
/**
*创建一个10^n-1大小的数组遍历写值就可以了
**/
public int[] printNumbers(int n) {
int[] res = new int[(int)Math.pow(10,n) - 1];
for(int i = 0;i < Math.pow(10,n) - 1;i++){
res[i] = i + 1;
}
return res;
}
//以上方法仅击败了15% 30%的用户，需要改进
//看评论得知本题原书考查的是大数问题
16、18删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
/**
*思路很简单：1、输入的初始条件判断一下 2、之后快慢指针找到有没有那个节点 3、找到了就删除
**/
public ListNode deleteNode(ListNode head, int val) {
if(head == null) return null;
if(head.val == val) return head.next;
//找到那个节点和它的前一个节点
ListNode pre = head;
ListNode cur = head.next;
while(cur != null && cur.val != val){
pre = pre.next;
cur = cur.next;
}
//如果没找到那cur就到了最后一个节点->null，找到了就非空
if(cur != null){
pre.next = cur.next;
}
return head;
}
17、19正则表达式匹配
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
/**
*动态规划
1、定义二维数组dp[i][j]:表示的是p的前j个字符和s的前i个字符匹配的结果
2、初始边界条件：dp[0][0] = true;
for (int i = 0; i < n; i++) {
//如果p的第i+1个字符也就是p.charAt(i)是"*"的话，
//那么他就可以把p的第i个字符给消掉（也就是匹配0次）。
//我们只需要判断p的第i-1个字符和s的前0个字符是否匹
//配即可。比如p是"a*b*"，如果要判断p的第4个字符
//"*"和s的前0个字符是否匹配，因为字符"*"可以消去
//前面的任意字符，只需要判断p的"a*"和s的前0个字符是否匹配即可
if (p.charAt(i) == '*' && dp[0][i - 1]) {
dp[0][i + 1] = true;
}
}
3、状态转移方程
-如果p的第j+1个字符和s的第i+1个字符相同，或者p的第j+1个字符是“.”（"."可以匹配任意字符），我们只需要判断p的前j个字符和s的前i个字符是否匹配
- 如果p的第j+1个字符和s的第i+1个字符不能匹配，并且p的第j+1个字符是"*"，那么就要分两种情况
- -（1）p的第j个字符和s的第i+1个字符不能匹配，
比如：s="abc"，p="abcd*"
我们就让p的第j个和第j+1个字符同时消失，也就是让"d*"消失，只需要判断p的前j-1个字符和s的前i+1个字符是否匹配即可。
--（2）p的第j个字符和s的第i+1个字符匹配成功，有3种情况
----类似于s="abc"，p="abcc*"; 我们就让*匹配0个，把p的"c*"砍掉，判断s="abc"和p="abc"是否匹配
dp[i+1][j+1] = dp[i+1][j-1]
----类似于s="abc"，p="abc*"; 我们就让*匹配1个，把p的字符"*"砍掉，判断s="abc"和p="abc"是否匹配
dp[i+1][j+1] = dp[i+1][j]
----类似于s="abcc"(或者s="abccc"，s="abcccc"……)，p="abc*"; 我们就让*匹配多个，把s的最后一个字符"c"砍掉，判断s="abc"(或者s="abcc"，s="abccc"……)和p="abc*"是否匹配
dp[i+1][j+1] = dp[i][j+1]
**/
public boolean isMatch(String s, String p) {
if (s == null || p == null)
return false;
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i < n; i++) {
if (p.charAt(i) == '*' && dp[0][i - 1]) {
dp[0][i + 1] = true;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.') {
dp[i + 1][j + 1] = dp[i][j];
} else if (p.charAt(j) == '*') {
//递归公式
if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.') {
dp[i + 1][j + 1] = dp[i][j + 1];
}
dp[i + 1][j + 1] |= dp[i + 1][j - 1];
}
}
}
return dp[m][n];
}
//效率不行
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] f = new boolean[n + 1][m + 1];//状态转移方程
for(int i = 0;i <= n;i++){
for(int j = 0;j <= m;j++){
if(j == 0){//第一种情况
f[i][j] = (i == 0);
}else{//第二种大情况
if(p.charAt(j-1) != '*'){//不的*
if(i>0 && ((s.charAt(i-1) == p.charAt(j-1))||(p.charAt(j-1) == '.'))){
f[i][j] = f[i - 1][j - 1];
}
}else{//是*
if(j >= 2){//最后两位直接不要了
f[i][j] |= f[i][j - 2];
}
if(i>=1 && j>=2 && (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.')){
//考虑c*替换大于一个的c
f[i][j] |= f[i-1][j];
}
}
}
}
}
return f[n][m];
}
18、20表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
/**
.不能在e和.前边
e之前不能有e
e之前必须有数字 e之后也要有数字
+-不能在第一个位置 或者e后边第一个位置
设置三个标志位，来代表前一个元素的状态，else if一次只能设置一个
**/
class Solution {
public boolean isNumber(String s) {
if (s == null || s.length() == 0) return false;
//去掉首位空格
s = s.trim();
boolean numFlag = false;
boolean dotFlag = false;
boolean eFlag = false;
for (int i = 0; i < s.length(); i++) {
//判定为数字，则标记numFlag
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
numFlag = true;
//判定为. 需要没出现过.并且没出现过e
} else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
dotFlag = true;
//判定为e，需要没出现过e，并且出过数字了
} else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
eFlag = true;
numFlag = false;//为了避免123e这种请求，出现e之后就标志为false
//判定为+-符号，只能出现在第一位或者紧接e后面
} else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 ||
s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {
//其他情况，都是非法的
} else {
return false;
}
}
return numFlag;//必须以数字结尾
}
}
19、21调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
/**
*使用双指针，left旨在左边的奇数，right旨在右边的偶数，交换
**/
class Solution {
public int[] exchange(int[] nums) {//左边奇数 右边偶数
int left = 0,right = nums.length - 1;
while(left < right){
while(nums[left] % 2 == 1 && left < right) left++;
while(nums[right] % 2 == 0 && left < right) right--;
if(left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
}
20、链表中倒数第K个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
/**
*不假思索、快慢指针
**/
public ListNode getKthFromEnd(ListNode head, int k) {//快慢指针
ListNode root1 = head;//快指针
ListNode root2 = head;//慢指针
while(/*root1 != null &&*/ k>0){//快指针先走k步
root1 = root1.next;
k--;
}
while(root1 != null/* && root2 != null*/){
root1 = root1.next;
root2 = root2.next;
}
return root2;//返回慢指针
}
21、24反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/**两种方法
*1、迭代法
*2、递归法
**/100% 88%
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
return head;
//用迭代法
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while(cur != null){
//每次迭代到cur，将cur的next指向pre，之后pre和cur前进一位
temp = cur.next;//保存本来的下一个节点，下一次用
cur.next = pre;
//pre和cur往后移
pre = cur;
cur = temp;
}
return pre;
}
//递归 100 60
public ListNode reverseList(ListNode head){
if(head == null || head.next == null) return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
22、25合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
/**
*设置两个指针挨个比较
*设置一个新头节点
**/
//迭代法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode root1 = l1,root2 = l2;
ListNode newhead = new ListNode(0);
ListNode root = newhead;
while(root1 != null && root2 != null){
if(root1.val < root2.val){
root.next = root1;
root1 = root1.next;
}else{
root.next = root2;
root2 = root2.next;
}
root = root.next;
}
if(root1 != null){
root.next = root1;
}
if(root2 != null){
root.next = root2;
}
return newhead.next;
}
//还可以继续优化，不用设这么多的临时节点 99 98
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode pre = dummyHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
pre.next = l1;
pre = pre.next;
l1 = l1.next;
}else{
pre.next = l2;
pre = pre.next;
l2 = l2.next;
}
}
if(l1 != null) pre.next = l1;
if(l2 != null) pre.next = l2;
return dummyHead.next;
}
}
//递归 98 80 太妙了
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//终止判断条件
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
23、26树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/
4 5
/
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
/**
*若B是A的子结构，则子结构的根节点可能是A的任意一个节点
1、先序遍历A的每个节点NodeA isSubStructure(A,B)
2、判断A中以NodeA做根节点的子树是否包含树B recur(A,B)
**/
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null) return false;
//A中匹配，失败就往左节点，再失败就右节点
return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean recur(TreeNode A,TreeNode B){
if(B == null) return true;//B空则匹配,考虑是先序遍历，此时B已经遍历完了
if(A == null) return false;//A空则匹配失败，此时A不空，B空则无法匹配
return A.val == B.val && recur(A.left,B.left) && recur(A.right,B.right);//A与B的值不一样则失败
}
}
24、二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/
2 7
/ /
1 3 6 9
镜像输出：
4
/
7 2
/ /
9 6 3 1
/**
*两种方法
1、递归
2、使用栈
**/
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return root;
TreeNode temp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(temp);
return root;
}
public TreeNode mirrorTree(TreeNode root) {//时间感人
if(root == null) return root;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();//左边先进，自然右边先出了
if(node.left != null) stack.push(node.left);
if(node.right != null) stack.push(node.right);
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
return root;
}
25、28对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
3 3
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return dfs(root.left,root.right);
}
private boolean dfs(TreeNode A,TreeNode B){
if(A == null && B == null) return true;//都空
if(A == null || B == null) return false;//一个空，一个非空
return (A.val == B.val) && dfs(A.left,B.right) && dfs(A.right,B.left);
}
}
25、29顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
/**
*设置上下左右四个指针 h,b,l,r
*数组下标x，巧妙利用++自增前后两种方式节省代码量
**/
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0) return new int[0];
int[] res = new int[matrix.length * matrix[0].length];
int x = 0,l = 0,r = matrix[0].length - 1,h = 0,b = matrix.length - 1;
while(true){//加其他判断也可以但是耗费资源
for(int i = l;i <= r;i++) res[x++] = matrix[h][i];//向右
if(++h > b) break;//下一层并判断
for(int i = h;i <= b;i++) res[x++] = matrix[i][r];//向下
if(--r < l) break;//左一层并判断
for(int i = r;i >= l;i--) res[x++] = matrix[b][i];//向左
if(--b < h) break;//想上一层并判断
for(int i = b;i >= h;i--) res[x++] = matrix[i][l];
if(++l > r) break;//向右一层并判断 开始下一圈
}
return res;
}
}
//写个逆时针玩玩
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0) return new int[0];
int[] res = new int[matrix.length * matrix[0].length];
int x = 0,l = 0,r = matrix[0].length - 1,h = 0,b = matrix.length - 1;
while(true){//加其他判断也可以但是耗费资源
for(int i = h;i <= b;i++) res[x++] = matrix[i][l];
if(++l > r) break;
for(int i = l;i <= r;i++) res[x++] = matrix[b][i];
if(--b < h) break;
for(int i = b;i >= h;i--) res[x++] = matrix[i][r];
if(--r < l) break;
for(int i = r;i >= l;i--) res[x++] = matrix[h][i];
if(++h > b) break;
}
return res;
}
}
26、30包含min函数的最小栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
//Java 代码中，由于 Stack 中存储的是 int 的包装类Integer ，因此需要使用equals() 代替 == 来比较值是否相等。
//此题如果用==将会无法通过 Integer的equals重写过，比较的是内部value的值， ==如果在[-128,127]会被cache缓存,超过这个范围 //则比较的是对象是否相同·
class MinStack {
Stack<Integer> A, B;//B是辅助栈，栈顶是最小值
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.add(x);
if(B.empty() || B.peek() >= x)
B.add(x);
}
public void pop() {
if(A.pop().equals(B.peek()))//用==为什么不行
B.pop();
}
public int top() {
return A.peek();
}
public int min() {
return B.peek();
}
}
27、31栈的压入弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
/**
*提醒：Java中和栈有关的操作建议都用Deque，避免使用Stack
*1、借助辅助栈，已知数组元素不充分，当栈顶元素等于数组的头一个元素的时候就出栈
**/
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
//借助辅助栈 模拟压入弹出 看是否成功
Deque<Integer> stack = new ArrayDeque<>();
//将pushed依次入栈，如和popped头元素相等则出栈
int index = 0;//数组pop的下标位置
for(int p : pushed){
stack.push(p);
while(!stack.isEmpty() && stack.peek().equals(popped[index])){
stack.pop();
index++;
}
}
return stack.isEmpty();
}
}
28、32-I从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回：[3,9,20,15,7]
//层序遍历DFS 利用队列先进先出特性来做
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
Queue<TreeNode> queue = new LinkedList<>();//队列先进先出
List<Integer> list = new ArrayList<>();//保存结果
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
}
int[] res = new int[list.size()];
for(int i = 0;i < list.size();i++){
res[i] = list.get(i);
}
return res;
}
}
29、32-II 从上到下打印二叉树II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
//每次先确定上一次遍历的数组规模，下一次保存上一层的数组
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();//返回结果
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();//初始化队列
queue.add(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
for(int i = queue.size();i > 0;i--){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
res.add(list);
}
return res;
}
}
//用递归的方法
//时间100%
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
recur(root,0);
return res;
}
private void recur(TreeNode root,int k){
if(root != null){
if(res.size() <= k) res.add(new ArrayList<Integer>());
res.get(k).add(root.val);
recur(root.left,k + 1);
recur(root.right,k + 1);
}
}
}
30、32-III 从上到下打印二叉树III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
//和上题一样，只是每一次判断一下，加一个反转即可
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//先写出正常的从左到右顺序
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()){
LinkedList<Integer> temp = new LinkedList<>();
for(int i = queue.size();i > 0;i--){
TreeNode newNode = queue.poll();
//加一个反转功能 addFirst addLast(LiList的方法)
//temp.add(newNode.val);
if(res.size()%2 != 0) temp.addFirst(newNode.val);
else temp.addLast(newNode.val);//尾插
if(newNode.left != null) queue.add(newNode.left);
if(newNode.right != null) queue.add(newNode.right);
}
res.add(temp);
}
return res;
}
}
31、33二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/
2 6
/
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
/**
*看到题目要验证二叉搜索树的后续遍历序列，那就要知道二叉搜索树的性质：根节点>左子树all 根节点<右子树all
*遍历后的结果【左子树、右子树、根节点】
*之后再判断左子树和右子树满足不满足二叉搜索树的后续遍历序列
* 看到这里就想到递归解决 dfs(postorder,0,postorder.length - 1)
*条件判断 找分解处
*return 看看指针能不能遍历到最后边 && dfs(左子树) && dfs(右子树)
*/
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder == null || postorder.length < 2) return true;
return dfs(postorder,0,postorder.length - 1);
}
private boolean dfs(int[] postorder,int i,int j){
if(i >= j) return true;//越界就停止
int index = i;//遍历用
while(postorder[index] < postorder[j]) index++;
int le = i;//左子树的根节点是le - 1 /右子树遍历开始处
while(postorder[index] > postorder[j]) index++;
return index == j && dfs(postorder,i,le - 1) && dfs(postorder,le,j - 1);
}
}
//插入知识点 ：如果是中序遍历的结果，则一定是有序的
//还有一种方法是使用栈解决
/**
很容易想到使用栈来解决。遍历数组的所有元素，如果栈为空，就把当前元素压栈。如果栈不为空，并且当前元素大于栈顶元素，说明是升序的，那么就说明当前元素是栈顶元素的右子节点，就把当前元素压栈，如果一直升序，就一直压栈。当前元素小于栈顶元素，说明是倒序的，说明当前元素是某个节点的左子节点，我们目的是要找到这个左子节点的父节点，就让栈顶元素出栈，直到栈为空或者栈顶元素小于当前值为止，其中最后一个出栈的就是当前元素的父节点。
**/
public boolean verifyPostorder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int parent = Integer.MAX_VALUE;
//注意for循环是倒叙遍历的
for (int i = postorder.length - 1; i >= 0; i--) {
int cur = postorder[i];
//当如果前节点小于栈顶元素，说明栈顶元素和当前值构成了倒叙，
//说明当前节点是前面某个节点的左子节点，我们要找到他的父节点
while (!stack.isEmpty() && stack.peek() > cur)
parent = stack.pop();
//只要遇到了某一个左子节点，才会执行上面的代码，才会更
//新parent的值，否则parent就是一个非常大的值，也就
//是说如果一直没有遇到左子节点，那么右子节点可以非常大
if (cur > parent)
return false;
//入栈
stack.add(cur);
}
return true;
}
32、34二叉树和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
/**
*经典回溯
pathSum(root, sum) 函数：
初始化： 结果列表 res ，路径列表 path 。
返回值： 返回 res 即可。
recur(root, tar) 函数：
递推参数： 当前节点 root ，当前目标值 tar 。
终止条件： 若节点 root 为空，则直接返回。
递推工作：
路径更新： 将当前节点值 root.val 加入路径 path ；
目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 00 ）；
路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。
先序遍历： 递归左 / 右子节点。
路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。
**/
class Solution {
List<List<Integer>> res = new LinkedList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root,sum);
return res;
}
public void recur(TreeNode root,int sum){
//停止条件
if(root == null) return;
path.add(root.val);
sum -= root.val;
if(sum == 0 && root.left == null && root.right == null){
res.add(new LinkedList(path));//复制一个新的，后续path也不会影响res
}
recur(root.left,sum);
recur(root.right,sum);
path.remove(path.size() - 1);//剪枝
}
}
33、35复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]、
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
// Definition for a Node.
// class Node {
// int val;
// Node next;
// Node random;
// public Node(int val) {
// this.val = val;
// this.next = null;
// this.random = null;
// }
// }
/**
*复制（意思是Deep Copy）一个链表并返回
*浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。
1、哈希表，时间空间O（n）
2、原地修改，空间将为O（1）
**/
class Solution {//1
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
//map中存的是(原节点，拷贝节点)的一个映射
Map<Node, Node> map = new HashMap<>();
for (Node cur = head; cur != null; cur = cur.next) {
map.put(cur, new Node(cur.val));
}
//将拷贝的新的节点组织成一个链表
for (Node cur = head; cur != null; cur = cur.next) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
}
return map.get(head);
}
}
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
// 1. 复制各节点，并构建拼接链表 例如1->2->3这样的链表就变成了这样1->1'->2->2'->3->3'
while(cur != null) {
Node tmp = new Node(cur.val);//在内存上new一个新的拷贝节点
tmp.next = cur.next;
cur.next = tmp;
cur = tmp.next;
}
// 2. 构建各新节点的 random 指向
cur = head;
while(cur != null) {
if(cur.random != null)
cur.next.random = cur.random.next;
cur = cur.next.next;
}
// 3. 拆分两链表 分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
cur = head.next;
Node pre = head, res = cur;
while(cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null; // 单独处理原链表尾节点
return res; // 返回新链表头节点
}
}
34、36二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/ 有图解
/**
*中序遍历 递归实现
**/
class Solution {
Node pre;
Node head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);//形成双向链表
head.left = pre;//头尾相连
pre.right = head;//头尾相连
return head;//返回头节点
}
private void dfs(Node cur){
if(cur == null) return;
dfs(cur.left);
//pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,
//当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
if(pre != null) pre.right = cur;
//反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
else head = cur;//“head” 表示指向链表中有最小元素的节点，保存这个头节点
cur.left = pre;//cur当前节点 上一个节点pre
pre = cur;//递归一层，cur交给递归参数来变化
dfs(cur.right);
}
}
/*
1、中序排序是递增序列
2、形成双向链表
3、头尾循环
*/
35、37序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/
2 3
/
4 5
序列化为 "[1,2,3,null,null,4,5]
/**
*层序遍历BFS
：通常的前中后序遍历记录的二叉树不完整，反序列化可能有多种可能性
1、序列化Serialize N N
特例判断：if(root == null) return []
初始化：队列queue,列表res
BFS： 节点出列
node != null +node.val add node.left node.right
node == null +null
**/
public String serialize(TreeNode root) {
if(root == null) return "[]";
StringBuilder sb = new StringBuilder();
sb.append("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp != null){
sb.append(temp.val + ",");
queue.add(temp.left);
queue.add(temp.right);
}else{
sb.append("null,");
}
}
sb.deleteCharAt(sb.length() - 1);//删去最后边的“,”
sb.append("]");
return sb.toString();
}
/**
*二、如何恢复/反序列化？利用队列按层构建二叉树，借助一个指针 i 指向节点 node 的左、右子节点，每构建一个 node 的左、右子节点，指针 i 就向右移动 1 位。
1、特例处理：data为空则return null
2、初始化：列表vals,指针i = 0;根节点root(vals[0])，队列queue
3、按层构建二叉树
节点出队，记为 node ；
构建 node 的左子节点：node.left 的值为 vals[i] ，并将 node.left 入队；
执行 i += 1 ；
构建 node 的右子节点：node.left 的值为 vals[i] ，并将 node.left 入队；
执行 i += 1 ；
4、返回root
**/
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] vals = data.substring(1,data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
int i = 1;//从第二个开始
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(!vals[i].equals("null")){
temp.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(temp.left);
}
i++;//null直接跳过去，不入列
if(!vals[i].equals("null")){
temp.right = new TreeNode(Integer.parseInt(vals[i]));
queue.add(temp.right);
}
i++;
}
return root;
}
36、38字符串的排序
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
/**
*标准的回溯模板题，需要考虑三个问题 == 决策树的遍历过程
1、路径：已经做出的选择
2、选择列表：当前可以做的选择
3、结束条件：到达决策树的底层，无法再做出选择的条件
**/
res = [];
void backtrack(路径,选择列表){
if(满足结束条件) {
res.add(路径)
return;
}
for(选择 ： 选择列表){
做选择
backtrack(路径,选择列表);
撤销选择；
}
class Solution {
List<String> res = new ArrayList<>();
public String[] permutation(String s) {
StringBuilder path = new StringBuilder();
char[] chars = s.toCharArray();
Arrays.sort(chars);
boolean[] visited = new boolean[chars.length];
dfs(path,chars,visited);
return res.toArray(new String[res.size()]);
}
private void dfs(StringBuilder path,char[] chars,boolean[] visited){
if(path.length() == chars.length){
res.add(path.toString());
return;
}
for(int i = 0;i < chars.length;i++){
if(visited[i]) continue;
if(i > 0 && chars[i] == chars[i - 1] && visited[i - 1]) continue;
path.append(chars[i]);
visited[i] = true;
dfs(path,chars,visited);
path.deleteCharAt(path.length() - 1);
visited[i] = false;
}
}
}
37、39数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
/**
1、排序法，出现超过一半的数字肯定在数组的中心处 复杂度O(nlgn)
2、摩尔投票法，对拼的过程，不一样的数字对拼消耗，剩下的肯定是人数过半的
**/
public int majorityElement(int[] nums) {
//排序法
Arrays.sort(nums);
return nums[nums.length / 2];
}
public int majorityElement(int[] nums) {
//初始化
int res = nums[0];
int count = 1;
for(int i = 1;i < nums.length;i++){
if(nums[i] != res){
count--;
if(count < 0){//
res = nums[i];
count = 1;
}
}else{
count++;
}
}
return res;
}
38、40最小的K个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
/**
1、快排，之后前k个数
2、大根堆（前K小） / 小根堆（前K大） 使用PriorityQueue
3、哈希数组，计数排序
**/
1、调用sort/自己写快排
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
int[] res = new int[k];
for(int i = 0;i < k;i++){
res[i] = arr[i];
}
return res;
}
///
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 最后一个参数表示我们要找的是下标为k-1的数
return quickSearch(arr, 0, arr.length - 1, k - 1);
}
private int[] quickSearch(int[] nums, int lo, int hi, int k) {
// 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
int j = partition(nums, lo, hi);
if (j == k) {
return Arrays.copyOf(nums, j + 1);
}
// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
}
// 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
private int partition(int[] nums, int lo, int hi) {
int v = nums[lo];
int i = lo, j = hi + 1;
while (true) {
while (++i <= hi && nums[i] < v);
while (--j >= lo && nums[j] > v);
if (i >= j) {
break;
}
int t = nums[j];
nums[j] = nums[i];
nums[i] = t;
}
nums[lo] = nums[j];
nums[j] = v;
return j;
}
}
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 默认是小根堆，实现大根堆需要重写一下比较器。
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num: arr) {
if (pq.size() < k) {
pq.offer(num);
} else if (num < pq.peek()) {
pq.poll();
pq.offer(num);
}
}
// 返回堆中的元素
int[] res = new int[pq.size()];
int idx = 0;
for(int num: pq) {
res[idx++] = num;
}
return res;
}
}
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
int[] count = new int[10001];
for(int a : arr){
count[a]++;
}
int[] res = new int[k];
int index = 0;
for(int i = 0;i < 100001;i++){
while(count[i]-- > 0 && index < k){
res[index++] = i;
}
if(index == k) break;
}
return res;
}
}
39、41数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
/**
用大顶堆+小顶堆方法
**/
class MedianFinder {
PriorityQueue<Integer> left;
PriorityQueue<Integer> right;
/** initialize your data structure here. */
public MedianFinder() {
left = new PriorityQueue<>((a, b) -> (b - a));//从大到小逆序排列 大顶 保留较小的一半 堆顶是最大值
right = new PriorityQueue<>();//从小到大排序 小顶 保留较大的一半 堆顶是最小值
}
// 1，2，3，4（大顶堆的poll）,5(小顶堆的poll),6,7,8
public void addNum(int num) {
left.add(num);
right.add(left.poll());
if(left.size() + 1 < right.size())
left.add(right.poll());
}
public double findMedian() {
if(right.size() > left.size()) return right.peek();
return (double)(left.peek() + right.peek()) / 2;
}
}
40、42连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
/**
1、常规动态规划
dp[i]表示nums[i]为结尾的最大连续子数组的和
dp[i] = max{nums[i],dp[i-1]+nums[i]}
dp[0]=nums[0];
2、简化版本
**/
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for(int i = 1;i < nums.length;i++){
dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
max = Math.max(max,dp[i]);
}
return max;
}
//dp[i]只和dp[i - 1]有关系
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);//巧夺天工
res = Math.max(res, nums[i]);
}
return res;
}
41、43.1~n整数中1出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
输入：n = 12
输出：5
输入：n = 13
输出：6
class Solution {
public int countDigitOne(int n) {
int digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while(high != 0 || cur != 0) {
if(cur == 0) res += high * digit;
else if(cur == 1) res += high * digit + low + 1;
else res += (high + 1) * digit;
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
}
链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
42、44.数字序列中某一位的数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
输入：n = 3
输出：3
输入：n = 11
输出：0
/* 数字范围 数量 位数 占多少位
1-9 9 1 9
10-99 90 2 180
100-999 900 3 2700
1000-9999 9000 4 36000 ...
例如 2901 = 9 + 180 + 2700 + 12 即一定是4位数,第12位 n = 12;
数据为 = 1000 + (12 - 1)/ 4 = 1000 + 2 = 1002
定位1002中的位置 = (n - 1) % 4 = 3 s.charAt(3) = 2;
*/
class Solution {
public int findNthDigit(int n) {
int digit = 1; // n所在数字的位数
long start = 1; // 数字范围开始的第一个数
long count = 9; // 占多少位
while(n > count){
n -= count;
digit++;
start *= 10;
count = digit * start * 9;
}
long num = start + (n - 1) / digit;
return Long.toString(num).charAt((n - 1) % digit) - '0';
}
}
43、45.把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
输入: [10,2]
输出: "102"
输入: [3,30,34,5,9]
输出: "3033459"
/**
把数组的元素排序，将首位小的放在前边，之后比较首位一样的排序位置
**/
// public String minNumber(int[] nums) {
// List<String> list = new ArrayList<>();
// for (int num : nums) {
// list.add(String.valueOf(num));
// }
// //lambda表达式，把代码块扔进去
// list.sort((o1, o2) -> (o1 + o2).compareTo(o2 + o1));
// StringBuilder res = new StringBuilder();
// for(String l : list){
// res.append(l);
// }
// return res.toString();
// }
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
44、46把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
/**
*动态规划
1、dp[i] 表示到第i位时的翻译种类
2、dp[0] = 1;dp[1]=1;
3、dp[i] = {
dp[i-2]+dp[i-1] 最后两位可以分开也可以一起翻译
dp[i - 1]最后两位没法一起翻译
}
**/
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i <= s.length();i++){
String temp = s.substring(i - 2,i);
dp[i] = (temp.compareTo("10") >= 0 &&
temp.compareTo("25") <=0) ? dp[i-1] + dp[i-2] : dp[i-1];
}
return dp[s.length()];
}
}
//只涉及到三个变量
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int a = 1,b = 1;
for(int i = 2;i <= s.length();i++){
String temp = s.substring(i - 2,i);
int res = (temp.compareTo("10") >= 0 &&
temp.compareTo("25") <=0) ? a + b : b;
a = b;
b = res;
}
return b;
}
}
//还可以继续优化，将字符串s的空间省掉
//利用num%10和num//10获取num的各位数字（个、十、百...）
//从右到左遍历，对称性结果一样
class Solution {
public int translateNum(int num) {
int a = 1, b = 1, x, y = num % 10;
while(num != 0) {
num /= 10;
x = num % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
b = a;
a = c;
y = x;
}
return a;
}
}
45、47.礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
//动态规划
class Solution {
public int maxValue(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
for(int i = 1;i < grid.length;i++)
grid[i][0] = grid[i - 1][0] + grid[i][0];
for(int i = 1;i < grid[0].length;i++)
grid[0][i] = grid[0][i - 1] + grid[0][i];
for(int i = 1;i < grid.length;i++){
for(int j = 1;j < grid[0].length;j++){
grid[i][j] = Math.max(grid[i - 1][j],grid[i][j - 1]) + grid[i][j];
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
}
46、48.最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//使用滑动窗口
//数组模拟哈希
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) return 0;
int[] index = new int[128];
for(int i = 0;i < 128;i++) index[i] = Integer.MIN_VALUE;
int left = 0,max = 0;
for(int i = 0;i < s.length();i++){
char temp = s.charAt(i);
left = Math.max(left,index[temp] + 1);//这个元素之前出现的位置在left右边，则更新left
max = Math.max(max,i - left + 1);
index[temp] = i;//更新最新位置
}
return max;
}
}
47、49丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
class Solution {
public int nthUglyNumber(int n) {
if(n == 0) return -1;
int[] arr = new int[n];
arr[0] = 1;
int num2 = 0;int num3 = 0;int num5 = 0;
for(int i = 1;i < n;i++){
arr[i] = Math.min(arr[num2] * 2,Math.min(arr[num3] * 3,arr[num5] * 5));
//谁最小，就移动谁指针
if(arr[i] == arr[num2] * 2) num2++;
if(arr[i] == arr[num3] * 3) num3++;
if(arr[i] == arr[num5] * 5) num5++;
}
return arr[n - 1];
}
}
class Solution {
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for(int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if(dp[i] == n2) a++;
if(dp[i] == n3) b++;
if(dp[i] == n5) c++;
}
return dp[n - 1];
}
}
48、50.第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 " "
public char firstUniqChar(String s) {
char[] ch = s.toCharArray();
Map<Character,Boolean> hashmap = new HashMap<>();
for(char c : ch){
hashmap.put(c,!hashmap.containsKey(c));
}
for(char c : ch){
if(hashmap.get(c)) return c;
}
return ' ';
}
}
//字典模拟哈希
public char firstUniqChar(String s) {
if(s.length() == 0) return ' ';
int[] count = new int[26];
for(int i = 0;i < s.length();i++){
count[s.charAt(i) - 'a']++;
}
for(int i = 0;i < s.length();i++){
if(count[s.charAt(i) - 'a'] == 1){
return s.charAt(i);
}
}
return ' ';
}
49、51.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
/**
1、暴力遍历要超时
2、用归并排序，在代码实现上，只需要在「归并排序」代码的基础上，加上「逆序对」个数的计算
**/
public class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
/**
* nums[left..right] 计算逆序对个数并且排序
*/
private int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairs(nums, left, mid, temp);//将左半边排序
int rightPairs = reversePairs(nums, mid + 1, right, temp);//将右半边排序
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
//使用辅助的数组进行归并排序
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
//复制给辅助数组
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left;//左边的头指针
int j = mid + 1;//右边的头指针
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {//左边已经被选取完了，把右边全都复制过去
nums[k] = temp[j];
j++;
} else if (j == right + 1) {//同理，右边选完了，左边全都复制过去
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {//左边小的时候
nums[k] = temp[i];
i++;
} else {//右边小的时候
nums[k] = temp[j];
j++;
count += (mid - i + 1);//因为是顺序排序的左边剩余的数量的数字，都比右边第一个要大
}
}
return count;
}
}
50、52.两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：在节点 c1 开始相交。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
//有缘的人会再相逢
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB){
if(headA == null || headB == null) return null;
ListNode curA = headA;
ListNode curB = headB;
while(curA != curB){
curA = curA == null ? headB : curA.next;
curB = curB == null ? headA : curB.next;
}
return curA;
}
}
51、53I.在排序数组中查找数字I
统计一个数字在排序数组中出现的次数。
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
//有序数组查找，直接二分。小技巧是寻找左指针的坐标，一直压缩右指针，之后从左往右计数
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return 0;
int res = 0;
int left = 0,right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] >= target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}
}
while(left < nums.length && nums[left++] == target){
res++;
}
return res;
}
}
52、53II.0~n-1中缺实的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
//二分查找 num[i] < i则缺失的数字在这个左区间，否则右区间。返回left第一个不符合的
class Solution {
public int missingNumber(int[] nums) {
int left = 0,right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == mid + 1) right = mid - 1;
else if(nums[mid] == mid) left = mid + 1;
}
return left;
}
}
53、54.二叉搜索树的第K大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 4
/**
*中序遍历的结果是从小到大升序的
1、中序遍历，取到结果，需要全部遍历浪费资源
2、改进型中序遍历
**/
class Solution {
public int kthLargest(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
midTraverse(root,list);
return list.get(list.size() - k);
}
//正常的中序遍历
public void midTraverse(TreeNode root,List<Integer> list){
if(root == null) return;
if(root.left != null) midTraverse(root.left,list);
list.add(root.val);
if(root.right != null) midTraverse(root.right,list);
}
}
class Solution{
private int res,k;
public int kthLargest(TreeNode root, int k){
this.k = k;
dfs(root);
return res;
}
//从大到小排序
private void dfs(TreeNode root){
if(root == null) return;
dfs(root.right);
if(k == 0) return;
if(--k == 0) res = root.val;//遍历到第K个的时候
dfs(root.left);
}
}
54、55.二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
//递归写法
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
}
}
//非递归就用层序遍历吧，BFS
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
int res = 0;
while(!queue.isEmpty()) {
tmp = new LinkedList<>();//就不用计数了
for(TreeNode node : queue) {
if(node.left != null) tmp.add(node.left);
if(node.right != null) tmp.add(node.right);
}
queue = tmp;
res++;
}
return res;
}
}
55.55-II.平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]，返回true
3
/
9 20
/
15 7
//后序遍历+剪枝，从顶至底
class Solution {
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
private int recur(TreeNode root){
if(root == null) return 0;
int left = recur(root.left);
if(left == -1) return -1;
int right = recur(root.right);
if(right == -1) return -1;
return Math.abs(left - right) < 2 ?
Math.max(left,right) + 1 : -1;
}
}
//先序遍历+判断深度（自顶向下） 有大量重复计算
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {//深度计算
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
56、56-I数组中数字出现的次数
一个整型数组 nums.里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
/**
有要求的时间复杂度 和 空间复杂度 考虑使用位运算
相同的数异或=0，不同的数疑惑等于1，0异或任何数等于这个数本身
数组中所有数的异或结果 == 结果两个数的异或结果 A^B
之后利用某种特性，将数组分成两组，这样就能在每组得到一个出现一次的数据
这种特性就是随便两个不同的数字总有一位不同，找出那个不同的数字当flag & 每一个数字完成分组
**/
public int[] singleNumbers(int[] nums){
int x = 0;
for(int num : nums) x ^= num;//A^B的结果
//int flag = x & (-x);最快捷 //我不太理解为什么能得到最低位的1 查：-x是x按位取反最后+1的结果
int flag = 1;
while(x & flag == 0) flag <<= 1;//左移增加一位，右边补0
int a,b;
for(int num : nums){//分成两部分
if(num & flag == 0) a ^= num;
else b ^= num;
}
return new int[]{a,b};
}
57、56-II.数组中数字出现的次数II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
//最高效的肯定是位运算，但是一时半会想不出思路，就先用map来做一些
public int singleNumber(int[] nums) {
Map<Integer,Boolean> map = new HashMap<>();
for(int num : nums){
if(!map.containsKey(num)){
map.put(num,true);
}else{
map.put(num,false);
}
}
for(Integer i : map.keySet()){
if(map.get(i) == true) return i;
}
return -1;
}
//位运算的思路
/*如果一个数字出现3次，它的二进制每一位也出现的3次。如果把所有的出现三次的数字的二进制表示的每一位都分别加起来，那么每一位都能被3整除。 我们把数组中所有的数字的二进制表示的每一位都加起来。如果某一位能被3整除，那么这一位对只出现一次的那个数的这一肯定为0。如果某一位不能被3整除，那么只出现一次的那个数字的该位置一定为1.*/
class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
for(int n : nums){
for(int i = 0;i < 32;i++){
count[i] += (n & 1);
n >>= 1;
}
}
int res = 0;
for(int i = 0;i < 32;i++){
if(count[i] % 3 == 1) res += (1 << i);
}
return res;
}
}
58、57.和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
//双指针 O(n) O(1)
class Solution {
public int[] twoSum(int[] nums, int target){
int left = 0,right = nums.length - 1;
while(left <= right){
if(nums[left] + nums[right] == target){
return new int[]{nums[left],nums[right]};
}else if(nums[left] + nums[right] > target){
right--;
}else{
left++;
}
}
return new int[]{0, 0};
}
}
59、57-II 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
//暴力法 5%
class Solution {
public int[] twoSum(int[] nums, int target){
int left = 0,right = nums.length - 1;
while(left <= right){
if(nums[left] + nums[right] == target){
return new int[]{nums[left],nums[right]};
}else if(nums[left] + nums[right] > target){
right--;
}else{
left++;
}
}
return new int[]{0, 0};
}
}
//滑动窗口，经典
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
int left = 1,right = 1;
int count = 0;
while(left <= target / 2){
if(count < target){
count += right++;
}else if(count > target){
count -= left++;
}else{//保存结果
int[] temp = new int[right - left];
for(int i = left;i < right;i++){
temp[i - left] = i;
}
res.add(temp);
count -= left++;
}
}
return res.toArray(new int[0][]);
}
}
60、58-I.翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
class Solution {
public String reverseWords(String s) {
StringBuilder res = new StringBuilder();
s = s.trim();//trim去掉字符串头尾空格
int i = s.length() - 1;
int j = i;
while(i >= 0){
while(i >= 0 && s.charAt(i) != ' ') i--;//从后往前
res.append(s.substring(i + 1,j + 1) + " ");//substing包头不包尾
while(i >= 0 && s.charAt(i) == ' ') i--;
j = i;//改一些尾巴
}
return res.toString().trim();
}
}
61、58-II.左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
//1、可以用内置函数
class Solution {
public String reverseLeftWords(String s, int n) {
return s.subString(0,n) + s.subString(n,s.length());
}
}
//2、不可以用内置函数
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
//char[] arr = s.toCharArray();
for(int i = n;i < s.length();i++) sb.append(s.charAt(i));
for(int i = 0;i < n;i++) sb.append(s.charAt(i));
return sb.toString();
}
}
//3、只能用String
class Solution {
public String reverseLeftWords(String s, int n) {
String res = "";
for(int i = n;i < s.length();i++) res += s.charAt(i);
for(int i = 0;i < n;i++) res += s.charAt(i);
return res;
}
}
62、59-I.滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
//1、一个窗口的元素为目标，找出最大值，缺点是每次都要找找全部值
//时间30% 空间60% 还需优化
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0) return new int[]{};
int left = 0,right = k - 1;
int[] res = new int[nums.length - k + 1];
int i = 0;
while(right < nums.length){
res[i++] = findMax(nums,left++,right++);
}
return res;
}
private int findMax(int[] nums,int start,int end){
int max = Integer.MIN_VALUE;
for(int i = start;i <= end;i++){
if(nums[i] > max){
max = nums[i];
}
}
return max;
}
}
//2、使用单调队列解决，单调队列就是对是队列中的元素关系具有单调性，队首和队尾都可以出队，只要队尾可以入队 //80% 30%
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0) return new int[]{};
int left = 0,right = k - 1;
int[] res = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
//初始化队列
for(int i = 0;i < k;i++){
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);
}
//给结果数列写值
res[0] = deque.peekFirst();
for(int i = k;i < nums.length;i++){
//移动窗口后，处理最左边抛出去的元素
if(deque.peekFirst() == nums[i - k]){
deque.removeFirst();
}
//维持队列
while(!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
deque.addLast(nums[i]);
res[i - k + 1] = deque.peekFirst();
}
return res;
}
}
//化简一下代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
if(i > 0 && deque.peekFirst() == nums[i - 1])
deque.removeFirst(); // 删除 deque 中对应的 nums[i-1]
while(!deque.isEmpty() && deque.peekLast() < nums[j])
deque.removeLast(); // 保持 deque 递减
deque.addLast(nums[j]);
if(i >= 0)
res[i] = deque.peekFirst(); // 记录窗口最大值
}
return res;
}
}
63、59-II.队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
//用一个队列来做主队列，另一个队列用来保存最大值
class MaxQueue {
Deque<Integer> deque;//主队列
Deque<Integer> max;//辅助队列
public MaxQueue() {
deque = new ArrayDeque<>();
max = new ArrayDeque<>();
}
public int max_value() {
return deque.isEmpty() ? -1 : max.peekFirst();
}
public void push_back(int value) {
deque.addLast(value);
while(!max.isEmpty() && max.peekLast() < value)
max.removeLast();
max.addLast(value);
}
public int pop_front() {
if(deque.isEmpty()) return -1;
int value = deque.removeFirst();
if(value == max.peek()) max.removeFirst();
return value;
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.max_value();
* obj.push_back(value);
* int param_3 = obj.pop_front();
*/
64、60.n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
//动态规划+统计
//dp[i][j]表示投掷i次，点数j出现的次数统计
//dp[1][j] = 1 (1<=j<=6)
class Solution {
public double[] dicesProbability(int n){
//定义dp数组
int[][] dp = new int[n + 1][6 * n + 1];
//初始化数组
for(int j = 1;j <= 6;j++){
dp[1][j] = 1;
}
//动态规划赋值
for(int i = 2;i <= n;i++){
for(int j = 1;j <= 6 * n;j++){
for(int k = 1;k <= 6;k++){
//每次至少点数为1共i-1次
if(j - k < i - 1) break;
dp[i][j] += dp[i - 1][j - k];
}
}
}
//统计结果
double sum = (double)Math.pow(6,n);
double[] res = new double[6 * n - n + 1];
for(int i = n;i <= 6 * n;i++){
res[i - n] = ((double)dp[n][i]) / sum;
}
return res;
}
}
65、61.扑克牌中的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
class Solution {
//set去重 记录最大值和最小值 是0
public boolean isStraight(int[] nums) {
Set<Integer> set = new HashSet<>();
int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
for(int num : nums){
if(num == 0) continue;
if(!set.add(num)) return false;
if(num > max) max = num;
if(num < min) min =num;
}
return (max - min) < 5;
}
}
//else:排序；2. 统计 0 和 其他数字间的空隙大小；3. 当 0 的个数大于等于间隙大小的时候返回真。
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int count0 = 0;//0的个数
int countNo = 0;//不连续的间隙
for(int i = 0;i < 4;i++){
if(nums[i] == 0) count0++;
else if(nums[i] == nums[i + 1]) return false;
else countNo += (nums[i + 1] - nums[i] - 1);
}
return count0 >= countNo;
}
}
66、62.圆圈中最后剩下的数字-约瑟夫环问题
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例2：
输入: n = 10, m = 17
输出: 2
//第一时间选择方便的数据结构才存储这些数字，考虑到ArrayList，时间26%空间34& 效率太低
class Solution {
public int lastRemaining(int n, int m) {
ArrayList<Integer> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) list.add(i);
int idx = 0;
while (n > 1) {
idx = (idx + m - 1) % n;
list.remove(idx);
n--;
}
return list.get(0);
}
}
//需要优化，使用数学解法反推：(当前index + m) % 上一轮剩余数字的个数 99% 70%
class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
67、63.股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
class Solution {
/* dp[i][k][0]表示在第i天的剩余最大操作数k且手里没有股票时的利润
dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k - 1][0] - peices[i])
k=1代入，且dp[i][0][0] = 0,剩余dp的第二个坐标可以省略
化简为dp[i][0] = max(dp[i-1][0],dp[i-1] + prices[i])
dp[i][1] = max(dp[i-1][1],-prices)
可以看到dp数组的更新只和前一个状态有关，化简数组
*/
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) return 0;
int dp_i_0 = 0,dp_i_1 = Integer.MIN_VALUE;
for(int i = 0;i < prices.length;i++){
dp_i_0 = Math.max(dp_i_0,dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1,-prices[i]);
}
return dp_i_0;
}
}
68、64.求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
//要避开限制条件 则考虑吧剩下的迭代方法
public int sumNums(int n) {
int sum = n;
sum += sumNums(n - 1);//这里需要判断n-1 > 0;
return sum;
}
//巧妙的利用双目运算符 && 前边的false就不再计算后边
boolean flag = (n > 0) && (sum += sumNums(n - 1) > 0);
class Solution {
public int sumNums(int n) {
int sum = n;
boolean flag = n > 0 && (sum += sumNums(n - 1)) > 0;
return sum;
}
}
69、 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
//只能用位运算
//非进位和n = a ^ b 0+0=0 1+1=0(进位1) 1+0 = 1
//进位和c = (a & b)<<1 1+1= <<1
public int add(int a,int b){//递归
if(b == 0) return a;
return add(a ^ b,(a & b) << 1);
}
public int add(int a,int b){//非递归
while(b != 0){
int c = (a & b) << 1;
a ^= b;
b = c;
}
return a;
}
70、66.构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
//第一轮遍历，从左到右坐标i的值等于左边的所有数的乘积，用一个临时变量来表示自己原本的值
for(int i = 0,temp = 1;i < n;i++){
res[i] = temp;//res是前边的数的乘积
temp *= a[i];//保存前边数的乘积*当前的数，给下一数使用
}
//第二轮遍历，从右到左，思路一样
for(int i = n - 1,temp = 1;i >= 0;i--){
res[i] *= temp;//已经赋值一遍了，要*=
temp *= a[i];
}
class Solution {
public int[] constructArr(int[] a) {
int n = a.length;
int[] res = new int[n];
for(int i = 0,temp = 1;i < n;i++){
res[i] = temp;
temp *= a[i];
}
for(int i = n - 1,temp = 1;i >= 0;i--){
res[i] *= temp;
temp *= a[i];
}
return res;
}
}
71、67.把字符串转换成整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换
示例 5:
91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
/**
1、先去除两端的空格
2、首字母必须是'+'、'-'、数字
3、取前边的有效数字 注意正负号
**/
class Solution {
public int strToInt(String str) {
//1、去除空格
str = str.trim();
char[] s = str.toCharArray();
int n = s.length;
//当前遍历位置的下标
int index = 0;
//初始判断
if(n == index) return 0;
//正负号的标识
boolean isPositive = true;
//首位判断并保留正负号
if(s[index] == '-'){
isPositive = false;
index++;
}else if(s[index] == '+'){
index++;
}else if(!Character.isDigit(s[index])){
return 0;
}
//保存结果
int res = 0;
while(index < n && Character.isDigit(s[index])){
int digit = s[index] - '0';
//条件判断 res * 10 + digit <= Integer.MAX_VALUE
if(res > (Integer.MAX_VALUE - digit) / 10){
return isPositive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
res = res * 10 + digit;
index++;
}
//输出带正负号的结果
return isPositive ? res : -res;
}
}
72、68-I.二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dzB8TOI9-1610625060534)(C:UsersPCAppDataRoamingTyporatypora-user-imagesimage-20201216110313758.png)]
//递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
//都在左子树
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
//都在右子树
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
//左子树和右子树都有，也有可能有一个就是根节点
return root;
}
//迭代
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null) {
if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
root = root.right; // 遍历至右子节点
else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
root = root.left; // 遍历至左子节点
else break;
}
return root;
}
}
73、68-II.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
/**
*和上一题不一样的是，这次是二叉树而不是二叉搜索树，二叉树没有规律可言
**/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
// 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
TreeNode left = lowestCommonAncestor(root.left,p,q);
// 同理
TreeNode right = lowestCommonAncestor(root.right,p,q);
// 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先
if(left == null) return right;
//同理
if(right == null) return left;
return root;
}
最后
以上就是彪壮帽子为你收集整理的《剑指Offer》Java实现版-电子科大-2021最新的全部内容，希望文章能够帮你解决《剑指Offer》Java实现版-电子科大-2021最新所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复