devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十四届 蓝桥杯java组备赛考纲解读 技巧 查找 深搜宽搜 DFS 动态规划 数论 暴力枚举_蓝桥杯java考试范围

作者：从前慢现在也慢 | 2024-02-10 00:58:35

赞

踩

蓝桥杯java考试范围

CSDN客服说是广告我就删减了一部分

大佬经验

第一次参赛获Java B组国二，给蓝桥杯Beginners的6700字保姆级经验分享

Java常用API
4. 集合API、集合遍历、排序（建议掌握）
7. 数学知识（建议掌握）
三、蓝桥杯官方常考点总结

官方竞赛大纲讲解

题型分值

【距省赛仅1个多月！蓝桥杯的比赛流程和必考点，你还不清楚？】听说省二四五道题就行

CC150给出算法题的五种解法
手算&填空题技巧
巧用编辑器
心算手数
巧用Excel

购物单

Excel文本转为列

巧用Python(字符、大数、日期)

平方和 确实 python处理字符简单一点哈

建议刷题

枚举和查找

!最少刷题数-蓝桥杯2022年第十三届省赛真题
  1. https://www.dotcpp.com/oj/problem2673.html
  2. 时间限制: 1s 内存限制: 512MB 提交: 1843 解决: 211
  3. 题目描述
  4. 小蓝老师教的编程课有 N 名学生，编号依次是 1 . . . N。第 i 号学生这学期刷题的数量是 Ai。
  5. 对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
  6.  
  7. 输入格式
  8. 第一行包含一个正整数 N。
  9. 第二行包含 N 个整数：A1, A2, A3, . . . , AN.
  10.  
  11. 输出格式
  12. 输出 N 个整数，依次表示第 1 . . . N 号学生分别至少还要再刷多少道题。
  13. 样例输入
  14. 5
  15. 12 10 15 20 6
  16. 样例输出
  17. 0 3 0 0 7
  18. 提示
  19. 对于 30% 的数据，1 ≤ N ≤ 1000, 0 ≤ Ai ≤ 1000. 
  20. 对于 100% 的数据，1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000.
  1. //自己做的 超时
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4. public class Main{
  5.     public static void main(String[] args) {
  6.         Scanner sc =new Scanner(System.in);
  7.         int n=sc.nextInt();
  8.         int[] arr=new int[n];
  9.         int[] brr=new int[n];
  10.         
  11.         for (int i = 0; i < n; i++) {
  12.             arr[i]=sc.nextInt();
  13.         }
  14.         int[] crr=arr.clone();
  15.         for (int i = 0; i < n; i++) {
  16.             int m=crr[i];
  17.             for (int j = i ; j < n; j++) {
  18.                 if(m>crr[j]) {
  19.                     m=crr[j];
  20.                     crr[j]=crr[i];
  21.                     crr[i]=m;
  22.                 }
  23.                 crr[i]=m;
  24.             }
  25.         }
  26.         for (int i = 0; i < n; i++) {
  27.             int count=0;
  28.             int k=0;
  29.             for (int j = 0; j < n; j++) {
  30.                 if(j<n-1){
  31.                     if(arr[i]<arr[j]) {
  32.                         count++;
  33.                     }
  34.                     else if(arr[i]==arr[j]) {
  35.                         k++;
  36.                     }
  37.                 }
  38.                 else{
  39.                     if(count<=(n-count-k)) {
  40.                         brr[i]=0;
  41.                     }
  42.                     else {
  43.                         brr[i]=crr[(n/2)]-arr[i]+1;
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.         System.out.println(Arrays.toString(brr));
  49.     }
  50. }
  1. 时间复杂度：O(N*log(max(A))*logN)
  2.  
  3. 二分找需要刷题数目a， 设已经刷了多少题为x，再二分找符合 < a + x - 1 与 > a + x + 1 的人数，根据题目要求比较即可。
  4. import java.util.*;
  5. import java.io.*;
  6. public class Main{
  7.     static int[] a, b;
  8.     static int n;
  9.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  10.     static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
  11.  
  12.     public static void main(String[] args) throws IOException{
  13.  
  14.         n = Integer.parseInt(reader.readLine());
  15.         String[] s = reader.readLine().split(" ");
  16.         a = new int[n];
  17.         b = new int[n];
  18.         for(int i = 0; i < n; i++){
  19.             a[i] = Integer.parseInt(s[i]);    
  20.             b[i] = a[i];
  21.         }
  22.         Arrays.sort(b);
  23.          
  24.         int[] res = new int[n];
  25.         for(int i = 0; i < n; i++) {
  26.             res[i] = getMin(a[i]);
  27.         }
  28.          
  29.         for(int i = 0; i < n; i++) {
  30.             log.write(res[i] + " ");
  31.         }
  32.          
  33.         // 释放资源
  34.         reader.close();
  35.         log.flush();
  36.         log.close();
  37.     }
  38.      
  39.     //lowerBound
  40.     public static int getMin(int nums) {
  41.         int l = 0, r = b[n - 1];
  42.         while(l < r) {
  43.             int mid = l + r >> 1;
  44.             if(getR(nums + mid - 1, mid) < getL(nums + mid + 1)) {
  45.                 l = mid + 1;
  46.             } else {
  47.                 r = mid;
  48.             }
  49.         }
  50.         return l;
  51.     }
  52.     public static int getR(int tar, int e) {
  53.         int l = 0, r = n - 1;
  54.         while(l < r) {
  55.             int mid = l + r + 1>> 1;
  56.             if(b[mid] <= tar) {
  57.                 l = mid;
  58.             } else {
  59.                 r = mid - 1;
  60.             }
  61.         }
  62.         return e == 0 ? l + 1 : l;
  63.     }
  64.      
  65.     public static int getL(int tar) {
  66.         int l = 0, r = n - 1;
  67.         while(l < r) {
  68.             int mid = l + r >> 1;
  69.             if(b[mid] < tar) {
  70.                 l = mid + 1;
  71.             } else {
  72.                 r = mid;
  73.             }
  74.         }
  75.         return tar > b[n - 1] ? 0 : n - l;
  76.     }
  77. }
力扣869. 重新排序得到 2 的幂

https://leetcode.cn/problems/reordered-power-of-2/solution/zhong-xin-pai-xu-de-dao-2-de-mi-by-leetc-4fvs/

  1. class Solution {
  2.     boolean[] vis;
  3.  
  4.     public boolean reorderedPowerOf2(int n) {
  5.         char[] nums = Integer.toString(n).toCharArray();
  6.         Arrays.sort(nums);
  7.         vis = new boolean[nums.length];
  8.         return backtrack(nums, 0, 0);
  9.     }
  10.  
  11.     public boolean backtrack(char[] nums, int idx, int num) {
  12.         if (idx == nums.length) {
  13.             return isPowerOfTwo(num);
  14.         }
  15.         for (int i = 0; i < nums.length; ++i) {
  16.             // 不能有前导零
  17.             if ((num == 0 && nums[i] == '0') || vis[i] || (i > 0 && !vis[i - 1] && nums[i] == nums[i - 1])) {
  18.                 continue;
  19.             }
  20.             vis[i] = true;
  21.             if (backtrack(nums, idx + 1, num * 10 + nums[i] - '0')) {
  22.                 return true;
  23.             }
  24.             vis[i] = false;
  25.         }
  26.         return false;
  27.     }
  28.  
  29.     public boolean isPowerOfTwo(int n) {
  30.         return (n & (n - 1)) == 0;
  31.     }
  32. }
*世纪末的星期
幸运数
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner scanner=new Scanner(System.in);
  7.         int m=scanner.nextInt();
  8.         int n=scanner.nextInt();
  9.         ArrayList<Integer> aee = new ArrayList<Integer>();
  10.        
  11.         for(int i=1;i<=n;i++){
  12.             if(i%2!=0)
  13.                 aee.add(i);
  14.         }
  15.         //System.out.println(aee);
  16.         
  17.         int l=3;
  18.         for(int j=1;j<aee.size();j++) {
  19.             for(int i=aee.size()-1;i>j;i--){
  20.                 if( (i+1)%l==0 ) {
  21.                     aee.remove(i);
  22.                 }
  23.             }
  24.             if(j!=aee.size()-1)
  25.                 l=aee.get(j+1);
  26.         }
  27.        // System.out.println(aee);
  28.         
  29.         int c=0;
  30.         for(int i=0;i<aee.size();i++){
  31.             int r=aee.get(i);
  32.             if(r>m&&r<n) {
  33.                 c++;
  34.             }
  35.         }
  36.         System.out.println(c);  
  37.     }
  38. }
错误票据
猜字母 太简单了
分糖果
  1.         return;
  2.         }
  3.     }
  4. }
