算法

基本查找

public class FindText {
    public static void main(String[] args) {
        //基本查找
        //需求：定义一个方法利用基本查找，查询某个数据是否存在
        int[] arr = {1, 2, 3, 4, 5, 5, 7, 8, 9, 10};
        System.out.println(myFind(arr, 11));//false
        System.out.println(myFind(arr, 1));//true


        //使用基本查找 找出元素索引，可能具有重复元素
        System.out.println(myFindRepeat(arr, 5));//[4, 5]
    }

    //基本查找
    private static Boolean myFind(int[] arr, int num) {
        for (int item : arr)
            if (item == num) return true;
        return false;
    }

    //使用基本查找 找出元素索引，可能具有重复元素
    private static ArrayList<Integer> myFindRepeat(int[] arr, int num) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) list.add(i);
        }
        return list;
    }
}

二分查找

package algorithm;

import java.util.ArrayList;

public class FindText {
    public static void main(String[] args) {
        //二分查找
        //二分查找的前提：数组中的数据必须是有序的
        //核心逻辑：排除掉一半的查找范围
        System.out.println("二分查找结果" + binarySearch(arr, 10));//9
        System.out.println("二分查找结果" + binarySearch(arr, 11));//-1
    }

    //二分查找
    private static int binarySearch(int[] arr, int num) {
        //小索引
        int left = 0;
        //大索引
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == num) return mid;
            else {
                if (num > arr[mid])
                    left = mid + 1;
                else
                    right = mid - 1;

            }
        }
        return -1;
    }
}

冒泡排序

规则：把相邻的数据两两比较，小的放前面，大的放后面

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 9, 2, 7, 4, 6, 8};
        int[] result = mySort(arr);
        System.out.println(Arrays.toString(result));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static int[] mySort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int j = 0;
            //内循环 每一轮中比较数据 寻找最大值
            //-1 防止索引越界
            //-i 提高效率
            while (j < arr.length - 1 - i) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                j++;
            }
        }
        return arr;
    }
}

选择排序

规则：从索引0开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面，以此类推

