08-04那天參加了一下網易互娛的模拟筆試，那天狀态不太好，再加上調試第一題花了很長時間，心态有點炸了，是以最後完成得并不理想。
總結：筆試心态還不夠穩，手速還不夠快，算法還不夠熟。
一共 3 道題，題目都很簡單，但是自己并沒有做完，汗顔羞愧。記錄一下。
第一題 個稅繳納
新稅收政策中，起征點是5000，超過5000的部分，需要進行分級納稅，請根據新納稅表計算個人所得稅，題目如圖：
要求：
多行輸入，每行輸入月收入，假設無需繳納其他費用，請輸出計算出所需繳納的個人所得稅，稅費四舍五入。
實作：
// 計算個人所得稅，income: 個人收入， taxs: 匯率表
int calTax(int income, map<int, double> &taxs){
int len = taxs.size();
if(income <= 5000){
return 0;
}
income = income - 5000;
int i = 0; // 記錄目前為第幾個區間
int res = 0;
map<int, double>::iterator iter_cur = taxs.begin(); // 目前區間疊代器
map<int, double>::iterator iter_next = ++taxs.begin(); // 下一區間疊代器，用于取得下一區間的起始值
for(; iter_cur != taxs.end(); iter_cur++, iter_next++){
if(income - iter_cur->first <= 0){
break;
}else{
int range_tax; // 目前區間所需繳納的稅額
if(income >= iter_next->first && i < len - 1){ // 收入大于目前納稅區間的最大值，即大于下一區間的起始值時。并且目前區間不是最後一個區間
range_tax = round((iter_next->first - iter_cur->first) * iter_cur->second); // 直接區間值 * 區間稅率
}else{
range_tax = round((income - iter_cur->first) * iter_cur->second); // 收入與區間起始值的差 * 區間稅率
}
res += range_tax;
i++;
}
}
return res;
}
int main(){
int T;
map<int, double> taxs = { // 稅率表
{0, 0.03},
{3000, 0.1},
{12000, 0.2},
{25000, 0.25},
{35000, 0.3},
{55000, 0.35},
{80000, 0.45}
};
cin >> T;
while(T--){
int N;
int tax;
cin >> N;
cout << calTax(N, taxs) << endl;
}
return 0;
}
AC 100%
源碼位址
第二題 字元串縮寫
将4個及4個以上連續字典序的字母轉為"首個字母-結束字母"的形式。
如 “ABCABCDEFGABCD” → “ABCA-GA-D”。字母都為大寫字母，沒有其他字元。
要求：
多行輸入，每行一個長度不超過5000的字元串。
輸出 縮寫後的字元串。
官方給出的解題思路：
算法複雜度是 O(N)
個人思路實作：
// 壓縮字元串函數，傳回縮寫後的字元串
string compressString(string str){
int len = str.size();
if(len < 4){
return str;
}
string res = ""; // 傳回結果
string sub_str = ""; // 用于暫存子串
int i = 0;
for(; i < len - 1; i++){
if(str[i] + 1 == str[i + 1]){
sub_str += str[i];
}else{
if(sub_str.size() >= 3){
res = res + sub_str[0] + "-" + str[i];
}else{
res = res + sub_str + str[i];
}
sub_str = ""; // 初始化
}
}
if(sub_str.size() >= 3 && str[i - 1] + 1 == str[i]){ // 因為 str[len - 1] 尚未周遊，是以還需再判斷一次
res = res + sub_str[0] + "-" + str[i];
}else{
res = res + sub_str + str[i];
}
return res;
}
int main(){
int T;
cin >> T;
while(T--){
string s;
cin >> s;
cout << compressString(s) << endl;
}
return 0;
}
源碼位址
第三題
由于打字員失誤，整數 N 的 X 進制和 Y 進制連在一起輸出了，請根據X、Y兩個進制連起來的字元串，識别出這個整數 N 的十進制值。資料保證隻有一個解。
要求：
多行輸入，每行輸入為 X Y Z 的形式，2 <= X, Y <= 16，Z 為 N 的 X 進制及 Y 進制連起來的字元串，請根據 X Y Z 識别出 N，并輸出 N 的十進制。10 ~ 15 用大寫 A ~ F 表示。0 < N < 2^31 - 1
如
輸入：13 7 1016
輸出：13
官方思路：
個人思路實作：
// 進制轉換函數， 将 k 機制字元串轉換為十進制數
long long kToDec(int k, string str){
int len = str.size();
long long res = 0;
for(int i = 0; i < len; i++){
if(str[i] >= 'A' && str[i] <= 'F'){
res = res * k + (str[i] - 'A') + 10;
}else{
res = res * k + (str[i] - '0');
}
}
return res;
}
// 識别數字函數，傳回識别結果
long long identifyNum(int x, int y, string str){
int len = str.size();
int left = 0;
int right = len - 1;
while(left < right ){ // 使用二分法尋找兩種進制的“中位數”
int median = (left + right) / 2;
long long num1 = kToDec(x, str.substr(0, median + 1)); // 左子串轉換成十進制
long long num2 = kToDec(y, str.substr(median + 1)); // 右子串轉換成十進制
if(num1 < num2){
left = median + 1;
}else if(num1 > num2){
right = median;
}else{
return num1;
}
}
return -1;
}
int main(){
int T; // 樣例數
cin >> T;
while(T--){
int X, Y; // X 進制，Y 進制，
string Z; // 為數字字元串
cin >> X >> Y >> Z; // 最大輸入示例：2 16 11111111111111111111111111111111FFFFFFFF
cout << identifyNum(X, Y, Z) << endl;
}
return 0;
}
源碼連結
第二、第三題我參考了一個哥們三題全AC的代碼，他是用JAVA寫的，感興趣的可以去看看，參考連結：
https://www.nowcoder.com/discuss/216766