另类加法与走方格的方案数

2022 年 7 月 21 日
本文字数：2209 字
阅读完需：约 7 分钟

⭐️另类加法⭐️

🔐题目详情

给定两个 int A 和 B。编写一个函数返回 A+B 的值，但不得使用+或其他算数运算符。

测试样例：

1,2返回：3

复制代码

题目链接：不用加减乘除做加法

💡解题思路

基本思路： 位运算

解题思路 1： 不让我使用加法，我为什么要听你话，我偏要用，反正也能过。

前置知识：

^运算符相当于不进位相加。
&可以判断两操作数位是否都为1，我们可以用来判断是否需要进位。
<<左移运算符，可以将操作数位左移。

解题思路 2：假设两数为a与b，我们可以使用^来进行不进位的加法a^b，为了知道哪些位需要进位，在执行此步骤之前，先得到tmp = (a&b)<<1的值，这句语句的意思就是得到两数都为1的位，左移1位是为了方便实现进位操作，因为进位不就是在某位的前一位进1吗？

如果tmp==0，表示不需要进位，那么此时我们的加法运算也就结束了，如果tmp!=0，我们需要将tmp与上次无进位加法得到的值再次进行无进位相加，并更新tmp的值，直到tmp为0，才能判定加法已经完成了。

有关^为什么是无进位加法，更详细的内容请参考：https://xie.infoq.cn/article/ab5edb33d4adf3f2c177cb3b5

🔑源代码

解题思路 2 代码：

import java.util.*;
public class UnusualAdd {    public int addAB(int a, int b) {        // write code here        while (b != 0) {            int tmp = (a & b) << 1;            a ^= b;            b = tmp;        }        return a;    }}

复制代码

🌱总结

不用加减乘除做加法，最容易想到的方法就是位运算，通过了解各种位运算的特点，找出模拟加法的适当方法。力扣同源题：371. 两整数之和面试题 17.01. 不用加号的加法力扣类似题：面试题 08.05. 递归乘法 29. 两数相除 50. Pow(x, n)69. Sqrt(x)面试题 16.07. 最大数值

⭐️走方格的方案数⭐️

🔐题目详情

请计算 n*m 的棋盘格子（n 为横向的格子数，m 为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

数据范围： 1≤n,m≤8

输入描述：

输入两个正整数 n 和 m，用空格隔开。(1≤n,m≤8)

输出描述：

输出一行结果

示例 1

输入：

2 2

复制代码

输出：

复制代码

题目链接：走方格的方案数

💡解题思路

基本思路： 动态规划

解题思路：首先我们来分析题目，简单来说题目告诉我们棋盘的行n与列m，我们将行数记为row，列数记为col，然后沿着这个row*col的棋盘中的分割线进行行走，那么其实就是从这个方格边缘线上的一端走到另外一端，对于row*col大小棋盘，在水平方向，他有col个格子，因此就有col+1个端点，同理在竖直方向有row+1个端点。

题目，让我们求从左上角顶点到右下角顶点的路径数，只能向右或向左走。

这道题是典型的路径问题，我们考虑动态规划，我们设左上角为原点，坐标为 $(0, 0)$ ，则终点右下角顶点的坐标为 $(r o w, c o l)$ 。

状态定义： 定义 $f [i] [j]$ 表示从原点到 $(i, j)$ 位置的路径数。确定初始状态： 当 $i = 0, j = 0$ 时，可以理解从原点到原点，那么路径数为 $1$ ，即 $f [0] [0] = 1$ 。状态转移方程： 三种情况：

$i = 0, j > 0$ ，点 $(i, j)$ 在棋盘上边界，只能经过点 $(i, j - 1)$ 运动到点 $(i, j)$ ，此时 $f [i] [j] = f [i] [j - 1]$ 。
$i > 0, j = 0$ ，点 $(i, j)$ 在棋盘左边界，只能经过点 $(i - 1, j)$ 运动到点 $(i, j)$ ，此时 $f [i] [j] = f [i - 1] [j]$ 。
$i > 0, j > 0$ ，点 $(i, j)$ 不在棋盘左边界与上边界，那么要么经过点 $(i - 1, j)$ 运动到点 $(i, j)$ ，要么经过点 $(i, j - 1)$ 运动到点 $(i, j)$ ，此时路径总数应为 $f [i] [j] = f [i - 1] [j] + f [i] [j - 1]$

综上分析状态转移方程就出来了：

🔑源代码

import java.util.*;
public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        //沿着边缘线走，那就相当于原网格的顶点作为一个新的格子，顶点数是输入数据(m+1)*(n+1)        int row = sc.nextInt();        int col = sc.nextInt();                //路径动态规划        //状态定义:定义f[i][j]为从(0,0)走到(i,j)位置的路径数        int[][] f = new int[row+1][col+1];        //确定初始状态:f[0][0]=1，(0,0)走到(0,0)位置的路径数可以理解为1种        f[0][0] = 1;        //状态转移方程:情况1:i=0,j>0,f[i][j]=f[i][j-1](在网格上边缘，路径数为左边那一格的路径数)        //情况2:i>0,j=0,f[i][j]=f[i-1][j](在网格左边缘，路径数为上边那一格的路径数)        //情况3:i>0,j>0,f[i][j]=f[i-1][j]+f[i][j-1](不在网格上与左边缘，路径数为左边那一格的路径数加上路径数为上边那一格的路径数)        for (int i = 0; i <= row; i++) {            for (int j = 0; j <= col; j++) {                if (i == 0 && j > 0) {                    //情况1:                    f[i][j] = f[i][j-1];                } else if (i > 0 && j == 0) {                    //情况2:                    f[i][j] = f[i-1][j];                } else if (i > 0 && j > 0) {                    //情况3:                    f[i][j] = f[i-1][j] + f[i][j-1];                }            }        }        System.out.println(f[row][col]);    }}