算法提高秘籍：一定记住。每一套题目都要独立得写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<Integer, Integer> 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<Integer> 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] <= height[r]) { ++l; } else { --r; } } return ans; } }15. 三数之和
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList(); int len = nums.length; if (nums == null || len < 3) return result; // 排序 Arrays.sort(nums); //遍历第一个数据 for (int i = 0; i < len; i++) { // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 if (nums[i] > 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; } }数组的常见问题一般比较多的采用的是的双指针来解决问题。
