打算從今天起開始每日一練唧垦，鞏固一下算法捅儒，數(shù)據(jù)結(jié)構(gòu)相關(guān)的知識，廢話少說振亮，開始看題巧还。
題目
以上是我近期面試中遇到的一些題，其中1坊秸，3題出自百度系面試官麸祷；2，4出自Uber系面試官妇斤。
兩個(gè)水杯倒出3L水的問題
先來看第一個(gè)問題摇锋，題干是要求倒騰出3L的水丹拯。我們可以從4、5兩個(gè)數(shù)字入手荸恕，觀察通過怎樣的方式能夠得到3乖酬，得到以下兩種情況
- 4 * 2 -5 == 3
- ( 5 - 4 ) * 3 == 3
轉(zhuǎn)換為文字
- 第一種方式
- 先將4L的杯子接滿水，全部倒入到5L的杯子中（tips：此時(shí)4L的杯子為空融求，5L的杯子中裝載了4L水咬像，還能再倒入1L）
- 再將4L的杯子接滿水，然后向5L的杯子倒水生宛，當(dāng)5L杯子倒?jié)M時(shí)县昂，4L杯子剩下3L水
- 第二種方式
- 將5L的杯子接滿水，倒入4L的杯子中（tips: 此時(shí)5L的杯子剩下1L水）陷舅，然后將4L杯子的水全部倒掉倒彰，再將5L杯子剩余的1L水倒入4L的杯子（tips: 此時(shí)4L杯子有1L水）
- 將5L的杯子接滿水，倒入4L的杯子中（tips: 由于上一輪4L杯子已存在1L水莱睁，本次5L杯最多只能倒出3L水待讳，倒出后5L杯剩余2L水），然后將4L杯子的水全部的倒掉仰剿，再將5L杯子剩余的2L水倒入到4L的杯子（tips: 此時(shí)4L杯子有2L水）
- 將5L的杯子接滿水创淡，倒入4L的杯子中（tips: 由于上一輪4L杯子已存在2L水，本次5L杯最多只能倒出2L水南吮，倒出后5L杯正好剩余3L水）
大數(shù)四則運(yùn)算
第二個(gè)問題是一個(gè)典型的大數(shù)運(yùn)算問題琳彩。編程中有時(shí)會(huì)遇到數(shù)字上溢（tips: 如數(shù)值的大小超過了Long型可表示的最大數(shù)）的問題，此時(shí)便需要采用字符串替換原有的數(shù)值計(jì)算部凑。
以10進(jìn)制加法為例露乏，解決思路如下：
- 使用字符串裝載參與計(jì)算的兩個(gè)數(shù)值
- 分別取兩個(gè)字符串的末尾數(shù)值 a和b，進(jìn)行相加計(jì)算 sum = a+b 砚尽，如結(jié)果sum大于9施无，則設(shè)置進(jìn)位標(biāo)志 flag = 1；否則設(shè)置 flag = 0必孤。記錄sum%10猾骡，表示當(dāng)前位的結(jié)果
- 再次取兩個(gè)字符串的次末尾數(shù)值 a和b，進(jìn)行相加計(jì)算 sum = a+b+flag 敷搪，如結(jié)果sum大于9兴想，則設(shè)置進(jìn)位標(biāo)志 flag = 1；否則設(shè)置 flag = 0赡勘。記錄sum%10嫂便，表示當(dāng)前位的結(jié)果
... - 重復(fù)以上步驟，若兩個(gè)數(shù)字字符串的長度不一致闸与，則當(dāng)其中較短字符串s1遍歷完成后毙替，只遍歷另一個(gè)字符串s2岸售，每次取出s2的末位數(shù)值與flag相加，得到新的進(jìn)制標(biāo)志和當(dāng)前位的結(jié)果厂画。
代碼如下：
public static String bigSumAdd(String s1, String s2) {
StringBuilder stringBuilder = new StringBuilder();//字符串構(gòu)造器
int flag = 0;//初始化進(jìn)位標(biāo)志
//判定操作數(shù)長度大小
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'方可得到數(shù)字1~9凸丸。
int sum = (currentShorter - '0') + (currentLonger - '0') + flag;
flag = sum > 9 ? 1 : 0;//設(shè)置進(jìn)位標(biāo)志flag
stringBuilder.append(sum % 10);//將當(dāng)前位結(jié)果append到stringBuilder中
} else {
int sum = currentLonger - '0' + flag;
flag = sum > 9 ? 1 : 0;
stringBuilder.append(sum % 10);
}
}
//反轉(zhuǎn)字符串，輸出
return stringBuilder.reverse().toString();
}
字符串去重
這道題比較簡單袱院，有多種方法屎慢。
先排序再去重，時(shí)間復(fù)雜度 O(N*LogN)
public static String deDuplicate(String str) {
char strArr[] = str.toCharArray();//將字符串能轉(zhuǎn)化為字符數(shù)組
Arrays.sort(strArr);//將字符數(shù)組排序
char pre = strArr[0];//取字符數(shù)組首位字符
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(pre);//添加到緩沖中
for (int i = 1; i < strArr.length; i++) {
char current = strArr[i];
if (current == pre) {//判斷當(dāng)前字符與之前字符是否一致忽洛，若一致則跳過此次循環(huán)
continue;
}
stringBuffer.append(current);//否則將當(dāng)前字符添加到緩沖中
pre = current;//將當(dāng)前字符賦值于pre
}
//輸出
return stringBuffer.toString();
}
采用輔助空間腻惠，時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度與字符串編碼集相關(guān)
public static String deDuplicate2(String str) {
int help[] = new int[65536];//65536即2^16,可對應(yīng)2個(gè)字節(jié)以內(nèi)的任意字符
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < str.length(); i++) {
char current = str.charAt(i);//去當(dāng)前字符
if (help[current] != 0) {//若當(dāng)前字符已存在欲虚，則跳過本次循環(huán)
continue;
} else {
help[current]++;//否則將當(dāng)前字符對應(yīng)的位置位非0
stringBuffer.append(current);//添加到緩沖中
}
}
//輸出
return stringBuffer.toString();
}
楊輝三角
這道題是一個(gè)三角問題集灌，觀察三角構(gòu)型，得到如下現(xiàn)象：
- 從第一行到第五行苍在，每行依次有1绝页，2，3寂恬，4，5個(gè)數(shù)字...
- n行的三角共有 1+2+..+n-1+n 個(gè)數(shù)字
- 每一行的首位及末位數(shù)字均為'1'莱没，中間數(shù)字為正上方左右兩個(gè)數(shù)字的和初肉。
若用一維數(shù)組存儲(chǔ)三角中的所有數(shù)字，從上到下饰躲，從左到右開始索引牙咏，則從第i行，索引值為index的數(shù)值 arr[index] = arr[index - i] + arr[index-i-1]嘹裂，代碼如下：
/**
* 打印楊輝三角
* @param n 表示楊輝三角的行數(shù)
*/
public static void yanhuiTriangle(int n){
int size = 0;
//得到一維數(shù)組長度
for (int i = 0; i <= n; i++) {
size += i;
}
int arr[] = new int[size];//創(chuàng)建一維數(shù)組
int index = 0;
for (int i = 0; i < n; i++) {//外層循環(huán)妄壶，控制行
for (int j = 0; j < n - i; j++) {
System.out.print(" ");//打印數(shù)字之前的空格
}
for (int j = 0; j <= i; j++) {//內(nèi)存循環(huán)，控制列
if (j == 0 || j == i) {//每行的首位及末尾
arr[index] = 1;
} else {
arr[index] = arr[index - i] + arr[index - i - 1];//中間位求值
}
System.out.print(arr[index] + " ");//打印數(shù)值
index++;
}
System.out.println();
}
}
總結(jié)
第一天的開胃菜到此結(jié)束寄狼，題目本身并不難丁寄，更多的是對編程思維的考察，今天先到這里泊愧，如有疑問歡迎與我聯(lián)系 ：）
