本文已收录于专栏

🌻

《刷题笔记》

前言

题目来源参考阿秀学长的刷题笔记，小戴只是把 C++的题解改成了 Java版本，并整理了其他思路，便于自己的学习~

如果解题有更好的方法，本文也会及时进行更新~

希望对你有帮助~ 一起加油哇~

🎨 1、合并两个有序链表

牛客原题链接

题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的

思路一（递归）

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1 == null){return list2;}if(list2 == null){return list1;}if(list1.val < list2.val){list1.next = Merge(list1.next,list2);return list1;}else{list2.next = Merge(list1,list2.next);return list2;}}
}

思路二（双指针）

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1 == null){return list2;}if(list2 == null){return list1;}// 创建一个头结点ListNode head = new ListNode(0);ListNode cur = head;while(list1!=null && list2!=null){if(list1.val <= list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if(list1 != null){cur.next = list1;}else{cur.next = list2;}return head.next;}
}

🎨 2、树的子结构

牛客原题链接

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路一（递归）

/
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public boolean HasSubtree(TreeNode root1, TreeNode root2) {if (root1 == null || root2 == null) {return false;}return HasSub(root1, root2) || HasSubtree(root1.left, root2) ||HasSubtree(root1.right, root2);}public boolean HasSub(TreeNode root1, TreeNode root2) {// 不匹配的情况有很多，先找匹配的情况// 遍历完root2，root2为空时，说明root2的所有结点都与root1的子结构匹配上if (root2 == null) {return true;}// 不匹配的情况// root2不为null的时候，root1为null了，显然不匹配if(root1 == null){return false;} // root1和root2都不为空，但是数值不同，所以不匹配if(root1.val != root2.val){return false;}// 到这里说明这个点是匹配的，继续判断左子树和右子树是否匹配return HasSub(root1.left,root2.left) && HasSub(root1.right,root2.right);}
}

🎨 3、二叉树的镜像

牛客原题链接

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像

思路一（递归）

先把根节点的左右子树进行交换，再递归子树进行镜像，不断交换底下的左右节点

import java.util.*;/ public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * @param pRoot TreeNode类 * @return TreeNode类*/public TreeNode Mirror (TreeNode pRoot) {// write code here// 空树返回if(pRoot == null) return null;// 交换TreeNode temp = pRoot.left;pRoot.left = pRoot.right;pRoot.right = temp;// 递归Mirror(pRoot.left);Mirror(pRoot.right);return pRoot;}
}

🎨 4、顺时针打印矩阵

牛客原题链接

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：

[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]

则依次打印出数字

[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

思路一（边界模拟法）

import java.util.ArrayList;
public class Solution {public ArrayList<Integer> printMatrix(int [][] matrix) {ArrayList<Integer> res = new ArrayList<>();if(matrix.length == 0){return res;}// 左边界int left = 0;// 右边界int right = matrix[0].length - 1;// 上边界int up = 0;// 下边界int down = matrix.length - 1;while(left <= right && up <= down){// 上边界的从左到右for(int i = left; i <=right; i++){res.add(matrix[up][i]);}up++;if(up > down){break;}// 右边界的从上到下for(int i = up; i <= down; i++){res.add(matrix[i][right]);}right--;if(left > right){break;}// 下边界的从右到左for(int i = right; i >= left; i--){res.add(matrix[down][i]);}down--;if(up > down){break;}// 左边界的从下到上for(int i = down; i >= up; i--){res.add(matrix[i][left]);}left++;if(left > right){break;}}return res;}
}