当前位置:网站首页>30-day question brushing plan (5)
30-day question brushing plan (5)
2022-08-01 19:38:00 【Red apples are delicious】
加油鸭
目录
1.另类加法
①题目及示例:
②Methods and Analysis:
Because the title clearly states that it cannot be used+And other arithmetic operators.所以,We can easily think of bitwise operators.
when using bitwise operators,Which bitwise operator should we use??
首先我们得知道,We will encounter two cases of carry and no carry.比如:1+2=3You don't have to carry(in binary),3+2=5就需要进位.如果不需要进位,Then we can directly use the XOR operation.如果需要进位,we need to know how to carry,This time we have to first carries on the bitwise and operation,Then shift the result one bit to the left.所以,We do nothing but the following two operations.
a.判断是否需要进位:(&运算符,因为全1为1,有0为0,若全为0,means that no carry is required,因为是二进制,满二进一)
b.Add the XORed result to the result of the carry left shift(XOR is still used here)
c.将bTwo-value repetition ina,b步骤,直到不需要进位为止
实质上:
位运算A^Bis the result of ignoring the carry,(A&B)<<1is the obtained carry
因此A^B+(A&B)<<1And are the result,只要(A&B)<<1=0,Two becomes one,No need to add
代码如下:
import java.util.*; public class UnusualAdd { public int addAB(int A, int B) { // write code here if(B==0){ return A; } int tmp; int sum; while(B!=0){ sum=A^B;//求两个数的和,the one that doesn't carry tmp=(A&B)<<1;//判断是否需要进位 A=sum; B=tmp; } return A; } }
2.求路径总数
①题目及示例:
②Methods and Analysis:
a.Recursive method to do it:
I've done this question before,It operates according to the idea of recursion,You can see the picture below.
代码如下:
import java.util.*; public class Main { public static int load(int m,int n){ if((m==1&&n>=1)||(n==1&&m>=1)){ return m+n; } return load(m-1,n)+load(m,n-1); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); System.out.println(load(m,n)); } }
b.动态规划来做:
First of all, we should understand the related ideas of dynamic programming:
Dynamic programming is actually very similar to recursion in principle,They are all started by induction in previous mathematics..通俗一点来说,This step is derived from the previous step,The previous step is derived from the previous step in the same way,Then the process by analogy.
The steps we often use in dynamic programming are often:
1.确定状态(两个核心:1最后一步 2化成子问题)
2.转移方程
3.Start and Boundary Conditions
Take the following question as an example,Let's do an analysis:
62. 不同路径 - 力扣(LeetCode)
https://leetcode.cn/problems/unique-paths/
Our ultimate goal is to make the pentagram go to the circle.(3行,4列)
(1)确定状态:
状态:设f[m][n]为机器人有多少种方式从左上角走到(m, n)
很显然,The last step is either[1][3]向下,要么是[2][2]向右
![]()
要是有m行,nColumns in the two dimensional array,我们就可以发现,To get to the circle[m-1][n-1];Then the last two results are nothing more than:[m-2][n-1]和[m-1][n-2];
So we then turn it into a sub-problem:
is to combine the above two results,separate reanalysis,find or get the same relationship.
到[m-2][n-1]the way is nothing more than:[m-3][n-1]和[m-2][n-2].其它的以此类推.
(2)We can then determine the equation of state as:对于任意一个格子(m, n)有:
f[m][n] = f[m-1][n] + f[m][n-1];
(3)Start and Boundary Conditions:
若是m,n均为0,So the only way to get to this position at this time is1中;because it is itself.
if only the linem,Then the result is(m-1,0);This time can only move right,只有一种方式.
即:f[m][n] = 1
同理,if only columnsn,Then the result is(0,n-1);Only go down,there is only one way.
即:f[m][n] = 1
代码如下:
import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(); int b = in.nextInt(); System.out.println(work(a,b)); } private static int work(int n, int m) { int[][] dp = new int[n][m]; // 只有1列 for (int i = 0; i <n; i++) { dp[i][0] = 1; }//只有1行 for (int j = 0; j <m; j++) { dp[0][j] = 1; } // 递推 for (int i = 1;i < n;i++){ for(int j = 1;j< m ;j++){ dp[i][j] = dp[i][j-1]+dp[i-1][j]; } } return dp[n-1][m-1]; } }
But ontology from the upper left vertex walked to the lower right,So the horizontal and vertical coordinates of the array here are+1;
代码如下:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(); int b = in.nextInt(); System.out.println(work(a,b)); } private static int work(int n, int m) { // define twodp数组dp[i,j] = dp[i-1,j]+dp[i,j-1]; //因为对于nFor a grid,有n+1个顶点 int[][] dp = new int[n + 1][m + 1]; // 只有1列 for (int i = 0; i <= n; i++) { dp[i][0] = 1; }//只有1行 for (int j = 0; j <= m; j++) { dp[0][j] = 1; } // 递推 for (int i = 1;i <= n;i++){ for(int j = 1;j<= m ;j++){ dp[i][j] = dp[i][j-1]+dp[i-1][j]; } } return dp[n][m]; } }
3.井字棋
①题目及示例:
②Methods and Analysis:
这个题很简单,In fact, we only need to ensure that the horizontal,纵列,number of main and sub-diagonals,There are a total for this1,那么则输出true.代码如下:
Special attention should be paid to the calculation of each row or column after the calculationsum置为0,Otherwise, it will still accumulate,resulting in inaccurate results.
import java.util.*; class Main{ public static boolean checkWon(int[][] board) { // write code here int sum=0; //对行 for(int i=0;i<board[0].length;i++){ sum=0; for(int j=0;j<board.length;j++){ sum+=board[i][j]; if(sum==board.length){ return true; } } }//对列 for(int i=0;i<board[0].length;i++){ sum=0; for(int j=0;j<board.length;j++){ sum+=board[j][i]; if(sum==board.length){ return true; } } }sum=0; //主对角线 for(int i=0;i<board.length;i++){ sum+=board[i][i]; if(sum==board.length){ return true; } }sum=0; //副对角线 for(int i=0;i<board.length;i++){ sum+=board[i][board.length-1-i]; if(sum==board.length){ return true; } } return false; } public static void main(String[]args){ Scanner sc=new Scanner(System.in); int[][]array={ {-1,1,-1},{0,0,1},{0,0,0}}; boolean flg=checkWon(array); System.out.println(flg); } }
4.Password level strength
①题目及示例:
②Methods and Analysis:
This is the list,直接上代码:
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNextLine()){ String str=sc.nextLine(); int sum1=getLen(str); int sum2=getChar(str); int sum3=getNum(str); int sum4=getSym(str); int sum=0; if(sum2==20&&sum3>=1&&sum4>=1){ sum=sum1+sum2+sum3+sum4+5; }else if(sum2==10&&sum3>=1&&sum4>=1){ sum=sum1+sum2+sum3+sum4+3; }else if(sum2==10&&sum3>=1&&sum4==0){ sum=sum1+sum2+sum3+sum4+2; }else{ sum=sum1+sum2+sum3+sum4; }if(sum>=90){ System.out.println("VERY_SECURE"); }else if(sum>=80){ System.out.println("SECURE"); }else if(sum>=70){ System.out.println("VERY_STRONG"); }else if(sum>=60){ System.out.println("STRONG"); }else if(sum>=50){ System.out.println("AVERAGE"); }else if(sum>=25){ System.out.println("WEAK"); }else if(sum>=0){ System.out.println("VERY_WEAK"); } } }public static int getLen(String str){ if(str.length()<=4){ return 5; }else if(7>=str.length()&&str.length()>=5){ return 10; }else if(str.length()>=8){ return 25; }return 0; }public static int getChar(String str){ int small=0; int big=0; for(int i=0;i<str.length();i++){ if(str.charAt(i)>=65&&str.charAt(i)<=90){ big++; }else if(str.charAt(i)>=97&&str.charAt(i)<=122){ small++; } }if(small>0&&big>0){ return 20; }else if(small>0||big>0){ return 10; }else{ return 0; } }public static int getNum(String str){ int num=0; for(int i=0;i<str.length();i++){ if(str.charAt(i)-'0'>=0 && str.charAt(i)-'0'<=9){ num++; } }if(num>1){ return 20; }else if(num==1){ return 10; }else{ return 0; } }public static int getSym(String str){ int num=0; for(int i=0;i<str.length();i++){ if(!(str.charAt(i)>=65&&str.charAt(i)<=90)&& !(str.charAt(i)>=97&&str.charAt(i)<=122)&& !(str.charAt(i)-'0'>=0&&str.charAt(i)-'0'<=9)){ num++; } }if(num>1){ return 25; }else if(num==1){ return 10; }else{ return 0; } } }
边栏推荐
猜你喜欢
Become a Contributor in 30 minutes | How to participate in OpenHarmony's open source contributions in multiple ways?
Risc-v Process Attack
哈哈!一个 print 函数,还挺会玩啊!
Gradle系列——Gradle文件操作,Gradle依赖(基于Gradle文档7.5)day3-1
面试必问的HashCode技术内幕
MySQL你到底都加了什么锁?
nacos installation and configuration
终于有人把AB实验讲明白了
百度无人驾驶商业化已“上路”
kubernetes-部署nfs存储类
随机推荐
Find the sum of two numbers
Pytorch模型训练实用教程学习笔记:二、模型的构建
Keras深度学习实战——交通标志识别
57: Chapter 5: Develop admin management services: 10: Develop [get files from MongoDB's GridFS, interface]; (from GridFS, get the SOP of files) (Do not use MongoDB's service, you can exclude its autom
安全作业7.25
Pytorch模型训练实用教程学习笔记:三、损失函数汇总
MySQL开发技巧——存储过程
把 Oracle 数据库从 RAC 集群迁移到单机环境
regular expression
DAO development tutorial [WEB3.0]
modbus总线模块DAM-8082
1个小时!从零制作一个! AI图片识别WEB应用!
Win10, the middle mouse button cannot zoom in and out in proe/creo
随时随地写代码--基于Code-server部署自己的云开发环境
58: Chapter 5: Develop admin management services: 11: Develop [admin face login, interface]; (not measured) (using Ali AI face recognition) (demonstrated, using RestTemplate to implement interface cal
从普通进阶成优秀的测试/开发程序员,一路过关斩将
PHP 安全最佳实践
部署zabbix
SQL的 ISNULL 函数
力扣刷题之合并两个有序数组