【算法刷题日记之本手篇】不用加减乘除做加法与三角形

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【不用加减乘除做加法】和【三角形】，展示语言java。

小贴士：本专栏所有题目来自牛客->面试刷题必用工具

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

---

---

注意事项：本专栏所有题目都来自牛客网，如果有小伙伴还没有注册牛客，可以点击下方链接进行注册，注册完就能立即刷题了。不仅是刷题，上面还有很多有关就业的面经，面试题库，以及名企的模拟面试，我非常推荐它，博主自己用的也很多，也刷了不少题了！下图可以作证：

注册地址：牛客网

有关任何问题都可以与博主交流，你可以在评论区留言，也可以私信我，更可以加上博主的vx与博主一对一交流（文章最下方有）。

---

⭐️不用加减乘除做加法⭐️

🔐题目详情

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

数据范围：两个数都满足 −10≤n≤1000
进阶：空间复杂度 O(1)，时间复杂度O(1)

示例1

输入

1,2
1

输出

3
1

示例2

输入

0,0
1

输出

0
1

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

💡解题思路

基本思路： 位运算

方法1：你说不能使用加减乘除运算符？我偏要用，直接将两数相加返回。

方法2：位运算。

预备知识：

• 按位与 & ：双目运算符，对每位取与，都为1则为1，否则为0。
• 按位异或 ^ ：双目运算符，对每位取异或，对应位两数不相同为1，否则为0。
• 左移 << ：双目运算符，a << b ，表示将a的二进制位左移b位，最右边补0。
• 加法进位的特点：对于二进制，发生进位的条件是两个数所对应的二进制位均为1。

解题思路：

实现a，b两数完整加法的步骤：

1. 将a与b按位与并左移一位，即(a & b) << 1，不妨将此结果存至变量tmp，若此数值为0，就表示两数未发生进位。
2. 将a与b进行非进位加法，即a ^ b，不妨将此结果赋值给a，将上面所得tmp值赋值给b。
3. 此时b的值为tmp，判断b是否为0，若b不为0，需要进位，重复上述步骤，将进位数b与前一次非进位加法的值非进位相加，若b为0，不需要进位，加法过程结束，最终结果即a的值。

注意：C/C++对负数左移存在溢出，先将 a & b 强转为 unsigned int 以保护左移溢出的情况！java不用注意这一点。

🔑源代码

