代码随想录day04

day01 数组

Java JDK是17.0.11

35 34 69 367

26 283 844 977

904 76

54 剑指offer 29

1 数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

数组下标都是从0开始的。

数组内存空间的地址是连续的。

因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作。

数组的元素是不能删的，只能覆盖。

Java：二维数组在内存中不是连续的，每个子数组是独立的对象。

public class FundamentalsTheory {public static void main(String[] args) {testArr();}public static void testArr(){//初始化二维数组int[][] arr=new int[2][3];arr[0]=new int[]{1,2,3};arr[1]=new int[]{4,5,6};//输出地址for(int i=0;i< arr.length;i++){System.out.println("Subarray " + i + ": " + System.identityHashCode(arr[i]));for(int j=0;j<arr[i].length;j++){System.out.println(System.identityHashCode(arr[i][j])+" ");}System.out.println();}}
}

Subarray 0: 1324119927
1607521710 
363771819 
2065951873 Subarray 1: 1791741888
1595428806 
1072408673 
1531448569 

Java：二维数组在内存中不是连续的，每个子数组是独立的对象。

2 二分查找法

区间定义，一般是左闭右闭，左闭右开。

左闭右闭

力扣题目链接

package com.jiangxun.array;/*** @author jiangxun*/public class BinarySearch {/*** leetcode27* 左闭右闭* while(left<=right) 小于等于 当 left=right  [1,1] 区间合法。 mid=left+(right-left)/2。target是我们的目标值* if(nums[mid] > target)，nums[mid]不等于target，我的搜索区间包含right，而nums[mid]确定不是target，right = mid-1。* if(nums[mid] < target)，nums[mid]不等于target，我的搜索区间包含left，而nums[mid]确定不是target，left = mid+1。* if(nums[mid] = target)返回mid。否则返回-1；* 左闭右开* 注意right=nums.length* while(left < right) 小于 当 left=right  [1,1） 区间不合法。mid=left+(right-left)/2。target是我们的目标值* if(nums[mid] > target)，nums[mid]不等于target，我的搜索区间不包含right，right = mid。* if(nums[mid] < target)，nums[mid]不等于target，我的搜索区间包含left，所以left = mid+1。*/public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5};int target1 = 3;int target2 = 4;int result1 = search1(nums, target1);int result2 = search2(nums, target2);System.out.println("Index of " + target1 + " is: " + result1);System.out.println("Index of " + target2 + " is: " + result2);}public static int search1(int[] nums, int target) {int left=0;int 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;}else{return mid;}}//没找到return -1;}public static int search2(int[] nums, int target) {int left=0;//注意数组区间个数int right=nums.length;while(left<right){int mid=left+(right-left)/2;if (nums[mid]>target){right=mid;}else if(nums[mid]<target){left=mid+1;}else{return mid;}}//没找到return -1;}
}//时间复杂度：O(log n)
//空间复杂度：O(1)

3 移除元素

力扣题目链接

