前言：這是曾經(jīng)公司的筆試題，現(xiàn)在做起來仍很有意思正林，遂分享出來，感興趣的一起來挑戰(zhàn)吧颤殴！關于前公司觅廓，表示還真挺懷念的，相關內(nèi)容也曾經(jīng)發(fā)了一篇文章紀念程序員在簡書|Bye涵但，28樓的歲月
-
1.在最短的計算時間和最小的存儲空間限制下完成下面這函數(shù)：
void reverse_words(char *sentence)
//
// 輸入串: 一個以空格分隔的字符串杈绸，字符串中只包含英文字母和空格
// 輸出串: 一個與輸入完全顛倒的字符串帖蔓，但每個單詞保持原樣
//
// 例子:
//
// char test[]= "Now is the winter of our discontent made glorious summer by this son of York";
//
// reverse_words(test);
//
// printf(“%s\n”, test);
//
// 輸出結(jié)果:
//
// York of son this by summer glorious made discontent our of winter the is Now
注意事項：
- 比如說一個需要O(n)計算時間和O(1)存儲空間的算法要比一個需要O(n^2)計算時間和O(n)存儲空間的算法要好。
- 你可以用任何ANSI C庫里的字符串函數(shù)來解決問題瞳脓。
- 2.已知一個數(shù)據(jù)結(jié)構(gòu)：
struct s_node
{
struct s_node *next;
struct s_node *reference;
};
在最短的時間和最小的空間限制下完成下面這函數(shù)：
struct s_node *duplicate_list(struct s_node *list)
//
// 輸入: 一個單項鏈接的列表塑娇，每個節(jié)點都包含該鏈表中隨機的一個節(jié)點的引用
// 輸出: 一個輸入鏈表一摸一樣的鏈表，并且輸出鏈表中的任何一個節(jié)點都和輸入鏈表不相關
注意事項：
- 比如說一個需要O(n)計算時間和O(1存儲空間)空間的算法要比一個需要O(n^2)計算時間和O(n)存儲空間的算法要好劫侧。
- 你可以在計算過程中修改原始鏈表埋酬，只要你能在算法完成時恢復原始鏈表就好。
- 最終得到的鏈表必須符合鏈表原始的數(shù)據(jù)結(jié)構(gòu)定義烧栋，并且必須在一個與原始鏈表分離的內(nèi)存空間写妥。
- 3.寫一個函數(shù)來找到Boggle填字游戲中的所有單詞。
如果你不知道什么是Boggle审姓，你可以先baidu或者google一下珍特，他們會解釋得比我清楚，但我在這里還是以例子解釋下：
比如說一個3x3的Boggle表：
y o x
r b a
v e d
根據(jù)規(guī)則你可以把相鄰的字母在不重復的情況下串聯(lián)起來組成單詞魔吐，比如說：
bred, yore, byre, abed, oread, bore, orby, robed, broad, byroad, robe
bored, derby, bade, aero, read, orbed, verb, aery, bead, bread, very, road
但是robbed或者rober不在其中扎筒，因為他們需要重新用到Boggle表中的字母。board和dove也不在其中酬姆，因為他們需要不相鄰的字母嗜桌。
#define MAX_ROWS 3
#define MAX_COLUMNS 3
#define MAX_WORDS 27
#define MAX_WORD_LENGTH MAX_ROWS*MAX_COLUMNS
#define MIN_WORD_LENGTH 4
typedef struct
{
char letter[MAX_ROWS][MAX_COLUMNS];
}
BoggleBoard;
typedef struct
{
char *words[MAX_WORDS];
int numberOfWords;
}
Dictionary;
void BoggleSover(int rows, int columns, BoggleBoard *boggleBoard, char ** dictionary,Dictionary* answer)
- 4.分別列出數(shù)組(array)和鏈表(list)的優(yōu)缺點。
- 5.面向?qū)ο缶幊坛霈F(xiàn)之后辞色，繼承這種設計模式被越來越多的應用于軟件工程當中骨宠。但現(xiàn)在卻有人提出要少用繼承多用組合這種設計模式，這是為什么呢淫僻？
- 6.下面這個陳述是正確的嗎诱篷？為什么壶唤？
我們知道TCP是一種面向連接的雳灵、可靠的、基于字節(jié)流的傳輸層通信協(xié)議闸盔，所以每當傳輸層通過TCP協(xié)議向另一端發(fā)出一個包悯辙，另一端的傳輸層就一定會收到完整并且順序正確的包，要么就整包都沒有收到迎吵。
答案后續(xù)更新躲撰，也歡迎各位大神能夠?qū)⑵浯鸢杆叫呕蛟u論于下方，共同探討進步击费。
解答：
1.先翻轉(zhuǎn)整個字符串拢蛋，再將每個子字符串反轉(zhuǎn)
class Solution:
def reverseWords(self, s: str) -> str:
s = list(s)
n = len(s)
# 翻轉(zhuǎn)數(shù)組
def reverse(s, i, j):
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
# 翻轉(zhuǎn)單個單詞
def word_reverse(s):
# 用雙指針找到一個單詞
i = 0
j = 0
while i < n:
# 找到一個單詞首字母
while i < n and s[i] == " ":
i += 1
j = i
# 找到一個單詞末位置
while j < n and s[j] != " ":
j += 1
reverse(s, i, j - 1)
i = j
# 清除多余空格
def clean_space(s):
i = 0
j = 0
while j < n:
# 找到一個單詞
while j < n and s[j] == " ":
j += 1
# 單詞朝前移
while j < n and s[j] != " ":
s[i] = s[j]
i += 1
j += 1
# 移動下一個單詞
while j < n and s[j] == " ":
j += 1
if j < n:
s[i] = " "
i += 1
return "".join(s[:i])
reverse(s, 0, n - 1)
word_reverse(s)
return clean_space(s)