30天刷题计划（五）

加油鸭 

目录

1.另类加法

2.求路径总数

3.井字棋

4.密码等级强度

---

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

①题目及示例：

 ②方法及解析：

因为题目中明确指出不得使用+和其他的算术运算符。所以，我们很容易想到位运算符。

在利用位运算符的时候，我们又该用哪种位运算符呢？

首先我们得知道，我们会遇到进位和不进位两种情况。比如：1+2=3就不用进位（用二进制来看），3+2=5就需要进位。如果不需要进位，那么我们直接用异或运算即可。如果需要进位，我们就需要知道如何才能进位，这个时候我们就得先进行按位与运算，然后将结果进行左移一位。所以，我们无非进行下面两个操作。

a.判断是否需要进位：（&运算符，因为全1为1，有0为0，若全为0，则表示不需要进位，因为是二进制，满二进一）

b.将异或后的结果与进位左移的结果的值进行相加（此处仍然用的是异或）

c.将b中的两值重复a,b步骤，直到不需要进位为止

实质上：位运算A^B是不考虑进位的结果，（A&B）<<1是求得的进位

因此A^B+（A&B）<<1的结果就是和，只要（A&B）<<1=0，两项就变成了一项，不需要加法了

代码如下：

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;//求两个数的和，不进位的那种
            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

①题目及示例：

 ②方法及解析：

a.递归方法来做：

这道题之前刷过，是按照递归的思想来进行操作的，大家可以看看下面这个图。

代码如下：

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.动态规划来做：

首先我们应该了解一下动态规划的相关思路：

动态规划实际和递归在原理上是非常像的，都是通过以前数学中的归纳法来着手。通俗一点来说，就是这一步是由上一步推导得来，而上一步又是以同样的规律由上上步得来，然后依次类推的过程。

而在动态规划中我们常用到的步骤往往是：

1.确定状态（两个核心：1最后一步  2化成子问题）

2.转移方程

3.开始和边界条件

以下面这个题为例，我们来做一个剖析：

62. 不同路径 - 力扣（LeetCode）https://leetcode.cn/problems/unique-paths/

我们的最终目的是让五角星走到圆圈处。(3行，4列)

（1）确定状态：

状态：设f[m][n]为机器人有多少种方式从左上角走到（m, n）

很显然，最后一步要么是[1][3]向下，要么是[2][2]向右

 

要是有m行，n列放在这种二维数组中，我们就可以发现，要到达的圆圈[m-1][n-1];那么最后的两种结果无非是：[m-2][n-1]和[m-1][n-2];

所以我们就进而转化成了子问题：

就是将上述两种结果，分别再分析，发现还是得到同样的关系。

到[m-2][n-1]的方式无非是：[m-3][n-1]和[m-2][n-2]。其它的以此类推。

（2）我们就可以确定状态方程为：对于任意一个格子（m, n）有：

  f[m][n] = f[m-1][n] + f[m][n-1];

（3）开始和边界条件：

若是m,n均为0，那么此时走到这个位置的方式只有1中；因为就是其本身。

若是只有行m,那么结果就是走到（m-1,0）;这个时候只能向右走，只有一种方式。

即：f[m][n] = 1

同理，若只有列n,那么结果就是走到（0,n-1）;这个时候只能向下走，也只有一种方式。

即：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];
    }
}

但是本题是从左上顶点走到右下顶点，所以这里的数组横纵坐标均要+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) {
        // 定义二位dp数组dp[i,j] = dp[i-1,j]+dp[i,j-1];
        //因为对于n个格子来说，有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

①题目及示例：

 

②方法及解析：

这个题很简单，实际上只需要我们保证横排，纵列，主对角线和副对角线的数，这其中有一种全为1，那么则输出true。代码如下：

特别需要注意一下的是每行或每列计算结束后要将sum置为0，否则还是会进行累加，而导致结果不准确。

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.密码等级强度

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

①题目及示例：

 ②方法及解析：

这个就是罗列出来，直接上代码：

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