public class SelectSort {
    public static void main(String[] args) {
        //选择排序
        //规则：从索引0开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面，以此类推
        int[] result1 = mySort1(arr);
        System.out.println(Arrays.toString(result1));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static int[] mySort1(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //拿着i跟i后面的数据进行比较交换
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

插入排序

将0索引的元素到n索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
遍历无序的数据，将遍历到的元素插入有序序列中的合适位置，如遇到相同数据，插在后面。
N的范围：0~最大索引

public class InsertSort {
    public static void main(String[] args) {

        //插入排序
        int[] result2 = mySort2(arr);
        System.out.println(Arrays.toString(result2));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static int[] mySort2(int[] arr) {
        //克隆数组
        int[] arrClone = arr.clone();
        //1.找到无序的那一组是从哪个索引开始的
        int startIndex = -1;
        for (int i = 0; i < arrClone.length - 1; i++) {
            if (arrClone[i] > arrClone[i + 1]) {
                startIndex = i + 1;//找到无序的那一组的开始索引
                break;
            }
        }
        //遍历无序的列表
        for (int i = startIndex; i < arrClone.length; i++) {
            //记录当前要插入数据的索引
            int j = i;
            //将当前数据倒着插入到有序的列表中
            while (j > 0 && arrClone[j] < arrClone[j - 1]) {
                //交换位置(与前面的数据进行交换)
                int temp = arrClone[j];
                arrClone[j] = arrClone[j - 1];
                arrClone[j - 1] = temp;
                j--;
            }

        }
        return arrClone;
    }
}

递归算法

递归算法：就是方法中调用方法本身的现象(自己调用自己)

注意

递归一定要有出口，否则就会出现内存溢出

书写递归的两个核心

找出口：什么时候不在调用此方法
找规则：如何把大问题变成规模较小的问题
方法内部再次调用方法的时候要更靠近出口

public class Recursion {
    public static void main(String[] args) {
        //递归求和
        int start = 1;
        int end = 100;
        int sum = mySum(start, end);
        System.out.println(start + "到" + end + "之间的和为：" + sum);//5050

        //递归求阶乘
        int result3 = myFactorial(5);
        System.out.println("阶乘为：" + result3);//120

    }

    //递归求阶乘
    private static int myFactorial(int i) {
        if (i == 1) return 1;
        else return i * myFactorial(i - 1);
    }

    //递归求和
    private static int mySum(int start, int end) {
        if (start == end)
            return start;
        else return start + mySum(start + 1, end);
    }
}

快速排序

快速排序用时非常快，在测试排序十万随机数时，快速排序比其他排序算法快了20倍

冒泡排序时间:19046
选择排序时间:15612
插入排序时间:1754
快速排序时间:20
第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置
结束后比基准数小的全部在左边，比基准数大的全部在右边

public class QuickSort {
    public static void main(String[] args) {
        //快速排序
        //第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置
        //          结束后比基准数小的全部在左边，比基准数大的全部在右边
        int[] result4 = myQuickSort3(arr.clone(), 0, arr.length - 1);
        System.out.println(Arrays.toString(result4));
    }

    //快速排序
    private static int[] myQuickSort3(int[] arr, int i, int j) {
        int start = i;
        int end = j;
        //递归的出口
        if (start > end) return arr;
        //1.记录基准数
        int base = arr[i];
        //2.利用循环找到要交换的数字
        while (start != end) {
            //3.利用end，从后往前开始找，找比基准数小的数字
            while (start < end && arr[end] >= base) {
                //左边找到比基准数大的数字
                end--;
            }
            //4.利用start找到比基准数大的数字
            while (start < end && arr[start] <= base) {
                start++;
            }
            //5.交换start和end找到的数字
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //当start和end都指向一个元素的时候，那么上面的循环就会结束
        //表示已经找到了基准数在数组中应该存入的位置
        //基准数归位
        //就是拿着这个范围中的第一个数字，跟start指向的元素进行交换
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        //确定基准数左边的位置 重复刚刚的事情
        myQuickSort3(arr, i, start - 1);

        //确定基准数右边的位置 重复刚刚的事情
        myQuickSort3(arr, end + 1, j);
        return arr;
    }

}

操作数组的工具类`Arrays`

方法	描述
`public static String toString(int[] a)`	将数组转换为字符串表示形式。
`public static int binarySearch(int[] a, int key)`	二分查找法查找元素
`public static void fill(int[] a, int val)`	使用指定的值填充数组
`public static int[] copyOf(int[] original, int newLength)`	创建一个新的数组
`public static int[] copyOfRange(int[] original, int from, int to)`	创建一个新的数组(指定范围)
`public static void sort(int[] a)`	按照默认方式对数组进行排序。
`public static void sort(int[] a, 排序规则)`	按照指定的规则进行排序

动态规划（矩阵连乘问题）

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：

输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]


import java.util.*;

class Scratch {
   //两数之和
   /*给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
    你可以按任意顺序返回答案。*/

   /* 示例 1： [2,7,11,15], target = 9
    输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。*/
    public static void main(String[] args) {
        int[] ints = twoSumHash(new int[]{1, 2, 3}, 7);
        System.out.println(Arrays.toString(ints));
    }
   public static int[] twoSum(int[] nums, int target) {

       for (int i = 0; i < nums.length - 1; i++) {
           if(nums[i]>=target)continue;
           for (int j = i + 1; j < nums.length; j++) {
               if(nums[i]+nums[j]==target)return new int[]{i,j};
           }
       }
       throw new IllegalArgumentException("没有找到数据");
   }
    public static int[] twoSumHash(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
       throw new IllegalArgumentException("没有找到数据");
    }
}

字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

 //字母异位词
    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> objectObjectHashMap = new HashMap<>();
    for(String str:strs){
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        String key = new String(charArray);
        List<String> list = objectObjectHashMap.getOrDefault(key, new ArrayList<>());
        list.add(str);
        objectObjectHashMap.put(key,list);
    }
        return new ArrayList<List<String>>(objectObjectHashMap.values());
    }
   //api方法
    public static List<List<String>> groupAnagrams(String[] strs) {
      return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(s -> Arrays.toString(s.codePoints().sorted().toArray()))).values());
    }

算法

ON THIS PAGE