leetcode
27. 移除元素【简单】
学习：移除元素，含最优解
题目链接：27. 移除元素
题目内容：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 明:为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); } 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
思路：
1、暴力
思路：每次找到要删除的元素之后，当前位置及其后面的元素会向前移动。
复杂度分析：时间复杂度为：O(n2) public int removeElement(int[] nums, int val) { int currentLength = nums.length; //初始值设置为数组长度，其会不断变化，实际可表示当前数组中不与val相同的元素数量 for (int i = 0; i < currentLength; i++) { if(nums[i] == val){ for (int j = i+1; j < currentLength; j++) { //整体数组向前移 nums[j-1] = nums[j]; } currentLength--; //由于向前移动，那么最后一个元素及倒数第二个元素重复，没有必要在之后重复进行检测 i--;//由于整体向前移动，那么当前i位置上的元素被原本i位置后的元素覆盖，若是不-1，那么之后会i++，就会在下一次检测时漏掉一个 } } return currentLength; }
2、双指针
复杂度分析：时间复杂度O(1)，借助两个指针，left指针指向不符合的元素假设初始为0，第二个指针就是遍历数组时每个指向，一旦找到不同的就存储在left下标，并且left向后继续一格。 思考：该方式的话将目光聚焦在不符合val的元素上，直接从数组第一格开始一旦遍历过程中有符合的就会移动到该坐标并且left同时就可以表示符合条件的数量。还是很妙的。 public int removeElement(int[] nums, int val) { int left = 0; for (int i = 0; i < nums.length; i++) { if(nums[i] != val){ //一旦有!=val的值，依次存储到索引为left下标中，依次覆盖之前的值即可 nums[left] = nums[i] ; left++; } } return left; }
977.有序数组的平方【简单】
学习： 977.有序数组的平方，题解含最优解
题目链接：977. 有序数组的平方
题目内容：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
思路：
1、暴力解法
思路：原本数组遍历一遍，平方之后，来进行统一排序。
复杂度分析：时间复杂度O(n+logn)
public int[] sortedSquares(int[] nums) { for(int i = 0; i<nums.length; i++){ nums[i] = nums[i]*nums[i]; } //选择排序 for(int i = 0;i<nums.length;i++){ int minCur = i; for(int j = i+1;j<nums.length;j++){ if(nums[j]<nums[minCur]){ minCur = j; } } if(i!=minCur){ nums[i] = nums[i]+nums[minCur]; nums[minCur] = nums[i]-nums[minCur]; nums[i] = nums[i]-nums[minCur]; } } return nums; }
2、双指针法
思路：核心关键点在于元素数组nums上，初始条件nums是递增的，我们就要从其特征进行下手。最左边与最右边必有一个最大值，照着这个思路，我们可以新创建一个数组，设置左右指针，依次比对出最大值放置到
复杂度分析：时间复杂度O(n)
public int[] sortedSquares(int[] nums) { //创建一个新数组（原数组中的值都是有用的，若是使用原数组进行覆盖值是不太行的，因为每次比较取到的值都是存储到right索引下，难免left下标取到最大值情况，所以要新建一个数组） int[] newArr = new int[nums.length]; //左右指针分别表示最左侧、最右侧(之后就根据这两个指针指向的元素进行比较，一定能够取出一个最大值) int left = 0; int right = nums.length-1; //标识新数组存储的下标(挺关键的) int index = nums.length-1; while (left<=right){ int leftNum = nums[left] * nums[left]; int rightNum = nums[right] * nums[right]; if(leftNum <= rightNum){ //核心思想就是拿着原始数组的最左边与右边(相乘)进行比较 newArr[index--] = rightNum; //新数组指定index索引位置存储好之后要更新下次存储的位置 right--; }else{ newArr[index--] = leftNum; left++; } } return newArr; }
179. 最大数【中等】
题目链接：179. 最大数
题目内容：
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。
思路：
1、排序。核心借助x+y与y+x来进行降序排序。
复杂度分析：时间复杂度O(nlogn)；空间复杂度O(n)
class Solution { //x + y < y + x public String largestNumber(int[] nums) { String[] strArr= new String[nums.length]; for (int i = 0; i < nums.length; i++) { strArr[i] = String.valueOf(nums[i]); } //核心：x + y < y + x Arrays.sort(strArr, (x, y)-> -(x + y).compareTo(y + x)); StringBuilder builder = new StringBuilder(); for (String str: strArr) { builder.append(str); } String res = builder.toString(); //去除前导0情况 int k = 0; //res.length() - 1考虑的是"0"情况 while (k < res.length() - 1 && res.charAt(k) == '0') { k++; } return res.substring(k); } }
31. 下一个排列【中等】
学习： leetcode题解
题目链接：31. 下一个排列
题目内容：
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。 必须 原地 修改，只允许使用额外常数空间。
思路：
1、逻辑推导
思路：下一个排列算法详解：思路+推导+步骤，看不懂算我输！，超详细还有可视化分析
从后往前依次两个进行遍历找到是升序的位置i-1，i。（待交换位置为i-1） 从[i,length-1]区间从后往前找到第一个比位置i-1大的位置k，此时交换在i-1、k两个位置上的值。 最后对[i,length-1]区间进行升序排序。 /** * 交换指定位置的两个数 * @param nums * @param left * @param right */ public void swap(int nums[], int left, int right) { int temp = nums[left] ^ nums[right]; nums[left] = nums[left] ^ temp; nums[right] = nums[right] ^ temp; } public void nextPermutation(int[] nums) { if (nums == null || nums.length <= 1){ return; } //1、从后往前找若是相邻两个数为升序情况 for (int i = nums.length - 1; i >= 1 ; i--) { if (nums[i] > nums[i - 1]){ //2、从[nums.length-1,i]区间中(也就是从后往前找)比i-1位置大的数 for (int j = nums.length - 1; j >= i; j--) { //若是找到了则进行兑换位置，且[i,nums.length-1]进行升序排序 if (nums[j] > nums[i - 1]){ swap(nums, i - 1 , j); if (j != i){ Arrays.sort(nums, i , nums.length); } return; } } } } //3、若是在上面遍历过程中并没有找到最终能够交换的数字，那么直接对整个数组进行排序处理 Arrays.sort(nums); }
209. 长度最小的子数组【中等】
学习： 209.长度最小的子数组
题目链接：209. 长度最小的子数组
题目内容：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。·
思路：
1、暴力解法
public int minSubArrayLen(int target, int[] nums) { if (nums.length == 0 || nums == null) { return 0; } int minSize = nums.length + 1; for (int i = 0; i < nums.length; i++) { int j = i; int size = 0; int targetVal = target; while (j < nums.length) { targetVal -= nums[j]; size++; if (targetVal <= 0) { if (size < minSize) { minSize = size; } break; } j++; } } return minSize == nums.length + 1 ? 0 : minSize; }
优化暴力：
public int minSubArrayLen(int target, int[] nums) { if (nums.length == 0 || nums == null) { return 0; } int minSize = nums.length + 1; for (int i = 0; i < nums.length; i++) { int num = 0; //从当前索引位置开始往后取到最小值，并得到符合情况的最小长度 for (int j = i; j < nums.length; j++) { num+=nums[j]; if(num>=target){ minSize = Math.min((j - i + 1), minSize); //(j-i+1)<minSize?(j-i+1):minSize => Math.min((j - i + 1), minSize) break; } } } return minSize == nums.length + 1 ? 0 : minSize;//判断一下是否与初始值一致，一致的话说明没有找到符合的最小子数组 }
2、滑动窗口
思路：每当找到>=target目标值时，来进行更新最短区间；通过使用双指针来进行滑动比对
复杂度分析：最优解，时间复杂度O(n)
public int minSubArrayLen(int target, int[] nums) { if (nums.length == 0 || nums == null) { return 0; } int minSubLen = nums.length+1;//最大数量 int leftCur = 0; //左指针 int sum = 0;//用于记录当前指针区间中的值 for (int i = 0; i < nums.length; i++) { sum += nums[i]; while(sum>=target){ //开始处理其中的情况 int subLen = i - leftCur + 1; //计算当前区间数量 minSubLen = Math.min(subLen, minSubLen);//与之前区间进行比较，得到最小区间数量 sum -= nums[leftCur++];//区间减小值 } } return minSubLen == nums.length + 1 ? 0 : minSubLen; }
优化细节：左 => 右，左边为自己原本代码，右为改进后值
第10行： while(sum>=target && leftCur<=nums.length) => while(sum>=target)
