目錄
1--調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面（21）
2--鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)（22）
3--反轉(zhuǎn)鏈表（24）
4--合并兩個(gè)排序的鏈表（25）
5--樹的子結(jié)構(gòu)（26）
6--二叉樹的鏡像（27）
7--對(duì)稱的二叉樹（28）
8--順時(shí)針打印矩陣（29）
9--包含min函數(shù)的棧（30）
1--調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面（21）
主要思路：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-516799.html
????????雙指針?lè)?，左指針?0 開始遍歷，直到遇到偶數(shù)，右指針從 len - 1 開始遍歷，直到遇到奇數(shù)；
????????這時(shí)左指針指向偶數(shù)，右指針指向奇數(shù)，交換兩個(gè)指針的數(shù)值，并繼續(xù)判斷下一組數(shù)；
#include <iostream>
#include <vector>
class Solution {
public:
std::vector<int> exchange(std::vector<int>& nums) {
if (nums.empty()){
return nums;
}
int len = nums.size();
int l = 0;
int r = len - 1;
int temp;
while(l < r){
while(l < len && nums[l] % 2 != 0){ // 為奇數(shù)，直到遇到偶數(shù)
l++;
}
while(r > 0 && nums[r] % 2 == 0){ // 為偶數(shù)，直到遇到奇數(shù)
r--;
}
if(l == len || r == 0) break; // 防止全是奇數(shù)或者全是偶數(shù)，導(dǎo)致溢出
// 交換左右指針的數(shù)
if(l < r){
temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
// 交換后判斷下一組數(shù)
l++;
r--;
}
return nums;
}
};
int main(int argc, char *argv[]){
// std::vector<int> nums = {1, 2, 3, 4};
std::vector<int> nums = {1, 11, 14};
Solution s1;
s1.exchange(nums);
for(int item : nums){
std::cout << item << " ";
}
return 0;
}2--鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)（22）
?主要思路：
????????雙指針?lè)?，先讓右指針移?dòng)?k 步，接著左右指針同時(shí)移動(dòng)；
????????當(dāng)右指針指向 NULL 時(shí)，結(jié)束遍歷；由于左右指針的間距為k，則左指針指向原鏈表的倒數(shù)第 k 個(gè)節(jié)點(diǎn)，直接返回即可；
#include <iostream>
#include <vector>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *left = head;
ListNode *right = head;
for(int i = 0; i < k; i++){
right = right->next;
}
while(right != NULL){
left = left->next;
right = right->next;
}
return left;
}
};
int main(int argc, char *argv[]){
ListNode *Node1 = new ListNode(1);
ListNode *Node2 = new ListNode(2);
ListNode *Node3 = new ListNode(3);
ListNode *Node4 = new ListNode(4);
ListNode *Node5 = new ListNode(5);
Node1->next = Node2;
Node2->next = Node3;
Node3->next = Node4;
Node4->next = Node5;
int k = 2;
Solution s1;
ListNode* head = s1.getKthFromEnd(Node1, k);
while(head != NULL){
std::cout << head->val << std::endl;
head = head->next;
}
return 0;
}3--反轉(zhuǎn)鏈表（24）
主要思路：
????????想象成環(huán)形鏈表，反轉(zhuǎn)鏈表的實(shí)質(zhì)上結(jié)點(diǎn)指向上一個(gè)結(jié)點(diǎn)，則只需遍歷鏈表，將當(dāng)前結(jié)點(diǎn)指向上一個(gè)結(jié)點(diǎn)，不斷更新當(dāng)前結(jié)點(diǎn)和上一個(gè)結(jié)點(diǎn)即可；
#include <iostream>
#include <vector>
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; // 前一個(gè)結(jié)點(diǎn)初始化為 null
while(cur != NULL){
ListNode *tmp = cur->next; // 記錄下一個(gè)結(jié)點(diǎn)
cur->next = pre; // 當(dāng)前結(jié)點(diǎn)指向上一個(gè)結(jié)點(diǎn)
pre = cur; // 更新上一個(gè)結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)
cur = tmp; // 更新當(dāng)前結(jié)點(diǎn)為記錄的下一個(gè)結(jié)點(diǎn)
}
return pre;
}
};
int main(int argc, char *argv[]){
ListNode *Node1 = new ListNode(1);
ListNode *Node2 = new ListNode(2);
ListNode *Node3 = new ListNode(3);
ListNode *Node4 = new ListNode(4);
ListNode *Node5 = new ListNode(5);
Node1->next = Node2;
Node2->next = Node3;
Node3->next = Node4;
Node4->next = Node5;
Solution s1;
ListNode *head = s1.reverseList(Node1);
while(head != NULL){
std::cout << head->val << " ";
head = head->next;
}
return 0;
}4--合并兩個(gè)排序的鏈表（25）
主要思路：
? ? ? ? 逐個(gè)比較兩個(gè)鏈表的元素，歸并到新的鏈表中；
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *L = new ListNode(0);
ListNode *last = L;
ListNode *head1 = l1;
ListNode *head2 = l2;
while(head1 != NULL && head2 != NULL){
if(head1->val <= head2->val){
last->next = head1;
head1 = head1->next;
}
else{
last->next = head2;
head2 = head2->next;
}
last = last->next;
}
if(head1 == NULL) last->next = head2;
if(head2 == NULL) last->next = head1;
return L->next;
}
};
int main(int argc, char *argv[]){
ListNode *Node1 = new ListNode(1);
ListNode *Node2 = new ListNode(2);
ListNode *Node3 = new ListNode(4);
Node1->next = Node2;
Node2->next = Node3;
ListNode *Node4 = new ListNode(1);
ListNode *Node5 = new ListNode(3);
ListNode *Node6 = new ListNode(4);
Node4->next = Node5;
Node5->next = Node6;
Solution s1;
ListNode *L = s1.mergeTwoLists(Node1, Node4);
while(L != NULL){
std::cout << L->val << " ";
L = L->next;
}
return 0;
}5--樹的子結(jié)構(gòu)（26）
主要思路：
? ? ? ? B 是 A 的子結(jié)構(gòu)，則 B 的根節(jié)點(diǎn)必和 A 的某一個(gè)結(jié)點(diǎn)相同；
? ? ? ? 當(dāng)找到與 B 根節(jié)點(diǎn)相同的 A 結(jié)點(diǎn)后，需要遞歸判斷其左右子樹是否相同；
????????遞歸終止條件：B 為空，表明B的所有數(shù)據(jù)都判斷完畢，返回 true；A 為空 或 A 的值不等于 B 的值，返回 false；
#include <iostream>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A == NULL || B == NULL) return false;
// B 可能存在于 A 的左子樹或右子樹中
return dec(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool dec(TreeNode* A, TreeNode* B){
if(B == NULL){ // B 為空，表明B的所有數(shù)據(jù)都判斷完畢，返回 true
return true;
}
if(A == NULL || A->val != B->val){ // A 為空，或 A 的值不等于 B 的值，返回false
return false;
}
// A 的值等于 B 的值，還需判斷 A 的左子樹和 B 的左子樹，A 的右子樹和 B 的右子樹
return dec(A->left, B->left) && dec(A->right, B->right);
}
};
int main(int argc, char *argv[]){
TreeNode *Node1 = new TreeNode(3);
TreeNode *Node2 = new TreeNode(4);
TreeNode *Node3 = new TreeNode(5);
TreeNode *Node4 = new TreeNode(1);
TreeNode *Node5 = new TreeNode(2);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
TreeNode *Node6 = new TreeNode(4);
TreeNode *Node7 = new TreeNode(1);
Node6->left = Node7;
Solution s1;
bool res = s1.isSubStructure(Node1, Node6);
if (res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}6--二叉樹的鏡像（27）
主要思路：遞歸交換左右子樹，直到最底層回溯；
#include <iostream>
#include <queue>
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 root;
TreeNode *tmp = root->left;
root->left = mirrorTree(root->right);
root->right = mirrorTree(tmp);
return root;
}
};
int main(int argc, char *argv[]){
// root = [4,2,7,1,3,6,9]
TreeNode *Node1 = new TreeNode(4);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(7);
TreeNode *Node4 = new TreeNode(1);
TreeNode *Node5 = new TreeNode(3);
TreeNode *Node6 = new TreeNode(6);
TreeNode *Node7 = new TreeNode(9);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Solution s1;
TreeNode *Node = s1.mirrorTree(Node1);
// 廣度優(yōu)先遍歷
std::queue<TreeNode *> q;
TreeNode *tmp;
q.push(Node);
while(!q.empty()){
tmp = q.front();
std::cout << tmp->val << " ";
if(tmp->left != NULL){
q.push(tmp->left);
}
if(tmp->right != NULL){
q.push(tmp->right);
}
q.pop();
}
return 0;
}7--對(duì)稱的二叉樹（28）
主要思路：
????????遞歸判斷左子樹的左子樹與右子樹的右子樹是否相等，左子樹的右子樹與右子樹的左子樹是否相等；
#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == NULL) return true;
return compare(root->left, root->right);
}
bool compare(TreeNode* left, TreeNode* right){
if(left == NULL && right == NULL){
return true;
}
if(left == NULL && right != NULL or left != NULL && right == NULL){
return false;
}
if(left->val != right->val){
return false;
}
if(compare(left->left, right->right) && compare(left->right, right->left)){
return true;
}
return false;
}
};
int main(int argc, char *argv[]){
// 1,2,2,3,4,4,3
TreeNode *Node1 = new TreeNode(1);
TreeNode *Node2 = new TreeNode(2);
TreeNode *Node3 = new TreeNode(2);
TreeNode *Node4 = new TreeNode(3);
TreeNode *Node5 = new TreeNode(4);
TreeNode *Node6 = new TreeNode(4);
TreeNode *Node7 = new TreeNode(3);
Node1->left = Node2;
Node1->right = Node3;
Node2->left = Node4;
Node2->right = Node5;
Node3->left = Node6;
Node3->right = Node7;
Solution s1;
bool res = s1.isSymmetric(Node1);
if(res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}8--順時(shí)針打印矩陣（29）
????????用四個(gè)指針（本質(zhì)上還是雙指針?biāo)惴ǎ┲赶蚓仃嚨乃膫€(gè)邊界(left, top, right, bottom)，打印邊界后更新當(dāng)前邊界條件；
#include <iostream>
#include <vector>
class Solution {
public:
std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
std::vector<int> Res_V;
if (matrix.size() == 0) return Res_V;
int left = 0;
int top = 0;
int right = matrix[0].size() - 1;
int bottom = matrix.size() - 1;
while(true){
for(int i = left; i <= right; i++){
Res_V.push_back(matrix[top][i]);
}
if(++top > bottom) break; // 上邊界下移
for(int j = top; j <= bottom; j++){
Res_V.push_back(matrix[j][right]);
}
if(--right < left) break; // 右邊界左移
for(int i = right; i >= left; i--){
Res_V.push_back(matrix[bottom][i]);
}
if(--bottom < top) break; // 下邊界上移
for(int j = bottom; j >= top; j--){
Res_V.push_back(matrix[j][left]);
}
if(++left > right) break; // 左邊界右移
}
return Res_V;
}
};
int main(int argc, char *argv[]){
std::vector<std::vector<int>> matrix = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
Solution S1;
std::vector<int> Res_V = S1.spiralOrder(matrix);
for(int item : Res_V){
std::cout << item << " ";
}
return 0;
}9--包含min函數(shù)的棧（30）
主要思路：
? ? ? ? 使用兩個(gè)棧即主棧和輔棧，主棧用于存儲(chǔ)元素，輔棧用于存儲(chǔ)相同位置對(duì)應(yīng)的最小值；主棧和輔棧同進(jìn)同出，每次push新元素時(shí)，需要與當(dāng)前最小值進(jìn)行判斷，插入最小值到輔棧中；文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-516799.html
#include <iostream>
#include <stack>
class MinStack {
public:
MinStack() {
}
void push(int x) {
if (Main_stack.size() == 0){
Main_stack.push(x);
Aux_stack.push(x);
}
else{
Main_stack.push(x);
min_value = min();
if(x <= min_value) Aux_stack.push(x);
else Aux_stack.push(min_value);
}
}
void pop() {
Main_stack.pop();
Aux_stack.pop();
}
int top() {
return Main_stack.top();
}
int min() {
return Aux_stack.top();
}
private:
std::stack<int> Main_stack;
std::stack<int> Aux_stack;
int min_value;
};
int main(int argc, char *argv[]){
MinStack* obj = new MinStack();
obj->push(-2);
obj->push(0);
obj->push(-3);
int min_value = obj->min();
std::cout << "min_value: " << min_value << std::endl;
obj->pop();
int top_value = obj->top();
std::cout << "top_value: " << top_value << std::endl;
min_value = obj->min();
std::cout << "min_value: " << min_value << std::endl;
return 0;
}到了這里，關(guān)于劍指offer刷題筆記--Num21-30的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
