⭐️前面的话⭐️
本篇文章介绍来自牛客试题广场的两道题题解，分别为【不用加减乘除做加法】和【三角形】，展示语言java。
小贴士：本专栏所有题目来自牛客->面试刷题必用工具
📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年9月15日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬推荐在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
注意事项：本专栏所有题目都来自牛客网，如果有小伙伴还没有注册牛客，可以点击下方链接进行注册，注册完就能立即刷题了。不仅是刷题，上面还有很多有关就业的面经，面试题库，以及名企的模拟面试，我非常推荐它，博主自己用的也很多，也刷了不少题了！下图可以作证：
注册地址：牛客网
有关任何问题都可以与博主交流，你可以在评论区留言，也可以私信我，更可以加上博主的vx与博主一对一交流（文章最下方有）。
⭐️不用加减乘除做加法⭐️
🔐题目详情
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 −10≤n≤1000
进阶：空间复杂度 O(1)，时间复杂度O(1)
示例1
输入
1,2
输出
3
示例2
输入
0,0
输出
0
链接：不用加减乘除做加法
💡解题思路
基本思路： 位运算
方法1：你说不能使用加减乘除运算符？我偏要用，直接将两数相加返回。
方法2：位运算。
预备知识：
- 按位与 & ：双目运算符，对每位取与，都为1则为1，否则为0。
- 按位异或 ^ ：双目运算符，对每位取异或，对应位两数不相同为1，否则为0。
- 左移 << ：双目运算符，a << b ，表示将a的二进制位左移b位，最右边补0。
- 加法进位的特点：对于二进制，发生进位的条件是两个数所对应的二进制位均为1。
解题思路：
实现a，b两数完整加法的步骤：
- 将a与b按位与并左移一位，即(a & b) << 1，不妨将此结果存至变量tmp，若此数值为0，就表示两数未发生进位。
- 将a与b进行非进位加法，即a ^ b，不妨将此结果赋值给a，将上面所得tmp值赋值给b。
- 此时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;
}
}
🌱总结
本题为位运算运用题，解题关键是知道运算符^相当于不进位的加法。
⭐️三角形⭐️
🔐题目详情
给定三条边，请你判断一下能不能组成一个三角形。
输入描述:
输入包含多组数据，每组数据包含三个正整数a、b、c（1≤a, b, c≤10^100）。
输出描述:
对应每一组数据，如果它们能组成一个三角形，则输出“Yes”；否则，输出“No”。
示例1
输入
1 2 3
2 2 2
输出
No
Yes
题目链接：三角形
💡解题思路
基本思路： 两边之和大于第三边
解题思路：
思路1：使用范围足够大的类型。
本题唯一的难点就是题目给的数据比较大，达到 1 0 100 10^{100} 10100，使用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");
}
}
}
}
使用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");
}
}
}
}
使用大数加法与比较模拟：
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;
}
}
🌱总结
本题为大数运算运用题，考查的目的不是判断三角形，而是对非常大的数据的处理以及运算与比较。
到文章最后，再来安利一下吧，博主也是经常使用，并且也经常在牛客上刷题，题库也非常丰富：牛客网，刷题，面试，内推都有。也欢迎与博主交流有关刷题，技术方面，以及与博主聊聊天，交个朋友也好啊，毕竟有朋自远方来！
