这里写目录标题
- 1.数组部分
- 1.1二分查找
- 1.2移除元素
- 1.3 有序数组的平方
- 1.4长度最小的子数组
- 1.5螺旋矩阵II
- 2. 链表部分
- 2.1移除链表元素
- 2.2设计链表
- 2.3反转链表
- 2.4两两交换相邻的节点
- 2.5删除链表的倒数第n个节点
1.数组部分
1.1二分查找
class Solution {
public int search(int[] nums, int target) {
if(nums.length==0)return -1;
int l=0,r=nums.length-1;
while(l<=r){
int mid=l+r>>1;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
l=mid+1;
}else{
r=mid-1;
}
}
return -1;
}
}
1.2移除元素
class Solution {
//双指针算法
public int removeElement(int[] nums, int val) {
int i=0;//标记目前位置
for(int j=0;j<nums.length;j++){
if(nums[j]!=val){
nums[i]=nums[j];
i++;
}
}
return i;
}
}
1.3 有序数组的平方
class Solution {
public int[] sortedSquares(int[] nums) {
int n=nums.length;
int[] ans=new int[n];
int k=n-1;
int i=0,j=nums.length-1;
//类似于归并排序
while(i<=j){
if(nums[i]*nums[i]<nums[j]*nums[j]){
ans[k--]=nums[j]*nums[j];
j--;
}else{
ans[k--]=nums[i]*nums[i];
i++;
}
}
return ans;
}
}
1.4长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minlen=0x3f3f3f3f;
int sum=0;
int j=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
while(sum>=target){//缩小区间
minlen=Math.min(minlen,i-j+1);
sum-=nums[j];
j++;//
}
}
if(minlen==0x3f3f3f3f)return 0;
return minlen;
}
}
1.5螺旋矩阵II
class Solution {
static boolean[][] st;
public int[][] generateMatrix(int n) {
st=new boolean[n][n];
int[] dx={0,1,0,-1},dy={1,0,-1,0};
int[][] ans=new int[n][n];
int x=0,y=0,d=0;//横，纵坐标，转向指针
for(int i=1;i<=n*n;i++){
ans[x][y]=i;
st[x][y]=true;
int a=x+dx[d],b=y+dy[d];
if(a<0 || a>=n || b<0 || b>=n || st[a][b]){
d=(d+1)%4;
a=x+dx[d];
b=y+dy[d];
}
x=a;
y=b;
}
return ans;
}
}
2. 链表部分
2.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 removeElements(ListNode head, int val) {
if(head==null)return null;
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode cur=dummy;
while(cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
}else cur=cur.next;
}
return dummy.next;
}
}
2.2设计链表
2.3反转链表
/**
* 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 cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
2.4两两交换相邻的节点
/**
* 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 swapPairs(ListNode head) {
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode cur=dummy;
while(cur.next!=null && cur.next.next!=null){
ListNode a=cur.next;
ListNode b=cur.next.next;
cur.next=b;
a.next=b.next;
b.next=a;
cur=a;
}
return dummy.next;
}
}
2.5删除链表的倒数第n个节点
/**
* 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) {
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode cur=head;
int cnt=0;
while(cur!=null){
cnt++;
cur=cur.next;
}
cur=dummy;
cnt=cnt-n;
while(cnt-->0)cur=cur.next;
cur.next=cur.next.next;
return dummy.next;
}
}
