2022-12-01
一.数组
基本概念
数组是连续存放在内存空间上的相同数据类型的集合
数组的下标都是从零开始的
数组的内存空间地址是连续的，因此字删除或添加数组的时候需要移动其他数组的地址。
二分查找
题目：在一个无重复有且升序的数组中找到目标元素target，并返回数组下标。
二分查找法重点：
满足条件：有序的数组，数组中没有重复的元素存在
主要是区间的定义：
两种写法：
左闭右闭区间
左闭右闭区间：[left,right]
//伪代码
//因为是左闭右闭区间，所以意味着返回的数组下标在[left,right]中，所以当定义右边界值时，right应该等于数组长度减一
int left=0,int right=nums.length-1;
while(left<=right){ //这里判断等式在你定义的区间中是否成立，区间中包含了left和right的值，所以等式成立
int mid=(left+right)/2; //两个int类型相加，有可能会溢出（left+（right-left）/2
if(nums[mid]>target){
right=mid-1; //当中间值大于目标值时，意味着目标值在区间的左边，所以重新定义区间时，此时上一个区间中已经包含了mid(因为是右闭区间，所以已经包含了mid)，再次定义区间的时候，right=mid-1；
}else if(nums[mid]<target){
left=mid+1; //同理
}else {
return mid;
}
}
return -1; //数组中不存在目标值
java左闭右开区间
左闭右开区间：[left,right)
//伪代码
//定义区间是左闭右开区间，意味着数组下标在[left,right)之间,right应该为数组的长度
int left=0,right=nums.lenth;
while(left<right){//这里等式取不取等于取决于你选择的区间范围，通过区间范围判断等式是否成立，因为这里是左闭右开区间，right的值是取不到的所以不能加等于
int mid=(left+right)/2;
if(nums[mid]>target){ //当中间值大于目标值时，意味着目标值在区间的左边，所以重新定义区间时，此时上一个区间中没有包含mid(因为是右开区间，所以没有包含mid)，再次定义区间的时候，right=mid；
right=mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
return mid;
}
return -1;
}
java35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
java移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/remove-element 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
双指针实现
因为在数组中实现删除元素的操作，本质上是将元素给覆盖掉，即将删除元素的后面元素向前移动一位
代码实现双指针：
//伪代码
int low;//定义一个慢指针，用来存新数组的下标
for(int fast=0;fast<nums.length;i++){
if(nums[fast]!=target){
nums[low]=num[fast]; //将值赋值给新数组
low++;
}
}
return low;//返回新数组长度
java997.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
暴力破解
public int[] sortedSquares(int[] nums) {
int[] reslut=new int[nums.length];
for(int i=0;i<nums.length;i++){
reslut[i]=nums[i]*nums[i];
}
Arrays.sort(reslut);
return reslut;
}
java双指针
int j=nums.length-1;
int k=nums.length-1;
int i=0;
int[] result=new int[nums.length];
while (i <= j) {
if(nums[i]*nums[i]<nums[j]*nums[j]){
result[k--]=nums[j]*nums[j];
j--;
}else{
result[k--]=nums[i]*nums[i];
i++;
}
}
return result;
}
java二.链表
基本概念
单链表
链表是通过指针串联起来的一个线性结构，每一个节点有两部分组成：指针域（存放指向下一个节点的指针）和数值域，其中最后一个节点指向空指针。
双链表
单链表中指针只能指向下一个节点
双链表中指针有两个指针域，一个指向上一个节点，一个指向下一个节点，双链表既可以向前查询又可以向后查询。
循环链表
链表首部和尾部相连，循环链表可以用来解决约瑟夫环问题。
链表的存储方式
数组在内存中是连续存储的，链表不是，链表是通过指针连接内存中的各个节点，所以链表的节点在内存中是可以不连续存储的
链表的定义
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
java203.移除链表元素
删除链表中等于给定值 val 的所有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
代码示例
//伪代码
public ListNode removeElements(ListNode head, int val) {
//在头结点前面定义一个虚拟头结点dummy
ListNode dummy= new ListNode(-1,head);
ListNode pre=dummy;
while(head!=null){//遍历链表直到（指针域指向最后一个位置的时候指针为空）
if(head.val==val){//取原头结点的值与目标值相比较
pre.next=head.next;/*相等移除元素，将虚拟节点的指针指向原结点的下一个位置*/
}else{
pre=head;//不相等就将节点的指针域给当前指针域的位置
}
head=head.next;//链表指向下一个位置再次比较
}
}
java707.设计链表
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
代码实现：
/**自定义链表结构
*/
class ListNode{
int val;//值
ListNode next;//指针域
public ListNode(){}
public ListNode(int val){
this.val=val;
}
}
class MyLinkedList {
int size;
ListNode head; //定义一个虚拟头结点
public MyLinkedList() {
size=0;
head=new ListNode(0);
}
public int get(int index) {
if(index<0 || index>=size){ /*index是链表节点，第零个节点是头结点，而Size是链表长度，所以当index等于size时index的数值也不合法*/
return -1;
}
ListNode pre=head;
//取得需要查询的当前节点的指针域位置
for(int i=0;i<=index;i++){
pre=pre.next;
}
return pre.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if(index<=0){
index=0;
}
if(index>size){//等于size的时候，插入尾部节点所以可以取到size的值
return;
}
size++;
ListNode pre=head;
ListNode addval=new ListNode(val);
for(int i=0;i<index;i++){
pre=pre.next;//找到目标值前一个指针域
}
addval.next=pre.next;
pre.next=addval;
}
public void deleteAtIndex(int index) {
if(index>=0 && index<size){
ListNode pre=head;
//找到目标值前一个指针域
for(int i=0;i<index;i++){
pre=pre.next;
}
size--;
//将指针域给下下个节点
pre.next=pre.next.next;
}else{
return ;
}
}
}
java206.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
代码实现
/**
* 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 reverseList(ListNode head) {
ListNode pre=null;
ListNode temp=null; //作为临时指针存放cur的下一个节点
ListNode cur=head;
while(cur!=null){
temp=cur.next;//先将cur的下一个指针存放在临时链表temp
//链表反转
cur.next=pre;
pre=cur;
//将cur重新赋值到原链表的头结点上
cur=temp;
}
return pre;
}
}
java本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-12-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
