Java常见算法(二)

• • 一、数组中找出两数之和为给定值的数组下标
  • • 1、暴力算法
    • 2、数组标记算法
    • 3、二分法
    • 4、双指针
  • 二、斐波那契数列
  • • 1、去重递归
    • 2、双指针迭代

给定一个整数数组 numbers , 从数组中找出两个数满足相加之和等于目标数target。
假设每个输入值对应唯一的答案，而且不可以重复使用相同的元素。
返回两数的下标值，以数组形式返回。

  //1.暴力算法
    public static int[] solution(int[] nums,int target){
        for (int i=0;i 
2、数组标记算法 
    //2.数组标记算法 ，时间复杂度 O（N）
    public static int[] solution1(int[] nums,int target){
        Map map = new HashMap<>();
        for (int i=0;i 
3、二分法 
 //3.二分法。（二分法的前提条件必须是有序）,时间复杂度为  O(NlogN)
    public static int[]  twoSearch(int[] nums,int target){
        for (int i = 0; i target-nums[i]){
                    //右指针左移
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
        }
        return null;
    }
 
4、双指针 
//4.双指针（最优）（前提条件必须是有序）
    public static int[] doublePointer(int[] nums,int target){
        int i=0;//左指针
        int j=nums.length-1;//右指针
        while (itarget-nums[j]){
                j--;
            }else{
                i++;
            }
        }
        return null;
     }
 
源码实验：
 
package com.example.rabbitmq;

import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

@SpringBootTest

class SuanfaApplicationTests7 {

    //1.暴力算法
    public static int[] solution(int[] nums,int target){
        for (int i=0;i map = new HashMap<>();
        for (int i=0;itarget-nums[i]){
                    //右指针左移
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
        }
        return null;
    }

    //4.双指针（最优）（前提条件必须是有序）
    public static int[] doublePointer(int[] nums,int target){
        int i=0;//左指针
        int j=nums.length-1;//右指针
        while (itarget-nums[j]){
                j--;
            }else{
                i++;
            }
        }
        return null;
     }

    @Test
    public void sf0(){
        int[] nums=new int[]{2,3,4,6,5,1,2,3};
        System.out.println(Arrays.toString(solution(nums,10)));
        System.out.println(Arrays.toString(solution1(nums,10)));

        Arrays.sort(nums);//二分法、双指针的前提条件就是数组有序
        System.out.println(Arrays.toString(twoSearch(nums,10)));
        System.out.println(Arrays.toString(doublePointer(nums,10)));
    }

}

 
结果：
 
//这里注意一下，这里找到的都是数组下标！
[5, 7]
[5, 7]
[2, 3]
[2, 3]
 
二、斐波那契数列 
求取斐波那契数列第 N 位的值
斐波那契数列：每一位的值等于他前两位数字之和。前两位固定： 0，1，1，2，3，5，8，13,21......
 
1、去重递归 

 
 
//1、去重递归
    public static int fbnq(int n){
        //我们定义一个数组
        int[] arr=new int[n+1];
        return recurse(arr,n);
    }
    //递归函数
    private static int recurse(int[] arr,int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        //去重递归其实关键的就是这个判断，看看之前是否已经有了这个数
        if(arr[n]!=0){
            return arr[n];
        }
        arr[n]=recurse(arr,n-1)+recurse(arr,n-2);
        return arr[n];
    }
 
2、双指针迭代 
//2、双指针迭代(推荐)
    private static int iterate(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int low=0,h=1;
        for (int i = 2; i <=n ; i++) {
            int sum=low+h;
            low = h;
            h=sum;
        }
        return h;
    }
 
实验源码：
 
package com.example.rabbitmq;

import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

@SpringBootTest

class SuanfaApplicationTests8 {

    //1、去重递归
    public static int fbnq(int n){
        //我们定义一个数组
        int[] arr=new int[n+1];
        return recurse(arr,n);
    }
    //递归函数
    private static int recurse(int[] arr,int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        //去重递归其实关键的就是这个判断，看看之前是否已经有了这个数
        if(arr[n]!=0){
            return arr[n];
        }
        arr[n]=recurse(arr,n-1)+recurse(arr,n-2);
        return arr[n];
    }

    //2、双指针迭代(推荐)
    private static int iterate(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int low=0,h=1;
        for (int i = 2; i <=n ; i++) {
            int sum=low+h;
            low = h;
            h=sum;
        }
        return h;
    }

    @Test
    public void sf0(){
        System.out.println(fbnq(10));

        System.out.println(iterate(10));
    }

}

 
实验结果：
 
55
55