字符串子序列

我自己写的拿了66.7 后面的超时了； 感觉写法稀碎，乱的一批！

  1. public class Main { 
  2.     static int c=0;
  3.     public static void main(String[] args) {
  4.         Scanner sc=new Scanner(System.in);
  5.         int n=sc.nextInt();
  6.         String s=sc.next().toLowerCase();
  7.         int m=sc.nextInt();
  8.         String z=sc.next().toLowerCase();
  9.         for (int j = 0,i = 0; j < n&&i<m; ) {
  10.             if(j==n)
  11.                 break;
  12.             Character zz=z.toCharArray()[i];
  13.             Character ss=s.toCharArray()[j];
  14.             if(zz==ss){
  15.                 if(i==m-1){
  16.                     System.out.println("YES");
  17.                     return;
  18.                 }
  19.                 i++; j++;
  20.             }
  21.             else
  22.                 j++;
  23.         }
  24.         System.out.println("NO");
  25. }}
  1. public class Main {
  2.     public static void main(String[] args) {
  3.         Scanner sc=new Scanner(System.in);
  4.         int n=sc.nextInt();
  5.         char[] s1=sc.next().toLowerCase().toCharArray();
  6.         int m=sc.nextInt();
  7.         char[] s2=sc.next().toLowerCase().toCharArray();
  8.         
  9.         int j=0;
  10.         for(int i=0;i<n;i++) {
  11.             if(j<m&&s1[i]==s2[j]) {
  12.                 j++;
  13.             }
  14.         }
  15.         System.out.println(j==m?"YES":"NO");
  16.     }
  17. }
