前言
本文属于特定的六道题目题解和调试代码。
1 ✔ [160]相交链表 Easy 2023-03-17 171
2 ✔ [54]螺旋矩阵 Medium 2023-03-17 169
3 ✔ [23]合并K个排序链表 Hard 2022-12-08 158
4 ✔ [92]反转链表 II Medium 2023-03-01 155
5 ✔ [415]字符串相加 Easy 2023-03-14 150
6 ✔ [142]环形链表 II Medium 2022-09-27 144
正所谓磨刀不误砍柴功。下面我做这几篇文档对于涉及的题型或者数据结构的分析都很有帮助，贴出来仅供参考。
如何调试递归程序，有何技巧？
按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)
1 ✔ [160]相交链表 Easy 2023-03-17 171
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
//
// 图示两个链表在节点 c1 开始相交：
//
//
//
// 题目数据 保证 整个链式结构中不存在环。
//
// 注意，函数返回结果后，链表必须 保持其原始结构 。
//
// 自定义评测：
//
// 评测系统 的输入如下（你设计的程序 不适用 此输入）：
//
//
// intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
// listA - 第一个链表
// listB - 第二个链表
// skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
// skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
//
//
// 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视
//作正确答案 。
//
//
//
// 示例 1：
//
//
//
//
//输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2,
//skipB = 3
//输出：Intersected at '8'
//解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
//在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
//— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内
//存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
//
//
//
//
// 示例 2：
//
//
//
//
//输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB =
//1
//输出：Intersected at '2'
//解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
//在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
//
//
// 示例 3：
//
//
//
//
//输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
//输出：null
//解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
//由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
//这两个链表不相交，因此返回 null 。
//
//
//
//
// 提示：
//
//
// listA 中节点数目为 m
// listB 中节点数目为 n
// 1 <= m, n <= 3 * 10⁴
// 1 <= Node.val <= 10⁵
// 0 <= skipA <= m
// 0 <= skipB <= n
// 如果 listA 和 listB 没有交点，intersectVal 为 0
// 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
//
//
//
//
// 进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
//
// Related Topics 哈希表 链表 双指针 👍 2020 👎 0
引用一下leetcode上对着道题目的神评论：走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
思路： 如果两个链表A B长度相等，两个指针a b 分别中A B的开头开始同步遍历，判断如果a b指向同一个节点，则相交，否者 两个指针同时走到结尾null，返回null即可。
那么如何保证A B长度相等或者消除它们之间的长度差？
通过 a b指针同时遍历，如果a走到头，这a再从B链表的开头开始走。这个时候a和b之间的距离就是A链表的长度，然后继续遍历直到b也走到尽头。这个时候a在B链表上到结尾的长度，和从A链表开始到结尾的长度相等。
然后让b从A链表的开头开始走，如果a 和b相等，这为相交的点。如果到尽头都没有相等，那么这个时候两个指针同时到尽头都等于null，也是相等，直接结束循环 返回null。
自测代码
public class P160_IntersectionOfTwoLinkedLists{
public static void main(String[] args) {
//测试代码
Solution solution = new P160_IntersectionOfTwoLinkedLists().new Solution();
ListNode listNode = new ListNode("[1,3,5,7,9,11,13,15,17,19,21]");
ListNode listNode1 = new ListNode("[2,1]");
System.out.println(solution.getIntersectionNode(listNode, listNode1));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b){
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b){
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
2 ✔ [54]螺旋矩阵 Medium 2023-03-17 169
//给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
//
//
//
// 示例 1：
//
//
//输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,3,6,9,8,7,4,5]
//
//
// 示例 2：
//
//
//输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
//输出：[1,2,3,4,8,12,11,10,9,5,6,7]
//
//
//
//
// 提示：
//
//
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 10
// -100 <= matrix[i][j] <= 100
//
//
// Related Topics 数组 矩阵 模拟 👍 1329 👎 0
纯手敲判断，
评论区一定会有更好的办法，这个时候我也纠结，到底应该去看最好的方法还是按照自己的思路做下去。（大人应该全都要吧 哈哈，不过我做出来就不想再去看别的方法了哎）
到底哪种收获更大？
自测代码
public class P54_SpiralMatrix{
public static void main(String[] args) {
//测试代码
Solution solution = new P54_SpiralMatrix().new Solution();
Integer[][] integers = ArrayUtil.StrToIntegerArray("[[2,3]]");
List<Integer> integers1 = solution.spiralOrder(integers);
System.out.println(PrintData.printArrayListToStrArray(integers1));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<Integer> spiralOrder(Integer[][] matrix) {
if (matrix == null) {
return null;
}
int len = matrix.length;
int length = matrix[0].length;
ArrayList<Integer> res = new ArrayList<>();
int x = 0;
int y = 0;
String direction = "右";
while (true){
res.add(matrix[x][y]);
matrix[x][y] = 111;
switch (direction){
case "右" : {
if (y+1 < length && matrix[x][y+1] != 111) {
y++;
}else if(x+1 <len && matrix[x+1][y] != 111){
direction = "下";
x++;
}else {
return res;
}
break;
}
case "下" : {
if (x+1 < len && matrix[x+1][y] != 111 ) {
x++;
}else if (y-1 >= 0 && matrix[x][y-1] != 111){
y--;
direction = "左";
}else {
return res;
}
break;
}
case "左" : {
if (0 <= y-1 && matrix[x][y-1] != 111 ) {
y--;
}else if (x-1 >= 0 && matrix[x-1][y] != 111){
x--;
direction = "上";
}else {
return res;
}
break;
}
case "上" : {
if (0 <= x-1 && matrix[x-1][y] != 111 ) {
x--;
}else if (y+1 < length && matrix[x][y+1] != 111){
y++;
direction = "右";
}else {
return res;
}
break;
}
}
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
if (matrix == null) {
return null;
}
int len = matrix.length;
int length = matrix[0].length;
ArrayList<Integer> res = new ArrayList<>();
int x = 0;
int y = 0;
String direction = "右";
while (true){
res.add(matrix[x][y]);
matrix[x][y] = 111;
switch (direction){
case "右" : {
if (y+1 < length && matrix[x][y+1] != 111) {
y++;
}else if(x+1 <len && matrix[x+1][y] != 111){
direction = "下";
x++;
}else {
return res;
}
break;
}
case "下" : {
if (x+1 < len && matrix[x+1][y] != 111 ) {
x++;
}else if (y-1 >= 0 && matrix[x][y-1] != 111){
y--;
direction = "左";
}else {
return res;
}
break;
}
case "左" : {
if (0 <= y-1 && matrix[x][y-1] != 111 ) {
y--;
}else if (x-1 >= 0 && matrix[x-1][y] != 111){
x--;
direction = "上";
}else {
return res;
}
break;
}
case "上" : {
if (0 <= x-1 && matrix[x-1][y] != 111 ) {
x--;
}else if (y+1 < length && matrix[x][y+1] != 111){
y++;
direction = "右";
}else {
return res;
}
break;
}
}
}
}
}
3 ✔ [23]合并K个排序链表 Hard 2022-12-08 158
//给你一个链表数组，每个链表都已经按升序排列。
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。
//
//
//
// 示例 1：
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
// 1->4->5,
// 1->3->4,
// 2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
//
//
// 示例 2：
//
// 输入：lists = []
//输出：[]
//
//
// 示例 3：
//
// 输入：lists = [[]]
//输出：[]
//
//
//
//
// 提示：
//
//
// k == lists.length
// 0 <= k <= 10^4
// 0 <= lists[i].length <= 500
// -10^4 <= lists[i][j] <= 10^4
// lists[i] 按 升序 排列
// lists[i].length 的总和不超过 10^4
//
//
// Related Topics 链表 分治 堆（优先队列） 归并排序 👍 2370 👎 0
自测代码
public class P23_MergeKSortedLists{
public static void main(String[] args) {
//测试代码
Solution solution = new P23_MergeKSortedLists().new Solution();
ListNode[] listNodes = ListNode.strToListNodeArray("[[1,4,5],[1,3,4],[2,6]]");
ListNode listNode = solution.mergeKLists(listNodes);
System.out.println(listNode.toString());
}
//力扣代码
//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 mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
int l = 0 ;
int r = lists.length-1;
while (l != r || r != 0){
if (l >= r) {
l = 0;
continue;
}
lists[l] = mergeKList(lists[l],lists[r]);
l++;
r--;
}
return lists[0];
}
public ListNode mergeKList(ListNode firster ,ListNode end ) {
ListNode heart = new ListNode(0);
ListNode mid = heart;
while ( firster != null || end != null){
if (firster == null) {
mid.next = end;
return heart.next;
}
if (end == null) {
mid.next = firster;
return heart.next;
}
if (firster.val < end.val) {
mid.next = firster;
firster = firster.next;
}else {
mid.next = end;
end = end.next;
}
mid = mid.next;
}
return heart.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
int l = 0 ;
int r = lists.length-1;
while (l != r || r != 0){
if (l >= r) {
l = 0;
continue;
}
lists[l] = mergeKList(lists[l],lists[r]);
l++;
r--;
}
return lists[0];
}
public ListNode mergeKList(ListNode firster ,ListNode end ) {
ListNode heart = new ListNode(0);
ListNode mid = heart;
while ( firster != null || end != null){
if (firster == null) {
mid.next = end;
return heart.next;
}
if (end == null) {
mid.next = firster;
return heart.next;
}
if (firster.val < end.val) {
mid.next = firster;
firster = firster.next;
}else {
mid.next = end;
end = end.next;
}
mid = mid.next;
}
return heart.next;
}
}
4 ✔ [92]反转链表 II Medium 2023-03-01 155
//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链
//表节点，返回 反转后的链表 。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
//
//
// 示例 2：
//
//
//输入：head = [5], left = 1, right = 1
//输出：[5]
//
//
//
//
// 提示：
//
//
// 链表中节点数目为 n
// 1 <= n <= 500
// -500 <= Node.val <= 500
// 1 <= left <= right <= n
//
//
//
//
// 进阶： 你可以使用一趟扫描完成反转吗？
//
// Related Topics 链表 👍 1523 👎 0
关于链表很经典的一道题目
解题思路大致分为两步，第一先找到所有特殊的点，比如要旋转的开头和结尾，前半部分的开头和结尾，后半部分的结尾， 找到之后拼接就可以
第二部分就是 将旋转部分 旋转，这个可以看看旋转列表，很简单的思路，直接旋转，然后各个节点拼接，思路还是比较清晰的
自测代码
public class P92_ReverseLinkedListIi{
public static void main(String[] args) {
//测试代码
Solution solution = new P92_ReverseLinkedListIi().new Solution();
ListNode listNode = new ListNode("[1,2,3,4,5]");
/*旋转链表*/
ListNode l = null;
ListNode r = listNode;
// ListNode temp= null;
// while (r != null) {
// temp = r.next;
// r.next = l;
// l = r;
// r = temp;
// }
// System.out.println(l.toString());
System.out.println(solution.reverseBetween(listNode,2,4).toString());
}
//力扣代码
//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 reverseBetween(ListNode head, int left, int right) {
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
ListNode heart = new ListNode(0);
/*排序完成后的开头*/
heart.next = head;
/*排序完成后的中间旋转位置前端的结尾*/
ListNode heartEnd = heart;
/*排序完成后的中间旋转部分结尾*/
ListNode midEnd ;
/*排序完成后的中间旋转部分开头*/
ListNode midHeart = null ;
/*排序完成后的中间旋转部分后面的开头*/
ListNode end = heart ;
for (int i = 0; i < left-1; i++) {
head = head.next;
heartEnd = heartEnd.next;
}
midEnd = heartEnd.next;
midHeart = midEnd;
end = midHeart.next;
ListNode temp= null;
for (int i = 0; i < right-left ; i++) {
temp = end.next;
end.next = midHeart ;
midHeart = end;
end = temp;
}
heartEnd.next = midHeart;
midEnd.next = end;
return heart.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
ListNode heart = new ListNode(0);
/*排序完成后的开头*/
heart.next = head;
/*排序完成后的中间旋转位置前端的结尾*/
ListNode heartEnd = heart;
/*排序完成后的中间旋转部分结尾*/
ListNode midEnd ;
/*排序完成后的中间旋转部分开头*/
ListNode midHeart = null ;
/*排序完成后的中间旋转部分后面的开头*/
ListNode end = heart ;
for (int i = 0; i < left-1; i++) {
head = head.next;
heartEnd = heartEnd.next;
}
midEnd = heartEnd.next;
midHeart = midEnd;
end = midHeart.next;
ListNode temp= null;
for (int i = 0; i < right-left ; i++) {
temp = end.next;
end.next = midHeart ;
midHeart = end;
end = temp;
}
heartEnd.next = midHeart;
midEnd.next = end;
return heart.next;
}
}
5 ✔ [415]字符串相加 Easy 2023-03-14 150
//给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
//
// 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
//
//
//
// 示例 1：
//
//
//输入：num1 = "11", num2 = "123"
//输出："134"
//
//
// 示例 2：
//
//
//输入：num1 = "456", num2 = "77"
//输出："533"
//
//
// 示例 3：
//
//
//输入：num1 = "0", num2 = "0"
//输出："0"
//
//
//
//
//
//
// 提示：
//
//
// 1 <= num1.length, num2.length <= 10⁴
// num1 和num2 都只包含数字 0-9
// num1 和num2 都不包含任何前导零
//
//
// Related Topics 数学 字符串 模拟 👍 696 👎 0
自测代码
public class P415_AddStrings{
public static void main(String[] args) {
//测试代码
Solution solution = new P415_AddStrings().new Solution();
solution.addStrings("584","18");
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String addStrings(String num1, String num2) {
int len = num1.length();
int len2 = num2.length();
int sgin = 0;
StringBuffer stringBuffer = new StringBuffer();
while (len>0||len2>0){
if (len <= 0) {
int i = Integer.parseInt(String.valueOf(num2.charAt(--len2)));
stringBuffer.append( (i +sgin) %10 ) ;
sgin = (i +sgin) /10;
continue;
}
if (len2 <= 0) {
int i = Integer.parseInt(String.valueOf(num1.charAt(--len)));
stringBuffer.append( (i +sgin) %10 ) ;
sgin = (i +sgin) /10;
continue;
}
char c = num1.charAt(--len);
int int1 = Integer.parseInt(String.valueOf(c));
int int2 = Integer.parseInt(String.valueOf(num2.charAt(--len2)));
stringBuffer.append( (int1+int2+sgin)%10 );
sgin = (int1+int2+sgin)/10;
}
if (1 == sgin) {
stringBuffer.append(sgin);
}
return stringBuffer.reverse().toString();
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public String addStrings(String num1, String num2) {
int len = num1.length();
int len2 = num2.length();
int sgin = 0;
StringBuffer stringBuffer = new StringBuffer();
while (len>0||len2>0){
if (len <= 0) {
int i = Integer.parseInt(String.valueOf(num2.charAt(--len2)));
stringBuffer.append( (i +sgin) %10 ) ;
sgin = (i +sgin) /10;
continue;
}
if (len2 <= 0) {
int i = Integer.parseInt(String.valueOf(num1.charAt(--len)));
stringBuffer.append( (i +sgin) %10 ) ;
sgin = (i +sgin) /10;
continue;
}
char c = num1.charAt(--len);
int int1 = Integer.parseInt(String.valueOf(c));
int int2 = Integer.parseInt(String.valueOf(num2.charAt(--len2)));
stringBuffer.append( (int1+int2+sgin)%10 );
sgin = (int1+int2+sgin)/10;
}
if (1 == sgin) {
stringBuffer.append(sgin);
}
return stringBuffer.reverse().toString();
}
}
6 ✔ [142]环形链表 II Medium 2022-09-27 144
//给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
// 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到
//链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
//
// 不允许修改 链表。
//
//
//
//
//
//
// 示例 1：
//
//
//
//
//输入：head = [3,2,0,-4], pos = 1
//输出：返回索引为 1 的链表节点
//解释：链表中有一个环，其尾部连接到第二个节点。
//
//
// 示例 2：
//
//
//
//
//输入：head = [1,2], pos = 0
//输出：返回索引为 0 的链表节点
//解释：链表中有一个环，其尾部连接到第一个节点。
//
//
// 示例 3：
//
//
//
//
//输入：head = [1], pos = -1
//输出：返回 null
//解释：链表中没有环。
//
//
//
//
// 提示：
//
//
// 链表中节点的数目范围在范围 [0, 10⁴] 内
// -10⁵ <= Node.val <= 10⁵
// pos 的值为 -1 或者链表中的一个有效索引
//
//
//
//
// 进阶：你是否可以使用 O(1) 空间解决此题？
//
// Related Topics 哈希表 链表 双指针 👍 2022 👎 0
[160]相交链表 Easy 2023-03-17 171 这道题那个题解思路的解释：
走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
让我对链表相关的题目都有了很深的印象，基本都是找关键节点，快慢指针，旋转链表这几个解决思路
自测代码
public class P142_LinkedListCycleIi{
public static void main(String[] args) {
//测试代码
Solution solution = new P142_LinkedListCycleIi().new Solution();
ListNode listNode = new ListNode("[1]");
// listNode.next.next = listNode;
System.out.println(solution.detectCycle(listNode).toString());
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode res = head;
ListNode l = res;
while (res !=null && res.next != null){
res = res.next.next;
l = l.next;
if (res == l) {
res = head;
while (true){
if (res == l) {
return res;
}
res = res.next;
l = l.next;
}
}
}
return null;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode res = head;
ListNode l = res;
while (res !=null && res.next != null){
res = res.next.next;
l = l.next;
if (res == l) {
res = head;
while (true){
if (res == l) {
return res;
}
res = res.next;
l = l.next;
}
}
}
return null;
}
}
发表于 2023-3-31 09:46
