用于记录刷题日常(LeetCode)，也算是整理笔记。
两数之和(力扣第1题)
题目要求：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值
target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 ：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
看到这道题的第一思路：定义两个指针(a,b)，a和b指针指向第一位，然后b指针右移，如果期间有满足的值则返回，否则当b指针移动到数组最后一位的时候回到第一位，同时a指针后移一位，直到a和b指针都移动到最后一位。
这里我就开始写代码了
public static int[] twoSum(int[] nums, int target) { int first = 0; int second = 0; while (true) { second++; if (second == nums.length) { second = 0; first++; } if (first == nums.length) { return new int[]{0, 0}; } if ((nums[first] + nums[second]) == target && first != second) { break; } } return new int[]{first, second}; }
提交代码傻眼了击败了百分之五的用户，由此可见这种解法是不好的。
查看评论区，我又发现了一种暴力解法，其实思路上和我一致，只是在书写上做了一些优化
public static int[] twoSum(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,0}; }
实际上这两种都可以称为暴力破解[时间复杂度为O(n^2),空间复杂度为O(1)]，因为它们都是遍历所有可能。
当然肯定还有更好的解决方法
思路二：使用map集合来存储数组，然后遍历数组，在map集合中查找target-nums[i]。
也就是说当我的数组为[3, 2, 4],target为6的时候，实际上在map中要找的数为6-3=3、6-2=4、6-4=2，但是这里要注意下标不能重复
public static 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++) { int subtraction = target - nums[i]; if (map.containsKey(subtraction) && i != map.get(subtraction)) { return new int[]{i, map.get(subtraction)}; } } return new int[]{0, 0}; }
但是有个弊端，就是遍历了两次，再进行优化得到
public static int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int subtraction = target - nums[i]; if (map.containsKey(subtraction) && i != map.get(subtraction)) { return new int[]{map.get(subtraction), i}; } map.put(nums[i], i); } return new int[]{0, 0}; }
这里时间复杂度已经达到了O(N),空间复杂度也是O(N),毕竟多出了map进行存储。
三数之和(力扣第15题)
题目要求：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a
+ b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
图解：
此方法为三指针法，根据图所示步骤，进行编写代码
public static List<List<Integer>> threeSum(int[] nums) { int n = nums.length; List<List<Integer>> result = new ArrayList<>(); // 1。排序 Arrays.sort(nums); //2。开始循环 for (int i = 0; i < n; i++) { //2-1。当i指针指向当数大于0当时候退出，也就是三个指针的和一定大于0 if (nums[i] > 0) { break; } //2-2。当目前当i和前一个i指向当数相等时直接跳过 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //2-3。定义左右指针 int left = i + 1; int right = n - 1; //2-4。只要左指针在右指针左边就一直循环 while (left < right) { //计算三个数之和 int sum = nums[i] + nums[left] + nums[right]; //当和为0当时候要添加到集合中进行保存，然后左右指针移动，如果有重复数就再进行移动 if (sum == 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); left++; right--; while (left < right && nums[left] == nums[left - 1]) { left++; } while (left < right && nums[right] == nums[right + 1]) { right--; } //当和小于0左指针右移，大于0的时候右指针左移 } else if (sum < 0) { left++; } else { right--; } } } return result; }
下一个排列(力扣第31题)
题目要求：例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
那么下一个排列代表下一个比123大的数，那么就是132。
当指定的arr = [3,2,1] 没有下一个比321大的数，那么久升序排列为123
示例 ：
输入：nums = [1,2,3] 输出：[1,3,2]
输入：nums = [3,2,1] 输出：[1,2,3]
输入：nums = [1,1,5] 输出：[1,5,1]
思路：
其实就是从右往左先找相邻的两个数并且满足生序，例如132那么13就满足条件，记录满足条件的下标，然后从第二个数开始进行升序，最终交换两个下标的值就可以了。
public static void nextPermutation(int[] nums) { int len = nums.length; for (int i = len - 1; i > 0; i--) { if (nums[i] > nums[i - 1]) { Arrays.sort(nums, i, len); for (int j = i; j < len; j++) { if (nums[j] > nums[i - 1]) { int temp = nums[j]; nums[j] = nums[i - 1]; nums[i - 1] = temp; return; } } } } Arrays.sort(nums); }
旋转图像(力扣第48题)
题目要求：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例1 ：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
示例2 ：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
图解1: 使用数学方法，先对矩阵进行转置，在反转每一行
public void rotate(int[][] matrix) { int n = matrix.length; //转置矩阵 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } } //翻转每一行 for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[i][n - j - 1]; matrix[i][n - j - 1] = tmp; } } }
图解2: 进行旋转，思路请看图解
这里以4*4矩阵作为例子，由外而内进行旋转。
public static void rotate(int[][] matrix) { int n = matrix.length; //外层控制几轮 for (int i = 0; i < (n + 1) / 2; i++) { //内层控制每轮要旋转的个数 for (int j = 0; j < n / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = temp; } } }
