溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這是我的第二個面試題匯總。想看之前的內容，請移步：
http://zhweizhi.blog.51cto.com/10800691/1763237
（若干數據結構 && 算法面試題【一】（更新完畢））
http://zhweizhi.blog.51cto.com/10800691/1787562
（若干數據結構 && 算法面試題【三】（更新中））
一、跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
f(n) = (最后一次跳一級臺階有多少種方法) + (最后一次跳兩級臺階有多少種方法)
即：
f(n) = f(n - 1) + f(n - 2)
class Solution
{
public:
int jumpFloor(int number)
{
if (number <= 1)
{
return number;
}
int first = 1;
int second = 1;
while (--number)
{
int tmp = second;
second += first;
first = tmp;
}
return second;
}
};完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/13_%E8%B7%B3%E5%8F%B0%E9%98%B6
二、變態跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
思路： 跳上n級臺階的方法 = (最后一次跳上一級) + (最后一次跳上兩級) + ...... + (最后一次跳上n級)
完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/14_%E5%8F%98%E6%80%81%E8%B7%B3%E5%8F%B0%E9%98%B6
三、矩形覆蓋
題目描述：
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/15_%E7%9F%A9%E5%BD%A2%E8%A6%86%E7%9B%96
四、二進制中1的個數
題目描述：
輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。
方法1：
int NumberOf1(int n)
{
int cur = 0x00000001;
int count = 0;
for (int i = 0; i < 32; i++)
{
if ( (n & cur) != 0)
{
count++;
}
cur = cur << 1;
}
return count;
}方法2（最佳）：
//最優解
int NumberOf1Best(int n)
{
int count = 0;
while (n != 0)
{
++count;
n = (n - 1) & n;
}
return count;
}
五、求數值的整數次方
題目描述：
給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。
完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/17_%E6%95%B0%E5%80%BC%E7%9A%84%E6%95%B4%E6%95%B0%E6%AC%A1%E6%96%B9
六、調整數組順序使奇數位于偶數前面
題目描述：
輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。
完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/18_%E8%B0%83%E6%95%B4%E6%95%B0%E7%BB%84%E9%A1%BA%E5%BA%8F%E4%BD%BF%E5%A5%87%E6%95%B0%E4%BD%8D%E4%BA%8E%E5%81%B6%E6%95%B0%E5%89%8D%E9%9D%A2
七、單鏈表的倒數第K個結點
通常有兩種思路：
1、用2個指針，一前一后，相距為k， 當前面的指針訪問到鏈表尾部時，另一個指針指向的就是倒數第K個結點。
2、遍歷一次，每次將訪問到的結點的地址壓入一個棧中，（為什么存放地址呢？因為如果元素的類型比較大，那么相比存放元素本身，開銷比較小）然后對這個棧進行彈出K - 1 次，這時棧頂的元素就是我們要的倒數第K個結點的地址。
思路都比較清晰，這里我采用的是第二種方法
完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/19_%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACk%E4%B8%AA%E7%BB%93%E7%82%B9
八、反轉單鏈表
思路：
遍歷，每次遍歷到的元素加到前一個元素的后面
完整代碼：
https://github.com/HonestFox/BrushQuestion/blob/master/20_%E5%8F%8D%E8%BD%AC%E5%8D%95%E9%93%BE%E8%A1%A8
八、合并有序單鏈表
代碼：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == NULL && pHead2 == NULL)
{
return NULL;
}
if (pHead1 == NULL)
{
return pHead2;
}
if (pHead2 == NULL)
{
return pHead1;
}
ListNode *cur1 = pHead1;
ListNode *cur2 = pHead2;
ListNode *NewNode = NULL;
if (cur1->val <= cur2->val)
{
NewNode = cur1;
cur1 = cur1->next;
}
else
{
NewNode = cur2;
cur2 = cur2->next;
}
ListNode *NewHead = NewNode;
while (cur1 != NULL && cur2 != NULL)
{
if (cur1->val <= cur2->val)
{
NewNode->next = cur1;
NewNode = NewNode->next;
cur1 = cur1->next;
}
else
{
NewNode->next = cur2;
NewNode = NewNode->next;
cur2 = cur2->next;
}
}
if (cur1 != NULL)
{
NewNode->next = cur1;
}
else if (cur2 != NULL)
{
NewNode->next = cur2;
}
return NewHead;
}github連接：（這次貼的代碼已經比較完整了）
https://github.com/HonestFox/BrushQuestion/blob/master/21_%E5%90%88%E5%B9%B6%E6%9C%89%E5%BA%8F%E5%8D%95%E9%93%BE%E8%A1%A8
（！兒童節快樂！）
九、二叉樹的鏡像
題目描述:
操作給定的二叉樹，將其變換為源二叉樹的鏡像。
輸入描述:
二叉樹的鏡像定義：源二叉樹
1
/ \
2 3
/ \ / \
4 5 6 7
鏡像二叉樹
1
/ \
3 2
/ \ / \
7 6 5 4
思路：
比較簡單，利用好遞歸的思想就好。
代碼：
void Mirror(TreeNode *pRoot)
{
if (pRoot == NULL)
{
return;
}
_Mirror(pRoot);
}
protected:
void _Mirror(TreeNode* pRoot)
{
if (pRoot == NULL)
{
return;
}
if (pRoot->left == NULL && pRoot->right == NULL)
{
return;
}
swap(pRoot->left, pRoot->right);
_Mirror(pRoot->left);
_Mirror(pRoot->right);
}github連接：
https://github.com/HonestFox/BrushQuestion/commit/8548f4e9704045be0ae0530a4c45a91b561c9281
十、順時針打印矩陣
題目描述:
輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字，
例如，如果輸入如下矩陣：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
則依次打印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
代碼：
vector<int> printMatrix(vector<vector<int> > matrix)
{
int max_line = matrix.size();
int max_col = matrix[0].size();
int size = max_line * max_col;
int count = 0;
int min_line = 0;
int min_col = 0;
int cur_line = 0;
int cur_col = 0;
vector<int> ret;
while (count < size)
{
//橫，從左向右
for (cur_col; cur_col < max_col; ++cur_col)
{
ret.push_back(matrix[cur_line][cur_col]);
count++;
}
cur_col = max_col - 1;
cur_line = min_line + 1;
min_line++;
//縱，從上到下
for (cur_line; cur_line < max_line; cur_line++)
{
ret.push_back(matrix[cur_line][cur_col]);
count++;
}
if (count >= size) //這里需要判斷一下
{
return ret;
}
cur_col = max_col - 2;
cur_line = max_line - 1;
max_col--;
//橫，從右到左
for (cur_col; cur_col >= min_col; cur_col--)
{
ret.push_back(matrix[cur_line][cur_col]);
count++;
}
cur_col = min_col;
cur_line = max_line - 2;
max_line--;
//縱，從下到上
for (cur_line; cur_line >= min_line; cur_line--)
{
ret.push_back(matrix[cur_line][cur_col]);
count++;
}
cur_col = min_col + 1;
cur_line = min_line;
min_col++;
}
return ret;
}github連接：
https://github.com/HonestFox/BrushQuestion/blob/master/24_%E9%A1%BA%E6%97%B6%E9%92%88%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5
十一、包含min函數的棧
題目描述:
定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。
（其實就是要求設計一個棧，能夠實現在O(1)時間復雜度內找到最小的元素）
思路：
必須包含兩個stack類型的成員變量：
其中一個存放數據(_Data)
另外一個存放最小的元素(_MinData)
新元素入棧時：
當_MinData為空，或新元素的值小于_MinData棧頂的元素時，將新元素入棧_MinData
出棧時：
當_MinData的棧頂元素是要出棧的元素是（即是_Data的棧頂元素時），
將該元素從_MinData彈出
這樣設計出來的棧，_MinData的棧頂元素始終是當前棧中存放的最小元素
代碼：
class Solution
{
public:
void push(int value)
{
_Data.push(value);
if (_MinData.empty() || value < _MinData.top())
{
_MinData.push(value);
}
}
void pop()
{
if (_Data.top() == _MinData.top())
{
_MinData.pop();
}
_Data.pop();
}
int top()
{
return _Data.top();
}
int min()
{
return _MinData.top();
}
protected:
stack<int> _Data;
stack<int> _MinData;
};github:
https://github.com/HonestFox/BrushQuestion/blob/master/25_%E5%8C%85%E5%90%ABmin%E5%87%BD%E6%95%B0%E7%9A%84%E6%A0%88
十二、從上到下訪問二叉樹（層序遍歷）
代碼：
vector<int> PrintFromTopToBottom(TreeNode *root)
{
vector<int> ret;
if (root == NULL)
{
return ret;
}
if (root->left == NULL && root->right == NULL)
{
cout << root->val << endl;
ret.push_back(root->val);
return ret;
}
vector<TreeNode*> box;
TreeNode *cur = root;
TreeNode *prev = cur;
while (ret.empty() || !box.empty())
{
if (!box.empty())
{
cur = box.front();
box.erase(box.begin());
}
cout << cur->val << " ";
ret.push_back(cur->val);
if (cur->left)
{
//cout << cur->left->val << " ";
box.push_back(cur->left);
}
if (cur->right)
{
//cout << cur->right->val << " ";
box.push_back(cur->right);
}
}
return ret;
}github：
https://github.com/HonestFox/BrushQuestion/blob/master/27_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86
十二、復雜鏈表的復制
題目描述：
輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點）。
代碼：
RandomListNode* Clone(RandomListNode* pHead)
{
if (pHead == NULL)
{
return NULL;
}
RandomListNode *cur = pHead;
while (cur)
{
RandomListNode *tmp = cur->next;
RandomListNode *NewNode = new RandomListNode(cur->label);
cur->next = NewNode;
NewNode->next = tmp;
cur = tmp;
}
cur = pHead;
while (cur)
{
RandomListNode *pos = cur->next;
if (cur->random)
{
pos->random = (cur->random)->next;
}
cur = pos->next;
}
cur = pHead;
RandomListNode *cur1 = cur->next;
RandomListNode *NewHead = cur1;
while (cur->next->next != NULL)
{
cur->next = cur->next->next;
cur = cur->next;
cur1->next = cur1->next->next;
cur1 = cur1->next;
}
return NewHead;
}github:
https://github.com/HonestFox/BrushQuestion/blob/master/28_%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6
十三、數組中出現次數超過一半的數據
題目描述：
數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。如果不存在則輸出0。
思路：
用哈希表的思想
代碼：
int MoreThanHalfNum_Solution(vector<int> numbers)
{
if (numbers.empty())
{
return 0;
}
int sz = numbers.size();
vector<int> HashList;
HashList.resize(numbers[0] + 1);
for (int i = 0; i < sz; ++i)
{
if (numbers[i] + 1 > HashList.size())
{
HashList.resize(numbers[i] + 1);
}
++HashList[numbers[i]];
if (HashList[numbers[i]] > sz / 2)
{
return numbers[i];
}
}
return 0;
}github：
https://github.com/HonestFox/BrushQuestion/blob/master/29_%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E6%AC%A1%E6%95%B0%E8%B6%85%E8%BF%87%E4%B8%80%E5%8D%8A%E7%9A%84%E6%95%B0%E5%AD%97
十四、最小的K個數
題目描述:
輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。
代碼：
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int> HashList;
vector<int> Ret;
if (k > input.size())
{
return Ret;
}
for (size_t i = 0; i < input.size(); ++i)
{
if (HashList.size() < input[i] + 1)
{
HashList.resize(input[i] + 1);
}
++HashList[input[i]];
}
for (size_t i = 0; i < HashList.size(); ++i)
{
while (HashList[i]--)
{
Ret.push_back(i);
k--;
if (k == 0)
{
return Ret;
}
}
}
return Ret;
}github：
https://github.com/HonestFox/BrushQuestion/blob/master/30_%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
