剑指offer刷题笔记--Num21-30

1年前作者：布吉岛呀~分类：Toy博客阅读(13)违法举报

这篇具有很好参考价值的文章主要介绍了剑指offer刷题笔记--Num21-30。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

1--调整数组顺序使奇数位于偶数前面（21）

2--链表中倒数第 k 个节点（22）

3--反转链表（24）

4--合并两个排序的链表（25）

5--树的子结构（26）

6--二叉树的镜像（27）

7--对称的二叉树（28）

8--顺时针打印矩阵（29）

9--包含min函数的栈（30）

1--调整数组顺序使奇数位于偶数前面（21）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

双指针法，左指针从 0 开始遍历，直到遇到偶数，右指针从 len - 1 开始遍历，直到遇到奇数；

这时左指针指向偶数，右指针指向奇数，交换两个指针的数值，并继续判断下一组数；

#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){ // 为奇数，直到遇到偶数
                l++;
            }
            while(r > 0 && nums[r] % 2 == 0){ // 为偶数，直到遇到奇数
                r--;
            }

            if(l == len || r == 0) break; // 防止全是奇数或者全是偶数，导致溢出

            // 交换左右指针的数
            if(l < r){
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
            // 交换后判断下一组数
            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--链表中倒数第 k 个节点（22）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

双指针法，先让右指针移动 k 步，接着左右指针同时移动；

当右指针指向 NULL 时，结束遍历；由于左右指针的间距为k，则左指针指向原链表的倒数第 k 个节点，直接返回即可；

#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--反转链表（24）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

想象成环形链表，反转链表的实质上结点指向上一个结点，则只需遍历链表，将当前结点指向上一个结点，不断更新当前结点和上一个结点即可；

#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; // 前一个结点初始化为 null
        while(cur != NULL){
            ListNode *tmp = cur->next; // 记录下一个结点
            cur->next = pre; // 当前结点指向上一个结点
            pre = cur; // 更新上一个结点为当前结点
            cur = tmp; // 更新当前结点为记录的下一个结点
        }
        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--合并两个排序的链表（25）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

逐个比较两个链表的元素，归并到新的链表中；

#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--树的子结构（26）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

B 是 A 的子结构，则 B 的根节点必和 A 的某一个结点相同；

当找到与 B 根节点相同的 A 结点后，需要递归判断其左右子树是否相同；

递归终止条件：B 为空，表明B的所有数据都判断完毕，返回 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的所有数据都判断完毕，返回 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）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：递归交换左右子树，直到最底层回溯；

#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);

    // 广度优先遍历
    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--对称的二叉树（28）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

递归判断左子树的左子树与右子树的右子树是否相等，左子树的右子树与右子树的左子树是否相等；

#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--顺时针打印矩阵（29）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

用四个指针（本质上还是双指针算法）指向矩阵的四个边界(left, top, right, bottom)，打印边界后更新当前边界条件；

#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函数的栈（30）

剑指offer刷题笔记--Num21-30,数据结构&LeetCode,leetcode,c++

主要思路：

使用两个栈即主栈和辅栈，主栈用于存储元素，辅栈用于存储相同位置对应的最小值；主栈和辅栈同进同出，每次push新元素时，需要与当前最小值进行判断，插入最小值到辅栈中；文章来源地址https://www.toymoban.com/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;
}

到了这里，关于剑指offer刷题笔记--Num21-30的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

《剑指offer》——刷题日记
本期，给大家带来的是《剑指offer》几道题目的讲解。希望对大家有所帮助！！！本文目录（一）JZ36 二叉搜索树与双向链表 1、题意分析 2、思路讲解 3、代码演示 4、最终结果（二）BM6 判断链表中是否有环 1、题意分析 2、思路讲解 3、代码演示 4、最终结果（三）JZ23 链
2023年04月21日
浏览(9)
【leetcode刷题】剑指offer基础版（完结）
剑指 Offer 05. 替换空格剑指 Offer 58 - II. 左旋转字符串剑指 Offer 67. 把字符串转换成整数❤️ 剑指 Offer 06. 从尾到头打印链表剑指 Offer 24. 反转链表剑指 Offer 35. 复杂链表的复制剑指 Offer 18. 删除链表的节点剑指 Offer 22. 链表中倒数第k个节点剑指 Offer 25. 合并两个排序的链表
2024年02月09日
浏览(9)
python_ACM模式《剑指offer刷题》链表1
询问面试官是否可以改变链表结构 1. 翻转链表，再遍历链表打印。 2. 想要实现先遍历后输出，即先进后出，因此可借助栈结构。 3. 可用隐式的栈结构，递归来实现。 1. 2. 3. 采用递归的思想注意是递归到最后一个元素才开始打印即要先写递归后写打印代码
2024年01月23日
浏览(5)
【leetcode刷题之路】剑指Offer（3）——搜索与回溯算法
7 搜索与回溯算法 7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树 https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/ 这里借助队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，所以可以考虑队列的先进先出，先把每一层的节
2024年02月13日
浏览(24)
【leetcode刷题之路】剑指Offer（4）——分治+排序算法+动态规划
8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/ 前序遍历是根左右，中序遍历是左根右，这也就意味着前序遍历的第一个节点是整棵树的根节点，顺着这个节点找到它在中序遍历中的位置，即为in_root，那么in_root左边的都在左子
2024年02月11日
浏览(13)
【剑指offer刷题记录 java版】数组双指针之滑动窗口
本系列文章记录labuladong的算法小抄中剑指offer题目题目链接：https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/ 题目链接：https://leetcode.cn/problems/MPnaiL/ 题目链接：https://leetcode.cn/problems/VabMRr/ 题目链接：https://leetcode.cn/problems/wtcaE1/ 题目链接：https://leetcode.cn/pr
2024年02月09日
浏览(12)
【剑指offer刷题记录 java版】数组双指针之其它题目
本系列文章记录labuladong的算法小抄中剑指offer题目题目链接：https://leetcode.cn/problems/XltzEq/ 题目链接：https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/ 题目链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/ 题目链接：https://leetcode.cn/problems/he-wei-sde-
2024年02月11日
浏览(9)
(排序) 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 ——【Leetcode每日一题】
难度：简单输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。示例：输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。提示： 0 = n u m s . l e n g t h = 50000 0 = nums.length = 50000 0 =
2024年02月12日
浏览(11)
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
各位CSDN的uu们你们好呀，今天继续数据结构与算法专栏中的二叉树，下面，让我们进入二叉树的世界吧！！！二叉树（上）——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客二叉树链式结构的实现二叉树链式结构的实现求二叉树的高度但是这种写法有很大的问题
2024年02月17日
浏览(13)
第8天-代码随想录刷题训练-字符串● 344.反转字符串 ● 541. 反转字符串II ● 剑指Offer 05.替换空格 ● 151.翻转字符串里的单词 ● 剑指Offer58-II.左旋转字符串
LeetCode链接编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 swap常见的两种交换形式常见的值交换通过位运算 LeetCode链接给定一个
2024年02月04日
浏览(10)