- 【Java】剑指offer-leetcode题解
- 数组中重复的数字
- 剑指offer思路
- 哈希
- 二维数组中的查找
- 替换空格
- 从尾到头打印链表
- 递归
- 辅助栈
- 重建二叉树
- 用两个栈实现队列
- 斐波那契数列
- 青蛙跳台阶问题
- 旋转数组的最小数字
- 矩阵中的路径
- 机器人的运动范围
- 剪绳子
- 剪绳子 II
- 二进制中1的个数
- 数值的整数次方
- 打印从1到最大的n位数
- 删除链表的节点
- 正则表达式匹配
- 表示数值的字符串
- 调整数组顺序使奇数位于偶数前面
- 链表中倒数第k个节点
- 反转链表
- 合并两个排序的链表
- 树的子结构
- 二叉树的镜像
- 对称的二叉树
- 顺时针打印矩阵
- 螺旋矩阵
- 包含min函数的栈
- 栈的压入、弹出序列
- I. 从上到下打印二叉树
- II. 从上到下打印二叉树 II
- III. 从上到下打印二叉树 III
- 二叉搜索树的后序遍历序列
- 二叉树中和为某一值的路径
- 复杂链表的复制
- 二叉搜索树与双向链表
- 序列化二叉树
剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com)
剑指offer思路class Solution {
public int findRepeatNumber(int[] nums) {
if(nums.length < 1 || nums == null) return -1;
for(int i = 0; i< nums.length;i++){
while(nums[i] != i){
if(nums[i] == nums[nums[i]]) return nums[i];
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
}
哈希
class Solution {
public int findRepeatNumber(int[] nums) {
if(nums.length < 1 || nums == null) return -1;
Set set = new HashSet<>();
for(int num: nums){
if(set.contains(num))return num;
set.add(num);
}
return -1;
}
}
二维数组中的查找
剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)return false;
int row = 0;
int col = matrix[0].length-1;
while(row < matrix.length && col >= 0){//当前行 当前列都在数组内
if(matrix[row][col] > target) col --;
else if(matrix[row][col] < target) row ++;
else return true;
}
return false;
}
}
替换空格
剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public String replaceSpace(String s) {
StringBuffer stringBuffer = new StringBuffer();
for(int i =0;i
if(s.charAt(i) == ' ') stringBuffer.append("%20");
else stringBuffer.append(s.charAt(i));
}
return stringBuffer.toString();
}
}
从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode） (leetcode-cn.com)
递归
class Solution {
ArrayList list = new ArrayList();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[list.size()];
for(int i = 0; i< list.size();i++){
res[i] = list.get(i);
}
return res;
}
void recur(ListNode head){
if(head == null) return;
recur(head.next);
list.add(head.val);
}
}
辅助栈
class Solution {
public int[] reversePrint(ListNode head) {
Stack stack = new Stack();
while(head !=null){
stack.push(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i++)
res[i] = stack.pop();
return res;
}
}
重建二叉树
Loading Question… - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
HashMap map = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0 ||preorder.length != inorder.length) return null;
for(int i = 0; i< inorder.length;i++) map.put(inorder[i],i);
return construct(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
//区间，左闭右闭
TreeNode construct(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend){
if (prestart > preend) return null;
TreeNode root = new TreeNode(preorder[prestart]);//当前的根结点
int index = map.get(preorder[prestart]);//找到中序遍历中根结点的下标
root.left = construct(preorder,prestart+1,prestart+index-instart,inorder,instart,index-1);//寻找左子树
root.right = construct(preorder,prestart+index-instart+1,preend,inorder,index +1,inend);//寻找右子树
return root;
}
}
用两个栈实现队列
剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)
class CQueue {
Stack stack1;
Stack stack2;
public CQueue() {
stack1 = new Stack();
stack2 = new Stack();
}
public void appendTail(int value) {
stack1.add(value);
}
public int deleteHead() {
if(stack2.isEmpty()){
if(stack1.isEmpty()) return -1;
while(!stack1.isEmpty()){
stack2.add(stack1.pop());
}
}
return stack2.pop();
}
}
斐波那契数列
剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int fib(int n) {
if(n == 0 || n == 1) return n;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i<= n;i++){
dp[i] = (dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
}
青蛙跳台阶问题
剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int numWays(int n) {
if(n == 0 || n == 1) return 1;
if(n == 2) return n;
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i<=n;i++){
dp[i] = (dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
}
旋转数组的最小数字
剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int minArray(int[] numbers) {
if(numbers == null || numbers.length == 0) return -1;
int start = 0;
int end = numbers.length-1;
int mid = start;
while(numbers[start] >= numbers[end]){//前半段数组的数，始终要大于后半段
if(end - start == 1) {
return numbers[end];//找到了最小的数
}
mid = start + (end - start)/2;
if(numbers[mid] == numbers[start] && numbers[mid] == numbers[end]) return getmin(numbers,start,end);
else if(numbers[mid] >= numbers[start]) start = mid;
else if(numbers[mid] <= numbers[end]) end = mid;
}
return numbers[mid];
}
//如果中间的节点等于start也等于end，那么就无法区分mid是在前一个数组还是在后一个数组，所以，只能从头开始遍历找到最小值并返回
public int getmin(int[] numbers,int start,int end){
int res = numbers[start];
for(int i = start+1;i<=end;i++) {
if(res > numbers[i]) res = numbers[i];
}
return res;
}
}
矩阵中的路径
剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0 || word == null) return false;
boolean[][] visited =new boolean[board.length][board[0].length];//用来存放，矩阵中的位置是否被访问过
char[] chars = word.toCharArray();
//从每一个点进行遍历
//如果(0,0)没有适合的路径，那就从（0，1）开始找
for(int i = 0; i< board.length;i++){
for(int j = 0; j< board[0].length;j++){
if(hasPathCore(board,i,j,visited,0,chars))
return true;
}
}
return false;
}
public boolean hasPathCore(char[][] board,int currow,int curcol,boolean[][] visited,int start,char[] chars){
//判断行列是否有在区域内，当前字符是否等于矩阵中当前行当前列的字符，该字符是否被访问过
if(currow < 0 ||currow >= board.length || curcol < 0 ||curcol >= board[0].length || chars[start] != board[currow][curcol] || visited[currow][curcol])
return false;
if(start == chars.length-1) return true; //说明字符已经被遍历完了，返回true，此时所有的字符已经被找到了
visited[currow][curcol] = true;//更新该位置已经被访问过
boolean haspath = false;
//上下左右是否符合
haspath = hasPathCore(board,currow+1,curcol,visited,start+1,chars)||
hasPathCore(board,currow,curcol+1,visited,start+1,chars)||
hasPathCore(board,currow-1,curcol,visited,start+1,chars)||
hasPathCore(board,currow,curcol-1,visited,start+1,chars);
visited[currow][curcol] = false;//更新位置信息，为未访问过，回溯
return haspath;
}
}
机器人的运动范围
剑指 Offer 13. 机器人的运动范围 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int movingCount(int m, int n, int k) {
if(m < 1 || n < 1 || k < 0) return 0;
boolean[][] visited = new boolean[m][n];
return dfs(visited,k,0,0,m,n);
}
public int dfs(boolean[][] visited,int k,int i,int j,int m, int n){
if(check(visited,k,i,j,m,n)){
visited[i][j] = true;
return dfs(visited,k,i,j+1,m,n) + dfs(visited,k,i+1,j,m,n)+dfs(visited,k,i-1,j,m,n)+dfs(visited,k,i,j+1,m,n)+1;
}
return 0;
}
//判断是否在小于k
public boolean check(boolean[][] visited,int k,int i,int j,int m, int n){
if( i < 0 || i>= m || j< 0 || j>= n || visited[i][j] || sum(i) + sum(j) > k) return false;
return true;
}
//一个数的数位之和
public int sum(int number){
int res = 0;
while(number > 0){
res += number%10;
number = number/10;
}
return res;
}
}
剪绳子
剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
int[] dp = new int[n+1];
//这里的3不要分，因为3分段最大为2，不分为3，同理2
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int max = 0;//用来存放当前绳子长度的最大乘积
//3之前的数都是固定的，4开始有可以分成多段 1*4 2*2
for(int i = 4; i<=n;i++){
max = 0;
//j<=i/2是因为1*3和3*1是一样的，没必要计算一次
//j从1开始，绳子长度不为0
for(int j = 1; j <= i/2 ;j++){
max =Math.max(max,dp[j]*dp[i-j]);
}
//更新当前绳子长度的最大乘积
dp[i] = max;
}
return dp[n];
}
}
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
int[] dp = new int[n+1];
dp[2] = 1;
//从2开始才可以进行剪
for(int i = 3; i<=n;i++){
//这里减去的长度从1 到 i /2 就包含了所有的情况
for(int j = 1; j<= i/2;j++){
//dp[i],不剪短的长度
//可以剪一次 j 和 i-j
//剪多次，j*dp[i-j] dp[i-j]剪去j长度后，最大乘积
dp[i] = Math.max(dp[i],Math.max(j*(i-j),dp[i-j]*j));
}
}
return dp[n];
}
}
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
//尽可能的剪成3段
int timeof3 = n/3;
//如果剩余1，则应把一份 3 +1 替换为 2 + 2，因为2×2>3×1
if(n -timeof3 *3 == 1) timeof3 -= 1;
int timeof2 = (n-timeof3*3) /2;
return (int)Math.pow(3,timeof3)*(int)Math.pow(2,timeof2);
}
}
剪绳子 II
剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
long res = 1;
while(n > 4){
res = res *3;
res = res %1000000007;
n = n-3;
}
//定义 res 作为乘积，每次乘 3 后，n 要减3，以此实现有多少3乘多少3；
//需要讨论的是最后一段的取值，若最后一段余下2，3，4直接返回，因为特例最后一段为 4 时需要拆为 2 * 2.
//如果是3就直接*3
//如果是2 就直接*2 1*1 < 2
return(int)((res*n)%1000000007);
}
}
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
int timeof3 = n/3;
if(n -timeof3*3 == 1) timeof3 -= 1;//分为三段的次数
int timeof2 = (n-timeof3*3)/2;//分为两段的次数
long res =1;
while(timeof3 > 0){
res *= 3;
res = res % 1000000007;
timeof3 -= 1;
}
while(timeof2 > 0){
res *= 2;
res = res % 1000000007;
timeof2 -= 1;
}
return (int)res;
}
}
二进制中1的个数
剑指 Offer 15. 二进制中1的个数 - 力扣（LeetCode） (leetcode-cn.com)
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while(n != 0){
n = n& (n-1);
res ++;
}
return res;
}
}
数值的整数次方
剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public double myPow(double x, int n) {
if(n == 0) return 1;
if(n == 1) return x;
long exp = n;
// n = -2147483648 时执行 n = -n 会因越界而赋值出错
//为了防止一个特例的溢出
if(n < 0) exp = -exp;
double res = powerWithUnsigned(x,exp);
if(n < 0) res = 1.0/res;
return res;
}
public double powerWithUnsigned(double x,long n){
if(n == 0) return 1;
if(n == 1) return x;
double res = powerWithUnsigned(x,n>>1);
res = res * res;
if(n % 2 !=0) res *= x;
return res;
}
}
打印从1到最大的n位数
剑指 Offer 17. 打印从1到最大的n位数 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
int[] res;
int count = 0;
public int[] printNumbers(int n) {
res = new int[(int)Math.pow(10, n) - 1];
for(int k = 1;k//不同的位数，创建不同的char
char[] nums = new char[k];//一共几位数
for(int i = 1; i< 10; i++){
nums[0] =(char)(i+'0');// 个位上的数字
dfs(k,nums,1);
}
}
return res;
}
public void dfs(int k,char[] nums,int index){
if(index == k) {
res[count++] = Integer.parseInt(String.valueOf(nums));
return;
}
for(int i =0; i < 10; i++){
nums[index] =(char)(i+'0');
dfs(k,nums,index+1);
}
}
}
删除链表的节点
剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head == null) return head;
ListNode cur = head;
if(head.val == val) return head.next;
//cur不为空cur.next也不为空。如果删除最后一个，那么cur指向了空，cur.next就会访问不到，从而报错
while(cur != null && cur.next != null ){
if(cur.next.val == val) cur.next = cur.next.next;
cur = cur.next;
}
return head;
}
}
正则表达式匹配
剑指 Offer 19. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1, n = p.length() + 1;
boolean[][] dp = new boolean[m][n];
dp[0][0] = true;
// 初始化首行
//首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配（即让 p 的奇数位出现 0 次，保持 p 是空字符串）
for(int j = 2; j < n; j += 2)
dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
// 状态转移
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(p.charAt(j - 1) == '*') {//前一个字符为*时
if(dp[i][j - 2]) dp[i][j] = true; //如果dp[i][j-2]可以匹配，那么p[j-2]*看作0次
// 如果s[i-1]和p[j-2]相等，且dp[i - 1][j]匹配 那么让p[j-2]出现多次，
else if(dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) dp[i][j] = true;
// dp[i - 1][j]匹配，且p[j-2]为.
else if(dp[i - 1][j] && p.charAt(j - 2) == '.') dp[i][j] = true;
} else {
if(dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = true;
else if(dp[i - 1][j - 1] && p.charAt(j - 1) == '.') dp[i][j] = true;
}
}
}
return dp[m - 1][n - 1];
}
}
表示数值的字符串
剑指 Offer 20. 表示数值的字符串 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean isNumber(String s) {
if(s == null || s.length() == 0) return false; // s为空对象或 s长度为0(空字符串)时, 不能表示数值
boolean isNum = false, isDot = false, ise_or_E = false; // 标记是否遇到数位、小数点、‘e’或'E'
char[] str = s.trim().toCharArray(); // 删除字符串头尾的空格，转为字符数组，方便遍历判断每个字符
for(int i=0; i
if(str[i] >= '0' && str[i] <= '9') isNum = true; // 判断当前字符是否为 0~9 的数位
else if(str[i] == '.') { // 遇到小数点
if(isDot || ise_or_E) return false; // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
isDot = true; // 标记已经遇到小数点
}
else if(str[i] == 'e' || str[i] == 'E') { // 遇到‘e’或'E'
if(!isNum || ise_or_E) return false; // ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
ise_or_E = true; // 标记已经遇到‘e’或'E'
isNum = false; // 重置isNum，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
}
else if(str[i] == '-' ||str[i] == '+') {
if(i!=0 && str[i-1] != 'e' && str[i-1] != 'E') return false; // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
}
else return false; // 其它情况均为不合法字符
}
return isNum;
}
}
调整数组顺序使奇数位于偶数前面
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int[] exchange(int[] nums) {
int left = 0;
int right = nums.length-1;
while(left < right){
while(left < right && nums[left] % 2 == 1) left ++;
while(left < right && nums[right] % 2 == 0) right --;
if(left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
}
链表中倒数第k个节点
剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(k < 1 || head==null) return null;
ListNode temp1 = head;
ListNode temp2 = head;
while(k-- > 0 && temp1!=null){
temp1 = temp1.next;
}
while(temp1 != null){
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp2;
}
}
反转链表
剑指 Offer 24. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val > l2.val) {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
else{
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
}
}
树的子结构
剑指 Offer 26. 树的子结构 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null) return false;
//判断B是不是A的子树,如果B不是A当前点的子树,那么判断B是不是A的左子树的子树或者右子树的子树
return dfs(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
public boolean dfs(TreeNode A,TreeNode B){
if(B == null) return true; //如果B为空，A不为空,返回true
if(A == null) return false; //如果A为空,B不为空，返回false
//如果当前节点的值相同，那么判断他的左节点和右节点是否都相同
return A.val == B.val && dfs(A.left, B.left)
&& dfs(A.right, B.right);
}
}
二叉树的镜像
剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//临时节点保存左节点
//在递归右子节点 “root.left = mirrorTree(root.right);
//执行完毕后，root.left 的值已经发生改变，此时递归左子节点 mirrorTree(root.left) 则会出问题
TreeNode temp = root.left;
root.left = mirrorTree(root.right);//右节点作为左节点返回
root.right = mirrorTree(temp);//左节点作为右节点返回
return root;
}
}
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//递归左右子树
//遍历所有的非叶子节点，并交换所有的非叶子节点
mirrorTree(root.left);
mirrorTree(root.right);
//反转根结点
swap(root);
return root;
}
public void swap(TreeNode root){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
对称的二叉树
剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return dfs(root.left,root.right);
}
public boolean dfs(TreeNode left,TreeNode right){
if(left == null && right == null) return true;
if(right == null) return false;
if(left == null) return false;
if(right.val != left.val) return false;
return dfs(left.left,right.right) && dfs(left.right,right.left);
}
}
顺时针打印矩阵
剑指 Offer 29. 顺时针打印矩阵 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length ==0) return new int[0];
int rows = matrix.length;
int cols = matrix[0].length;
int[] nums = new int[rows*cols];
int index = 0;
int startx = 0;
int starty = 0;
int offest = 1;
int loop = Math.min(rows,cols)/2;
while(loop-- > 0){
int i = startx;
int j = starty;
//上面一行
for(;jstarty;j--) nums[index++] = matrix[i][j];
//左边一行
for(;i>startx;i--) nums[index++] = matrix[i][j];
offest++;
startx++;
starty++;
}
//如果行列相等，且为奇数
if(rows == cols && rows% 2 ==1) nums[index++] = matrix[rows/2][cols/2];
//如果行大于列，且列不为偶数
if(rows > cols && cols %2 ==1){
for(int i = cols/2;i
nums[index++] = matrix[i][cols/2];
}
}
//列大于行，行不为偶数
if(rows
for(int i = rows/2;i
nums[index++] = matrix[rows/2][i];
}
}
return nums;
}
}
螺旋矩阵
54. 螺旋矩阵 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public List spiralOrder(int[][] matrix) {
List list = new LinkedList();
int startx = 0;
int starty = 0;
int offest = 1;
int loop = Math.min(matrix.length,matrix[0].length)/2;
int n = matrix.length;
int m = matrix[0].length;
while(loop > 0){
int i = startx;
int j = starty;
//上面一行
for(;j
list.add(matrix[i][j]);
}
//右边
for(;i
list.add(matrix[i][j]);
}
for(;j>starty;j--){
list.add(matrix[i][j]);
}
for(;i>startx;i--){
list.add(matrix[i][j]);
}
loop --;
startx ++;
starty ++;
offest ++;
}
if(n == m && n%2 ==1){
list.add(matrix[n/2][m/2]);
}
if (m > n && n%2!=0 ){
for (int i = n/2; i < m-n/2; i++) {
list.add(matrix[n/2][i]);
}
}
//针对行大于列且，列不是偶数的时候；
if (m < n && m%2 !=0){
for (int i = m/2; i < n-m/2; i++) {
list.add(matrix[i][m/2]);
}
}
return list;
}
}
包含min函数的栈
剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode） (leetcode-cn.com)
class MinStack {
private Stack stack;
private Stack min;
public MinStack() {
stack = new Stack();
min = new Stack();
}
public void push(int x) {
stack.push(x);
if(min.isEmpty()) min.push(x);
else min.push(Math.min(min.peek(),x));
}
public void pop() {
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return min.peek();
}
}
栈的压入、弹出序列
剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque deq = new ArrayDeque();
int index = 0;
for(int num:pushed){
deq.push(num);//把入栈的元素放入deq
//如果deq不为空，且dep的栈顶等于出栈元素，则deq出栈，出栈元素指针++
while(!deq.isEmpty() && deq.peek() == popped[index]) {
deq.pop();
index++;
}
}
//如果栈为空，则合法
return deq.isEmpty();
}
}
I. 从上到下打印二叉树
剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
Deque deq = new LinkedList();
List list = new ArrayList();
deq.add(root);
while(!deq.isEmpty()){
TreeNode node = deq.pop();
list.add(node.val);
if(node.left != null) deq.add(node.left);
if(node.right != null) deq.add(node.right);
}
return list.stream().mapToInt(Integer::intValue).toArray();
}
}
II. 从上到下打印二叉树 II
剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public List> levelOrder(TreeNode root) {
if(root == null) return new ArrayList();
List> res = new ArrayList();
Deque deq = new LinkedList();
deq.add(root);
while(!deq.isEmpty()){
int size = deq.size();
List path = new ArrayList();
while(size-- > 0){
TreeNode temp = deq.pop();
path.add(temp.val);
if(temp.left!=null) deq.add(temp.left);
if(temp.right != null) deq.add(temp.right);
}
res.add(path);
}
return res;
}
}
III. 从上到下打印二叉树 III
剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
LinkedList tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
class Solution {
public List> levelOrder(TreeNode root) {
Deque deque = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) deque.add(root);
while(!deque.isEmpty()) {
// 打印奇数层
List tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从左向右打印
TreeNode node = deque.removeFirst();
tmp.add(node.val);
// 先左后右加入下层节点
if(node.left != null) deque.addLast(node.left);
if(node.right != null) deque.addLast(node.right);
}
res.add(tmp);
if(deque.isEmpty()) break; // 若为空则提前跳出
// 打印偶数层
tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从右向左打印
TreeNode node = deque.removeLast();
tmp.add(node.val);
// 先右后左加入下层节点
if(node.right != null) deque.addFirst(node.right);
if(node.left != null) deque.addFirst(node.left);
}
res.add(tmp);
}
return res;
}
}
二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder.length<2) return true;
return verify(postorder,0,postorder.length-1);
}
public boolean verify(int[] postorder,int start,int end){
if(start >= end) return true;
int rootValue = postorder[end];//根结点
int index = start;
//寻找左子树
while(index < end && postorder[index] < rootValue) index ++;
//寻找右子树
int right = index; //右子树的第一个节点
while(index < end && postorder[index] > rootValue) index ++;
if(index != end) return false;
return verify(postorder,start,right-1) && verify(postorder,right,end-1);
}
}
二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
private List> res = new ArrayList();
private List path = new ArrayList();
public List> pathSum(TreeNode root, int target) {
if(root == null) return new ArrayList();
BFS(root,target);
return res;
}
public void BFS(TreeNode root,int target){
if(root == null) return;
target -= root.val;
path.add(root.val);
if(target == 0 && root.left == null && root.right == null) res.add(new ArrayList(path));
else{
BFS(root.left,target);
BFS(root.right,target);
}
path.remove(path.size()-1);
target += root.val;
}
}
复杂链表的复制
剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return head;
Node cur = head;
//复制链表
while(cur != null){
Node copynode = new Node(cur.val);
copynode.next = cur.next;
cur.next = copynode;
cur = cur.next.next;
}
//完成连接
cur = head;
while(cur !=null){
if(cur.random != null){
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
//将链表一分为二
Node cpoyHead = head.next;
cur = head;
Node copy = cur.next;
while(cur !=null){
//两个指针分别往后移两位，进行分开
cur.next = cur.next.next;
cur = cur.next;
if(copy.next != null){
copy.next = copy.next.next;
copy = copy.next;
}
}
return cpoyHead;
}
}
二叉搜索树与双向链表
剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
Node pre,head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
//最后让头尾相连
head.left =pre;
pre.right = head;
return head;
}
public void dfs(Node cur){
if(cur == null) return;
//中序遍历，左
dfs(cur.left);//寻找第一个左子节点
//如果pre 为空。说明为第一个节点，也就是头节点
if(pre == null) head = cur;
//中
//如果pre不为空，让上一个节点的右指针指向当前节点
else if(pre!=null) pre.right = cur;
//让当前节点的左子节点指向pre，形成双向链表
cur.left = pre;
pre = cur;//将前一个结点指向当前节点，然后递归右子树
//右
dfs(cur.right);
}
}
序列化二叉树
剑指 Offer 37. 序列化二叉树 - 力扣（LeetCode） (leetcode-cn.com)
public class Codec {
public String serialize(TreeNode root) {
if(root == null) return "[]";
StringBuilder res = new StringBuilder("[");
Queue queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp != null){
res.append(temp.val + ",");
queue.add(temp.left);
queue.add(temp.right);
}else res.append("null,");
}
res.deleteCharAt(res.length()-1);
res.append("]");
return res.toString();
}
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] arr = data.substring(1,data.length()-1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));//第一个字符为根结点
int index = 1;
Queue queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(!arr[index].equals("null")){
node.left = new TreeNode(Integer.parseInt(arr[index]));
queue.add(node.left);
}
index ++;
if(!arr[index].equals("null")){
node.right = new TreeNode(Integer.parseInt(arr[index]));
queue.add(node.right);
}
index ++;
}
return root;
}
}