package com.jiangxun.array;/*** @author jiangxun*/
public class RemoveElement {public static void main(String[] args) {int[] nums = {3, 2, 2, 3};int val = 3;
//        int result1 = removeElement1(nums, val);
//        System.out.println("New length: " + result1);int result2 = removeElement2(nums, val);System.out.println("New length: " + result2);}/*** leetcode27* 移除数组中值为val的元素，返回 nums 中与 val 不同的元素的数量。* 快指针用来获取新数组中的元素，慢指针用来获取新数组中需要更新的位置* @param nums* @param val* @return*/public static int removeElement1(int[] nums, int val) {int fast=0;int slow=0;while(fast<nums.length){if(nums[fast]!=val){nums[slow]=nums[fast];slow++;}fast++;}return slow;}/*** 双向指针移动 一个指针从左向右移动，另一个指针从右向左移动，如果左指针指向的元素等于val，* 则将右指针指向的元素赋值给左指针指向的元素，右指针向左移动。* @param nums* @param val* @return*/public static int removeElement2(int[] nums, int val) {int left=0;int right=nums.length-1;while(left<=right){if(nums[left]==val){nums[left]=nums[right];right--;}else{left++;}}return left;}}

4 平方数

力扣题目链接

package com.jiangxun.array;import java.util.Arrays;/*** @author jiangxun*/
public class SortedSquares {public static void main(String[] args){int[] nums = {-4,-1,0,3,10};
//        int[] result = sortedSquares1(nums);int[] result = sortedSquares2(nums);for (int i : result){System.out.println(i);}}/*** 977 终于碰到简单的题了！* @param nums* @return*/public static int[] sortedSquares1(int[] nums){for (int i = 0; i < nums.length; i++) {nums[i] = nums[i] * nums[i];}Arrays.sort(nums);return nums;}/*** 初始化结果数组 result，长度与输入数组相同。* 使用两个指针 left 和 right 分别指向数组的起始和末尾。* 使用 pos 指向结果数组的末尾。* 在 while 循环中，比较 left 和 right 所指元素的平方值，将较大的平方值放入结果数组的 pos 位置，并移动相应的指针。* 重复上述步骤，直到所有元素都被处理完。* 返回结果数组。* @param nums* @return*/public static int[] sortedSquares2(int[] nums) {int n = nums.length;int[] result = new int[n];int left = 0;int right = n - 1;int pos = n - 1;while (left <= right) {int leftSquare = nums[left] * nums[left];int rightSquare = nums[right] * nums[right];if (leftSquare > rightSquare) {result[pos] = leftSquare;left++;} else {result[pos] = rightSquare;right--;}pos--;}return result;}
}

day02 数组

1 长度最小的子数组

介绍数组操作中另一个重要的方法：滑动窗口。

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

那么问题来了， 滑动窗口的起始位置如何移动呢？

这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0, sum = 0, minLen = Integer.MAX_VALUE;while (right < nums.length) {sum += nums[right];while (sum >= target) {minLen = Math.min(minLen, right - left + 1);sum -= nums[left];left++;}right++;}return minLen == Integer.MAX_VALUE ? 0 : minLen;}
}
//leetcode submit region end(Prohibit modification and deletion)

2 螺旋数组59

package com.jiangxun.leetcode.editor.cn;//<p>给你一个正整数&nbsp;<code>n</code> ，生成一个包含 <code>1</code> 到&nbsp;<code>n<sup>2</sup></code>&nbsp;所有元素，且元素按顺时针顺序螺旋排列的&nbsp;<code>n x n</code> 正方形矩阵 <code>matrix</code> 。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg" style="width: 242px; height: 242px;" /> 
//<pre>
//<strong>输入：</strong>n = 3
//<strong>输出：</strong>[[1,2,3],[8,9,4],[7,6,5]]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 1
//<strong>输出：</strong>[[1]]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= n &lt;= 20</code></li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>数组</li><li>矩阵</li><li>模拟</li></div></div><br><div><li>👍 1340</li><li>👎 0</li></div>//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[][] generateMatrix(int n) {int[][] nums = new int[n][n];//从1开始放数字int number = 1;//循环次数countint count = 1;//起点（x，y）,i是行，j是列int startX = 0;int startY = 0;int i=1;int j=1;//初始化偏移值设为 1，固定某一循环，每一次填充数量int offset = 1;/*** 3*3的矩阵* 第一次填充上部 1 2，第二次填充右侧 3 4 左闭右开* 第三次填充下部 5 6，第四次填充左部 7 8* （以此循环）填充 9*/while (count <= n / 2) {//上for (j = startY; j < n - offset; j++) {nums[i][j] = number++;}//右for (i = startX; i < n - offset; i++) {nums[i][j] = number++;}//下for(; j > startY; j--){nums[i][j] = number++;}//左for(; i > startX; i--){nums[i][j] = number++;}//更新起点startX++;startY++;//更新偏移值offset++;//更新循环次数count++;}//如果n是奇数，单独处理中间数字if(n % 2 == 1){nums[startX][startY] = number;}return nums;}
}
//leetcode submit region end(Prohibit modification and deletion)

package com.jiangxun.leetcode.editor.cn;//<p>给你一个正整数&nbsp;<code>n</code> ，生成一个包含 <code>1</code> 到&nbsp;<code>n<sup>2</sup></code>&nbsp;所有元素，且元素按顺时针顺序螺旋排列的&nbsp;<code>n x n</code> 正方形矩阵 <code>matrix</code> 。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg" style="width: 242px; height: 242px;" /> 
//<pre>
//<strong>输入：</strong>n = 3
//<strong>输出：</strong>[[1,2,3],[8,9,4],[7,6,5]]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 1
//<strong>输出：</strong>[[1]]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= n &lt;= 20</code></li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>数组</li><li>矩阵</li><li>模拟</li></div></div><br><div><li>👍 1340</li><li>👎 0</li></div>//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[][] generateMatrix(int n) {int[][] nums = new int[n][n];//从1开始放数字int number = 1;//循环次数countint count = 1;//起点（x，y）,i是行，j是列int startX = 0;int startY = 0;int i=1;int j=1;//初始化偏移值设为 1，固定某一循环，每一次填充数量int offset = 1;/*** 3*3的矩阵* 第一次填充上部 1 2，第二次填充右侧 3 4 左闭右开* 第三次填充下部 5 6，第四次填充左部 7 8* （以此循环）填充 9*/while (count <= n / 2) {//上for (j = startY; j < n - offset; j++) {i=startX;nums[i][j] = number++;}//右for (i = startX; i < n - offset; i++) {nums[i][j] = number++;}//下for(; j > startY; j--){nums[i][j] = number++;}//左for(; i > startX; i--){nums[i][j] = number++;}//更新起点startX++;startY++;//更新偏移值offset++;//更新循环次数count++;}//如果n是奇数，单独处理中间数字if(n % 2 == 1){nums[startX][startY] = number;}return nums;}
}
//leetcode submit region end(Prohibit modification and deletion)