*承压计算 本题坑在于两次计量单位怎么试出来 先扩大倍数防止精度丢失，然后缩小

<<1(更快！)等价于*2；乘factor保证除30次没有小数，防止精度丢失；

最终试错发现最小的电子秤是题目给的两倍，说明试的factor不对

卡片 真服了 
  1. public class Main {//自己作的
  2.   static int[] arr={2021,2021,2021,2021,2021,2021,2021,2021,2021,2021};
  3.   static int ans=1; 
  4.  
  5.     public static void main(String[] args) {
  6.        while(true){
  7.           ans++;
  8.          if(!check(ans)){//检查不合法
  9.             break;
  10.          }
  11.        }
  12.        System.out.println(ans-1);//ans-2答案正确，但是我就觉得是-1呀！
  13.     }
  14.     public static boolean check(int x){
  15.       while(x>0){
  16.         int a=x%10;
  17.         if(arr[a]>0){
  18.           arr[a]--;
  19.         }
  20.         else{
  21.           return false;
  22.         }
  23.         x/=10;
  24.       }
  25.       return true;
  26.     }
  27. }
  28. ------------------------------以下是官方题解
  29. public class Main {
  30.     static int[] num = {2021,2021,2021,2021,2021,2021,2021,2021,2021,2021};
  31.     static int check(int x){
  32.         while(x > 0){
  33.             int now = x % 10;
  34.             if(num[now] > 0) num[now]--;
  35.           else return 0;
  36.             x /= 10;
  37.         }
  38.         return 1;
  39.     }
  40.     public static void main(String[] args) {
  41.         for(int i = 1;;i++) {
  42.             if (check(i) == 0) {
  43.                 System.out.println(i - 1);
  44.                 break;
  45.             }
  46.         }
  47.     }
  48. }

深搜DFS宽搜BFS(A组*题目) 回溯算法

*带分数

其实感觉这道题10层循环也可以吧

  1. public class Main02 {
  2.     static int ans; //全局变量 return最终结果
  3.     public static void main(String[] args) {
  4.         
  5.      Scanner sc=new Scanner(System.in);
  6.      int N=sc.nextInt();
  7.      int[] arr= {1,2,3,4,5,6,7,8,9};
  8.      f(arr,0,N);
  9.      System.out.println(ans);
  10.     }
  11.  
  12.     //确认某排列的第k位
  13.     private static void f(int[] arr, int k,int n) {
  14.         //全排列全部确认
  15.         if(k==9) {
  16.             Check(arr,n);
  17.             return;
  18.         }
  19.         //选定第k位
  20.         for(int i=k;i<arr.length;i++) {
  21.             //第i位和第k位 交换
  22.             int t=arr[i];
  23.             arr[i]=arr[k];
  24.             arr[k]=t;
  25.             //移交下一层去确认k+1位
  26.             f(arr, k+1,n);
  27.             //回溯上一次，交换回来 下一次循环的新一种(k+1)的可能
  28.              t=arr[i];
  29.              arr[i]=arr[k];
  30.              arr[k]=t;
  31.         }
  32.     }
  33.  
  34.     //枚举+和/的位置
  35. //    这是俺自己写的 数组转int太乱了！写函数吧！
  36. //    private static boolean Check(int[] arr,int n) {
  37. //        //+前最多有7个字符
  38. //        int left=0,mid=0,right=0;
  39. //        for (int i = 0; i < 7; i++) {
  40. //            //如果+前的字符数超过N，没必要验算
  41. //            left += (int) (arr[i]*Math.pow(10, i) );
  42. //                    
  43. //            if(left>n) return false;
  44. //            // /后面至少有1个数字,前面
  45. //            for (int j = i+1; j < 8-i; j++) {
  46. //                mid += (int) (arr[j]*Math.pow(10, j-i-1));
  47. //                right += (int) (arr[j+1]*Math.pow(10, j-i-2));
  48. //                if(mid<right||right==0) 
  49. //                    return false;
  50. //                if( (left+mid/right)==n )
  51. //                    return true;
  52. //            }
  53. //        }
  54. //        return false;
  55. //    }
  56.     private static void Check(int[] arr,int n) {
  57.         //+前最多有7个字符
  58.         for (int i = 1; i < 7; i++) {
  59.             //如果 +号 前的字符数超过N，没必要验算    
  60.             int num1=toInt(arr,0,i);
  61.             if( num1>=n ) 
  62.                 continue;
  63.             // /后面至少有1个数字,前面
  64.             for (int j = 1; j <= 8-i; j++) {
  65.                 int num2=toInt(arr,i,j);
  66.                 int num3=toInt(arr,j+i,9-(i+j));
  67.                 if(num3==0) return;
  68.                 if(num2%num3==0&&num1+num2/num3==n)
  69.                     ans++;
  70.             }
  71.         }
  72.     }
  73.  
  74.     //把数组元素拼接 成数字
  75.     private static int toInt(int[] arr, int pos, int len) {
  76.         int t=1;//10,100,1000...
  77.         int ans=0;
  78.         for (int i = pos+len-1; i >= pos; i--) {
  79.             ans+=arr[i]*t;//进位
  80.             t*=10;
  81.         }
  82.         return ans;
  83.     }
  84. }
