常见算法总结

算法
字数统计: 1.9k字   |   阅读时长≈ 9分钟

一、基础算法

1. 斐波那锲数列

2. 从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路：使用栈实现，先全部入栈，再依次出栈

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
public static ArrayList<Integer> fromTailtoHead(ListNode listNode){
       Stack<Integer> stack=new Stack<>();
       ArrayList<Integer> arrayList=new ArrayList<>();
       while (listNode!=null){
           stack.push(listNode.val);
           listNode=listNode.next;
       }
       while (!stack.isEmpty()){
           arrayList.add(stack.pop());
       }
       return arrayList;
   }

3. 反转链表

核心代码：

1
2
3
4
5
6
7
8
9
10
11
public ListNode ReverseList(ListNode listNode){
    ListNode pre=null;
    ListNode next=null;
    while(listNode!=null){
        next=listNode.next;
        listNode.next=pre;
        pre=listNode;
        listNdoe=next;
    }
    return pre;
}

4. 栈实现队列操作

用两个栈来实现一个队列，完成队列的Push和Pop操作，队列中元素为int类型

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class demo3 {
    Stack<Integer> stack1=new Stack<>();
    Stack<Integer> stack2=new Stack<>();
    public void push(int node){
        stack1.push(node);
    }
    public int pop(){
        if (stack1.isEmpty()&&stack2.isEmpty()){
            System.out.println("队列为空");
        }
        if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

5. 数组中的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字，如果不存在输出0

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int moreThanHalf(int[] arr){
    Arrays.sort(arr);
    int count=0;
    int half=arr.length/2;
    for (int i=0;i<arr.length;i++){
        if (arr[i]==arr[half]){
            count++;
        }
    }
    if (count>half){
        return arr[half];
    }else {
        return 0;
    }
}

6. 二叉树的深度

输入一棵二叉树，求该数的深度。

核心代码

1
2
3
4
5
6
7
8
public int TreeDepth(TreeNode treeNode){
    if (treeNode==null){
        return 0;
    }
    int left=TreeDepth(treeNode.left);
    int right=TreeDepth(treeNode.right);
    return Math.max(left,right)+1;
}

7. 青蛙跳台阶

一只青蛙一次可以跳1级台阶，也可以跳2级，求该青蛙跳上一个n级台阶总共有多少种跳法。

变态跳台阶

青蛙可以一次跳1级、2级、n级，求该青蛙跳上一个n级台阶总共有多少种跳法

1
2
3
public int jumpFloor(int n){
    return (int)Math.pow(2,target-1);
}

8. 双重校验实现单例模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Singleton {
    private volatile static Singleton instance;
    private Singleton(){}
    public static Singleton getInstance(){
        if (instance==null){
            synchronized (Singleton.class){
                if (instance==null){
                    instance=new Singleton();
                }
            }
        }
        return instance;
    }
}

9. 给定字符串去重

1
2
3
4
5
6
7
String str="2,4,3,6,5,8,7,9,10";
String[] strs=str.split(",");
TreeSet<Integer> tree=new TreeSet<>();
for (String a:strs){
    tree.add(Integer.parseInt(a));
}
System.out.println(tree);

10. 对文件中的数字排序

某一个文件中存在1000个乱序的数字，彼此用“，”隔开，请读取里面的内容，并把它们排序遍历出来。

1
2
3
4
5
6
7
8
9
10
BufferedReader br=new BufferedReader(new FileReader("test.txt"));
StringBuffer sb=new StringBuffer();
String flag;
while((flag=br.readLine())!=null){
    sb.append(flag);
}
br.close();
String[] strs=sb.toString().split(",");
Arrays.sort(strs,((o1, o2) -> Integer.valueOf(o1)-Integer.valueOf(o2)));
System.out.println(Arrays.toString(strs));

11. 字符替换

将一个字符串中的每个空格替换成”/“

  1. 方法一

    1
    2
    3
    String str="www yolin xyz";
    String s=str.replace(" ","/");
    System.out.println(s);

  2. 方法二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    String str="www yolin xyz";
    StringBuilder sb=new StringBuilder();
    for (int i=0;i<str.length();i++){
        char c=str.charAt(i);
        if (c==' '){
            sb.append("/");
        }else {
            sb.append(c);
        }
    }
    System.out.println(sb.toString());

12. 写一个单例模式的伪代码

1
2
3
4
5
6
7
8
9
10
public class Singleton(){
    private Singleton(){}
    private static Singleton instance;
    public static Singleton getInstance(){
        if(instance==null){
            instance=new Singleton();
        }
        return instance;
    }
}

13. 字符串反转

方法一

1
2
3
4
5
6
7
public String reverse1(String str){
    if(str==null || str.length()<=1){
        return str;
    }
    StringBuffer sb=new StringBuilder(str);
    return sb.reverse().toString();
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static String reverse2(String str){
    if (str==null||str.length()<=1){
        return  str;
    }
    char[] chars = str.toCharArray();
    Stack<Character> stack = new Stack<>();
    for (char c:chars){
        stack.push(c);
    }
    ////使用length暂存堆的大小，因为遍历的过程中，会改变堆的大小
    int length=stack.size();
    StringBuffer sb = new StringBuffer();
    for (int i=0;i<length;i++){
        sb.append(stack.pop());
    }
    return sb.toString();
}

14. 二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test {
    public static void main(String[] args) {
        int[] arr={10,14,21,30,45,47,90,100};
        int index=binarySearch(arr,14);
        System.out.println(index);
    }

    private static int binarySearch(int[] arr, int i) {
        int left=0;
        int right=arr.length-1;
        while(left<=right){
            int middle=(left+right)/2 ;
            if (arr[middle]==i){
                return middle;
            }else if (arr[middle] <i){
                left=middle+1;
            }else {
                right=middle-1;
            }
        }
        return -1;
    }
}

二、排序算法

1. 冒泡排序

首先从数组第一个元素开始到最后一个元素为止，对数组中相邻的两个元素进行比较，若左大于右，则交换他们的位置，接着对剩下的元素依次进行排序，直到整个数组有序排列。

时间复杂度：O（n^2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class demo1 {
    public static void main(String[] args) {
        int[] arr={6,8,9,4,5,1,2,3,7,2};
        for(int i=0;i<arr.length;i++){
            for (int j=0;j<arr.length-i-1;j++){
                if (arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        for (int i:arr){
            System.out.print(i+",");
        }
    }
}

2. 选择排序

假设长度为n的数组arr，先从第n个数字中找到最小值min1，如果最小值min1不在数组的最左端，则将最小值min1和arr[0]交换，接着在剩下的数中找最小值，如果最小值不等于arr[1],则交换这两个数，依次类推。

个人理解：第一遍遍历元素，找到最小元素的索引值，判断是否为第一个元素对应的索引，不是的话进行值的交换，保证最左边是最小值，依次类推

时间复杂度：O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class demo2 {
    public static void main(String[] args) {
        int[] arr={6,8,9,4,5,1,2,3,7,2};
        for (int i=0;i<arr.length;i++){
            int min=i;
            for (int j=i;j<arr.length;j++){
                if (arr[j]<arr[min]){
                    min=j;
                }
            }
            if (min!=i){
                int temp=arr[i];
                arr[i]=arr[min];
                arr[min]=temp;
            }
        }
        for (int i:arr){
            System.out.print(i+",");
        }
    }
}

3. 插入排序

基本思路是将无序序列插入到有序序列中。

时间复杂度: O（n^2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Arrays;

public class demo3 {
    public static void main(String[] args) {
        int[] arr={6,8,-2,9,4,5,1,2,3,7,2};
        for (int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j;
            for ( j=i;j>0&&arr[j-1]>temp;j--){
                arr[j]=arr[j-1];
            }
            arr[j]=temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

4. 快速排序

第一步：将第一个数作为基准数，小于基准的放在基准的前面，大于的放在后面，这一步，基准数会被排到正确位置

第二步：对于基准数前后的数分别执行第一步。

重复，直到没有数可以分为止

时间复杂度 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class demo4 {
    public static void main(String[] args) {
        int[] arr={6,8,-2,9,4,5,1,2,3,7,2};
        QuickSort(arr,0,arr.length-1);
        for (int i:arr){
            System.out.print(i+",");
        }
    }
    public static   int[] QuickSort(int arr[],int start,int end){
        if (start>end){
            return arr;
        }
        int i=start;
        int j=end;
        //基准数
        int base=arr[start];
        while (i<j){
            //从右向左找比基准数小的数
            while(i<j && arr[j]>=base){
                j--;
            }
            if (i<j){
                arr[i]=arr[j];
                i++;
            }
            //从左向右找比基准数大的数
            while (i<j && arr[i]<base){
                i++;
            }
            if (i<j){
                arr[j]=arr[i];
                j--;
            }
        }
        //把基准数放到i的位置
        arr[i]=base;
        QuickSort(arr,start,i-1);
        QuickSort(arr,i+1,end);
        return arr;
    }
}

请我喝杯咖啡吧~

支付宝
微信