A基础算法
排序 归并思想
786. 第 K 个最小的素数分数
二分 4. 寻找两个正序数组的中位数
786. 第 K 个最小的素数分数 实数域二分
模拟运算 8 字符串转换整数 (atoi)
前缀和与差分 干草堆
双指针 3. 无重复字符的最长子串
438. 找到字符串中所有字母异位词 30. 串联所有单词的子串 固定大小的滑窗
5966. 还原原数组 匹配二元组
位运算
离散化
区间合并

排序

归并思想

786. 第 K 个最小的素数分数

  1. class Solution {
  2.     /*
  3.        思路1：多路归并
  4.        结果集合可以表示为:
  5.        arr[0]/arr[1]
  6.        arr[0]/arr[2],arr[1]/arr[2]
  7.        arr[0]/arr[3],arr[1]/arr[3],arr[2]/arr[3]
  8.        ...
  9.        问题转化为多个有序数组寻找第k小的数?
  10.        s1:将每个数组的最小值放入小根堆中
  11.        s2:进行k-1次更新操作,此时堆顶就是第k小值
  12.        时间复杂度：
  13.        s1: n*logn
  14.        s2: k*logn
  15.        总： max(n,k)*logn
  17.        为什么使用堆？
  18.        假设有t个有序数组，暴力解法每次找t个最小值中的最小值，然后将最小值所在数组的指针移动1位，这里通过堆维护t个有序数组中最小值的最小值，降低了寻找最小值的时间复杂度。
  20.        思路2：双指针+二分
  21.              由于所有结果集的范围在[0,1]的范围内,因此可以猜1个数值x,然后采用双指针策略确定
  22.              有序数组中有多少个小于x的结果
  24.         时间复杂度:二分次数取决于精度，精度为 C = 10^8,总的时间复杂度 n*logC
  25.     */
  27.     public int[] kthSmallestPrimeFraction(int[] arr, int k) {
  28.         Queue<int[]> q = new PriorityQueue<>((o1,o2)->{   // 小根堆,存储的是下标
  29.             int v1 = arr[o1[0]] * arr[o2[1]];
  30.             int v2 = arr[o2[0]] * arr[o1[1]];
  31.             return Integer.compare(v1,v2);
  32.         });
  34.         int n = arr.length;
  35.         for(int j = 1;j < n;++j) q.offer(new int[]{0,j});
  37.         while(k-- > 1){
  38.             int[] top = q.poll();
  39.             int i = top[0],j = top[1];
  40.             if(i+1 < j) q.offer(new int[]{i+1,j});
  41.         }
  43.         int[] res = q.peek();
  44.         return new int[]{arr[res[0]],arr[res[1]]};
  45.     }
  46. }

二分

4. 寻找两个正序数组的中位数

  1. class Solution {
  2.     /*
  3.        两个思路：
  4.        1)递归求解两个正序数组中从小到大第k个数,每次递归都能舍弃k/2的数,时间复杂度O(log(m+n)) (推荐,容易想)
  5.        2)利用中位数的性质二分查找第k个数,时间复杂度O(log(min(m,n)))
  7.        注意: 两个方法都需要特别关注一些corner case的处理
  9.     */
  10.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  11.         int len = nums1.length + nums2.length;
  12.         if(len % 2 == 0){
  13.             int v1 = find(nums1,0,nums2,0,len/2);
  14.             int v2 = find(nums1,0,nums2,0,len/2+1);
  15.             return (double)(v1+v2) / 2.0;
  16.         }else{
  17.             return (double)find(nums1,0,nums2,0,len/2+1);
  18.         }
  19.     }
  21.     /*
  22.       两个数组分别从s1和s2开始,查找两个数组的第k个数
  23.       难点: 下标处理以及数组为空以及越界情况的考虑
  24.     */
  25.     int find(int[] nums1,int s1,int[] nums2,int s2,int k){
  26.         if(nums1.length-s1 > nums2.length-s2)            // 确保num1的长度更短
  27.             return find(nums2,s2,nums1,s1,k);
  28.         if(s1 == nums1.length) return nums2[s2+k-1];     // num1长度为0
  29.         if(k == 1 && s1 != nums1.length) return Math.min(nums1[s1],nums2[s2]);
  31.         int ns1 = Math.min(s1 + k/2,nums1.length);       // 可能越界
  32.         int ns2 = s2 + (k-k/2);
  33.         if(nums1[ns1-1] > nums2[ns2-1]){
  34.             return find(nums1,s1,nums2,ns2,k-(ns2-s2));
  35.         }else
  36.             return find(nums1,ns1,nums2,s2,k-(ns1-s1));
  37.     }
  38. }

模拟运算