46. 全排列
47. 全排列 II

https://leetcode.cn/problems/permutations-ii/solution/quan-pai-lie-ii-by-leetcode-solution/

地宫取宝 没看懂

dsf(坐标x,坐标y，最大值，物品数);//第一个值可能是0所以传-1，

扑克序列(全排列+check)

技巧7: 重复元素去重用set；

凑算式 凑分式相加res=整数(通分)
！剪邮票 DFS连通性
！生命之树
首先暴力枚举所有子集30：DFS探测是否连通
魔方状态 空间状态搜索。模拟操作+判重
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef char st[8][7];
  4. st state[2000000];  
  5. set<string> all;
  6. st begin={{"oybbgb"},{"oygbbb"},{"bygbby"},{"bybbgy"},{"obbogb"},{"obgobb"},{"bbgoby"},{"bbbogy"}}; 
  7. //st begin={{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"}};
  8. //只有一个颜色的魔方 ans=1 
  9. //st begin={{"rykkbk"},{"rygkkk"},{"kygkko"},{"kykkbo"},{"rkkwbk"},{"rkgwkk"},{"kkgwko"},{"kkkwbo"}};
  10. //正常2阶魔方状态  r红 y黄 b蓝 g绿 w白 o橙  k黑(红对橙，白对黄，蓝对绿，颜色相近的相对)这里白为底 前为红
  11. //需要将state大小改为4000000 
  12. //这个测试用例跑了20分钟左右 560M内存  ans=3674160 与实际二阶魔方状态数相同 见下截图 
  13. int front, tail;
  14. void ucell(char *a){swap(a[0], a[2]); swap(a[2], a[5]); swap(a[5], a[4]);}
  15. void rcell(char *a){swap(a[1], a[0]); swap(a[0], a[3]); swap(a[3], a[5]);}
  16. void fcell(char *a){swap(a[2], a[1]); swap(a[1], a[4]); swap(a[4], a[3]);}
  17. void u(st &s)//顶层顺时针旋转 
  18. {
  19.     ucell(s[0]);
  20.     ucell(s[1]);
  21.     ucell(s[2]);
  22.     ucell(s[3]);
  23.     swap(s[1], s[0]);
  24.     swap(s[2], s[1]);
  25.     swap(s[3], s[2]);
  26. }
  27. void uwhole(st &s)//整个魔方从顶部看 顺时针转 用于判重 
  28. {
  29.     u(s);
  30.     ucell(s[4]);
  31.     ucell(s[5]);
  32.     ucell(s[6]);
  33.     ucell(s[7]);
  34.     swap(s[5], s[4]);
  35.     swap(s[6], s[5]);
  36.     swap(s[7], s[6]);
  37. }
  38. void f(st &s)//前面一层 顺时针转 
  39. {
  40.     fcell(s[0]);
  41.     fcell(s[1]);
  42.     fcell(s[4]);
  43.     fcell(s[5]);
  44.     swap(s[1], s[5]);
  45.     swap(s[0], s[1]);
  46.     swap(s[4], s[0]);
  47. }
  48. void fwhole(st &s)//整个魔方从前面看 顺时针转 用于判重 
  49. {
  50.     f(s);
  51.     fcell(s[2]);
  52.     fcell(s[6]);
  53.     fcell(s[7]);
  54.     fcell(s[3]);
  55.     swap(s[2], s[6]);
  56.     swap(s[3], s[2]);
  57.     swap(s[7], s[3]);
  58. }
  59. void r(st &s)//魔方右层顺时针转 
  60. {
  61.     rcell(s[1]);
  62.     rcell(s[2]);
  63.     rcell(s[6]);
  64.     rcell(s[5]);
  65.     swap(s[2], s[1]);
  66.     swap(s[5], s[1]);
  67.     swap(s[6], s[5]);
  68. }
  69. void rwhole(st &s)//整个魔方从右边看 顺时针转 用于判重 
  70. {
  71.     r(s);
  72.     rcell(s[0]);
  73.     rcell(s[3]);
  74.     rcell(s[4]);
  75.     rcell(s[7]);
  76.     swap(s[3], s[7]);
  77.     swap(s[0], s[3]);
  78.     swap(s[4], s[0]);
  79. }
  80. string convert(st &s)//魔方状态二维字符数组 转化为string 
  81. {
  82.     string ss;
  83.     for(int i=0; i<8; i++)ss+=s[i];
  84.     return ss;
  85. }
  86. bool try_to_insert(int tail)//判重 
  87. {
  88.     st k;
  89.     memcpy((void*)k, (void*)state[tail], sizeof(state[tail]));
  90.     for(int i=0; i<4; i++)
  91.     {
  92.         fwhole(k);
  93.         for(int j=0; j<4; j++)
  94.         {
  95.             uwhole(k);
  96.             for(int q=0; q<4; q++)
  97.             {
  98.                 rwhole(k);
  99.                 if(all.count(convert(k))==1)
  100.                 {
  101.                     return false;
  102.                 }
  103.             }
  104.         }
  105.     }
  106.     all.insert(convert(k));
  107.     return true;
  108. }
  109. int main()
  110. {
  111.     front=0,tail=1; //队列中的首尾
  112.     all.insert(convert(begin));
  113.     memcpy((void*)state[0],(void*)begin,sizeof(begin));
  114.     while(front!=tail)
  115.     {
  116.         //对当前状态分别模拟三种操作U R F 然后判重 
  117.         for(int i=0; i<3; i++)
  118.         {
  119.             memcpy((void*)state[tail], (void*)state[front], sizeof(state[front]));
  120.             if(i==0)
  121.             {
  122.                 u(state[tail]);
  123.                 if(try_to_insert(tail))tail++;
  124.             }
  125.             else if(i==1)
  126.             {
  127.                 r(state[tail]);
  128.                 if(try_to_insert(tail))tail++;
  129.             }
  130.             else if(i==2)
  131.             {
  132.                 f(state[tail]);
  133.                 if(try_to_insert(tail))tail++;
  134.             }
  135.         }
  136.         front++;
  137.     }
  138.     cout<<front<<endl;
  139.     return 0;
  140. }
  141. //ans 229878
