30-day question brushing plan (5)

加油鸭 

目录

1.另类加法

2.求路径总数

3.井字棋

4.Password level strength

---

1.另类加法

另类加法_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/e7e0d226f1e84ba7ab8b28efc6e1aebc?tpId=8&&tqId=11065&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

①题目及示例：

 ②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.求路径总数

走方格的方案数_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b?tpId=37&&tqId=21314&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

①题目及示例：

 ②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.井字棋

井字棋_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/e1bb714eb9924188a0d5a6df2216a3d1?tpId=8&&tqId=11055&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

①题目及示例：

 

②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

密码强度等级_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/52d382c2a7164767bca2064c1c9d5361?tpId=37&&tqId=21310&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

①题目及示例：

 ②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; 
}
 } 
}