算法训练营——数组 链表 跳表基本的实现和特性(第二课)

算法提高秘籍：一定记住。每一套题目都要独立得写5遍以上。把leetcode上的思路多去思考，并独立完成代码。

数组和链表、跳表的的基本的原理

ArrayList和LinkList的时间复杂度和空间复杂度的比较（增删改查）

数组作为重要的额数据结构结构是很多的数据结构的底层是实现 例如跳跃表 还有的Arraylist 等……

Arrays常用函数：

1.equals(int[] a, int[] b)方法：判断两个数组是否相等

    int[] array1 = new int[]{1, 2, 3, 4};
    int[] array2 = new int[]{1, 2, 3, 4};
    int[] array3 = new int[]{1, 3, 2, 4};
    boolean b1 = Arrays.equals(array1, array2);
    boolean b2 = Arrays.equals(array1, array3);
    System.out.println(b1);// 返回true
    System.out.println(b2);// 返回false

2.toString(int[] a)方法：返回一个指定数组的字符串表现形式

    int[] array1 = new int[]{1, 2, 3, 4};
    System.out.println(Arrays.toString(array1));
	// 输出结果为[1, 2, 3, 4]

3.fill(int[] a, int value)方法：给指定数组的每个元素分配指定的值

    int[] array1 = new int[5];
    Arrays.fill(array1, 1);
    System.out.println(Arrays.toString(array1));
	// 输出结果为[1, 1, 1, 1, 1]

4.sort(int[] a)：按升序对指定数组进行排序

    int[] array = new int[]{99, 23, 33, 0, 65, 9, 16, 84};
    Arrays.sort(array);
    System.out.println(Arrays.toString(array));
	// 输出结果为[0, 9, 16, 23, 33, 65, 84, 99]

5.binarySearch(int[] a, int value)：使用二分搜索算法在指定的数组中搜索指定的值，并返回该值所在索引位置；若查询不到，则返回-1

    int[] array = new int[]{1, 17, 20, 44, 45, 62, 79, 88, 93};
    int i = Arrays.binarySearch(array, 44);
    System.out.println(i);
	// 输出结果为3
6.拷贝数组元素，传输两个参数Arrays.copy（arr[],newlength）参数1为将要拷贝的对象参数2为返回的新数组的长度
Random random = new Random();
        int[] intarr = new int[10];
        for (int i = 0; i < intarr.length; i++) {
            intarr[i] = random.nextInt(1000);
        }
        System.out.println(Arrays.toString(intarr));
        int[] intarr2 = Arrays.copyOf(intarr,intarr.length);
        System.out.println(Arrays.toString(intarr2));
        Arrays.sort(intarr);
        System.out.println(Arrays.equals(intarr,intarr));
        System.out.println(Arrays.equals(intarr2,intarr));
//        Array 类输出方法
        System.out.println(Arrays.toString(intarr));

Arraylist和LinkList的源码实现

LRU的缓存的实现的代码：146. LRU缓存机制

数组和链表、跳表实战题目的训练 简单

1. 两数之和

/**
 * Copyright (C), 2018-2020
 * FileName: 两个数之和1
 * Author:   xjl
 * Date:     2020/11/2 16:32
 * Description:
 */
package 数组问题;

import org.junit.Test;

import java.util.HashMap;

public class 两个数之和1 {
    /**
     * 将里面的元素存储在hasmap中的 然后保证的key不相同就好key-value :nums[i] index
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap();
        //存储
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
                return new int[]{i, map.get(target - nums[i])};
            }
        }
        return null;
    }

    @Test
    public void test() {
        int[] ints = twoSum(new int[]{4,4, 11, 11, 15}, 8);
        System.out.println(ints[0]+"--"+ints[1]);
    }

    /**
     * 暴力的方法：最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
     * 当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。
     * 而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

}

中等

283. 移动零

/**
 * Copyright (C), 2018-2020
 * FileName: 移动零283
 * Author:   xjl
 * Date:     2020/10/23 9:49
 * Description:
 */
package 数组问题;

import org.junit.Test;

import java.util.ArrayList;

public class 移动零283 {

    @Test
    public void test6() {
        moveZeroes6(new int[]{0, 1, 0, 3, 12});
    }

    /**
     * 一次遍历的就可以实现
     *
     * @param nums
     */
    public void moveZeroes6(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                //进行元素交换
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }

    public void moveZeroes(int[] nums) {
        if (nums == null) {
            return;
        }
        //两个指针i和j
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if (nums[i] != 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }

    @Test
    public void test4() {
        moveZeroes(new int[]{0, 1, 0, 3, 12});
    }

    /**
     * 默写的一遍 时间复杂度为o(n)+o(m)表示的0的个数
     *
     * @param nums
     */
    public void moveZeroes5(int[] nums) {
        int a = 0;
        //将不是0的全部放置子新的数组上
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[a++] = nums[i];
            }
        }
        for (int i = a; i < nums.length; i++) {
            nums[i] = 0;
        }

        for (int i : nums) {
            System.out.print(i + " ");
        }
    }

    /**
     * 通过使用的是的两次遍历 第一次的将将不是0的元素放置在前面  遍历完成所有的元素后在来重第一次后的遍历并将元素设置为0
     *
     * @param nums
     */
    public void moveZeroes3(int[] nums) {
        if (nums == null) {
            return;
        }
        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for (int i = j; i < nums.length; ++i) {
            nums[i] = 0;
        }
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }

    @Test
    public void test3() {
        moveZeroes(new int[]{0, 1, 0, 3, 12});
    }

    /**
     * 采用的是的双指针的进行移动
     *
     * @param nums
     */
    public void moveZeroes2(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return;
        }
        int index1 = 0;//记录0的位置
        int index2 = 0;//记录不是0的位置
        while (index2 < nums.length) {
            if (nums[index2] == 0) {
                if (nums[index1] != 0) {
                    index1 = index2;
                }
                index2++;
            } else {
                if (nums[index1] == 0) {
                    //交换元素
                    int tmp = nums[index1];
                    nums[index1] = nums[index2];
                    nums[index2] = tmp;
                }
                index1++;
                index2++;
            }
        }
    }

    @Test
    public void test() {
        moveZeroes(new int[]{0, 1, 0, 3, 12});
    }

    /**
     * 采用的是的一个数组
     *
     * @param nums
     */
    public void moveZeroes1(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return;
        }
        ArrayList list = new ArrayList();
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                list.add(nums[i]);
            } else {
                count++;
            }
        }
        while (count > 0) {
            list.add(0);
            count--;
        }
        for (int i : list) {
            System.out.print(i + " ");
        }
    }

    @Test
    public void test1() {
        moveZeroes(new int[]{0, 1, 0, 3, 12});
    }

}

11. 盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l]  0) break;
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //制定两个指针
            int L = i + 1;
            int R = len - 1;
            //如果是左边的指针小于就表示可以进行
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    //添加进入list中
                    result.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    // 左边去重
                    while (L < R && nums[L] == nums[L + 1]) L++;
                    // 右边去重
                    while (L < R && nums[R] == nums[R - 1]) R--;
                    L++;
                    R--;
                } else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return result;
    }
}

数组 链表的问题方法总结：

数组的常见问题一般比较多的采用的是的双指针来解决问题。