代码随想录打卡Day1

day01

Java JDK是17.0.11

1 数组理论基础

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

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

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

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

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

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

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

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;}
}