帝國國王科技大學上機題解（二）

1.找到字元串中出現次數最少的字元

題目描寫叙述

給定一個字元串（長度小于50）

找到該字元串出現次數最少的字元

假設有兩個字元出現次數同樣，并且均出現最少。那麼ASCII碼小的字元優先

輸入

輸入為一行字元串。不含空格

輸出

輸出出現次數最少的字元

例子輸入

rra3

333444abcd

例子輸出

3

a

解題思路：

先将字元串内部依據字元順序排序，然後周遊一遍。記錄出現次數最小的（假設有多個次數最小的。選排序在最前的）。

代碼：

2.歸并兩個已排序的數組（數組長度在1-20之間）。将其歸并成一個順序的數組

注意：在輸出時。最後一個數字後邊要列印一個空格

第一行給定測試用例的個數N。接下來兩行資料為一組，每行的第一個數是一個整數，表示的是該行數組的大小。

輸出每一個測試用例的結果。每行資料為一行。注意：在輸出時，最後一個數字後邊要列印一個空格

2

4 1 3 5 7

3 2 4 6

2 3 5

3 -1 2 3

1 2 3 4 5 6 7 

-1 2 3 3 5

用兩個指針周遊兩個數組。每次輸出小的。

3.推斷二叉樹的先序周遊序列

一種線性表示二叉樹的方式是使用先序周遊序列，假設遇到非空節點。我們記錄它的值，假設遇到空節點，我們用固定字元或者數字表示。比如用數字0表示

比如上邊這樣一顆二叉樹，其先序周遊序列為“9 3 4 0 0 1 0 0 2 0 6 0 0”，當中0表示空節點。給出一個線性序列，推斷這個序列是否為一個二叉樹的先序周遊序列。

序列中每一個非空節點的值均為非0整數，0表示空節點。節點之間用空格隔開，節點個數不超過20個

輸入一行序列。序列中每一個數字表示一個節點的值，非空節點的值均為非0整數，0代表空節點，節點之間用空格隔開，節點個數不超過20個。

假設該序列是一個二叉樹的先序周遊序列。輸出一行“True”,否則輸出“False”

9 3 4 0 0 1 0 0 2 0 6 0 0

1 0

9 0 0 1

True

False

首先一個二叉樹必須是葉子節點個數等于枝幹節點數+1。

即數組裡面0的個數等于非0個數+1。假設不滿足。直接輸出False。

然後依照先序建立二叉樹的方法。記錄建立二叉樹總共用的節點。

假設

1）建立二叉樹使用的節點數index等于數組裡數的個數n，

2）數組裡面0的個數等于非0個數+1。

那麼輸出True，否則輸出False。

4.最短路徑和

輸出一個大小為M×N的方格，每一個方格填滿了非負整數。找到一條從左上角到右下角的路徑，使得路徑經過的全部方格内的值相加和最小

1 2 3

1 1 1

比如如上方格，從左上角開始先向下走，再向右走。得到的路徑和最短。最短為1+1+1+1=4

注意：在随意時刻。你僅僅有向下移動或者向右移動。

輸入第一行為該方格的行數和列數。行數和列數不超過1000。

接着輸入數字矩陣

輸出最短路徑和

2 3

1 1

4

在随意時刻。你僅僅有向下移動或者向右移動。

不論什麼一個狀态僅僅能從上方或者左方得到。

用二維數組a存儲該方格。用dp[i][j]表示到達第i行第j列這個數的最小值。

1）dp[1][j]僅僅能從左方得到。dp[1][j]=dp[1][j-1]+a[1][j];

2)

dp[i][1]僅僅能從上方得到。dp[i][1]=dp[i-1][1]+a[i][1];

3) dp[i][j](i>1,j>1)能夠從左方和上方得到。狀态轉移方程為

dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) +a[i][j]

最後輸出dp[m][n]即為結果

5.找出一個缺失的正整數

描寫叙述

給定一個未排序的數組，找出一個缺失的正整數

比如

數組 1 2 0

有正整數1和2。缺失的第一個正整數是3

輸入為一個未排序的整數數組。數組長度不超過1000000

輸出為整數數組中第一個缺失的正整數

1 2 0

3 4 -1 1

把全部的正正整數都映射到map裡面。

然後從最小的正整數1開始找，假設沒有被映射。便輸出。然後結束。