8. 字符串转换整数 (atoi)

  1. class Solution {
  3.     public int myAtoi(String s) {
  4.         // 去除空格
  5.         int len = s.length();
  6.         int i = 0;
  7.         while(i < len && s.charAt(i) == ' ') ++i;
  8.         if(i == len) return 0;
  10.         // 确定符号位
  11.         int sign = 1;
  12.         if(s.charAt(i) == '-'){
  13.             sign = -1; ++i;
  14.         }else if(s.charAt(i) == '+'){
  15.             ++i;
  16.         }
  18.         // 处理符号位后数字部分(注意溢出处理)
  19.         int res = 0;
  20.         while(i < len && Character.isDigit(s.charAt(i))){
  21.             int v = s.charAt(i) - '0';
  22.             /*溢出处理*/
  23.             if(sign > 0 && res > (Integer.MAX_VALUE-v)/10){
  24.                 res = Integer.MAX_VALUE; break;
  25.             }
  26.             if(sign < 0 && res < (Integer.MIN_VALUE + v)/10){
  27.                 res = Integer.MIN_VALUE; break;
  28.             }
  29.             res = res * 10 + sign * v;
  30.             ++i;
  31.         }
  32.         return res;
  33.     }
  34. }

前缀和与差分

干草堆

  1. import java.util.*;
  2. import java.io.*;
  4. class Main{
  5.     /*
  6.        基本思路:差分+求中位数
  8.        求中位数的的方式：
  9.        1)排序，这里值域范围比较小(25000)，也可以采用桶排序
  10.        2)也可以采用快排思想找到第k大的数
  12.     */
  14.     public static int solve(int[] arr,int l,int r,int k) {
  15.         if(l >= r) return arr[l];
  16.         int mid = (r - l)/2 + l;
  17.         int pivot = arr[mid];
  18.         int ll = l-1,rr = r+1;
  19.         do{
  20.             do ++ll; while(arr[ll] < pivot);
  21.             do --rr; while(arr[rr] > pivot);
  22.             if(ll < rr){
  23.                 int temp = arr[ll]; arr[ll] = arr[rr]; arr[rr] = temp;
  24.             }
  25.         }while(ll < rr);
  27.         return rr >= k ? solve(arr,l,rr,k) : solve(arr,rr+1,r,k);
  28.     }
  30.     public static void main(String[] args) throws NumberFormatException, IOException{
  31.          BufferedReader buf =new BufferedReader(new InputStreamReader(System.in));
  32.          String[] arr = buf.readLine().split(" ");
  33.          int N = Integer.parseInt(arr[0]),K = Integer.parseInt(arr[1]);
  35.          int[] diff = new int[N+2];
  36.          while(K-- > 0){
  37.              arr = buf.readLine().split(" ");
  38.              int l = Integer.parseInt(arr[0]),r = Integer.parseInt(arr[1]);
  39.              diff[l] += 1; diff[r+1] -= 1;
  40.          }
  42.          for(int i = 1;i <= N;++i) diff[i] = diff[i-1] + diff[i];
  44.          System.out.println(solve(diff,1,N,N/2+1));
  45.     }
  46. }

双指针枚举

3. 无重复字符的最长子串

  1. class Solution {
  2.     /*
  3.        基本思路: 双指针优化枚举
  4.        i:表示以i位置字符结尾的子串集合
  5.        j:代表不包含重复字符的最左边界
  6.        i,j在枚举过程中都单调不减
  7.     */
  8.     public int lengthOfLongestSubstring(String s) {
  9.         int[] map = new int[256];
  10.         int res = 0;
  11.         for(int i = 0,j = 0;i < s.length();++i){
  12.             char c = s.charAt(i); map[c]++;
  13.             while(map[c] > 1){                   // 重复的字符必定是划入的字符
  14.                 map[s.charAt(j)]--; ++j;
  15.             }
  16.             res = Math.max(res,i-j+1);
  17.         }
  18.         return res;
  19.     }
  20. }

固定大小的滑窗

438. 找到字符串中所有字母异位词

  1. class Solution {
  2.     /*
  3.       基本思路：滑动窗口(双指针)+map维护状态
  4.       map[i] = p中字符i出现次数-s中窗口内字符i出现次数
  5.     */
  6.     public List<Integer> findAnagrams(String s, String p) {
  7.         int len1 = s.length(),len2 = p.length();
  8.         int[] map = new int[26];                   // 
  10.         for(int i = 0;i < len2;++i) map[p.charAt(i)-'a']++;
  11.         int sum = 0;
  12.         for(int i = 0;i < 26;++i) sum = map[i] > 0 ? sum + 1 : sum;
  14.         int cnt = 0;
  15.         List<Integer> res = new ArrayList<>();
  17.         int l = 0;
  18.         for(int r = 0;r < len1;++r){
  19.             int k = s.charAt(r)-'a'; map[k]--;
  20.             if(map[k] == 0) ++cnt;
  22.             if(r-l+1 > len2){
  23.                 int idx = s.charAt(l) - 'a';
  24.                 if(map[idx] == 0) --cnt;
  25.                 map[idx]++;
  26.                 ++l;
  27.             }
  29.             if(cnt == sum) res.add(l);
  30.         }
  31.         return res;
  32.     }
  33. }

