打算从今天起开始每日一练，巩固一下算法，数据结构相关的知识，废话少说，开始看题。
题目
以上是我近期面试中遇到的一些题，其中1，3题出自百度系面试官；2，4出自Uber系面试官。
两个水杯倒出3L水的问题
先来看第一个问题，题干是要求倒腾出3L的水。我们可以从4、5两个数字入手，观察通过怎样的方式能够得到3，得到以下两种情况
- 4 * 2 -5 == 3
- ( 5 - 4 ) * 3 == 3
转换为文字
- 第一种方式
- 先将4L的杯子接满水，全部倒入到5L的杯子中（tips：此时4L的杯子为空，5L的杯子中装载了4L水，还能再倒入1L）
- 再将4L的杯子接满水，然后向5L的杯子倒水，当5L杯子倒满时，4L杯子剩下3L水
- 第二种方式
- 将5L的杯子接满水，倒入4L的杯子中（tips: 此时5L的杯子剩下1L水），然后将4L杯子的水全部倒掉，再将5L杯子剩余的1L水倒入4L的杯子（tips: 此时4L杯子有1L水）
- 将5L的杯子接满水，倒入4L的杯子中（tips: 由于上一轮4L杯子已存在1L水，本次5L杯最多只能倒出3L水，倒出后5L杯剩余2L水），然后将4L杯子的水全部的倒掉，再将5L杯子剩余的2L水倒入到4L的杯子（tips: 此时4L杯子有2L水）
- 将5L的杯子接满水，倒入4L的杯子中（tips: 由于上一轮4L杯子已存在2L水，本次5L杯最多只能倒出2L水，倒出后5L杯正好剩余3L水）
大数四则运算
第二个问题是一个典型的大数运算问题。编程中有时会遇到数字上溢（tips: 如数值的大小超过了Long型可表示的最大数）的问题，此时便需要采用字符串替换原有的数值计算。
以10进制加法为例，解决思路如下：
- 使用字符串装载参与计算的两个数值
- 分别取两个字符串的末尾数值 a和b，进行相加计算 sum = a+b ，如结果sum大于9，则设置进位标志 flag = 1；否则设置 flag = 0。记录sum%10，表示当前位的结果
- 再次取两个字符串的次末尾数值 a和b，进行相加计算 sum = a+b+flag ，如结果sum大于9，则设置进位标志 flag = 1；否则设置 flag = 0。记录sum%10，表示当前位的结果
... - 重复以上步骤，若两个数字字符串的长度不一致，则当其中较短字符串s1遍历完成后，只遍历另一个字符串s2，每次取出s2的末位数值与flag相加，得到新的进制标志和当前位的结果。
代码如下：
public static String bigSumAdd(String s1, String s2) {
StringBuilder stringBuilder = new StringBuilder();//字符串构造器
int flag = 0;//初始化进位标志
//判定操作数长度大小
String longer = s1.length() > s2.length() ? s1 : s2;
String shorter = s1.length() > s2.length() ? s2 : s1;
for (int i = 1; i <= longer.length(); i++) {
int last1 = longer.length() - i ;//取longger最后一位的索引值
int last2 = shorter.length() - i ;//取shorter最后一位的索引值
int currentLonger = (int) longer.charAt(last1);
if (i < shorter.length()) {
int currentShorter = (int) shorter.charAt(last2);
//每次charAt()取出的只是char型变量 '1'~'9',需减去'0'方可得到数字1~9。
int sum = (currentShorter - '0') + (currentLonger - '0') + flag;
flag = sum > 9 ? 1 : 0;//设置进位标志flag
stringBuilder.append(sum % 10);//将当前位结果append到stringBuilder中
} else {
int sum = currentLonger - '0' + flag;
flag = sum > 9 ? 1 : 0;
stringBuilder.append(sum % 10);
}
}
//反转字符串，输出
return stringBuilder.reverse().toString();
}
字符串去重
这道题比较简单，有多种方法。
先排序再去重，时间复杂度 O(N*LogN)
public static String deDuplicate(String str) {
char strArr[] = str.toCharArray();//将字符串能转化为字符数组
Arrays.sort(strArr);//将字符数组排序
char pre = strArr[0];//取字符数组首位字符
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(pre);//添加到缓冲中
for (int i = 1; i < strArr.length; i++) {
char current = strArr[i];
if (current == pre) {//判断当前字符与之前字符是否一致，若一致则跳过此次循环
continue;
}
stringBuffer.append(current);//否则将当前字符添加到缓冲中
pre = current;//将当前字符赋值于pre
}
//输出
return stringBuffer.toString();
}
采用辅助空间，时间复杂度 O(N)，空间复杂度与字符串编码集相关
public static String deDuplicate2(String str) {
int help[] = new int[65536];//65536即2^16,可对应2个字节以内的任意字符
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < str.length(); i++) {
char current = str.charAt(i);//去当前字符
if (help[current] != 0) {//若当前字符已存在，则跳过本次循环
continue;
} else {
help[current]++;//否则将当前字符对应的位置位非0
stringBuffer.append(current);//添加到缓冲中
}
}
//输出
return stringBuffer.toString();
}
杨辉三角
这道题是一个三角问题，观察三角构型，得到如下现象：
- 从第一行到第五行，每行依次有1，2，3，4，5个数字...
- n行的三角共有 1+2+..+n-1+n 个数字
- 每一行的首位及末位数字均为'1'，中间数字为正上方左右两个数字的和。
若用一维数组存储三角中的所有数字，从上到下，从左到右开始索引，则从第i行，索引值为index的数值 arr[index] = arr[index - i] + arr[index-i-1]，代码如下：
/**
* 打印杨辉三角
* @param n 表示杨辉三角的行数
*/
public static void yanhuiTriangle(int n){
int size = 0;
//得到一维数组长度
for (int i = 0; i <= n; i++) {
size += i;
}
int arr[] = new int[size];//创建一维数组
int index = 0;
for (int i = 0; i < n; i++) {//外层循环，控制行
for (int j = 0; j < n - i; j++) {
System.out.print(" ");//打印数字之前的空格
}
for (int j = 0; j <= i; j++) {//内存循环，控制列
if (j == 0 || j == i) {//每行的首位及末尾
arr[index] = 1;
} else {
arr[index] = arr[index - i] + arr[index - i - 1];//中间位求值
}
System.out.print(arr[index] + " ");//打印数值
index++;
}
System.out.println();
}
}
总结
第一天的开胃菜到此结束，题目本身并不难，更多的是对编程思维的考察，今天先到这里，如有疑问欢迎与我联系 ：）
