2022-11-09

字数统计: 4.6k字 | 阅读时长: 22分

剑指offer-2

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* pre = head;
        ListNode* cur = head;
        while(k != 0) {
            cur = cur->next;
            k--;
        }
        while(cur != NULL) {
            pre = pre->next;
            cur = cur->next;
        }
        return pre;
    }
};

剑指 Offer 24. 反转链表 - 力扣（LeetCode）

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

/**
 * 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) {
        ListNode* dummynode = NULL;
        ListNode* pre = dummynode;
        ListNode* cur = head;
        while(cur != NULL) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

/**
 * 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) {
        if(l1 == NULL) {
            return l2;
        }
        if(l2 == NULL) {
            return l1;
        }
        ListNode* dummynode = new ListNode(0);
        ListNode* cur = dummynode;
        while(l1 != NULL || l2 != NULL) {
            if(l1 != NULL && l2 != NULL) {
                if(l1->val < l2->val) {
                    cur->next = new ListNode(l1->val);
                    cur = cur->next;
                    l1 = l1->next;
                }
                else {
                    cur->next = new ListNode(l2->val);
                    cur = cur->next;
                    l2 = l2->next;
                }
            }
            if(l1 == NULL && l2 != NULL) {
                cur->next = new ListNode(l2->val);
                cur = cur->next;
                l2 = l2->next;
            }
            if(l2 == NULL && l1 != NULL) {
                cur->next = new ListNode(l1->val);
                cur = cur->next;
                l1 = l1->next;
            }
        }
        return dummynode->next;
    }
};

剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode）

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

/**
 * 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;
        }
        TreeNode* left = mirrorTree(root->right);
        TreeNode* right = mirrorTree(root->left);
        root->left = left;
        root->right = right;
        return root;
    }
};

剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode）

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

递归的思想，一层一层的遍历

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) {
            return true;
        }
        else {
            return compare(root->left, root->right);
        }
    }
    bool compare(TreeNode* left, TreeNode* right) {
        if(left == NULL && right == NULL) {
            return true;
        }
        if(left == NULL || right == NULL || left->val != right->val) {
            return false;
        }
        return compare(left->left, right->right) && compare(left->right, right->left);
    }
};

剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

st1进行正常的栈逻辑，st2维护栈中最小的元素，将其放在栈顶。

class MinStack {
public:
    /** initialize your data structure here. */
    stack <int> st1;
    stack <int> st2;
    MinStack() {
        st2.push(INT_MAX);
    }
    
    void push(int x) {
        st1.push(x);
        if(x <= st2.top()) {
            st2.push(x);
        }
    }
    
    void pop() {
        if(st1.top() == st2.top()) {
            st2.pop();
        }
        st1.pop();
    }
    
    int top() {
        return st1.top();
    }
    
    int min() {
        return st2.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();
 */

剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode）

实际上就是层序遍历，层序遍历用队列比较合理

/**
 * 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:
    vector<int> levelOrder(TreeNode* root) {
        vector <int> result;
        queue <TreeNode*> que;
        if(root != NULL)
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode * node = que.front();
                que.pop();
                result.push_back(node->val);
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
        }
        return result;		//result存的是每一层的数据
    }
};

剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）

也是层序遍历，就是输出到二维数组中，而不是一个vector中。

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> result;
        queue <TreeNode*> que;
        if(root != NULL)
        que.push(root);
        while(!que.empty())
        {
            vector <int> vec;
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode * node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;		//result存的是每一层的数据
    }
};

剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode）

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

在上一个题的基础上增加一个reverse函数判断

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> result;
        queue <TreeNode*> que;
        if(root != NULL)
        que.push(root);
        while(!que.empty())
        {
            vector <int> vec;
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode * node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
            if(result.size() % 2 == 1) {
                reverse(vec.begin(), vec.end());
            }
            result.push_back(vec);
        }
        return result;		//result存的是每一层的数据
    }
};

剑指 Offer 26. 树的子结构 - 力扣（LeetCode）

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

/**
 * 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:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(B == NULL || A == NULL) {
            return false;
        }
        return iscontain(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);        //递归根节点，左子树和右子树
    }
    bool iscontain(TreeNode* A, TreeNode* B) {
        if(B == NULL) {
            return true;
        }
        if(A == NULL || A->val != B->val) {
            return false;
        }
        return iscontain(A->left, B->left) && iscontain(A->right, B->right);
    }
};

剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

可以用一个栈来模拟压入和弹出，如果最后栈为空就说明栈可以实现，

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size() == 0) {
            return true;
        }
        stack <int> st;
        int j = 0; //记录popped数组的下标
        for(int i = 0; i < pushed.size(); i++) {
            st.push(pushed[i]);
            while(!st.empty() && st.top() == popped[j]) {   //必须加上!st.empty()，否则当st为空时取st.top()会出错
                st.pop();
                j++;
            }
        }
        if(st.empty()) {
            return true;
        }
        return false;
    }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（LeetCode）

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        
        return verifyorder(postorder, 0, postorder.size() - 1);
    }
    bool verifyorder(vector<int>& postorder, int l, int r) {        //r对应根节点
        if(l >= r) {
            return true;
        }
        int i;
        for(i = r; i >= l; i--) {
            if(postorder[i] < postorder[r]) {   //i及其左边都是左子树的元素
                break;
            }
        }
        for(int j = i; j >= l; j--) {	//判断二叉搜索树的左子树应该都小于根节点，不符合则返回假
            if(postorder[j] > postorder[r]) {
                return false;
            }
        }
        return verifyorder(postorder, l, i) && verifyorder(postorder, i + 1, r - 1);	//递归的检查左子树和右子树
    }
};

剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode）

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

本题是回溯的思想，主要包括先序遍历和路径记录两步。

先序遍历：按照 “根、左、右” 的顺序，遍历树的所有节点。
路径记录：在先序遍历中，记录从根节点到当前节点的路径。当路径为根节点到叶节点形成的路径，且各节点值的和等于目标值 sum 时，将此路径加入结果列表。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector <vector<int>> result;
    vector <int> path;
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        recur(root, target);
        return result;
    }
    void recur(TreeNode* root, int target) {
        if(root == NULL) {
            return;
        }
        path.push_back(root->val);
        target = target - root->val;
        if(target == 0 && root->left == NULL && root->right == NULL) {
            result.push_back(path);
        }
        recur(root->left, target);
        recur(root->right, target);
        path.pop_back();
    }
};

剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

因为不知道random指针具体指向的是哪个元素，因此不能直接遍历复制，而是需要建立哈希表进行映射。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) {
            return NULL;
        }
        unordered_map <Node*, Node*> map;
        Node* cur = head;
        while(cur != NULL) {
            map[cur] = new Node(cur->val);      //先把值拷贝过来
            cur = cur->next;
        }
        cur = head;
        while(cur != NULL) {
            map[cur]->next = map[cur->next];        //map[cur]->next是复制后的next节点，map[cur->next]是复制前的next节点
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];
    }
};

剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode）

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

dfs函数进行中序遍历，左中右。pre和cur指针记录链表节点并进行双向连接。最后将头尾节点连接形成环形链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node *pre, *head;
    void dfs(Node* cur) {       //中序遍历，左中右
        if(cur == NULL) {
            return;
        }
        dfs(cur->left);
        if(pre != NULL) {
            pre->right = cur;
        }
        else {
            head = cur;
        }
        cur->left = pre;
        pre = cur;
        dfs(cur->right);
    }
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return nullptr;
        dfs(root);
        head->left = pre;       //将头尾连接，变成双向链表
        pre->right = head;
        return head;
    }
};

剑指 Offer 37. 序列化二叉树 - 力扣（LeetCode）

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if ( root == nullptr ) return "";       //返回空字符串
        ostringstream output;
        queue<TreeNode*> que;
        que.push(root);
        while ( !que.empty() ) {		//层序遍历
            TreeNode* node = que.front();
            que.pop();
            if ( node == nullptr ) output << "# ";
            else {
                output << node->val << ' ';
                que.push(node->left);
                que.push(node->right);
            }
        }
        return output.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if ( data.empty() ) return nullptr;
        vector<TreeNode*> nodes;
        string val;
        istringstream input(data);
        while ( input >> val ) {    //没遇到一个空格会断开
            if ( val == "#" ) nodes.push_back(nullptr);
            else nodes.push_back(new TreeNode(stoi(val)));
        };
        int pos = 1;
        for ( int i = 0; i < nodes.size(); ++i ) {
            if ( nodes[i] == nullptr ) continue;
            nodes[i]->left = nodes[pos++];
            nodes[i]->right = nodes[pos++];
        }
        return nodes[0];
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode）

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

class Solution {
public:
    vector<string> permutation(string s) {
        dfs(s, 0);
        return res;
    }
private:
    vector<string> res;
    void dfs(string s, int x) {
        if(x == s.size() - 1) {
            res.push_back(s);                       // 添加排列方案
            return;
        }
        set<int> st;    //用set记录使用的元素，进行剪枝
        for(int i = x; i < s.size(); i++) {
            if(st.find(s[i]) != st.end()) continue; // 重复，因此剪枝
            st.insert(s[i]);
            swap(s[i], s[x]);                       // 交换，将 s[i] 固定在第 x 位
            dfs(s, x + 1);                          // 开启固定第 x + 1 位字符
            swap(s[i], s[x]);                       // 恢复交换
        }
    }
};

剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode）

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map <int, int> map;   //分别对应数字和其出现的次数
        for(int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
            if(map[nums[i]] > nums.size() / 2) {
                return nums[i];
            }
        }
        return 0;
    }
};

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector <int> result;
        sort(arr.begin(), arr.end());
        for(int i = 0; i < k; i++) {
            result.push_back(arr[i]);
        }
        return result;
    }
};

剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode）

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

方法一：暴力法，会超时

class MedianFinder {
private:
    vector <double> nums;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        nums.push_back(num);
    }
    
    double findMedian() {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(n == 0) {
            return 0;
        }
        if(n % 2 == 1) {
            return nums[n / 2];
        }
        else return (nums[n / 2 - 1] + nums[n / 2]) / 2;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

方法二：使用优先队列

class MedianFinder {
public:
    // 最大堆，存储小的一半的数据，左边堆，堆顶为最大值，对应上图中的b
    priority_queue<int, vector<int>, less<int>> maxHeap;
    // 最小堆，存储大的一半的数据，右边堆，堆顶为最小值，对应上图中的a
    priority_queue<int, vector<int>, greater<int>> minHeap;	//greater就是队内元素越来越大，队口的最小
    /** initialize your data structure here. */
    MedianFinder() {
    }

    // 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
    void addNum(int num) {
        /*
         * 当两堆的数据个数相等时候，左边堆，最大堆添加元素。
         * 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
         * 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
         * 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
         */
        if (maxHeap.size() == minHeap.size()) {
            minHeap.push(num);
            int top = minHeap.top();
            minHeap.pop();
            maxHeap.push(top);
        } else {
            maxHeap.push(num);
            int top = maxHeap.top();
            maxHeap.pop();
            minHeap.push(top);
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top()+minHeap.top())*1.0/2;
        } else {
            return maxHeap.top()*1.0;
        }
    }
};

剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

动态规划，dp[i]指的是i之前的子数组最大和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector <int> dp(nums.size() , 0);
        dp[0] = nums[0];
        int result = dp[0];
        for(int i = 1; i < nums.size(); i++)
        {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if(dp[i] > result)
            result = dp[i];
        }
        return result;
    }
};