给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
public void moveZeroes(int[] nums) { int n=nums.length; int j=-1; for(int i=0;i<n;i++){ if(nums[i]!=0){ j++; int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } } public void moveZeroes(int[] nums) { int n=nums.length; int arr[]=new int[n]; int j=0; for(int i=0;i<nums.length;i++){ if(nums[i]!=0){ arr[j++]=nums[i]; } } for(int i=0;i<n;i++){ nums[i]=arr[i]; } }给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 注意这五个元素可为任意顺序。 你不需要考虑数组中超出新长度后面的元素。
public int removeElement(int[] nums, int val) { int j=-1; int n=nums.length; for(int i=0;i<n;i++){ if(nums[i]!=val){ j++; int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } return j+1; }给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。
public int removeDuplicates(int[] nums) { int n=nums.length; if(n<2) return n; int j=0; for(int i=1;i<n;i++){ if(nums[i]!=nums[j]) nums[++j]=nums[i]; } return j+1; }给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。
示例 2:给定 nums = [0,0,1,1,1,1,2,3,3], 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面的元素。
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
//方法1 基数排序 class Solution { public void sortColors(int[] nums) { int[] count=new int[3]; for(int i=0;i<nums.length;i++){ count[nums[i]]++; } int index=0; for(int i=0;i<count[0];i++){ nums[index++]=0; } for(int i=0;i<count[1];i++){ nums[index++]=1; } for(int i=0;i<count[2];i++){ nums[index++]=2; } } } //方法2 快排(荷兰国旗) public void sortColors(int[] nums) { int i=0; int low=0; int high=nums.length-1; while(i<=high){ if(nums[i]==1){ ++i; }else if(nums[i]==0){ int temp=nums[i]; nums[i]=nums[low]; nums[low]=temp; //等于v部分不用再加 ++low; ++i; }else if(nums[i]==2&&i<=high){ int temp=nums[i]; nums[i]=nums[high]; nums[high]=temp; --high; } } }给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
public void merge(int[] nums1, int m, int[] nums2, int n) { int len1 = m - 1; int len2 = n - 1; int len = m + n - 1; while(len1 >= 0 && len2 >= 0) { // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码 nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--]; } // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1 while (len2 >= 0) { nums1[len--] = nums2[len2--]; } }在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
class Solution { public int findKthLargest(int[] nums, int k) { quick_select(nums,k,0,nums.length-1); return nums[k-1]; } private void quick_select(int []nums,int k,int start,int end){ if(start>=end) return ; int pivot=nums[start]; int l=start+1,r=end; while(l<=r){ if(nums[l]>pivot){ l++; continue; } if(nums[r]<=pivot){ r--; continue; } swap(nums,l,r); } swap(nums,start,r); if(r-start+1==k)return ; if(r-start+1>k) quick_select(nums,k,start,r-1); else quick_select(nums,k-(l-start),l,end); } private void swap(int[]nums,int i ,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } }给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明: 返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2
/** * * 思路1 哈希表 时间复杂度O(N) 空间复杂度O(N) * * * @param numbers * @param target * @return */ public static int[] twoSum(int[] numbers, int target) { int n=numbers.length; HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<n;i++){ if(map.containsKey(target-numbers[i])){ return new int[]{map.get(target-numbers[i])+1,i+1}; }else map.put(numbers[i],i); } return new int[]{}; } /** * * * 思路2 指针碰撞 时间复杂度O(N) 空间复杂度O(1) * * */ public static int[] twoSum2(int[] numbers, int target) { int n=numbers.length; int l=0; int r=n-1; while(l<r){ if(numbers[l]+numbers[r]==target){ return new int[]{l+1,r+1}; }else if(numbers[l]+numbers[r]<target){ l++; }else{ r--; } } return new int[]{}; } /** * * 思路3 暴力法 * * */ public static int[] twoSum3(int[] numbers, int target) { int n=numbers.length; for (int i = 0; i <n ; i++) { for (int j = i+1; j <n ; j++) { if(numbers[i]+numbers[j]==target){ return new int[]{i+1,j+1}; } } } return new int[]{}; }给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: “A man, a plan, a canal: Panama” 输出: true
/** * * 方法1 筛选 + 判断 * @param s * @return */ public boolean isPalindrome(String s) { StringBuffer sgood = new StringBuffer(); int length = s.length(); for (int i = 0; i < length; i++) { char ch = s.charAt(i); if (Character.isLetterOrDigit(ch)) { sgood.append(Character.toLowerCase(ch)); } } StringBuffer sgood_rev = new StringBuffer(sgood).reverse(); return sgood.toString().equals(sgood_rev.toString()); } /** * * 思路2 双指针 O(N) * * */ public boolean isPalindrome2(String s) { StringBuffer sgood = new StringBuffer(); int length = s.length(); for (int i = 0; i < length; i++) { char ch = s.charAt(i); if (Character.isLetterOrDigit(ch)) { sgood.append(Character.toLowerCase(ch)); } } int n = sgood.length(); int left = 0, right = n - 1; while (left < right) { if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) { return false; } ++left; --right; } return true; } /** * * 思路3 空间复杂度O(1) * * */ public boolean isPalindrome3(String s) { int n = s.length(); int left = 0, right = n - 1; //从左右两边选出第一个字符 while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { ++left; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { --right; } //比较左右两个字符 if (left < right) { if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false; } ++left; --right; } } return true; }编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
public static void reverseString(char[] s) { int n=s.length; int l=0; int r=n-1; while(l<r){ Character temp=s[l]; s[l]=s[r]; s[r]=temp; l++; r--; } System.out.println(s); }给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器，且 n 的值至少为 2。
/** * 思路1 暴力法 * */ public int maxArea(int[] height) { int res=0; for (int i = 0; i <height.length ; i++) { for (int j = 0; j <height.length ; j++) { res=Math.max(res,(j-i)*Math.min(height[i],height[j])); } } return res; } /** *思路2 * 双指针 时间复杂度O(N) * * * @param height * @return */ public int maxArea2(int[] height) { int i = 0, j = height.length - 1, res = 0; while(i < j){ res = height[i] < height[j] ? Math.max(res, (j - i) * height[i++]): Math.max(res, (j - i) * height[j--]); } return res; }给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例： 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
暴力 O(N*N) public int minSubArrayLen(int s, int[] nums) { int res=nums.length+1; for(int i=0;i<nums.length;i++){ int sum=0; for(int j=i;j<nums.length;j++){ sum+=nums[j]; if(sum>=s){ res=Math.min(res,j-i+1); break; } } } return res=res==nums.length+1?0:res; } 滑动窗口O(N) public int minSubArrayLen(int s, int[] nums) { // if(nums.length==0||nums==null) return 0; int l=0; int r=-1; int n=nums.length; //sum子序列之和 int sum=0; //res子序列长度 int res=nums.length+1; while( l<n){ if(r+1<n&&sum<s){ sum+=nums[++r]; } else{ sum-=nums[l++]; } if(sum>=s){ res=Math.min(res,r-l+1); } } return res==nums.length+1?0:res; }给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
public class lengthOfLongestSubstring { /** * * 思路1 滑动窗口 * * */ public int lengthOfLongestSubstring(String s) { int l=0; int r=-1; int res=0; int n=s.length(); //这里freq存放元素，也可以用其他结构 // HashSet<Character> subset = new HashSet<>(); int freq[]=new int[256];//这里freq[k]存放的是acsll为k字符存放的频率 while(l<n){ if(r+1<n&&freq[s.charAt(r+1)]==0) { freq[s.charAt(++r)]++; } //当右边元素已经包含于窗口,窗口收缩至重复元素下一个元素 else{ freq[s.charAt(l++)]--; } res=Math.max(res,r-l+1); } return res==0?0:res; } /** * * 思路2 hashset * * */ public int lengthOfLongestSubstring2(String s) { Set<Character> oc=new HashSet<>() ; int n=s.length(); int rk=-1; int res=0; for(int i=0;i<n;i++){ //左指针向右移动一格，移除一个字符 if(i!=0){ oc.remove(s.charAt(i-1)); } //右指针下一个字符不会溢出并且下一个字符没遇到过 while(rk+1<n&&!oc.contains(s.charAt(rk+1))){ oc.add(s.charAt(rk+1)); rk++; // 加入右边元素，右移指针 } res=Math.max(res,rk-i+1); } return res; // return res==0?0:res; } /** * 思路3 hashmap * */ public int lengthOfLongestSubstring3(String s) { int n = s.length(); int res = 0; int end=0,start=0; Map<Character,Integer> map=new HashMap<>(); for(;start<n && end<n;end++){ if(map.containsKey(s.charAt(end))){ start=Math.max(map.get(s.charAt(end)),start);//从有重复的下一个位置继续找 } map.put(s.charAt(end),end+1);//map每次更新 res=Math.max(res,end-start+1);//结果每次更新 } return res; } }给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明： 字母异位词指字母相同，但排列不同的字符串。 不考虑答案输出的顺序。 示例 1: 输入: s: “cbaebabacd” p: “abc” 输出: [0, 6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1： 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2： 输入: “cbbd” 输出: “bb”
给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例： 输入：S = “ADOBECODEBANC”, T = “ABC” 输出：“BANC”
