• 每日一题（刷题记录）

    H指数 10.7

    给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

    根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

    示例 1：输入：citations = [3,0,6,1,5] 输出：3

    解释：给定数组表示研究者总共有 5篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5次。由于研究者有 3 篇论文每篇 至少 被引用了 3
    次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

    示例 2：输入：citations = [1,3,1] 输出：1

    1. class Solution {
    2.     public int hIndex(int[] citations) {
    3.         Arrays.sort(citations);
    4.         for(int i=0;i
    5.         {
    6.             if(citations[i]>=citations.length-i)
    7.             {
    8.                 return Math.min(citations[i],citations.length-i);
    9.             }
    10.         }
    11.         return 0;
    12.     }
    13. }

    该解决方案首先对传入的引用次数组进行排序。然后，通过遍历排序后的数组，从最低引用次开始，检查是否存在至少有citations.size() - i次引用的论文数量。如果存在，则返回当前引用次和剩余未遍历的论文数量中较小的那个值作为H指数。如果不满足条件，则返回0。

    O(1)时间复杂度增删获取随即元素

    实现RandomizedSet 类：

    • RandomizedSet() 初始化 RandomizedSet 对象
    • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
    • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
    • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

    你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

    1. class RandomizedSet {
    2.     ArrayList list;
    3.     public RandomizedSet() {
    4.         this.list=new ArrayList<>();
    5.     }
    6.  
    7.     public boolean insert(int val) {
    8.         if(list.contains(val))return false;
    9.         list.add(val);
    10.         return true;
    11.     }
    12.  
    13.     public boolean remove(int val) {
    14.         if(list.contains(val))
    15.         {
    16.             list.remove((Integer) val);
    17.             return true;
    18.         }
    19.         return false;
    20.  
    21.     }
    22.  
    23.     public int getRandom() {
    24.         Random random=new Random();
    25.         int x=random.nextInt(list.size());
    26.         return list.get(x);
    27.     }
    28. }

     此题实现很简单，有个雷，就是remove方法，要类型转换，不然删除的就是下标为val的值而不是元素val，淦！ex！又是想念c++的一天~

    查找最小K对数字

    对列表排序（暴力做法）（想念c++的第10086天~呜呜呜）

    1. class Solution {
    2.     public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    3.         List> arr=new ArrayList<>();
    4.         if(nums1.length==0||nums2.length==0||k==0)return arr;
    5.         PriorityQueue minHeap = new PriorityQueue<>();
    6.         for(int i=0;i
    7.         {
    8.             for(int j=0;j
    9.             {
    10.                 minHeap.offer(new Nums(nums1[i],nums2[j]));
    11.             }
    12.         }
    13.         while(k-->0&&!minHeap.isEmpty())
    14.         {
    15.             Nums c=minHeap.poll();
    16.             Listlist=new ArrayList<>();
    17.             list.add(c.a);
    18.             list.add(c.b);
    19.             arr.add(list);
    20.         }
    21.         return arr;
    22.     }
    23. }
    24. class Nums implements Comparable{
    25.     int a,b,sum=0;
    26.     public Nums(int a,int b)
    27.     {
    28.         this.a=a;
    29.         this.b=b;
    30.         this.sum=a+b;
    31.     }
    32.  
    33.     @Override
    34.     public int compareTo(Nums o) {
    35.         return this.sum-o.sum;
    36.     }
    37. }

    堆优化+lamdba表达式

    1. class Solution {
    2.     public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    3.         List> arr=new ArrayList<>();
    4.         if(nums1.length==0||nums2.length==0||k==0)return arr;
    5.         PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
    6.         for (int i = 0; i < Math.min(nums1.length, k); i++) {
    7.             minHeap.offer(new int[]{nums1[i]+nums2[0],i,0});
    8.         }
    9.         while(k>0&&!minHeap.isEmpty())
    10.         {
    11.             int c[]=minHeap.poll();
    12.             Listlist=new ArrayList<>();
    13.             if (c[2]+1
    14.                 minHeap.offer(new int[]{nums1[c[1]]+nums2[c[2]+1],c[1],c[2]+1});
    15.             list.add(nums1[c[1]]);
    16.             list.add(nums2[c[2]]);
    17.             arr.add(list);
    18.             k--;
    19.         }
    20.         return arr;
    21.     }
    22. }

     移动机器人（数学，前缀和）10.10

    1. import java.util.Arrays;
    2.  
    3. class Solution {
    4.     public int sumDistance(int[] nums, String s, int d) {
    5.         long sum[]=new long[nums.length];
    6.         final int MOD=1000000007;
    7.         for(int i=0;i
    8.         {
    9.             if(s.charAt(i)=='R')sum[i]=nums[i]+d;
    10.             else sum[i]=nums[i]-d;
    11.         }
    12.         Arrays.sort(sum);
    13.         long res = 0;
    14.         for (int i = 1; i < nums.length; i++) {
    15.             res += 1L * (sum[i] - sum[i - 1]) * i % MOD * (nums.length - i) % MOD;
    16.             res %= MOD;
    17.         }
    18.         return (int)res;
    19.     }
    20. }
    21.  
    22. //R: +1
    23. //L: -1

    除自身以外数组的乘积 10/11

    1. import java.util.Arrays;
    2.  
    3. class Solution {
    4.     public int[] productExceptSelf(int[] nums) {
    5.         int ansPre[]=new int[nums.length];
    6.         int ansLas[]=new int[nums.length];
    7.         int ans[]=new int[nums.length];
    8.         ansPre[0]=1;
    9.         ansLas[0]=1;
    10.         int res=1;
    11.         for(int i=1;i< nums.length;i++)
    12.         {
    13.             ansPre[i]=nums[i-1]*ansPre[i-1];
    14.             ansLas[i]=nums[nums.length-i]*ansLas[i-1];
    15.         }
    16.         for(int i=0;i< nums.length;i++)
    17.         {
    18.             ans[i]=ansPre[i]*ansLas[nums.length-i-1];
    19.         }
    20.         return ans;
    21.     }
    22. }

    奖励最顶尖的K名学生 （废物方法）

    1. import java.util.*;
    2. class Solution {
    3.     public List topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
    4.         List id = new ArrayList<>();
    5.         PriorityQueue> stu = new PriorityQueue<>((o1, o2) -> {
    6.             if (o1.getValue() > o2.getValue()){
    7.                 return -1;
    8.             }
    9.             else if (o1.getValue() < o2.getValue()) {
    10.                 return 1;
    11.             } else {
    12.                 if (o1.getKey() > o2.getKey()) {
    13.                     return 1;
    14.                 } else return -1;
    15.             }
    16.         });
    17.         Setpf=new HashSet<>(Arrays.asList(positive_feedback));
    18.         Setnf=new HashSet<>(Arrays.asList(negative_feedback));
    19.         int score[] = new int[student_id.length];
    20.         for (int i = 0; i < report.length; i++) {
    21.             String s = report[i];
    22.             String ns[]=s.split(" ");
    23.             for (int j=0;j< ns.length;j++) {
    24.                 if (pf.contains(ns[j])) score[i] += 3;
    25.                 if (nf.contains(ns[j])) score[i] -= 1;
    26.             }
    27.         }
    28.         for (int i = 0; i < report.length; i++) {
    29.             AbstractMap.SimpleEntry pair = new AbstractMap.SimpleEntry(student_id[i], score[i]);
    30.             stu.offer(pair);
    31.         }
    32.         System.out.println(Arrays.toString(score));
    33.         for (int i = 0; i < k; i++) {
    34.             int pid = stu.poll().getKey();
    35.             id.add(pid);
    36.         }
    37.         return id;
    38.     }
    39.  
    40. }

    找出数组串联值  10/12（简单题）

    1. import java.util.ArrayList;
    2.  
    3. import java.util.Arrays;
    4.  
    5. import java.util.LinkedList;
    6.  
    7.  
    8.  
    9. class Solution {
    10.  
    11.     public long findTheArrayConcVal(int[] nums) {
    12.  
    13.         long ans=0;
    14.  
    15.         if(nums.length==0)return 0;
    16.  
    17.         if(nums.length==1)return nums[0];
    18.  
    19.         LinkedListlinkedList=new LinkedList<>();
    20.  
    21.         for(int i=0;i
    22.  
    23.         while(!linkedList.isEmpty()&&linkedList.size()>=2)
    24.  
    25.         {
    26.  
    27.             int pre=linkedList.pollFirst();
    28.  
    29.             int last=linkedList.pollLast();
    30.  
    31.             ans+=last;
    32.  
    33.             int cnt=0;
    34.  
    35.             while(last>0)
    36.  
    37.             {
    38.  
    39.                 last/=10;
    40.  
    41.                 cnt++;
    42.  
    43.             }
    44.  
    45.             ans+=pre*Math.pow(10,cnt);
    46.  
    47.         }
    48.  
    49.         if(!linkedList.isEmpty())ans+=linkedList.poll();
    50.  
    51.         return ans;
    52.  
    53.     }
    54.  
    55. }

    10/13避免洪水泛滥

    1. import java.util.Arrays;
    2. import java.util.HashMap;
    3. import java.util.Map;
    4. import java.util.TreeSet;
    5.  
    6. class Solution {
    7.     public int[] avoidFlood(int[] rains) {
    8.         int ans[]=new int[rains.length];
    9.         Arrays.fill(ans,1);
    10.         TreeSettreeSet=new TreeSet<>();
    11.         Map map=new HashMap<>();
    12.         for(int i=0;i
    13.         {
    14.             if(rains[i]==0)treeSet.add(i);//记录所有晴天
    15.             else {//如果是雨天，寻找最近的晴天抽水
    16.                 ans[i] = -1;
    17.                 if (map.containsKey(rains[i])) {
    18.                     Integer it = treeSet.ceiling(map.get(rains[i]));//寻找后面几天最近的晴天
    19.                     if (it == null) {
    20.                         return new int[0];
    21.                     } else {
    22.                         ans[it] = rains[i];
    23.                         treeSet.remove(it);
    24.                     }
    25.                 }
    26.                 map.put(rains[i], i);
    27.             }
    28.         }
    29.         return ans;
    30.     }
    31. }

    TreeSet中ceiling用法：

    public E ceiling(E e)

    参数

    e - 这是要匹配的值。

    返回值

    方法调用返回大于或等于e的最小元素，如果没有这样的元素则返回null。

    模拟题（今天的代码越写越长就离谱，纯纯模拟了）

    第一次用异常，好用+1+1+1螺旋矩阵

    1. import java.util.ArrayList;
    2. import java.util.Arrays;
    3. import java.util.List;
    4.  
    5. class Solution {
    6.     Listlist;
    7.     int m,n;
    8.     public List spiralOrder(int[][] matrix) {
    9.         list=new ArrayList<>();
    10.         m= matrix.length;
    11.         n=matrix[0].length;
    12.         if(m==1)
    13.         {
    14.             for(int i=0;i0][i]);
    15.             return list;
    16.         }
    17.         if(n==1)
    18.         {
    19.             for(int i=0;i0]);
    20.             return list;
    21.         }
    22.         for(int i=0,j=0;i<(m+1)/2;i++,j++)
    23.         {
    24.             try{
    25.                 add(i,j,matrix);
    26.             }catch (Exception E){
    27.                 break;
    28.             }
    29.             
    30.  
    31.         }
    32.         return list;
    33.     }
    34.     public void add(int i,int j,int[][] matrix)
    35.     {
    36.         for(int k=j;k
    37.             if(matrix[i][k]!=-101)
    38.             {
    39.                 list.add(matrix[i][k]);
    40.                 matrix[i][k]=-101;
    41.             }
    42.  
    43.         }
    44.         for(int k=i+1;k
    45.             if(matrix[k][n-1-j]!=-101){
    46.                 list.add(matrix[k][n-1-j]);
    47.                 matrix[k][n-1-j]=-101;
    48.             }
    49.  
    50.         }
    51.         for(int k=n-2-j;k>j;k--){
    52.             if(matrix[m-1-i][k]!=-101){
    53.                 list.add(matrix[m-1-i][k]);
    54.                 matrix[m-1-i][k]=-101;
    55.             }
    56.         }
    57.         for(int k=m-1-i;k>i;k--){
    58.             if(matrix[k][j]!=-101){
    59.                 list.add(matrix[k][j]);
    60.                 matrix[k][j]=-101;
    61.             }
    62.         }
    63.     }
    64. }

    矩阵置零

    1. import java.util.ArrayList;
    2. import java.util.Arrays;
    3. import java.util.List;
    4.  
    5. class Solution {
    6.     int dx[]=new int[]{0,1,-1,0};
    7.     int dy[]=new int[]{-1,0,0,1};
    8.     public void setZeroes(int[][] matrix) {
    9.         List>list=new ArrayList<>();
    10.         for(int i=0;i
    11.         {
    12.             for(int j=0;j
    13.             {
    14.                 if(matrix[i][j]==0)
    15.                     list.add(Arrays.asList(i,j));
    16.             }
    17.         }
    18.         for(int i=0;i
    19.         {
    20.             int x=list.get(i).get(0);
    21.             int y=list.get(i).get(1);
    22.             for(int j=0;j< matrix[0].length;j++)matrix[x][j]=0;
    23.             for(int k=0;k< matrix.length;k++)matrix[k][y]=0;
    24.         }
    25.     }
    26. }

    11/7打卡，好久没打卡啦，但每天都坚持在刷题哦~我觉得最大的进步不是只做自己会的，而是去接受自己不会的，做自己从未做过的~打破舒适圈~！！！

    1. import java.util.*;
    2.  
    3. class Solution {
    4.     public static void main(String[] args) {
    5.         System.out.println(vowelStrings(new String[]{"are", "amy", "u"}, 0, 2));
    6.     }
    7.  
    8.     public static int vowelStrings(String[] words, int left, int right) {
    9.         int ans = 0;
    10.         List list = new ArrayList<>();
    11.         list.add('a');
    12.         list.add('e');
    13.         list.add('i');
    14.         list.add('o');
    15.         list.add('u');
    16.         for (int i = left; i <= right; i++) {
    17.             if (list.contains(words[i].charAt(0)) && list.contains(words[i].charAt(words[i].length() - 1))) ans++;
    18.         }
    19.         return ans;
    20.     }
    21. }

    12.25

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

    利用归并排序的思想，返回最中间的中位数

    1. class Solution {
    2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    3.         //一边归并，一边找中位数
    4.         int len = nums1.length + nums2.length;
    5.         int cnt = 0;
    6.         int arr[] = new int[len];
    7.         double ans;
    8.         int i = 0, j = 0;
    9.         while (i < nums1.length && j < nums2.length) {
    10.             if (nums1[i] <= nums2[j]) {
    11.                 arr[cnt++] = nums1[i++];
    12.                 continue;
    13.             }
    14.             if (nums1[i] >= nums2[j]) {
    15.                 arr[cnt++] = nums2[j++];
    16.                 continue;
    17.             }
    18.         }
    19.         while (i < nums1.length) arr[cnt++] = nums1[i++];
    20.         while (j < nums2.length) arr[cnt++] = nums2[j++];
    21.         return len % 2 == 0 ? (float) (arr[len / 2 - 1] + arr[len / 2]) / 2 : (float) arr[len / 2];
    22.     }
    23. }

     

  • 相关阅读:
    sqli-labs/Less-60
    二维偏序问题
    【Java】之Java8新特性
    带你深入理解面向对象三大特性 - 继承，多态
    SpringBoot 自动配置预加载类-01
    静态文件鉴权
    [二进制学习笔记]LibcSearcher报错Requirements for download
    给定一个字符串str，求最长回文子序列长度。
    gpt-4-vision-preview 识图
    Service详解
  • 原文地址：https://blog.csdn.net/m0_71385141/article/details/133633491