【Java版oj】day09不用加号的加法、走方格的方案数

忘是亡心i 2024-03-25 14:06 1阅读 0赞

**目录**

一、不用加号的加法

（1）原题再现

（2）问题分析

（3）完整代码

二、走方格的方案数

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、不用加号的加法 ##
> 
> ### （1）原题再现 ###
> 
> [面试题 17.01. 不用加号的加法][17.01.]
> 
> 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
> 
> 示例:
> 
> 输入: a = 1, b = 1
> 
> 输出: 2
> 
> ### （2）问题分析 ###
> 
> 这道题要求不能用“+”等算数运算符，所以我们可以想到使用**位运算符**。
> 
> <table style="width:500px;"> 
> <tbody> 
> <tr> 
> <td style="text-align:center;width:67px;">符号</td> 
> <td style="text-align:center;width:71px;">描述</td> 
> <td style="text-align:center;width:360px;">运算规则</td> 
> </tr> 
> <tr> 
> <td style="text-align:center;width:67px;">&amp;</td> 
> <td style="text-align:center;width:71px;">与</td> 
> <td style="text-align:center;width:360px;">两个位都为1时，结果才为1。</td> 
> </tr> 
> <tr> 
> <td style="width:67px;"> | </td> 
> <td style="text-align:center;width:71px;">或</td> 
> <td style="text-align:center;width:360px;">两个位都为0时，结果才为0。</td> 
> </tr> 
> <tr> 
> <td style="text-align:center;width:67px;">^</td> 
> <td style="text-align:center;width:71px;">异或</td> 
> <td style="text-align:center;width:360px;">两个位相同为0，相异为1。</td> 
> </tr> 
> <tr> 
> <td style="text-align:center;width:67px;">~</td> 
> <td style="text-align:center;width:71px;">取反</td> 
> <td style="text-align:center;width:360px;">0变1，1变0。</td> 
> </tr> 
> <tr> 
> <td style="text-align:center;width:67px;">&lt;&lt;</td> 
> <td style="text-align:center;width:71px;">左移</td> 
> <td style="text-align:center;width:360px;">各二进位全部左移若干位，高位丢弃，低位补0</td> 
> </tr> 
> <tr> 
> <td style="text-align:center;width:67px;">&gt;&gt;</td> 
> <td style="text-align:center;width:71px;">右移</td> 
> <td style="text-align:center;width:360px;">各二进位全部右移若干位，对无符号数，高位补0，有符号数，右移补1。</td> 
> </tr> 
> </tbody> 
> </table>
> 
> 本题可以使用&和^运算符，使用&得到两数相加的进位情况，使用^得到两数相加的结果（没有加进位）![0038917001f343e0909b6ac2cdcd14c0.png][]
> 
> ### （3）完整代码 ###
> 
> class Solution {
> public int add(int a, int b) {
> // write code here
> 	int ans=a^b;//无进位的情况下
> 	int carry=a&b;//需要进位的地方
> 	while(carry!=0) {
> 		carry=carry<<1;
> 		int tmp=ans;
> 		ans=ans^carry;
> 		carry=tmp&carry;
> 	}
> 	return ans;
> }
> }
> 
> ![0ccda4f9c8dd42279892ca8e58bbcddb.png][]

> ## 二、走方格的方案数 ##
> 
> ### （1）原题再现 ###
> 
> [走方格的方案数\_牛客题霸\_牛客网][Link 1]
> 
> 描述
> 
> 请计算n\*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
> 
> 注：沿棋盘格之间的边缘线行走
> 
> **输入描述：**
> 
> 输入两个正整数n和m，用空格隔开。(1≤n,m≤8)
> 
> **输出描述：**
> 
> 输出一行结果
> 
> **示例:**
> 
> **输入：**
> 
> 2 2
> 
> **输出：**
> 
> 6
> 
> ### （2）问题分析 ###
> 
> 这道题很明显是一道动态规划的题。需要额外注意的是n、m表示的是格子数，而我们走的是边，所以n和m都要+1，即2\*2的4个格子有3\*3的边框。
> 
> ![0563373660c84bdda3c4f39f779a6299.png][]
> 
> 我们用二维数据记录每一步的状态。
> 
> **状态：** 
> **子状态：**从(0,0)到达(1,0),(1,1),(2,1),...(n,m)的路径数 
> **F(i,j): 从(0,0)到达F(i,j)的路径数**
> 
> ![0055d4175d7d4d7194759c6aefeea972.png][]
> 
> 到达黄色这一状态时可能是从上面走下来，也可能是从左边走过来的。这一点的路径数，就是左边一点的路径数+上边一点的路径数。 
> **状态递推：** 
> **F(i,j) = F(i-1,j) + F(i,j-1)** 
> **初始化：** 因为只能向左或者向下，所以当只有一行时，只能向左，走法也只有一种；同理，当只有一列时，只能向下，走法也只有一种。 
> 特殊情况：第0行和第0列 
> **F(0,i) = 1 
> F(i,0) = 1** 
> **返回结果：**右下角 
> **F(n,m)**
> 
> ### （3）完整代码 ###
> 
> import java.util.*;
> 
> public class Main {
> 	public static void main(String[] args) {
> 		Scanner sc=new Scanner(System.in);
> 		int n=sc.nextInt();
> 		int m=sc.nextInt();
> 		int [][]maxNum=new int[n+1][m+1];
> 		for(int i=0;i<=m;i++) {
> 			maxNum[0][i]=1;
> 		}
> 		for(int i=0;i<=n;i++) {
> 			maxNum[i][0]=1;
> 		}
> 		for(int i=1;i<=n;i++) {
> 			for(int j=1;j<=m;j++) {
> 				maxNum[i][j]=maxNum[i-1][j]+maxNum[i][j-1];
> 			}
> 		}
> 		System.out.println(maxNum[n][m]);
> 	}
> }
> 
> ![ffedd39f4de045faacef377a7527958e.png][]

--------------------

![f75050c438cb4f74ab624af5f2155f56.png][]

[17.01.]: https://leetcode.cn/problems/add-without-plus-lcci/
[0038917001f343e0909b6ac2cdcd14c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7bc1ea5299b7475fbf99911730aea20a.png
[0ccda4f9c8dd42279892ca8e58bbcddb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/963016fe73a3466cb8e424cb825a9f6f.png
[Link 1]: https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
[0563373660c84bdda3c4f39f779a6299.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0f04b06086d345abb4bf6293cb1d55cb.png
[0055d4175d7d4d7194759c6aefeea972.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/85c06a01144d4adb88c4531c50546f7b.png
[ffedd39f4de045faacef377a7527958e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7c65c83ac0064bf0901b662d962dfe3e.png
[f75050c438cb4f74ab624af5f2155f56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0a2193dd066348369f563f7fecb2f090.png