前言
本文属于特定的六道题目题解和调试代码。
1 ✔ [300]最长上升子序列 Medium 2023-03-17 143
2 ✔ [42]接雨水 Hard 2023-03-18 139
3 ✔ [143]重排链表 Medium 2023-03-16 124
4 ✔ [124]二叉树中的最大路径和 Hard 2023-03-16 123
5 ✔ [94]二叉树的中序遍历 Easy 2023-03-17 118
6 ✔ [19]删除链表的倒数第N个节点 Medium 2023-03-08 116
正所谓磨刀不误砍柴功。下面我做这几篇文档对于涉及的题型或者数据结构的分析都很有帮助，贴出来仅供参考。
如何调试递归程序，有何技巧？
按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)
1 ✔ [300]最长上升子序列 Medium 2023-03-17 143
//给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
//
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子
//序列。
//
// 示例 1：
//
//
//输入：nums = [10,9,2,5,3,7,101,18]
//输出：4
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
//
//
// 示例 2：
//
//
//输入：nums = [0,1,0,3,2,3]
//输出：4
//
//
// 示例 3：
//
//
//输入：nums = [7,7,7,7,7,7,7]
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 2500
// -10⁴ <= nums[i] <= 10⁴
//
//
//
//
// 进阶：
//
//
// 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
//
//
// Related Topics 数组 二分查找 动态规划 👍 3074 👎 0
我总觉得利用二叉树也可以做，二分查找是不是和二叉树有一定的关系？
解题思路： 知道题目提示用动态规划做和二分查找做
动态规划： 分析原问题=》查找相关子问题 =》 确定子问题和原问题的关系 =》 解决子问题 =》 解决原问题。
子问题 ： 计算以i结尾的最长子序列，i从0开始到数组长度。
通过一个数组记录下来每个位置结尾时的最长子序列长度。
关系： 第i个值结尾的最长子序列就是，0-i之前比他小的值的最长子序列上+1；
遍历完成后，直接从记录的数组中找到最大值即可。或者用一个字段始终保留最大值。
上面的解法时间复杂度为 O（n*n）
这道题目的进阶要求 时间复杂度为O(n log(n)) 我觉得利用二叉树也可以做，但是还没有想明白
上面的解题方式算是贪心算法
换一种角度看问题，
创建一个数组res，数组的下标+1 保留的值，表示子序列长度为 index+1 时，子序列末尾的最小值
这样做其实是用了假设：保存了两个重要信息，一个时子序列长度，一个是末尾的值，因为子序列是递增的，末尾的值就是最大值。
- 假设目前的这个长度的值的最后一位的最小值就是我们保留的值
- 当出现一个新值的时候，如果比数组刚加入的值大，我们可以直接添加到数组里，也就是总长度加1时，子序列最后以为就是新进来的值。
- 当新来的值比保存数组中的值小时，利用数组的单调递增特性，利用二分法找到 证明用这个值可以替换res中第一个比它大的值
自测代码
public class P300_LongestIncreasingSubsequence{
public static void main(String[] args) {
//测试代码
Solution solution = new P300_LongestIncreasingSubsequence().new Solution();
solution.lengthOfLIS(ArrayUtil.StrToIntArray("[1,2,-10,-8,-7]"));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null) {
return 0;
}
int len = nums.length;
int[] res = new int[len];
res[0] = nums[0];
int resi = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > res[resi-1]) {
res[resi++] = nums[i];
}else if (nums[i] < res[resi -1]){
binarySearch(res,resi,nums[i]);
}
}
return resi;
}
/*二分查找*/
public void binarySearch(int[] nums,int len ,int data){
int l = 0 ;
int r = len;
while (l <= r){
int mid = (l + r) / 2;
if (nums[mid] == data) {
return;
}else if (nums[mid] > data){
if ( mid -1 < 0 || nums[mid-1] < data){
nums[mid] = data;
return;
}
r = mid-1;
}else {
if (mid +1 >= len || nums[mid+1] > data){
nums[mid+1] = data;
return;
}
l = mid+1;
}
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null) {
return 0;
}
int len = nums.length;
int[] res = new int[len];
res[0] = nums[0];
int resi = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > res[resi-1]) {
res[resi++] = nums[i];
}else if (nums[i] < res[resi -1]){
binarySearch(res,resi,nums[i]);
}
}
return resi;
}
/*二分查找*/
public void binarySearch(int[] nums,int len ,int data){
int l = 0 ;
int r = len;
while (l <= r){
int mid = (l + r) / 2;
if (nums[mid] == data) {
return;
}else if (nums[mid] > data){
if ( mid -1 < 0 || nums[mid-1] < data){
nums[mid] = data;
return;
}
r = mid-1;
}else {
if (mid +1 >= len || nums[mid+1] > data){
nums[mid+1] = data;
return;
}
l = mid+1;
}
}
}
}
2 ✔ [42]接雨水 Hard 2023-03-18 139
//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// 1 <= n <= 2 * 10⁴
// 0 <= height[i] <= 10⁵
//
//
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 4209 👎 0
看着题目的实例思考了良久
抓住一个现象，所有可以存储雨水的地方都是不单调的。也就是说雨水灌满之后，会出现单调递增或者单调递减，或者先递增再递减的情况
所以先用双指针从0开始标记所有不递增且后一个指针值比前一个大的区域，
全部填充上前一个指针的值，差值就是雨水。
然后通过记录的最大数的下标。
从len-1递减到最大数的下标，标记所有不递增的区域，再次填充。
两次填充的值就是存储的雨水。
自测代码
public class P42_TrappingRainWater {
public static void main(String[] args) {
//测试代码
Solution solution = new P42_TrappingRainWater().new Solution();
System.out.println(solution.trap(ArrayUtil.StrToIntArray("[4,2,3]")));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int trap(int[] height) {
int len = height.length;
int max = 0;
int res = 0;
int l = 0 ;
boolean sgin = true;
/*单调递增栈*/
Stack<Integer> increase = new Stack<>();
for (int i = 1; i < len; i++) {
if (height[max] <= height[i]) {
max = i;
}
if (height[i] < height[l]) {
sgin = false;
}else {
for (int i1 = l+1; i1 < i; i1++) {
res += (height[l] - height[i1]);
height[i1] = height[l];
}
l = i-1;
sgin = true;
}
if (sgin) {
l++;
}
}
l = len-1;
for (int i = len-2; i >= max; i--) {
if (height[i] < height[l]) {
sgin = false;
}else {
for (int i1 = l-1; i1 > i; i1--) {
res += (height[l] - height[i1]);
height[i1] = height[l];
}
l = i+1;
sgin = true;
}
if (sgin) {
l--;
}
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int trap(int[] height) {
int len = height.length;
int max = 0;
int res = 0;
int l = 0 ;
boolean sgin = true;
/*单调递增栈*/
Stack<Integer> increase = new Stack<>();
for (int i = 1; i < len; i++) {
if (height[max] <= height[i]) {
max = i;
}
if (height[i] < height[l]) {
sgin = false;
}else {
for (int i1 = l+1; i1 < i; i1++) {
res += (height[l] - height[i1]);
height[i1] = height[l];
}
l = i-1;
sgin = true;
}
if (sgin) {
l++;
}
}
l = len-1;
for (int i = len-2; i >= max; i--) {
if (height[i] < height[l]) {
sgin = false;
}else {
for (int i1 = l-1; i1 > i; i1--) {
res += (height[l] - height[i1]);
height[i1] = height[l];
}
l = i+1;
sgin = true;
}
if (sgin) {
l--;
}
}
return res;
}
}
3 ✔ [143]重排链表 Medium 2023-03-16 124
//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//
//L0 → L1 → … → Ln - 1 → Ln
//
//
// 请将其重新排列后变为：
//
//
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//
//
// 示例 1：
//
//
//
//
//输入：head = [1,2,3,4]
//输出：[1,4,2,3]
//
// 示例 2：
//
//
//
//
//输入：head = [1,2,3,4,5]
//输出：[1,5,2,4,3]
//
//
//
// 提示：
//
//
// 链表的长度范围为 [1, 5 * 10⁴]
// 1 <= node.val <= 1000
//
//
// Related Topics 栈 递归 链表 双指针 👍 1165 👎 0
思路想到了
但是最后把链表最后一位的下一个指针为null没有想到，看到链表的里的各个节点也混乱了。
链表里的节点添加到线性表之后，依然保留原来的关系，属于引用传递
自测代码
public class P143_ReorderList{
public static void main(String[] args) {
//测试代码
Solution solution = new P143_ReorderList().new Solution();
solution.reorderList(new ListNode("[1,2,3,4,5]"));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ArrayList<ListNode> listNodes = new ArrayList<>();
ListNode l = head;
while (l != null) {
listNodes.add(l);
l = l.next;
}
int left = 0;
int right = listNodes.size()-1;
// [1,2,3,4]
while (left < right){
ListNode listNode = listNodes.get(left);
listNode.next = listNodes.get(right);
left++;
if (left == right){
break;
}
listNodes.get(right--).next = listNodes.get(left);
}
listNodes.get(left).next = null;
System.out.println(head.toString());
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ArrayList<ListNode> listNodes = new ArrayList<>();
ListNode l = head;
while (l != null) {
listNodes.add(l);
l = l.next;
}
int left = 0;
int right = listNodes.size()-1;
// [1,2,3,4]
while (left < right){
ListNode listNode = listNodes.get(left);
listNode.next = listNodes.get(right);
left++;
if (left == right){
break;
}
listNodes.get(right--).next = listNodes.get(left);
}
listNodes.get(left).next = null;
System.out.println(head.toString());
}
}
4 ✔ [124]二叉树中的最大路径和 Hard 2023-03-16 123
//路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不
//一定经过根节点。
//
// 路径和 是路径中各节点值的总和。
//
// 给你一个二叉树的根节点 root ，返回其 最大路径和 。
//
//
//
// 示例 1：
//
//
//输入：root = [1,2,3]
//输出：6
//解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
//
// 示例 2：
//
//
//输入：root = [-10,9,20,null,null,15,7]
//输出：42
//解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
//
//
//
//
// 提示：
//
//
// 树中节点数目范围是 [1, 3 * 10⁴]
// -1000 <= Node.val <= 1000
//
//
// Related Topics 树 深度优先搜索 动态规划 二叉树 👍 1890 👎 0
问题的纠结点在于，应该返回经过这个节点的最大值，还是这个节点是顶点的最大值
解决办法，返回经过该节点的最大值，
另外通过一个变量记录这个节点是顶点的最大值，遇到更大的则更新
自测代码
public class P124_BinaryTreeMaximumPathSum{
public static void main(String[] args) {
//测试代码
Solution solution = new P124_BinaryTreeMaximumPathSum().new Solution();
TreeNode treeNode = new TreeNode("[1,2,3]");
TreeNode.TreeNodeshow(treeNode);
System.out.println(solution.maxPathSum(new TreeNode("[1,2,3]")));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int res = Integer.MIN_VALUE ;
public int maxPathSum(TreeNode root) {
max(root);
return res;
}
public int max(TreeNode root){
if (root == null) {
return 0;
}
/*问题的纠结点在于，应该返回经过这个节点的最大值，还是这个节点是顶点的最大值*/
/*解决办法，返回经过该节点的最大值，另外通过一个变量记录左右节点和本身的值，遇到更大的则更新*/
int val = root.val;
int left = max(root.left);
int right = max(root.right);
left = left >= 0 ? left : 0;
right = right >= 0 ? right : 0;
int max = Math.max(left, right);
this.res = Math.max(this.res,left+right+val);
return max + val;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
int res = Integer.MIN_VALUE ;
public int maxPathSum(TreeNode root) {
max(root);
return res;
}
public int max(TreeNode root){
if (root == null) {
return 0;
}
/*问题的纠结点在于，应该返回经过这个节点的最大值，还是这个节点是顶点的最大值*/
/*解决办法，返回经过该节点的最大值，另外通过一个变量记录左右节点和本身的值，遇到更大的则更新*/
int val = root.val;
int left = max(root.left);
int right = max(root.right);
left = left >= 0 ? left : 0;
right = right >= 0 ? right : 0;
int max = Math.max(left, right);
this.res = Math.max(this.res,left+right+val);
return max + val;
}
}
5 ✔ [94]二叉树的中序遍历 Easy 2023-03-17 118
//给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
//
//
//
// 示例 1：
//
//
//输入：root = [1,null,2,3]
//输出：[1,3,2]
//
//
// 示例 2：
//
//
//输入：root = []
//输出：[]
//
//
// 示例 3：
//
//
//输入：root = [1]
//输出：[1]
//
//
//
//
// 提示：
//
//
// 树中节点数目在范围 [0, 100] 内
// -100 <= Node.val <= 100
//
//
//
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
//
// Related Topics 栈 树 深度优先搜索 二叉树 👍 1749 👎 0
利用这篇文章
按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)
自测代码
public class P94_BinaryTreeInorderTraversal{
public static void main(String[] args) {
//测试代码
Solution solution = new P94_BinaryTreeInorderTraversal().new Solution();
TreeNode treeNode = new TreeNode("[1,null,2,3]");
TreeNode.TreeNodeShow(treeNode);
List<Integer> integers = solution.inorderTraversal(treeNode);
System.out.println(PrintData.printArrayListToStr(integers));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
arry(root,list);
return list;
}
public void arry(TreeNode root,ArrayList<Integer> list){
if (root == null) {
return;
}
arry(root.left,list);
list.add(root.val);
arry(root.right,list);
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
arry(root,list);
return list;
}
public void arry(TreeNode root,ArrayList<Integer> list){
if (root == null) {
return;
}
arry(root.left,list);
list.add(root.val);
arry(root.right,list);
}
}
6 ✔ [19]删除链表的倒数第N个节点 Medium 2023-03-08 116
//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
//
//
// 示例 2：
//
//
//输入：head = [1], n = 1
//输出：[]
//
//
// 示例 3：
//
//
//输入：head = [1,2], n = 1
//输出：[1]
//
//
//
//
// 提示：
//
//
// 链表中结点的数目为 sz
// 1 <= sz <= 30
// 0 <= Node.val <= 100
// 1 <= n <= sz
//
//
//
//
// 进阶：你能尝试使用一趟扫描实现吗？
//
// Related Topics 链表 双指针 👍 2467 👎 0
这道题发现一个问题
我们把head赋值给left.next后
再把left.next变成null之后，head不会变成null。
但是我们如果修改到head里面的值为null时，
head里面的null也会被修改。
Java是值传递。当传的是基本类型时，传的是值的拷贝，对拷贝变量的修改不影响原变量；当传的是引用类型时，传的是引用地址的拷贝，但是拷贝的地址和真实地址指向的都是同一个真实数据，因此可以修改原变量中的值；当传的是String类型时，虽然拷贝的也是引用地址，指向的是同一个数据，但是String的值不能被修改，因此无法修改原变量中的值。
但是这种临界点 修改的时候却不会修改引用地址里的值。
自测代码
public class P19_RemoveNthNodeFromEndOfList{
public static void main(String[] args) {
//测试代码
Solution solution = new P19_RemoveNthNodeFromEndOfList().new Solution();
solution.removeNthFromEnd(new ListNode("[1]"),1);
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode left = new ListNode(0);
left.next = head;
ListNode res = left;
ListNode right = head;
while (n-- > 0 ){
right = right.next;
}
while (right != null)
{
right = right.next;
left = left.next;
}
if (left.next != null) {
left.next = left.next.next;
}
return res.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode left = new ListNode(0);
left.next = head;
ListNode res = left;
ListNode right = head;
while (n-- > 0 ){
right = right.next;
}
while (right != null)
{
right = right.next;
left = left.next;
}
if (left.next != null) {
left.next = left.next.next;
}
return res.next;
}
}
发表于 2023-4-3 10:20