全球变暖BFS宽搜连通块模板

BFS=自定义对象+队列；

纸牌三角形 全排列

正三角形，三边和相等的旋转3种，镜像3种 都算同种，所以有六种重复ans/6；

最大公共子串

动态规划(逆向思维+分类讨论)

我觉得用数组代替函数这个思想非常哇塞

暴力dfs-->记忆化搜索-->递推-->动态规划;层层优化
*李白打酒
  1. //自己写的垃圾，还错了
  2. public class Main {
  3.   static int ans=0;
  4.   static StringBuilder s=new StringBuilder();
  5.     public static void main(String[] args) {
  6.         System.out.println( dp(2,5,9)+dp(2,4,10) )  ;
  7.     }
  8.     static int dp(float count,int a,int b){
  9.         if(b==0&&count==1&&a==0) {
  10.             ans++;
  11.             return ans;
  12.         }else if(b==2&&count==2&&a==0) {
  13.             return dp( count, a, b-=2);
  14.         }else if(b==2&&count==1&&a==1) {
  15.             return dp(count, a-1, b-=2);
  16.         }
  17.         return dp(count-1, a-1, b)+dp(count-1, a, b-1);
  18.     }
  19. }
李白打酒加强版

因为题目要求最后一个是遇到花，所以可以少枚举一个

DP一般以样例为例子： 一直分类下图是 前两次的分法

5店8花2斗的方案分类

*198. 打家劫舍

https://leetcode.cn/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/

  1. class Solution {//自己写的
  2.     public int rob(int[] nums) {
  3.             int n=nums.length-1;
  4.             if(n==0)  return nums[0];
  5.             else if(n==1) return Math.max(nums[0],nums[1]);
  6.             int[] db=new int[nums.length];
  7.             db[0]=nums[0];
  8.             db[1]=nums[1];
  9.             for(int i=2;i<nums.length;i++){
  10.                 db[i]=db[i-2]+nums[i];
  11.             }
  12.             return Math.max(db[n-2]+nums[n],db[n-1]);
  13.         }
  14. }
  1. class Solution {//官方
  2.     public int rob(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  6.         int length = nums.length;
  7.         if (length == 1) {
  8.             return nums[0];
  9.         }
  10.         int[] dp = new int[length];
  11.         dp[0] = nums[0];
  12.         dp[1] = Math.max(nums[0], nums[1]);
  13.         for (int i = 2; i < length; i++) {
  14.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  15.         }
  16.         return dp[length - 1];
  17.     }
  18. }
振兴中华
  1. public class Main {
  2.     public static void main(String[] args) {
  3.         System.out.println(f(0,0));
  4.     }
  5.     public static int f(int a,int b){
  6.       if(a==3||b==4)
  7.         return 1;
  8.       return f(a+1,b)+f(a,b+1);
  9.     } 
  10. }
牌型总数

k代表考虑到第几张牌，cnt代表手里牌的总数

