算法学习--持续更新

算法

2025年5月24日

• 完成：快速排序、快速排序基数优化、尾递归优化

  • 快排

    public class QuickSort {public void sort(int[] nums, int left, int right) {if(left>right){return;}int partiton = quickSort(nums,left,right);sort(nums,left,partiton-1);sort(nums,partiton+1,right);}int  quickSort(int[] nums, int left, int right) {int i = left,j=right;while (i<j){while (i<j&&nums[left]>=nums[j]) {//TODO nums[left]>nums[j]从大到小排序j--;}while (i<j && nums[left]<nums[i]) {i++;}swap(nums,i,j);}swap(nums,i,left);return left;}void swap(int[] nums,int left ,int right){int temp = nums[left];nums[left]= nums[right];nums[right] = temp;}
    }
    

  • 快速排序基数优化：注意拿到mid之后要与left交换，后续不变。有一个取中位数的新方法

    int mid = midThree(nums, left, right, left + (right - left) / 2);
    swap(nums,mid,left);//交换mid和left TODO 交换完成后以后需要用left
    

    left要与mid交换，后续直接依旧用left做基准。

    可一直用left做基准，通过修改left所对应的值来优化代码。

    int midThree(int[] nums,int num1,int num2,int num3){//取中位数int j = nums[num1],k=nums[num2],l=nums[num3];if ((j<=k&&j>=l)||(j>=k&&j<=l))return num1;if ((k<=j && k>=l)||(k>=j&&k<=l))return num2;return num3;}
    

  • 尾递归优化：排序算法的选择注意是

    //        if (left>right){
    //            return;
    //        }   TODO 不能写这种形式，原因为这种只计算一遍修改后的right和left并未递归while (left<right){//...//用partition-left和right-partition来判断，选择短的进行计算}
    

leetcode100

1.两数之和easy

• 暴力解法：开始想的先排序，后再判断target-nums[i]<nums[j],之后的直接不计算，但是这种方法也改了数组的下标，这种方法适合不用找下标的。

  class Solution {public int[] twoSum(int[] nums, int target) {//暴力 不可排序for (int j =0 ;j<nums.length;++j){for (int i = j+1; i < nums.length; ++i) {if (nums[i]==target-nums[j]){return new int[]{j,i};}}}return null;}
  }
  

  Arrays.sort(nums);//改变了下标
  for (int j =0 ;j<nums.length-1;j++){for (int i = j+1; i < nums.length; i++) {if (nums[i]<target-nums[j]){continue;}if (nums[i]==target-nums[j]){return new int[]{j,i};}elsebreak;}
  }
  return null;
  

  时间复杂度O(N2)—两次嵌套for循环

  空间复杂度O(1)—无需其他数组

  

• 哈希表：保证下标和数组一一对应，且可以快速找到。

  // TODO 哈希表解法
  //写入哈希表 key--数组值  value--小标
  //对于每一个 x，我们首先查询哈希表中是否存在 target - x，
  // 然后将 x 插入到哈希表中，
  HashMap<Integer,Integer> map = new HashMap<>();
  for(int i = 0 ; i < nums.length ; i++){if (map.isEmpty()||!map.containsKey(target-nums[i]))//先判断是否存在再去放入mapmap.put(nums[i],i);								//可避免Value值一致所导致的key一致elsereturn new int[]{map.get(target-nums[i]),i};
  }
  return new int[0];
  

  由题意可判断，出现两个相同的数必为解。因为题中说每一个target只有一个解，若两个相同的数非题解的话，则出现一个target有两个解。

  时间复杂度O(N)—一次循环处理

  空间复杂度O(N)—一个等长度的HashMap

  重点⭐：先检查是否有target - x，再插入map

2.字母异位词分组mid

要点⭐⭐：字母出现的次数相同

• 排序法：将strs数组中的str进行排序，那么异位词之间的排序应该相同，则将这些排序作为key存入HashMap，value为字母异位次的List<String>列表。

  HashMap<String, List<String>>  map = new HashMap<>();
  for (String str : strs){//此句的空间复杂度  nchar[] arrs = str.toCharArray();Arrays.sort(arrs);//此句的空间复杂度 klogkString key = new String(arrs);//此处不可用arrs.toString()List<String> list = map.getOrDefault(key,new ArrayList<String>());list.add(str);map.put(key,list);//得到list之后要放入Map中
  }
  return new ArrayList<List<String>>(map.values());
  

  arrs.toString()的结果是：

  stdout:
  [C@20ad9418
  [C@31cefde0
  [C@439f5b3d
  [C@1d56ce6a
  [C@5197848c
  [C@17f052a3

时间复杂度：O(nklogk)—n为strs的长度，k为最大str的长度

​ 对于每个字符串，需要 O(klogk) 的时间进行排序–所以准确来说为O(nklogk);

空间复杂度：O(nk)

• 计数法：通过计算每一个str中所含有字母的个数来判断，每一个str都计算一个26位的数组用来计数。通过构建字符串key=“[字母][个数][字母][个数]”的形式来构成HashMap的key，value为字母异位次的List<String>列表。

  HashMap<String, List<String>>  map = new HashMap<>();
  for(String str : strs){//此句时间复杂度 nchar[] arrs = str.toCharArray();//此句空间复杂度 nint[] count = new int[26];for (int i = 0; i < arrs.length; i++) { 此句空间复杂度 k 时间复杂度 kcount[arrs[i]-'a']++;}StringBuilder sb = new StringBuilder();//使用builder来构建Stringfor (int i = 0; i < 26; i++) {if (count[i]!=0){sb.append((char)i+'a');   //需注意区分i(--代表字母)和count[i](--代表个数)的含义sb.append(count[i]);}}String key = sb.toString();List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key,list);
  }
  return new ArrayList<List<String>>(map.values());
  

  时间复杂度：O(nk)

  空间复杂度：O(nk)

3.最长连续序列mid

解决办法是连续序列就找这个连续中最小的值（若有当前值-1的值，则跳过），找到后再去找是否存在最小值+1的值。若存在则当前长度+1，再去找再+1的值，直至不存在。若不存在则将longestLength=Math.max(currentLength,LongestLength)赋值。

HashSet<Integer> setNum = new HashSet<>();//用来去重和找有否包含
//放入Set
for (int num:nums){setNum.add(num);
}
/*** 是否含有num-1，若有则跳过。* 若没有着当前长度为1，再寻找num+1，若有当前长度+1。* 若没有则当前长度传给总长度，当前长度清零。*/
int longestLength = 0;
for (int num : setNum){//这里遍历的是set，去重之后运算时间更快int currentLength = 0;int currentNum = num;if (!setNum.contains(currentNum-1)) {currentLength++;while (setNum.contains(++currentNum)){currentLength++;}longestLength=Math.max(longestLength,currentLength);}}
return longestLength;

时间复杂度和空间复杂度都为O(n)

找最小值

4.连续零easy

双指针：办法就是右指针遍历一遍，找到所有的非零值，然后依次放在左边⭐。左边每放一个值，左指针就往右移动一个。直到右指针走到数组的末尾，此时左指针指的是0的开始第一位，将左指针所指开始到结束所有位置写上零。

int left = 0,right = 0;
//找到第一个零，从第一个0开始
//while (left<nums.length&&nums[left]!=0){//加一句判断是否越界//  left++;
//}
//for (right=left+1; right < nums.length; right++) {
for (right=0; right < nums.length; right++) {//右指针从零开始，查询所有的非零数，查到之后直接写道左边if (nums[right]!=0){//用if，若是用while的话nums[left++]=nums[right];//这一句的left一直++}
}
while (left<nums.length){//左指针之后的所有数均为零。nums[left++]=0;
}

时间复杂度：O(n)

空间复杂度：O(1)

5.盛最多水的容器mid

双指针：数组左右两边一边一个指针，计算当前面积currentArea并于最大面积比较，将较大的值赋值给largestArea。然后，比较两个指针所对应的值，移动较小的那个指针⭐，再计算面积，再赋值。

int left = 0;
int right = height.length-1;
int currentArea = 0;
int largestArea = Integer.MIN_VALUE;
while (left<right){currentArea=(right-left)*Math.min(height[left],height[right]);largestArea=Math.max(largestArea,currentArea);if (height[left]<=height[right]){left++;}elseright--;
}
return largestArea;

时间复杂度：O(n)

空间复杂度：O(1)

重点是⭐：两个指针放在左右两边，然后将较小的那个往中间移动。移动较大的话，最大也不会大于当前的值。

6.三数之和mid

最常见的就是一个遍历算法，三层遍历的方法。分别选出第一个第二个和第三个。

问题：

• 这种算法不容易避免结果重复
• 算法的时间复杂度将达到O(N3)

但是我们可以先对数组排序，依次遍历第一个和第二个数。知道第一个和第二个数之后，由于nums[first]+nums[second]+nums[third]=0可知，针对排序后的数组，去倒序遍历第三个数。三个数不重复的情况下便有first>second>third。则第三个数只需要遍历到second，若之后还未找到满足第三个数则第二个循环结束。

Arrays.sort(nums);//排完序从小到大 空间复杂度O(nlogn)
List<List<Integer>> res  =new ArrayList<>();
for (int i = 0; i < nums.length; i++) {if (i>0&&nums[i]==nums[i-1]){  //第一个数，不取与上次相同的数。重点continue;}int k = nums.length-1;//第三个数声明在这，即第二个数依次增大，大于上一个的数不必要再取。for (int j = i+1; j < nums.length; j++) {if (j>i+1&&nums[j]==nums[j-1]) continue；//第一个数，不取与上次相同的数。while (k>j&&nums[k]>-nums[i]-nums[j]）{k--;}if (k<=j){  //若全是大于的数，则跳出第二个数的遍历。重点break;}if (nums[k]==-nums[i]-nums[j]){List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);res.add(list);}}
}
return res;

两次去重，可保证不再有重复的结果。

第三个数声明在第二次遍历之外，当第二次遍历second时。

• 若第三个数一直大于-nums[second]-nums[third],则second之后的数也将找不到满足条件的数。所以跳出二次遍历。
• 若第三个数找到满足条件的了，那么第二个数继续遍历，由于是排序之后的，则下一个second一定比当前的大。所以满足条件的third一定在当前third的左边，所以third不需要重置。

时间复杂度：O(n2)

​ 可将second遍历和third遍历看成一次。

空间复杂度：O(nlogn)/+O(n)

7.接雨水hard

• 动态规划：采用两个数组left[]和right[]来记录第i个位置的左右边界，左边界的值从左往右遍历为left[i]=max(left[i-1],height[i])。右边界的值从右往左遍历为right[height.length-1-i] = Math.max(right[height.length-i],height[height.length-1-i]);。计算i位置的存水量为Math.min(left[i],right[i])-height[i];。并且两个数组的初始值为height[0],height[n-1]。

  //左右边界
  int[] left = new int[height.length];
  int[] right = new int[height.length];
  int v=0;
  Arrays.fill(left,0);
  Arrays.fill(right,0);
  //确定左右边界
  left[0]=height[0];
  right[right.length-1]=height[height.length-1];//初始化边界很重要
  for (int i = 1; i < height.length; i++) {left[i] = Math.max(left[i-1],height[i]);right[height.length-1-i]=Math.max(right[height.length-i],height[height.length-1-i]);
  }
  //计算ide水量=
  for (int i = 0; i < height.length; i++) {v+=Math.min(left[i],right[i])-height[i];
  }
  return v;
  

  时间复杂度：O(n)

  空间复杂度：O(n)

• 单调栈：采用栈的形式，维护一个递减的单调栈。保证里面可以有一个凹陷，所以栈中最少有两个值。

  • 当栈为空时，直接将当前的i压入栈。

  • 当不为空时，只要当前的height[i]>height[stack.peek()]是一个升序，就可进行判断，是否要计算或者弹出。升序最起码证明出stack.peek()较小。只需证明除了栈顶元素栈内还有元素，就可证明栈内至少有两个元素。

    • 若没有两个元素，则当前栈内+当前这个为升序，所以弹出栈内元素，保证递减。重新压入当前的i。

    • 若有两个元素，则进行计算，并且弹出top。将left作为新的top。重新压入当前的i。（这两步无论走哪一条逻辑都有弹出元素，所以在判断之前先弹出栈顶。并且之后都要压入当前的元素，所以push放在最后统一执行。）

      

      //单调栈,递减
      Stack<Integer> stack = new Stack<>();
      int v = 0;
      for (int i = 0; i < height.length; i++) {if (stack.isEmpty()){stack.push(i);continue;}while (height[i]>height[stack.peek()]) {//只要满足此条件就一直执行，计算所有以heigh[i]作为右边界的所有区间int top = stack.pop();//先弹出栈顶，看能否剩下一个if (stack.isEmpty()) {//保证不会为空,判断是否多于两个break;}int left = stack.peek();v += (i - left - 1) * (Math.min(height[i], height[left]) - height[top]);//计算i位置的存水量。}stack.push(i);
      }
      return v;
      

• 双指针：有动态规划推导而来。可见两个边界数组均为有序的，且一个递增一个递减。那我们可以用两个常量leftMax=max(leftMax,height[left])和rightMax=max(rightMax,height[right])来表示当前left位置的左边界和当前right位置的右边界。

  • 当leftMax<rightMax时，此时当前left位置左边界固定为leftMax，而右边界又为递增的，所以left的之后的右边界将一直大于leftMax，所以决定left位置的存水量的为leftMax。计算left位置存水量：leftMax-height[left];

  • 当leftMax>=rightMax时，此时right的右边界为rightMax，此后leftMax将一直增大。rightMax将限制right位置存水量，计算right位置的存水量为：rightMax-height[right];。

    //双指针
    int heightLength = height.length;
    int leftMax = 0,rightMax = 0;
    int v = 0;
    int left = 0,right=heightLength-1;//两个指针，从左从右遍历
    while ( left<=right) {//直到相遇leftMax=Math.max(leftMax,height[left]);rightMax=Math.max(rightMax,height[right]);//left的村水量if (leftMax<rightMax){v+=leftMax-height[left];left++;//计算完left之后，计算下一个left}else {v+=rightMax-height[right];right--;}
    }
    return v;
    

    时间复杂度：O(n)

    空间复杂度：O(1)

  

8.无重复数组的最长子串mid

采用滑动窗口的方法，使用HashSet结构记录当前窗口内所包含的不重复的子串。判断set中是否包含right的位置的字符。如果包含则移除set中arr[i],并且i++滑动窗口左边界向右移。如果不包含则将arr[right]加入set中，并扩展右边界right++，记录当前最长的子串。

//选定一个开始，一个结尾。记录当前的子串长度
int longest = 0,current = 0;
int right = 0;
int sLength = s.length();
char[] arr = s.toCharArray();
Set<Character> set  = new HashSet<>();//去重set
for (int i = 0; i < sLength; i++) {while (right<sLength&&(set.isEmpty()||!set.contains(arr[right]))){//若right没到结尾，并且set为空（窗口为空）或者set不包含right位置的字符。则加入窗口，更新最大值。set.add(arr[right++]);current++;longest = Math.max(longest,current);}set.remove(arr[i]);//若有重复的则删除左边界，更新当前长度。current--;
}
return longest;

时间复杂度：O(n)

空间复杂度：O(n)

9.找到所有字符串中的字母异位词mid

采用计数的方式，pCount统计p中的每个字符个数。而s中则采用定长的滑动窗口。初始化之后，若pCount与sCount相同Arrays.equals(pCount,sCount)则记录当前的字符的下标。

public List<Integer> findAnagrams(String s, String p) {if (p.length()>s.length()){//判断是否合理return new ArrayList<>();//返回空List}//计数int[] countp = new int[26];int[] countstr = new int[26];//子串的计数List<Integer> list = new ArrayList<>();//pfor (int i = 0; i < p.length(); i++) {//分别记录plength长度内字符出现的字数countp[p.charAt(i)-'a']++;countstr[s.charAt(i)-'a']++;//先记录0~plength-1内的}//if (Arrays.equals(countp,countstr)){//判断0~plength-1内有没有，有的话记录0list.add(0);}//for (int i = 0; i < s.length() - p.length(); i++) {//注意i的取值范围countstr[s.charAt(i)-'a']--;//去除滑动窗口左边的countstr[s.charAt(i+p.length())-'a']++;//加上滑动窗口右边的，因为要定长if (Arrays.equals(countp,countstr)){//走一下判断一下list.add(i+1);}}return list;
}

时间复杂度：O(n)??

p[p.charAt(i)-‘a’]++;
countstr[s.charAt(i)-‘a’]++;//先记录0~plength-1内的
}
//
if (Arrays.equals(countp,countstr)){//判断0~plength-1内有没有，有的话记录0
list.add(0);
}
//
for (int i = 0; i < s.length() - p.length(); i++) {//注意i的取值范围
countstr[s.charAt(i)-‘a’]–;//去除滑动窗口左边的
countstr[s.charAt(i+p.length())-‘a’]++;//加上滑动窗口右边的，因为要定长
if (Arrays.equals(countp,countstr)){//走一下判断一下
list.add(i+1);
}
}
return list;
}

> 时间复杂度：O(n)??
>
> 空间复杂度：O(1)??