58. 区间和

【题目描述】

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

【输入示例】

3 3 1 2 3 2 1 3 1 2 3

【输出示例】

0

【提示信息】

如果将区域按照如下方式划分：

1 2 | 3 2 1 | 3 1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

【数据范围】：

1 <= n, m <= 100；

n 和 m 不同时为 1。

#思路

看到本题，大家如果想暴力求解，应该是 n^3 的时间复杂度，

一个 for 枚举分割线， 嵌套 两个for 去累加区间里的和。

如果本题要求 任何两个行（或者列）之间的数值总和，大家在0058.区间和 的基础上 应该知道怎么求。

就是前缀和的思路，先统计好，前n行的和 q[n]，如果要求矩阵 a行 到 b行 之间的总和，那么就 q[b] - q[a - 1]就好。

至于为什么是 a - 1，大家去看 0058.区间和 的分析，使用 前缀和 要注意 区间左右边的开闭情况。

本题也可以使用 前缀和的思路来求解，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int sum = 0;int[][] vec = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {vec[i][j] = scanner.nextInt();sum += vec[i][j];}}// 统计横向int[] horizontal = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {horizontal[i] += vec[i][j];}}// 统计纵向int[] vertical = new int[m];for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) {vertical[j] += vec[i][j];}}int result = Integer.MAX_VALUE;int horizontalCut = 0;for (int i = 0; i < n; i++) {horizontalCut += horizontal[i];result = Math.min(result, Math.abs(sum - 2 * horizontalCut));}int verticalCut = 0;for (int j = 0; j < m; j++) {verticalCut += vertical[j];result = Math.min(result, Math.abs(sum - 2 * verticalCut));}System.out.println(result);scanner.close();}
}

day03 链表

单链表：链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的存储方式

了解完链表的类型，再来说一说链表在内存中的存储方式。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

接下来说一说链表的定义。

链表节点的定义，很多同学在面试的时候都写不好。

这是因为平时在刷leetcode的时候，链表的节点都默认定义好了，直接用就行了，所以同学们都没有注意到链表的节点是如何定义的。

而在面试的时候，一旦要自己手写链表，就写的错漏百出。

这里我给出C/C++的定义链表节点方式

public static class ListNode{// 节点上存储的元素int val; // 指向下一个节点的指针ListNode next; // 节点的构造函数ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}

203 移除链表元素

class Solution203 {public ListNode removeElements(ListNode head, int val) {ListNode dummyHead = new ListNode();dummyHead.next = head;ListNode cur = dummyHead;while (cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;} else {cur = cur.next;}}return dummyHead.next;}/*public ListNode removeElements(ListNode head, int val) {while(head!=null&&head.val==val){head=head.next;}ListNode cur=head;while(cur!=null && cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;}else {cur=cur.next;}}return head;}
*/
}

707 设计链表