归结为 每个牌出现0~4次，超过13不行，超过13的return；

70. 爬楼梯
  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int[] a=new int[n+1];
  4.         a[1]=1;a[0]=1;
  5.         for(int i=2;i<=n;i++){
  6.             a[i]=(a[i-1])+(a[i-2]);
  7.         }
  8.         return a[n];
  9.     }    
  10. }
官方题解 滚动数组
  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int p = 0, q = 0, r = 1;
  4.         for (int i = 1; i <= n; ++i) {
  5.             p = q; 
  6.             q = r; 
  7.             r = p + q;
  8.         }
  9.         return r;
  10.     }    }
118. 杨辉三角

我的想法就根据上一行 递归 跟官方思路也一样；但是集合brr 的静态改变不如动态函数传参

  1. class Solution {
  2.     public List<List<Integer>> generate(int numRows) {
  3.         ArrayList<List<Integer>> list=new ArrayList<>();
  4.         List<Integer> first=new ArrayList<>();
  5.         first.add(1);
  6.         list.add(first);
  7.         List<Integer> second=new ArrayList<>();
  8.         if(numRows>=2)
  9.         {
  10.             second.add(1);
  11.             second.add(1);
  12.             list.add(second); 
  13.         }    
  14.         for(int i=3;i<=numRows;i++){
  15.             List<Integer> arr=new ArrayList<>();
  16.             arr.add(1);
  17.             List<Integer> brr=second;
  18.             for(int j=1;j<i-2;j++){
  19.  
  20.                 arr.set(i, (brr.get(i-1) + brr.get(i) ) );
  21.                 arr.set(i-1,1);
  22.  
  23.             }
  24.             list.add(arr);
  25.         }
  26.         return list;
  27.     }        }
  1. class Solution {
  2.     public List<List<Integer>> generate(int numRows) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         List<Integer> firstRow = new ArrayList<>();
  5.         firstRow.add(1);
  6.         res.add(firstRow);
  7.         func(res, firstRow, numRows);
  8.         return res;
  9.     }
  10.     private void func(List<List<Integer>> res, List<Integer> lastRow, int numRows) {
  11.         if (lastRow.size() == numRows) {
  12.             return;
  13.         }
  14.         List<Integer> curRow = new ArrayList<>();
  15.         for (int i = 0; i < lastRow.size() - 1; i++) {
  16.             curRow.add(lastRow.get(i) + lastRow.get(i + 1));
  17.         }
  18.         curRow.add(0, 1);
  19.         curRow.add(curRow.size(), 1);
  20.         res.add(curRow);
  21.         func(res, curRow, numRows);
  22.     }    }
数学解法(官方)
  1. class Solution {
  2.     public List<List<Integer>> generate(int numRows) {
  3.         List<List<Integer>> ret = new ArrayList<List<Integer>>();
  4.         for (int i = 0; i < numRows; ++i) {
  5.             List<Integer> row = new ArrayList<Integer>();
  6.             for (int j = 0; j <= i; ++j) {
  7.                 if (j == 0 || j == i) {
  8.                     row.add(1);
  9.                 } else {
  10.                     row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
  11.                 }
  12.             }
  13.             ret.add(row);
  14.         }
  15.         return ret;
  16.     }    }
  1. class Solution {
  2.     public List<List<Integer>> generate(int numRows) {
  3.         if (numRows < 1) return new ArrayList<>();
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         ans.add(new ArrayList<>(){{add(1);}});
  6.         for (int i = 1; i < numRows; i++) {
  7.             Integer[] arr = new Integer[i + 1];
  8.             arr[0] = arr[i] = 1;
  9.             for (int x = 1; x < i; x++)
  10.                 arr[x] = ans.get(i - 1).get(x) + ans.get(i - 1).get(x - 1);
  11.             ans.add(Arrays.asList(arr));
  12.         }
  13.         return ans;
  14.     }    
  15. }
很巧妙的找规律

我刚开始看到这个思路感觉很巧妙，但是细细照着这个思路做了半个小时，作者做的是Python所以这个思路很适合，首先我认为就是这个思路做java不合适，因为java的要求是返回List<List<Integer>> 要的是杨辉三角每个数字组成一行小List，再每行组成一个大List；

如果用这个思路做，就必须先把一行组装成一个int，前面+0，后面+0再相加； 然后 再次拆分成一个个 个位数add到小List，add到大List 很浪费时间就下面这个代码效率很差

  1. class Solution {
  2.     public List<List<Integer>> generate(int numRows) {        
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if(numRows == 0) return res;
  5.          res.add( new ArrayList<>() {{ add(1); }} );//第一行
  6.         int size = res.size();
  7.         while(size < numRows){
  8.             LinkedList<Integer> first = new LinkedList<>();
  9.             first.addFirst(0);
  10.             LinkedList<Integer> second = new LinkedList<>();
  11.             second.addLast(0);
  12.             for(int x: res.get(size-1)){
  13.                 first.addFirst(x);
  14.                 second.addLast(x);
  15.             }
  16.             List<Integer> newRow = new ArrayList<>();
  17.             for(int i=0; i<first.size(); i++){
  18.                 newRow.add(first.get(i) + second.get(i));
  19.             }
  20.             res.add(newRow);
  21.             size++;
  22.         }
  23.         return res;
  24.     }
  25. }
