NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

今天做了順豐科技的線上筆試題,選擇題方面感覺考得很基礎,有資料結構、編譯原理方面的題目,以及設計模式的題目。編譯原理的內容基本忘記了,設計模式也沒有進行深入的學習,所以這兩塊大的並不是太好。再有就是排序演算法,出現了兩道排序演算法思想的問題:一個是給一個序列,指明使用的排序演算法,寫出經過兩趟排序後的序列;另一個是給出原序列和n次排序後的序列,指出使用的排序演算法。另外,對常見的排序演算法的穩定性、時間複雜度的考察也涉及到了。

好了廢話不多說,進入今天的正題吧:兩道演算法題的解決思路課編碼實現

第一題:

題目描述:
木木一不小心不記得電腦的鎖屏密碼了,木木很著急,所以找到安安來解決,因為密碼是安安幫木木設定的。
設木木的密碼為B數列,安安的密碼為A數列,A,B數列的長度都為n,並滿足以下條件:
對於安安密碼中的第i個數Ai ,有:Ai = Bi − Bi 1    Bi 2 − Bi 3….Ai = B_i - B_{i 1}    B_{i 2} - B_{i 3}….
現在,知道安安的密碼,即A數列,求木木的密碼。

輸入
第一行輸入一個整數n,(2 ≤ n ≤ 100 000) ,代表密碼的長度。
接下來n行,每行輸入一個整數Ai,(按下標字典序輸入)代表安安的密碼,即A數列( -109 ≤ Ai≤ 109)。
輸出
輸出n行,每行一個整數,(按下標字典序輸出)代表木木的密碼,即B數列。

樣例輸入
5
3
-2
-1
5
6
樣例輸出
1
-3
4
11
6

題目給出了程式碼框架,我們只需要實現解決的方法solve();其實拿到題目第一眼會感覺比較複雜,又是加密又是數學表示式,很能唬人。但是經過深入的分析發現其實式子時可以整理的,整理後其實就是Bi={Ai Ai 1,Ai,if i<n if i=nB_i =
\begin{cases}
A_i A_{i 1}, & \text{if $i < n$ } \\
A_i, & \text{if $i = n$}
\end{cases} 
這樣就容易編碼為:

static int[] solve(int[] a) {
int [] res = new int[a.length];
//不用遞迴是因為遞迴的時間和空間複雜度較非遞迴大
for (int i = 0; i < res.length; i  ) {
if(i != res.length - 1 )
res[i] = a[i] a[i 1];
else
res[i] = a[i];
}
return res;
}

第二題:題目忘記copy了,憑記憶寫吧

大致意思是給定一個數n求小於等於n的“幸運數字”。幸運數字的定義:這個數只由4或者7組成,那麼稱此數字為幸運數字。
另外由於輸出可能很大,所以輸出的結果為幸運數字的個數除以108 710^8 7還是多少…記得不太清了
樣例輸入:
125
輸出:
6

這裡給出我的解決思路和程式碼,由於測試的時候有一個函式沒能實現完成,所以沒有全部AC。在結束測試後實現了該部分程式碼,自己進行測試可以通過,但是不知道在系統中會不會超時或者超出記憶體。
解決思路:

通過觀察規律,
0-10之內的數中,幸運數的個數是4、7即有兩個
10-100之內的數中,幸運數的個數是44、47、74、77既有四個


以此類推,我們不難發現n位數內的幸運數個數是2的n次排列組合即2n2^n個,那麼可以根據輸入的數字的位數n,先得到n-1位數以下有多少個幸運數,然後加上從最小的n位數即(444…)開始到n之間的幸運數個數。

到這裡,我們可以容易得到n位數中最小的幸運數是444…4,最大的幸運數是777…7,那麼我麼可以分情況討論:
當輸入的數字小於444..44那麼結果就是n-1位數以下幸運數的個數;當輸入的數字大於等於777…7那麼結果就是n位數下的幸運數個數;當輸入的數在444…4到777…7之間那麼就需要運算從444…4到n之間的幸運數個數了。

理清了思路就可以開始編碼了:
整體程式碼應該比較好理解

package timu2;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print(getLuckyNumCount(n));
}
//獲得幸運數字的個數
private static int getLuckyNumCount(int n) {
int numLength = getLength(n);
int count = numLength;
int result = 0;
int minLuckNum = getMinLuckNum(numLength);
int maxLuckNum = getMaxLuckNum(numLength);
if (n == minLuckNum) {
while (count > 1) {
result  = Math.pow(2, count - 1);
count--;
}
result  = 1;
} else if (n < minLuckNum) {
while (count > 1) {
result  = Math.pow(2, count - 1);
count--;
}
} else if (n >= maxLuckNum) {
while (count >= 1) {
result  = Math.pow(2, count);
count--;
}
} else if (n > minLuckNum && n < maxLuckNum) {
while (count > 1) {
result  = Math.pow(2, count - 1);
count--;
}
result  = getCount(n, numLength);
}
return result % (1000000000   7);
}
//獲得444..4到輸入的數字n之間的幸運數字的個數
private static int getCount(int n, int numLength) {
int result = 0;
for (int i = 444; i <= n; i  ) {
if (isLuckNum(i)) {
result  ;
}
}
return result;
}
//判斷是否為幸運數字
private static boolean isLuckNum(int i) {
String str = i   "";
char[] chs = str.toCharArray();
int a = 0;
int b = chs.length;
for (int j = 0; j < chs.length; j  ) {
if ((chs[j] "").matches("4|7"))
a  ;
}
return b == a;
}
//獲得n位數中最小的幸運數字
private static int getMinLuckNum(int numLength) {
StringBuilder sb = new StringBuilder();
while (numLength-- > 0) {
sb.append("4");
}
// System.out.println(sb);
return Integer.parseInt(sb.toString());
}
//獲得n位數最大的幸運數字
private static int getMaxLuckNum(int numLength) {
StringBuilder sb = new StringBuilder();
while (numLength-- > 0) {
sb.append("7");
}
// System.out.println(sb);
return Integer.parseInt(sb.toString());
}
//得到數字的位數
private static int getLength(int n) {
return (""   n).length();
}
}

以上就是我自己在做順豐科技的筆試題的時候的思路和編碼,也許不是最優解,也歡迎大家來批評指正~
這幾天被各大公司的筆試題程式設計題輪番虐,有點懷疑人生了…不過只要沒有停止學習,相信一切都會好的。找工作,繼續加油!!!

相關文章

程式語言 最新文章