力扣算法题

╰+哭是因爲堅強的太久メ 2023-09-25 19:23 102阅读 0赞

## 1. 排序 ##

//排序，冒泡排序，介绍两种排序的方式，1.升序 2.降序
        public static void main(String[] args) {
        
            int[] arr = {
        1, 8, 4, 2, 4};
    
            //升序
            orderByAsc(arr);
    
            //降序
            orderByDesc(arr);
    
        }

### 1. 1 升序 ###

//升序
        private static int[] orderByAsc(int[] arr) {
        
            if (null == arr || arr.length == 0) {
        
                return new int[0];
            }
    
            //外层循环控制次数
            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;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
            return arr;
        }

### 1. 2 降序 ###

//降序
        private static int[] orderByDesc(int[] arr) {
        
            if (null == arr || arr.length == 0) {
        
                return new int[0];
            }
    
            //外层循环控制次数
            for (int i = 0; i < arr.length; i++) {
        
                //内层循环排序，判断当前值与上一个值的大小，将较大的值覆盖到上一个值
                for (int j = arr.length - 1; j > i; j--) {
        
                    if (arr[j] > arr[j - 1]) {
        
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
            return arr;
        }

## 2.两数之和 ##

需求介绍：

/**
         * 角标: 0 1 2 3 4 5 6
         * 数组：3 4 5 4 7 8 1
         * 需求：查找出数据中两数之和为12的任意一组两个数的角标,且同一元素不能使用两次
         * 如：1,5
         *    2,4
         *    3,5
         */
        public static void main(String[] args) {
        
    
            int[] arr = {
        3, 4, 5, 4, 7, 8, 1};
            int target = 12;
    
            //1. 两数之和（线性查询）
            int[] ints1 = twoSum1(arr, target);
    
            //2. 两数之和（二分查找）
            int[] ints2 = twoSum2(arr, target);
    
            //3. 两数之和（哈希查找）
            int[] ints3 = twoSum3(arr, target);
    
        }

### 2.1 两数之和（线性查找） ###

/**
         * 1. 两数之和（线性查找）
         *
         * 时间复杂度：O(N^2)
         * 空间复杂度：O(1)
         *
         * 注：时间复杂度怎么计算？
         * 看if (arr[i] + arr[j] == target) 执行的次数
         *
         * 等差数列：(n-1)*n/2 ===>  (n^2-n)/2 ===>  去掉系数二分之一 ===> n^2 -n
         *
         */
        private static int[] twoSum1(int[] arr, int target) {
        
            if (null == arr || arr.length == 0) {
        
                return new int[0];
            }
            
            for (int i = 0; i < arr.length; i++) {
        
                for (int j = i + 1; j < arr.length; j++) {
        
                    if (arr[i] + arr[j] == target) {
        
                        return new int[]{
        i, j};
                    }
                }
            }
    
            return new int[0];
        }

### 2.1 两数之和（二分查找） ###

/**
         * 2. 两数之和（二分查找）
         *    二分查找的使用前提是有序集合
         *
         * 时间复杂度：O(N log n)
         * 空间复杂度：O(n)
         *
         */
        private static int[] twoSum2(int[] arr, int target) {
        
            //1.先排序
    
            //2.排序后的原始的数据的角标已经乱序了，需要处理，不适用
    
            return new int[0];
        }

### 2.3 两数之和（哈希查找） ###

/**
         * 3.两数之和（哈希查找）
         * 时间复杂度：O(2N)
         * 空间复杂度：O(N)
         */
        private static int[] twoSum3(int[] arr, int target) {
        
            if(null == arr || arr.length == 0){
        
                return new int[0];
            }
    
            //数据预处理
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
        
                map.put(arr[i], i);
            }
    
            for (int i = 0; i < arr.length; i++) {
        
                //为了避免key和index是同一个角标
                if(map.containsKey(target - arr[i])){
        
                    Integer index = map.get(target - arr[i]);
                    if(i != index){
        
                        return new int[]{
        i,index};
                    }
                }
            }
    
            return new int[0];
        }

### 2.4 两数之和（哈希查找）优化两次for循环 ###

/**
         * 4.两数之和（哈希查找）优化两次for循环
         * 时间复杂度：O(N)
         * 空间复杂度：O(N)
         */
        private static int[] twoSum4(int[] arr, int target) {
        
            if(null == arr || arr.length == 0){
        
                return new int[0];
            }
            
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
        
                //为了避免key和index是同一个角标
                if(map.containsKey(target - arr[i])){
        
                    Integer index = map.get(target - arr[i]);
                    return new int[]{
        i,index};
                }
                map.put(arr[i], i);
            }
            return new int[0];
        }