!垒骰子_15

！测试次数

if手机摔坏，初始3个，3--

！堆的计数

!取球博弈
博弈问题 身份互换 三判定

技巧13：判断奇数( (a&1)==1);判偶( (a&1) ==0)

优化重复数据组合，减小规模，缓存实现记忆性递归

记忆性递归技巧：在函数出口下面查

数学思维和知识

修改数组 
  1. public class Main {//自己写的40%
  2.     static int[] arr;
  3.     static int[] brr;
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         //在此输入您的代码...
  7.         int n=scan.nextInt();
  8.         arr=new int[n];
  9.         for(int i=0;i<n;i++){
  10.             arr[i]=scan.nextInt();
  11.         }
  12.         brr=new int[n*n];
  13.         dp(0);
  14.  
  15.         for(int i=0;i<n;i++){
  16.             System.out.print(arr[i]+" ");
  17.         }
  18.         scan.close();
  19.     }
  20.     static boolean dp(int i) {
  21.         if (i == arr.length )
  22.             return true;
  23.         else {
  24.             if (brr[arr[i]] == 0) {
  25.                 brr[arr[i]]++;
  26.                 dp(i + 1);
  27.             } else {//之前出现过
  28.                 arr[i]++;
  29.                 dp(i);
  30.             }
  31.         }
  32.         return false;
  33.     }
  34. }
  1. import java.util.Scanner;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         Scanner sc=new Scanner(System.in);
  5.         int  n=sc.nextInt();
  6.         int[] count=new int[1000001]; //记录每一个Ai出现的次数
  7.         long[] arr=new long[n];  //最终数组
  8.         for(int i=0;i<n;i++){
  9.             int num=sc.nextInt();
  10.             if(count[num]==0){    //出现0次输出arr[i],并记录count[num]++
  11.                 arr[i]=num;
  12.                 count[num]++;
  13.             }else{
  14. //Ai已经出现过，循环找到count[num]为0的num，利用num+=count[num]-1;减少循环次数，以免超时
  15.                 while(count[num]!=0){
  16.                     count[num]++; //只要出现过就++
  17.                     num+=count[num]-1; //如果大于1说明已经加过了，直接count[num]-1
  18.                 }
  19.                 count[num]++;
  20.                 arr[i]=num;
  21.             }
  22.             System.out.print(arr[i]+" ");
  23.         }
  24.     }
  25. }
黄金连分数-大数

.ROUNG_HALF_DOWN四舍五入

阶乘约数_国20-大数
  1. Scanner scan = new Scanner(System.in);  
  2. System.out.println(scan.next());
很神奇的题解？为甚？
立方变自身

当99的时候就不可能成立了所以上限99即可

连号区间数
三羊献瑞

不能直接枚举,太麻烦。先观察几个再枚举，我就觉得e=1没毛病,但是a=8后面进位也有可能，他应该验证一下8不对，不能跳了直接到a=9

武功秘籍 我觉得很怪
圆周率
抽签
复数幂 (大数)
螺旋折线

n代表等差数列有多少项，d代表减的距离。

日期问题

我的想法就是 挨个判断 但是老师的讲法就是 不符合的return“”；剩下的情况就是对的！

