[数据结构与算法]【算法刷题日记之本手篇】另类加法与走方格的方案数

??前面的话??

本篇文章介绍来自牛客试题广场的两道题题解，分别为【另类加法】和【走方格的方案数】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏??留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年7月19日🌴
??坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

??另类加法??

🔐题目详情

给定两个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，才能判定加法已经完成了。

有关^为什么是无进位加法，更详细的内容请参考：剑指 Offer 65. 不用加减乘除做加法

🔑源代码

解题思路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

输出：

6

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

💡解题思路

基本思路： 动态规划

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

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


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

状态定义： 定义$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]$

综上分析状态转移方程就出来了：
$$f[i][j]=?\begin{array}{c}f[i][j]=1,i=0,j=0\\ f[i][j]=f[i][j?1],i=0,j>0\\ f[i][j]=f[i?1][j],i>0,j=0\\ f[i][j]=f[i?1][j]+f[i][j?1],i>0,j>0\end{array}$$

🔑源代码

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

🌱总结

本题为路径问题，常见的解题思路为动态规划，重点是知道如何状态定义，确定初始状态和推导状转移方程。

类似题：
62. 不同路径
63. 不同路径 II

升级题：
64. 最小路径和
120. 三角形最小路径和
931. 下降路径最小和

困难题：
1289. 下降路径最小和 II

推荐参考读物：DP - 路径问题