基础算法题目

leetcode是个很好的算法题网站

时间复杂度的基本类型：

O(1):常熟复杂度 O(log n):对数复杂度 O(n):线性事件复杂度 O(n^2):平方

O(n^3):立方 O（2^n）:指数 O(n！)：阶乘

实例：移动零：（0，1，0，2，5） 把0移动到后面去 （此题是一维坐标的交替变换）

public void movezeroes(int [] nums){

int j=0 新加入的下标元素j 代表只要是非零元素那么就赋值到j上

for (int i=0;i<nums.length;++i){

if

(nums[i]!=0){ 判断第一数字开始是不是不是0

nums[j]=nums[i] 不是0就把i的值赋给j if (i!=j){ nums[i]=0 然后让i为0

}

j++ j继续往后走

}

}

}

盛水最多容器问题 （最优解） 也是两个坐标i j 时间复杂度：O(n^2)

public int maxarea(int [] a){

int

max=0 初始化最大值

for(int

i=0;j=a.length-1;i<j;){ 定义最右边j

int

minHeight=a[i]<a[j]?a[i]++:a[j]-- 左右柱子哪个高 左边高i右移 右边高j左移

int

area=(j-i+1) * minHeight 求以柱子较矮的为主的面积

max=Math.max(max,area) 更细max

}

return max

}

（第二种解法） 时间复杂度：O(n) 左右夹逼

public int maxarea(int [] h){

int

maxarea=0,int l=0,int r=h.length-1; 定义最左指针l 最有指针r 初始化面积

while(l<r){ maxarea=Math.max(maxarea,Math.min(h[l],h[r])*(r-l)); 只要左指针在右指针左面 就计算每次移动的指针的面积 } if(h[l]<h[r]) h++;else l--;

retrun maxarea;

}

爬楼梯问题 递推法 F(0)=0 F(1)=1 F(2)=1 F(n)=F(n-1)+F(n-2)(也是斐波那契法 及即Fibonacci) 时间复杂度：O（1）

public int jumpFloor(int i){

if(n==0) return -1; if(n==1||n==2) return n; else int

f1=1;

int

f2=2;

int

f3=3;

for(i=0;i<n;i++){ f3=f1+f2; f1=f2; f2=f3;

}

return f3;

}

三数之和问题：【-1，0，-4，-1，2，1】 让其三个数加一起等于0且无重复数 暴力求解发 hash表记录a b a+b=-c法 定义枚举指针 双指针夹逼法（即定义三个指针） O(n^2)

Arrays.sort方法是将数组内的元素进行升序排列  Arrays.asList方法是将数组转化为List集合的方法

public List<List> threenum(int[] nums){

Arrays.sort(nums); 将数组从小到大排列 List<List<Integer>>

res=new LinkedList<>(); 定义存放结果的数组

for(int

i=0;i<nums.length-2;i++){ 因为l r最后在i的后两个上 所以不用重复循环

if(nums[i]>0)

break; 当数组i上的数字大于0时 三数之和肯定大于0 直接跳出

if(i==0||(i>0&&nums[i]!=nums[i-1])){ 当i前后数值不一样时开始 int

l=i+1;int r=nums.length-1;int targer=0-nums[i]; i是枚举 l在i右侧 r在最左侧

while(l<r){ if(nums[l]+nums[r]==target){ res.add(Arrays.asList(nums[i],nums[l],nums[r])); 符合的结果存入集合 while(l<r&&nums[l]==nums[l+1]) l++; 排除l右侧的一样数 while(l<r&&nums[r]==nums[r-1]) r--; 排除r左侧的一样数 l++;

r–;

else

if(nums[l]+nums[r]<nums[i]) l++; lr加一起的数小于i 那么就让l往右走 否则的话 就是r往左走

else

r–;

}

}

}

}

}

return res;

}

链表反转（将一个顺序链表反转）（1->2->3->0变成0<-1<-2<-3）(三个辅助接点pqr 即每个节点的后续变成它的前驱) O（n）

public Node inverse(Node q){

if(q==null) return null;

q是头节点（head） q空直接结束

Node

p=null; 初始话p空

Node

r=q.next; r是q的后一个节点

while(r!=null){ q.next=p; pq换完之后 让pqr都往前进一个 p=q; q=r; r=r.next;

}

q.next=p; 最后一次r到空指针上 pq进行最后转换

return q;

}

static class Node{

Node

next;

int

data;

Node(int

data){

this.data=data; this.next=next;

}

}

判断链表是否有环（采用快慢指针法）O(n)

public Boolean hasCycle(Node head){

if(head==null||head.next==null){ return

false;

}

Node

slow=head; Node fast=head.next;

while(slow!=fast){ if(fast==null||fast.next==null){ return

flase;

}

slow=slow.next;

fast=fast.next.next;

}

return

true;

}

static class Node{

Node

next;

int

data;

Node(int

data){

this.data=data; this.next=next;

}

}