劍指 Offer 21-30
難度簡單38收藏分享切換爲英文關注反饋
輸入一個整數陣列，實現一個函數來調整該陣列中數位的順序，使得所有奇數位於陣列的前半部分，所有偶數位於陣列的後半部分。
範例：
輸入：nums = [1,2,3,4]
輸出：[1,3,2,4]
注：[3,1,2,4] 也是正確的答案之一。
雙指針
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
//奇數在前，偶數在後
while(left<right){
if(left<right&&nums[left]%2==1) left++;
if(left<right&&nums[right]%2==0) right--;
swap(nums[left],nums[right]);
}
return nums;
}
};
難度簡單70收藏分享切換爲英文關注反饋
輸入一個鏈表，輸出該鏈表中倒數第k個節點。爲了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點。例如，一個鏈表有6個節點，從頭節點開始，它們的值依次是1、2、3、4、5、6。這個鏈表的倒數第3個節點是值爲4的節點。
範例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.
返回鏈表 4->5.
面試問題總結
無法高效獲取長度，無法根據偏移快速存取元素，是鏈表的兩個劣勢。然而面試的時候經常碰見諸如獲取倒數第k個元素，獲取中間位置的元素，判斷鏈表是否存在環，判斷環的長度等和長度與位置有關的問題。這些問題都可以通過靈活運用雙指針來解決。
先來看"倒數第k個元素的問題"。設有兩個指針 p 和 q，初始時均指向頭結點。首先，先讓 p 沿着 next 移動 k 次。此時，p 指向第 k+1個結點，q 指向頭節點，兩個指針的距離爲 k 。然後，同時移動 p 和 q，直到 p 指向空，此時 p 即指向倒數第 k 個結點。可以參考下圖來理解：
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *p = head, *q = head; //初始化
while(k--) { //將 p指針移動 k 次
p = p->next;
}
while(p != nullptr) {//同時移動，直到 p == nullptr
p = p->next;
q = q->next;
}
return q;
}
};
獲取中間元素的問題。設有兩個指針 fast 和 slow，初始時指向頭節點。每次移動時，fast向後走兩次，slow向後走一次，直到 fast 無法向後走兩次。這使得在每輪移動之後。fast 和 slow 的距離就會增加一。設鏈表有 n 個元素，那麼最多移動 n/2 輪。當 n 爲奇數時，slow 恰好指向中間結點，當 n 爲 偶數時，slow 恰好指向中間兩個結點的靠前一個(可以考慮下如何使其指向後一個結點呢？)。
下述程式碼實現了 n 爲偶數時慢指針指向靠後結點
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *p = head, *q = head;
while(q != nullptr && q->next != nullptr) {
p = p->next;
q = q->next->next;
}
return p;
}
};
總結快慢指針的特性 —— 每輪移動之後兩者的距離會加一。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while(fast != nullptr) {
fast = fast->next;
if(fast != nullptr) {
fast = fast->next;
}
if(fast == slow) {
return true;
}
slow = slow->next;
}
return nullptr;
}
};
如果存在環，如何判斷環的長度呢？方法是，快慢指針相遇後繼續移動，直到第二次相遇。
難度簡單82
定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表並輸出反轉後鏈表的頭節點。
範例:
輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL
限制：
0 <= 節點個數 <= 5000
反轉鏈表有很多，可以再記哦。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
/*
if(head==NULL) return head;
ListNode* cur=head;
ListNode* pre=NULL;
while(cur!=NULL){
ListNode* next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
*/
if(head==NULL) return head;
if(head->next == NULL) return head;
ListNode* last = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return last;
}
};
難度簡單39
輸入兩個遞增排序的鏈表，合併這兩個鏈表並使新鏈表中的節點仍然是遞增排序的。
範例1：
輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4
限制：
0 <= 鏈表長度 <= 1000
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l3=new ListNode(0);
ListNode* ans=l3;
while(l1!=NULL||l2!=NULL){
if(l1!=NULL&&l2!=NULL){
if(l1->val<l2->val){
l3->next=l1;
l1=l1->next;
}else{
l3->next=l2;
l2=l2->next;
}
}else if(l1!=NULL){
l3->next=l1;
l1=NULL;
}else{
l3->next=l2;
l2=NULL;
}
l3=l3->next;
}
return ans->next;
}
};
難度中等93
輸入兩棵二元樹A和B，判斷B是不是A的子結構。(約定空樹不是任意一個樹的子結構)
B是A的子結構， 即 A中有出現和B相同的結構和節點值。
例如:
給定的樹 A:
3
/ \
4 5
/ \
1 2
給定的樹 B：
4
/
1
返回 true，因爲 B 與 A 的一個子樹擁有相同的結構和節點值。
範例 1：
輸入：A = [1,2,3], B = [3,1] 輸出：false
範例 2：
輸入：A = [3,4,5,1,2], B = [4,1] 輸出：true
限制：
0 <= 節點個數 <= 10000
匹配類二元樹題目總結
面試題 04.10. 檢查子樹
求解思路可以分解爲以下兩步：
-
匹配根節點：首先在
A中找到與B的根節點匹配的節點C； -
匹配其他節點：驗證
C的子樹與B的子樹是否匹配。
dfs 函數將注意力集中在了根節點已經匹配的情況。當從根節點同時開始向下遍歷時
現在將視野放遠來看，主函數則解決了如何確定 A 的哪個節點是 B 的根節點。
//注意此處說了空樹不是子結構。
class Solution {
public:
//遍歷結點...
bool sameRootSub(TreeNode* t1,TreeNode* t2){
if(t2==NULL) return true;
if(t1==NULL) return false;
return t1->val==t2->val&&sameRootSub(t1->left,t2->left)&&sameRootSub(t1->right,t2->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A==NULL) return false;
if(B==NULL) return false;
return sameRootSub(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
};
難度簡單49收藏分享切換爲英文關注反饋
請完成一個函數，輸入一個二元樹，該函數輸出它的映象。
例如輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
映象輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
範例 1：
輸入：root = [4,2,7,1,3,6,9] 輸出：[4,7,2,9,6,3,1]
限制：
0 <= 節點個數 <= 1000
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root==NULL) return NULL;
if(root->left==NULL&&root->right==NULL) return root;
swap(root->left,root->right);
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
};
//或者用棧做or用佇列做
TreeNode* mirrorTree(TreeNode* root) {
if(root==NULL) return root;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* now=q.front();q.pop();
if(now->left!=NULL) q.push(now->left);
if(now->right!=NULL) q.push(now->right);
swap(now->left,now->right);
}
return root;
}
難度簡單65收藏分享切換爲英文關注反饋
請實現一個函數，用來判斷一棵二元樹是不是對稱的。如果一棵二元樹和它的映象一樣，那麼它是對稱的。
例如，二元樹 [1,2,2,3,4,4,3] 是對稱的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面 下麪這個 [1,2,2,null,3,null,3] 則不是映象對稱的:
1
/ \
2 2
\ \
3 3
範例 1：
輸入：root = [1,2,2,3,4,4,3] 輸出：true
範例 2：
輸入：root = [1,2,2,null,3,null,3] 輸出：false
class Solution {
public:
bool isSame(TreeNode* root1,TreeNode* root2){
if(root1==NULL&&root2==NULL) return true;
else if(root1==NULL||root2==NULL) return false;
else if(root1->val!=root2->val) return false;
return isSame(root1->right,root2->left)&&isSame(root1->left,root2->right);
}
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
else return isSame(root->left,root->right);
}
利用佇列進行迭代。佇列中每兩個連續的結點應該是相等的，而且它們的子樹互爲映象。最初，佇列中包含的是 root->left 以及 root->right。該演算法的工作原理類似於 BFS，但存在一些關鍵差異。每次提取兩個結點並比較它們的值。然後，將兩個結點的左右子結點按相反的順序插入佇列中。當佇列爲空時，或者檢測到樹不對稱（即從佇列中取出兩個不相等的連續結點）時，該演算法結束。
作者：bryceustc
鏈接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/cyu-pythonliang-chong-jie-fa-shi-xian-di-gui-yu-di/
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
// else return isSame(root->left,root->right);
queue<TreeNode*> q;
q.push(root->left);
q.push(root->right);
while(!q.empty()){
TreeNode* a=q.front();q.pop();
TreeNode* b=q.front();q.pop();
if(a==NULL&&b!=NULL||a!=NULL&&b==NULL) return false;
if(a!=NULL&&b!=NULL&&a->val!=b->val) return false;
if(a!=NULL&&b!=NULL){
q.push(a->left);q.push(b->right);
q.push(b->left);q.push(a->right);
}
}
return true;
}
難度簡單124收藏分享切換爲英文關注反饋
輸入一個矩陣，按照從外向裡以順時針的順序依次列印出每一個數字。
範例 1：
輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 輸出：[1,2,3,6,9,8,7,4,5]
範例 2：
輸入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 輸出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
（這很簡單嗎，我以爲中級模擬呢，PAT裡中級模擬）
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if(matrix.size()==0) return ans;
int x=0,y=0;
int n=matrix.size()-1,m=matrix[0].size()-1;
int n1=0,m1=0;
int cnt=0;
int sum=(n+1)*(m+1);
while(cnt<sum){
for(int i=m1;i<=m;i++){
ans.push_back(matrix[n1][i]);cnt++;
}
n1++;
if(cnt==sum) break;
for(int i=n1;i<=n;i++){
ans.push_back(matrix[i][m]);cnt++;
}
m--;
if(cnt==sum) break;
for(int i=m;i>=m1;i--){
ans.push_back(matrix[n][i]);cnt++;
}
n--;
if(cnt==sum) break;
for(int i=n;i>=n1;i--){
ans.push_back(matrix[i][m1]);cnt++;
}
m1++;
if(cnt==sum) break;
}
return ans;
}
難度簡單36
定義棧的數據結構，請在該型別中實現一個能夠得到棧的最小元素的 min 函數在該棧中，呼叫 min、push 及 pop 的時間複雜度都是 O(1)。
範例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
提示：
- 各函數的呼叫總次數不超過 20000 次
class MinStack {
public:
/** initialize your data structure here. */
stack<int> data,fu;
MinStack() {
fu.push(INT_MAX);
}
void push(int x) {
data.push(x);
if(fu.top()>x){
fu.push(x);
}else fu.push(fu.top());
}
void pop() {
data.pop();fu.pop();
}
int top() {
return data.top();
}
int min() {
return fu.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
解決方案
WHEN PUSH：儲存最小值資訊。每次 push 都將當前值與 minVal 比較，若不大於，則首先將 minVal 入棧，然後 push；否則，直接 push.
需要取不大於，而不是小於，是由第 2 點決定的
WHEN POP：回溯最小值資訊。每次 pop 都將返回值與 minVal 比較，若等於則再次 pop，這時的值爲最小值的回溯值（回溯值可能與 minVal 相等），將 minVal 更新爲該值.
作者：xi-lin
鏈接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/shuang-zhan-orzeng-qiang-xing-dan-zhan-by-xi-lin/
如果當前壓入的值比當前最小值小，則壓入一個當前最小值，再壓入當前的值！
class MinStack {
public:
/** initialize your data structure here. */
stack<int> data;
int minx=INT_MAX;
MinStack() {
}
void push(int x) {
//請注意是小於等於。
if(x<=minx){
data.push(minx);
minx=x;
}
data.push(x);
}
void pop() {
if(data.top()==minx){
data.pop();
minx=data.top();
}
data.pop();
}
int top() {
return data.top();
}
int min() {
return minx;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/