30. 串联所有单词的子串

  1. class Solution {
  2.     /*
  3.        分组+双指针(滑动窗口)  
  4.        由于每个单词的长度是固定的,设为w,
  5.        因此可以从
  6.        0, w , 2w, 3w, ...
  7.        1, w+1,2w+1,...
  8.        ....
  10.        分组采用滑动窗口判断，通过hash表+cnt标识当前窗口是否由words组成
  13.        题目中cnt表示与子集数量一致的单词种类个数,去除注释部分也正确,原因待探究
  14.        该题解题思路类似于LC78 最小覆盖子串，但题意上略有差别
  16.     */
  17.     public List<Integer> findSubstring(String s, String[] words) {
  18.         List<Integer> res = new ArrayList<>();
  19.         if(words.length == 0) return res;
  20.         int n = s.length(),m = words.length,w = words[0].length();
  22.         Map<String,Integer> smap = new HashMap<>(),wmap = new HashMap<>(); 
  23.         for(String t:words) wmap.put(t,wmap.getOrDefault(t,0)+1);
  24.         int cnt = 0;
  26.         for(int i = 0;i < w;++i){
  27.             smap.clear(); cnt = 0;
  28.             int l = i;
  29.             for(int r = i+w;r <= n;r += w){
  30.                 String tmp = s.substring(r-w,r);
  31.                 if(wmap.containsKey(tmp)){
  32.                     int v1 = smap.getOrDefault(tmp,0)+1,v2 = wmap.get(tmp);
  33.                     smap.put(tmp,v1);
  34.                     if(v1 == v2) ++cnt;
  35.                     // if(v1 == v2+1) --cnt;
  36.                 }
  38.                 if((r-l)/w > m){
  39.                     String sl = s.substring(l,l+w);
  40.                     if(wmap.containsKey(sl)){
  41.                         int v1 = smap.get(sl)-1,v2 = wmap.get(sl);
  42.                         smap.put(sl,v1);
  43.                         // if(v1 == v2) ++cnt;
  44.                         if(v1 == v2-1) --cnt;
  45.                     }
  46.                     l += w;
  47.                 }
  49.                 if((r-l)/w == m && cnt == wmap.size()) res.add(l);
  50.             }
  51.         }
  52.         return res;
  53.     }
  54. }

匹配二元组

5966. 还原原数组

  1. class Solution {
  2.     /*
  3.        排序+双指针检查
  4.        思路：nums中最小的数字必定对应着原始数组中最小的数字,根据这个性质枚举k值
  5.        双指针的作用：实现lower和higher的两两匹配,固定low匹配high(必须先排序)
  6.     */
  7.     public int n;
  8.     public boolean[] vis;
  9.     int[] res;
  11.     public int[] recoverArray(int[] nums) {
  12.         n = nums.length;
  13.         vis = new boolean[n];
  14.         res = new int[n/2];
  16.         Arrays.sort(nums);
  18.         int right = -1;
  19.         for(int i = 1;i < n;++i){
  20.             int tmp = nums[i]-nums[0];
  21.             if(tmp == 0 || (tmp & 1) == 1) continue;
  22.             if(check(nums,tmp,i)) break;
  23.         }
  24.         return res;
  25.     }
  27.     /*l:lower起始位置  r:high起始位置 */
  28.     boolean check(int[] nums,int val,int r){
  29.         Arrays.fill(vis,false);
  31.         int l = 0,idx = 0;
  32.         while(r < n){
  33.             // 已经配对
  34.             if(vis[l]){
  35.                 ++l; continue;
  36.             }
  38.             // 匹配新的low
  39.             if(nums[r]-nums[l] == val){
  40.                 vis[l] = true; vis[r] = true;
  41.                 res[idx++] = nums[l] + val / 2;   // 匹配过程中存储值
  42.                 ++l; 
  43.             }
  44.             ++r;
  45.         }
  47.         // 检查所有数字是否都已经配对
  48.         for(int i = 0;i < n;++i)
  49.             if(!vis[i]) return false;
  51.         return true;
  52.     }
  53. }