import java.util.*;
public class Solution {
    public int Add(int num1,int num2) {
        //突破口^运算相当于不进位的加法
        //使用按位与加左移1位保存进位信息
        while (num2 != 0) {
            int tmp = (num1 & num2) << 1;
            num1 ^= num2;
            //更新num2为进位信息数
            num2 = tmp;
        }
        return num1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

🌱总结

本题为位运算运用题，解题关键是知道运算符^相当于不进位的加法。

⭐️三角形⭐️

🔐题目详情

给定三条边，请你判断一下能不能组成一个三角形。

输入描述:

输入包含多组数据，每组数据包含三个正整数a、b、c（1≤a, b, c≤10^100）。
1

输出描述:

对应每一组数据，如果它们能组成一个三角形，则输出“Yes”；否则，输出“No”。
1

示例1

输入

1 2 3
2 2 2
1
2

输出

No
Yes
1
2

题目链接：三角形

💡解题思路

基本思路： 两边之和大于第三边
解题思路：

思路1：使用范围足够大的类型。

本题唯一的难点就是题目给的数据比较大，达到$10^{100}$，使用int long肯定是行不通的，为了解决数据范围的问题可以使用double或者BigDecimal类，这两种类型是可以满足题目的要求的，至于题目的解题，其实就是我们小学学过的两边之和大于第三边，判断一下就可以了。

思路2：大数加法模拟与大数比较。

这个简单说一下，所谓大数模拟加法，就是将输入的数存放到数组中，在数组中从地位到高位进行模拟加法，不妨设数组中某位加数为a，另一位为b，数组每一位对应位加法的结果为(a + b +up) % 10。考虑到进位我们可以使用一个变量up来储存每次进位值的大小，初始为0，则每轮加法后up=(a + b + up)/10。

大数比较简单一些，首先判断数据数组长度大小，如果长度不一样，那就直接返回第一个数与第二个数的长度差，否则从高位开始比较，如果对应位的数不同，直接返回第一个数与第二个数在此位的差值即可，差值大于0表示第一个数大于第二个数，差值小于0表示第一个数小于第二个数，差值等于0那就是相等了。

我们根据实现的模拟大数加法与模拟大数比较，就可以实现两边之和与第三边大小的判断。

大数模拟加法实现过程中，推荐将高位存入数组的靠后的位置，如1234，在数组中存放位置为[4, 3, 2, 1]，这个目的是为了方便进位的实现。

一个长度为n的数与另一个长度为m的数相加，结果的长度顶多为max(n,m)+1，所以得到的结果数组长度可以定为max(n,m)+1，当然这样设计会导致最高位出现0的情况，为了避免得到的数组长度与数的长度可能不一致的问题，我们先判断最高位是否为0，如果为0我们将数的长度记为数组长度减1即可。

🔑源代码

使用double，范围不会溢出。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            //数字过大使用double
            double a = sc.nextDouble();
            double b = sc.nextDouble();
            double c = sc.nextDouble();
        
            if (a + b > c && a + c > b && b + c > a) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

使用BigDecimal类

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            //数字过大使用BigDecimal
            BigDecimal a = sc.nextBigDecimal();
            BigDecimal b = sc.nextBigDecimal();
            BigDecimal c = sc.nextBigDecimal();
        
            if (a.add(b).compareTo(c) > 0 
                && a.add(c).compareTo(b) > 0 
                && b.add(c).compareTo(a) > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

使用大数加法与比较模拟：

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            //使用大数加法与比较模拟
            String a = sc.next();
            String b = sc.next();
            String c = sc.next();
            
            char[] ca = a.toCharArray();
            char[] cb = b.toCharArray();
            char[] cc = c.toCharArray();
            
            int n = ca.length;
            int m = cb.length;
            int k = cc.length;
            
            int[] add1 = new int[n];
            int[] add2 = new int[m];
            int[] add3 = new int[k];
            
            int j = 0;
            for (int i = n - 1; i >= 0; i--) {
                add1[j++] = ca[i] - '0';
            }
            j = 0;
            for (int i = m - 1; i >= 0; i--) {
                add2[j++] = cb[i] - '0';
            }
            j = 0;
            for (int i = k - 1; i >= 0; i--) {
                add3[j++] = cc[i] - '0';
            }
            //判断两边之和大于第三边
            if (compare(add(add1, add2), add3) > 0 
                && compare(add(add2, add3), add1) > 0
                && compare(add(add1, add3), add2) > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
    //模拟加法
    private static int[] add(int[] add1, int[] add2) {
        int len1 = add1.length;
        int len2 = add2.length;
        //判断是否存在前导0，存在使长度减1
        len1 = add1[len1 - 1] == 0 ? len1 - 1 : len1;
        len2 = add2[len2 - 1] == 0 ? len2 - 1 : len2;
        int n = len1 > len2 ? len1 : len2;
        int[] ret = new int[n + 1];
        int up = 0;
        int i = 0;
        for (i = 0; i < n; i++) {
            int a = i >= len1 ? 0 : add1[i];
            int b = i >= len2 ? 0 : add2[i];
            ret[i] = (a + b + up) % 10;
            up = (a + b + up) / 10;
        }
        while (up > 0) {
            ret[i++] = up % 10;
            up /= 10;
        }
        return ret;
    }
    //模拟比较
    private static int compare(int[] a, int[] b) {
        int len1 = a.length;
        int len2 = b.length;
        //判断是否存在前导0，存在使长度减1
        len1 = a[len1 - 1] == 0 ? len1 - 1 : len1;
        len2 = b[len2 - 1] == 0 ? len2 - 1 : len2;
        if (len1 != len2) return len1 - len2;
        
        for (int i = len2 - 1; i >= 0; i--) {
            if (a[i] != b[i]) return a[i] - b[i];
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

🌱总结

本题为大数运算运用题，考查的目的不是判断三角形，而是对非常大的数据的处理以及运算与比较。

---

到文章最后，再来安利一下吧，博主也是经常使用，并且也经常在牛客上刷题，题库也非常丰富：牛客网，刷题，面试，内推都有。也欢迎与博主交流有关刷题，技术方面，以及与博主聊聊天，交个朋友也好啊，毕竟有朋自远方来！

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！