class ListNode {int val;ListNode next;ListNode prev;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}ListNode(int val, ListNode next, ListNode prev) { // 构造函数新增 prev 参数this.val = val;this.next = next;this.prev = prev;}
}class MyLinkedList {//记录链表中元素的数量int size;//记录链表的虚拟头结点和尾结点ListNode head,tail;public MyLinkedList() {//初始化操作this.size = 0;this.head = new ListNode(0);this.tail = new ListNode(0);//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！head.next=tail;tail.prev=head;}public int get(int index) {//判断index是否有效if(index>=size){return -1;}ListNode cur = this.head;//判断是哪一边遍历时间更短if(index >= size / 2){//tail开始cur = tail;for(int i=0; i< size-index; i++){cur = cur.prev;}}else{for(int i=0; i<= index; i++){cur = cur.next;}}return cur.val;}public void addAtHead(int val) {//等价于在第0个元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等价于在最后一个元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于链表长度if(index>size){return;}size++;//找到前驱ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}//新建结点ListNode newNode = new ListNode(val);newNode.next = pre.next;pre.next.prev = newNode;newNode.prev = pre;pre.next = newNode;}public void deleteAtIndex(int index) {//判断索引是否有效if(index>=size){return;}//删除操作size--;ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}pre.next.next.prev = pre;pre.next = pre.next.next;}
}
/*class MyLinkedList {int size;*/
/*** 虚拟头节点*//*ListNode dummyHead;*/
/*** 初始化链表*//*public MyLinkedList() {size = 0;dummyHead = new ListNode();}public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode curNode = dummyHead;//包含虚拟头节点，找index+1个节点for (int i = 0; i < index + 1; i++) {curNode = curNode.next;}return curNode.val;}public void addAtHead(int val) {ListNode newNode=new ListNode(val);//先处理后面一条线，在处理前面的线newNode.next=dummyHead.next;dummyHead.next=newNode;size++;}public void addAtTail(int val) {ListNode newNode=new ListNode(val);//找到尾节点ListNode cur=dummyHead;while(cur.next!=null){cur = cur.next;}cur.next=newNode;size++;}*/
/*** addAtIndex(0, int val) 头插* addAtIndex(size, int val) 尾插* index>size，返回-1*//*public void addAtIndex(int index, int val) {if(index>size){return;}if(index<0){return;}//找到前驱节点ListNode predNode=dummyHead;for (int i=0;i<index;i++){predNode=predNode.next;}//创建待插入的新结点ListNode toAddNode=new ListNode(val);//先处理后一根线，再处理前面一个线toAddNode.next=predNode.next;predNode.next=toAddNode;//长度加一size++;}public void deleteAtIndex(int index) {if(index<0||index>=size){return;}//有虚拟头节点，不用考虑index=0；ListNode predNode=dummyHead;//找到前驱接节点for(int i=0;i<index;i++){predNode=predNode.next;}predNode.next=predNode.next.next;size--;}
}
*/

206 反转链表

day04 链表

24 两两交换链表中的节点

    public ListNode swapPairs(ListNode head) {// base case 退出提交if(head == null || head.next == null) return head;// 获取当前节点的下一个节点ListNode next = head.next;// 进行递归ListNode newNode = swapPairs(next.next);// 这里进行交换next.next = head;head.next = newNode;return next;}

19.删除链表的倒数第N个节点

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyNode = new ListNode(0);dummyNode.next = head;ListNode fast = dummyNode;ListNode slow = dummyNode;// 快慢指针差n个节点for (int i = 0; i <= n; i++) {fast=fast.next;}while (fast!=null){fast=fast.next;slow=slow.next;}if(slow.next!=null){slow.next=slow.next.next;}return dummyNode.next;}

面试题 02.07. 链表相交

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA, p2 = headB;while (p1 != p2) {if (p1 == null) p1 = headB;else            p1 = p1.next;if (p2 == null) p2 = headA;else            p2 = p2.next;}return p1;}
}

142. 环形链表 II

public class Solution {
public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {ListNode index1 = fast;ListNode index2 = head;while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}

总结

1. 链表理论基础
   链表是一种线性数据结构，但不像数组那样在内存中连续存储。链表由一系列节点组成，每个节点包含数据部分和一个指向列表中下一个节点的引用（或指针）。

2. 移除链表元素 (Remove Linked List Elements)
   题目要求移除链表中所有具有特定值的元素。可以通过遍历链表并检查每个节点的数据来实现。如果节点的数据等于给定值，就跳过该节点，即让前一个节点直接指向下一个节点。

3. 设计链表 (Design Linked List)
   题目要求实现一个单链表类，支持一些基本操作如获取、添加、删除节点等。通常需要定义一个内部的节点类，并且维护一个指向链表头部的指针。

4. 翻转链表 (Reverse Linked List)
   翻转链表是一个常见的面试题，可以通过迭代或递归的方式来解决。迭代方法中，我们需要三个指针分别用来记录当前节点、前一个节点和后一个节点。

5. 两两交换链表中的节点 (Swap Nodes in Pairs)
   这个题目要求以两个节点为一组进行交换。可以使用递归或迭代的方法来解决，关键在于正确地调整节点之间的连接关系。

6. 删除链表的倒数第N个节点 (Remove Nth Node From End of List)
   为了删除链表的倒数第N个节点，可以使用双指针技术。首先让第一个指针向前移动N步，然后同时移动两个指针直到第一个指针到达链表末尾。此时第二个指针所指向的就是要删除的节点。

7. 链表相交 (Intersection of Two Linked Lists)
   要找到两个链表的交点，可以先计算两个链表的长度，然后让较长的链表先走几步，使两个链表剩余长度相同。之后同步遍历两个链表，当遇到相同的节点时即为交点。

8. 环形链表II (Linked List Cycle II)
   检测链表中是否存在环，并返回环的起始节点。这通常通过快慢指针法实现，先用快慢指针检测环的存在，再通过数学方法找到环的入口。