还有用treeset排序去重！我自己写的忘记了去重

  1. public class Main
  2. {    public static void main(String[] args){
  3.         Scanner scanner=new Scanner(System.in);
  4.         String str=scanner.next();
  5.         int a=Integer.parseInt(str.split("/")[0]);
  6.         int ar=Integer.parseInt(str.split("/")[1]);
  7.         int arr=Integer.parseInt(str.split("/")[2]);
  8.     
  9.             panduan(a, ar, arr);            
  10.             panduan(arr, ar, a);
  11.             panduan(arr, a, ar);
  12.     }
  13.     public static void panduan(int a,int b,int c) {
  14.             if(a<60&&b<12) {
  15.                 LocalDate ld=LocalDate.of(2000+a, b+1, 1);
  16.                 LocalDate ld2=ld.minusDays(1);
  17.                 int day2=ld2.getDayOfMonth();
  18.                 if(c<=day2) {
  19.                     if(b<10&&c>=10)
  20.                         System.out.println(2000+a+"-0"+b+"-"+c);
  21.                     else if(b<10&&c<10)
  22.                         System.out.println(2000+a+"-0"+b+"-0"+c);
  23.                     else if(b>=10&&c<10)
  24.                         System.out.println(2000+a+"-"+b+"-0"+c);
  25.                     else
  26.                         System.out.println(2000+a+"-"+b+"-"+c);
  27.                 }
  28.             }
  29.             else if(a<60&&b==12) {
  30.                 LocalDate ld=LocalDate.of(2001+a, 1, 1);
  31.                 LocalDate ld2=ld.minusDays(1);
  32.                 int day2=ld2.getDayOfMonth();
  33.                 if(c<=day2) {
  34.                     if(b<10&&c>=10)
  35.                         System.out.println(2000+a+"-0"+b+"-"+c);
  36.                     else if(b<10&&c<10)
  37.                         System.out.println(2000+a+"-0"+b+"-0"+c);
  38.                     else if(b>=10&&c<10)
  39.                         System.out.println(2000+a+"-"+b+"-0"+c);
  40.                     else
  41.                         System.out.println(2000+a+"-"+b+"-"+c);
  42.                 }
  43.                 
  44.             }
  45.             else if(a>=60&&b<12) {
  46.                 LocalDate ld=LocalDate.of(1900+a, b+1, 1);
  47.                 LocalDate ld2=ld.minusDays(1);
  48.                 int day2=ld2.getDayOfMonth();
  49.                 if(c<=day2) {
  50.                     if(b<10&&c>=10)
  51.                         System.out.println(1900+a+"-0"+b+"-"+c);
  52.                     else if(b<10&&c<10)
  53.                         System.out.println(1900+a+"-0"+b+"-0"+c);
  54.                     else if(b>=10&&c<10)
  55.                         System.out.println(1900+a+"-"+b+"-0"+c);
  56.                     else
  57.                         System.out.println(1900+a+"-"+b+"-"+c);
  58.                 }
  59.             }
  60.             else if(a>=60&&b==12) {
  61.                 LocalDate ld=LocalDate.of(1901+a, 1, 1);
  62.                 LocalDate ld2=ld.minusDays(1);
  63.                 int day2=ld2.getDayOfMonth();
  64.                 if(c<=day2) {
  65.                     if(b<10&&c>=10)
  66.                         System.out.println(1900+a+"-0"+b+"-"+c);
  67.                     else if(b<10&&c<10)
  68.                         System.out.println(1900+a+"-0"+b+"-0"+c);
  69.                     else if(b>=10&&c<10)
  70.                         System.out.println(1900+a+"-"+b+"-0"+c);
  71.                     else
  72.                         System.out.println(1900+a+"-"+b+"-"+c);
  73.                 }
  74.             }
  75.     }
  76. }
！日志统计map尺取法

暴力枚举

一直不知道啥意思，其实很简单，就是猜或者遍历

生日蜡烛
四平方和 因为a最小 所以a²取值范围≤N/4 四次遍暴力枚举超时

暴力枚举优化1减少变量取值范围,变量个数；数据缓存到hashMap,减少变量个数

K倍区间
技巧11.5：计算1~n用 t--,别用fori
  1. int t = sc.nextInt();
  2. while(t-- > 0){}
递增三元组
  1. public class Main {//自己写的三重暴力拿了62.5的分数
  2.     public static void main(String[] args) {
  3.         Scanner scan = new Scanner(System.in);
  4.         int n=scan.nextInt();
  5.         scan.nextLine();//吞掉第一行的剩下的东西
  6.         int[][] arr=new int[3][n];
  7.         String s0=scan.nextLine();
  8.         String s1=scan.nextLine();
  9.         String s2=scan.nextLine();
  10.         //System.out.println(s0);
  11.         for(int i=0;i<n;i++){
  12.           arr[0][i]=Integer.parseInt(s0.split(" ")[i]);
  13.           arr[1][i]=Integer.parseInt(s1.split(" ")[i]);
  14.           arr[2][i]=Integer.parseInt(s2.split(" ")[i]);
  15.         }
  16.         //for(int[] i:arr) 
  17.         //    System.out.println(Arrays.toString( i ));
  18.         int ans=0;
  19.          for (int i = 0; i < n; i++) {
  20.              for (int j = 0; j < n; j++) {
  21.                  for (int k = 0; k < n; k++) {
  22.                      if(arr[0][i]<arr[1][j]&&arr[1][j]<arr[2][k]) {
  23.                          ans++;
  24.                     //     System.out.println(arr[0][i]+"+"+arr[1][j]+"+"+arr[2][k]);
  25.                      }
  26.                  }
  27.              }
  28.          }
  29.         System.out.println(ans);
  30.     }
  31. }
分巧克力 用二分优化暴力

从 int len=100000；开始 用二分法 找最大的切割块

技巧14:区间树(线段树)优化区间和的查询,也可用于求区间最值

！他的优化也是数组赋值，快速识别！我差了一点捏

九进制转十进制_2022
  1. import java.util.Scanner;
  2. // 1:无需package
  3. // 2: 类名必须Main, 不可修改
  4.  
  5. public class Main {
  6.     public static void main(String[] args) {
  7.         String rs="2022";
  8.         System.out.println(Integer.parseInt(rs,9));
  9.     }
  10. }

常见错误解析

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/73602
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号