剑指offer题解c++版(一)

• 一，常见数据结构
  • 1，数组
  • 2，链表
  • 3，栈队列堆
  • 4，字符串
  • 5，哈希表
  • 6，二叉树
  • 7，图
• 二，算法
  • 1，递归
  • 2，二分查找
  • 3，排序
  • 4，贪心
  • 5，分治
  • 6，回溯
  • 7，动态规划

一，常见数据结构

1，数组

3-找出数组中重复的数字

剑指 Offer 03. 数组中重复的数字

解题方法：

1. 直接排序，然后遍历，思路很简单但是执行起来比较麻烦
2. 哈希表，就是找另一个数组，把nums的元素一个一个放进去，放进去之前判断里面有没有，如果里面已经有了那就遇到重复元素，结束。
3. 原地置换。思路是重头扫描数组，遇到下标为 i 的数字如果不是 i 的话（假设为m), 那么我们就拿与下标 m 的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回 ture。

C++代码：

class Solution {
private:
    void swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param numbers int整型vector 
     * @return int整型
     */
    // 哈希表法
    int duplicate(vector<int>& numbers) {
        // write code here
        multiset<int> set1;          
        for(auto i: numbers){
            set1.insert(i);
            if (set1.count(i) > 1)
                return i;
        }
        return -1;
    }
    // 原地置换法
    int findRepeatNumber(vector<int>& numbers) {
        int n = numbers.size();
        for(int i=0; i<n; i++){
            // 如果遇到下标i与nums[i]不一样，那么就要把这个nums[i]换到它应该去的下标下面
            if(numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]])  // 如果那么下标下面已经被占了，那么就找到了重复值，结束！
                    return numbers[i];
                else
                    swap(numbers[i],numbers[numbers[i]]);
            }
        }
        return 0;
    }
};

4-二维数组中的查找

剑指offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

• 给定 target = 5，返回 true。
• 给定 target = 20，返回 false。

c++ 代码如下：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0)
            return false;
        int rows = matrix.size();
        int cols = (*matrix.begin()).size();
        int r = 0, c = cols -1; // 从右上角开始
        while(r<=rows-1 && c >>0){
            if(target == matrix[r][c])
                return true;
            else if(target > matrix[r][c])
                r++;
            else
                c--;
        }
        return false;
    }
};

5-替换空格

剑指 offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

限制：0 <= s 的长度 <= 10000

解题方法：
题解：双指针法： p2 指针指向扩容之后的 string 最后一位，p1 指向原指针最后一位，遍历指针，如果 p1 遇到空格，就将 p2 向前移动三次并赋值为’%20’，没有，则将 p1 字符赋值给 p2 字符。

C++代码：

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        for(char& c:s){
            if(c == ' ') count++;
        }
        s.resize(len + 2*count);
        cout << count;
        for(int i = len-1, j=s.size()-1; i<j; i--,j--){
            if(s[i] == ' '){
                cout << s[i];
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2;
            }
            else{
                s[j] = s[i];
            }
        }
        return s;
    }
};

29-顺时针打印矩阵

剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 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 <= 100
• 0 <= matrix[i].length <= 100

解题方法：

从左到右，从上到下，检查一次是否遍历完，从右到左，从下到上

C++代码：

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        // left to right, top to bottom
        if(matrix.empty()) return {};
        vector<int> res;
        int l = 0, r = matrix[0].size()-1, t = 0, b = matrix.size()-1;
        int nums = (r+1) * (b+1);
        while(res.size() != nums){
            for(int i=l; i<=r; i++)  // 从左往右遍历：行索引不变，列索引增加
                res.push_back(matrix[t][i]);
            t++;
            for(int j=t; j<=b; j++)  // 从上到下遍历:列索引不变，行索引增加
                res.push_back(matrix[j][r]);
            r--;
            // 检查一次是否遍历完
            if(res.size() == nums)  break;
            for(int m=r; m>=l; m--)  // 从右往左遍历：行索引不变，列索引减少
                res.push_back(matrix[b][m]);
            b--;
            for(int n=b; n>=t; n--)  // 从下往上遍历：列索引不变，行索引减少
                res.push_back(matrix[n][l]);
            l++;            
        } 
        return res;
    }
};

leetcode 989-数组形式的整数加法

leetcode 989-数组形式的整数加法

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例 1：

输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：

输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455

限制：

1. 1 <= A.length <= 10000
2. 0 <= A[i] <= 9
3. 0 <= K <= 10000
4. 如果 A.length > 1，那么 A[0] != 0

解题方法：

两数相加形式的题目，可用以下加法公式模板。

当前位 = (A 的当前位 + B 的当前位 + 进位carry) % 10

while ( A 没完 || B 没完)
    A 的当前位
    B 的当前位

    和 = A 的当前位 + B 的当前位 + 进位carry

    当前位 = 和 % 10;
    进位 = 和 / 10;

判断是否还有进位

复杂度分析：

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

C++代码：

class Solution {
public: // 逐位相加法，使用加法模板
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int sum = 0;
        int carry = 0;
        int n = num.size()-1;
        vector<int> res;
        while(n >=0 || k != 0){
            int remainder = k % 10; // k 的当前位
            if(n>=0) sum = num[n] + remainder + carry;
            else sum = remainder + carry;
            carry = sum / 10;  // 进位计算
            sum %= 10;  // 当前位计算
            res.push_back(sum);
            k /= 10;
            n -= 1;
        }
        if(carry != 0) res.push_back(carry);  // 判断是否还有进位

        reverse(res.begin(), res.end());  // 反转数组
        return res;
    }
};

leetcode26-删除有序数组中的重复项

leetcode26-删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解题思路：

双指针：

1. 一个读指针、一个写指针遍历数组；
2. 遇到重复的元素，读指针继续前进，写指针不做操作；
3. 遇到不同的元素，写指针前进一步，并写入那个元素。

class Solution {
public:
    // 双指针法
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int r=0, w = 0;
        // int n = nums.size(); // 数组长度
        while(r < nums.size()){
            if(nums[r] != nums[w]){
                w++;
                nums[w] = nums[r];
            }
            r += 1;
        }
        return w+1;
    }
    int removeDuplicates2(vector<int>& nums) {
        if (nums.empty()) return 0;
        int duplicatedNum = nums[0];
        int j=0;
        for(int i=1;i<nums.size(); i++){
            if(duplicatedNum != nums[i]) {
                j += 1;
                nums[j] = nums[i];
                duplicatedNum = nums[i];
            }
        }
        return j+1;
    }
};

leetcode35-搜索插入位置

leetcode35-搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

解题方法：

二分查找法（非递归实现），查找结束如果没有相等值则返回 left，该值为插入位置

class Solution {
public:
    // 二分法+非递归实现
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while( low <= high){
            int mid = low+(high-low)/2; //mid = low+((high-low)>>1)
            // int mid = (low+high)/2;
            if( nums[mid] == target ) return mid;
            else if (target < nums[mid]) high = mid - 1;
            else low = mid + 1;
        }
        return low;
    }
};

2，链表

6-从尾到头打印单链表

剑指 offer 6: 从尾到头打印单链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：0 <= 链表长度 <= 10000

解题方法：

使用栈的思想(Python 用 list 模拟栈, pop 弹出栈头元素)，栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。注意和 C 语言不同，C++ 的结构体可以有构造函数！

C++代码：

class Solution{
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> values;  // 创建一个不包含任何元素的 stack 适配器，并采用默认的 deque 基础容器：
        vector<int> result;
        while (head != nullptr){
            values.push(head->val);
            head = head->next;
        }
        while(!values.empty()){
            result.push_back(values.top());
            values.pop();
        }
        return result;
    }
};

18.1-删除链表的节点

剑指 Offer 18.1 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。（注意：此题对比原题有改动）

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

解题思路：

1. 定位节点： 遍历链表，直到 head.val == val 时跳出，即可定位目标节点。
2. 修改引用： 设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。

C++代码：

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head -> next;
        ListNode* pre = head; ListNode* cur = head->next;
        while(cur != nullptr && cur->val != val) {
            pre = cur; 
            cur = cur->next;
        }
        pre->next = cur->next;
        return head;
    }
};

18.2 删除链表中重复的节点

剑指 Offer 18.2 删除链表中重复的节点

题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解题方法：

迭代解法

C++代码：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode *vhead = new ListNode(-1);
        vhead->next = head;
        ListNode* pre = vhead,*cur = head;
        while(cur){
            if(cur->next && cur->val==cur->next->val){
                cur = cur->next;
                while(cur->next && cur->val == cur->next->val){
                    cur = cur->next;
                }
                cur = cur -> next;
                pre->next = cur;
            }
            else{
                pre = cur;
                cur = cur->next;
            }
        }
        return vhead->next;
    }
};

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

剑指 Offer 22. 链表中倒数第k个节点

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

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

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

解题方法：

双指针法。不用统计链表长度。前指针 former 先向前走 k 步。

C++代码：

// 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* former = head;
        ListNode* latter = head;
        for(int i=0;i<k;i++){
            former = former->next;
        }
        while(former != NULL){
            former = former->next;
            latter = latter->next;
        }
        return latter;
    }
};

23-链表中环的入口结点

链表中环的入口结点

给一个长度为 n 的链表，若其中包含环，请找出该链表的环的入口结点，否则，返回 null。

• 输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表
• 返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点

示例1：

输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3   

解题思路：

采用双指针解法，一快一慢指针。快指针每次跑两个element，慢指针每次跑一个。如果存在一个圈，总有一天，快指针是能追上慢指针的。

C++代码：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        
        while( fast && fast->next) {  // 找到 fast 指针和 slow 指针相遇位置
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow ) break;
        }
        if (!fast || !fast->next) return nullptr;
        fast = pHead; // fast 指针指向头节点，slow 指针原地不变
        while(fast != slow ) {  // 两个指针重新相遇于环的入口点
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

24-反转一个单链表

剑指 offer 24: 反转一个单链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解题思路：

双指针迭代法。

C++代码：

class Solution {
public: // 双指针迭代法
    ListNode* reverseList(ListNode* head) {
         // 判断链表为空或长度为1的情况
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* pre = nullptr; // 当前节点的前一个节点
        ListNode* next = nullptr; // 当前节点的下一个节点
        while( head != nullptr){
            next = head->next; // 记录当前节点的下一个节点位置；
            head->next = pre; // 让当前节点指向前一个节点位置，完成反转
            pre = head; // pre 往右走
            head = next;// 当前节点往右继续走
        }
        return pre;
    }
};

52-两个链表的第一个公共节点

剑指 offer 52: 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

解题方法：

1，双指针法：设节点指针 A 指向头节点 headA, 节点指针 B 指向头节点 headB。

1. A 先遍历完链表 headA，然后遍历 headB;
2. B 先遍历完链表 headB，然后遍历 headA;

只要有公共节点，总路程数，或者说 A 经过的节点数和 B 经过的节点数是一样的，
如果没有公共节点，只有当 A 和 B都变成了 nullptr的时候，两者最终走的路程才是一样的。
然后只需比较 A和 B是否相等，相等的那个位置即为公共节点，因为此使，两者走的步数开始相等了。

2，栈特性解法。两个链表从公共结点开始后面都是一样的，顺着链表从后向前查找，很容易就能查找到链表的公共结点（第一个不相同的结点的下一个结点即所求）；而从后向前的特性自然联想到栈。

3，哈希表法。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

C++代码：

class Solution {
public:
    // 双指针法
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A =  headA;
        ListNode* B = headB;
        while(A != B){
            if(A != nullptr) A = A->next;
            else A = headB;
            if (B != nullptr) B = B->next;
            else B = headA;
        }
        return A;
    }
    // 哈希表法，哈希表中存储链表节点指针
    ListNode *getIntersectionNode2(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> visited;
        ListNode* temp = headA;
        while(temp != nullptr){
            visited.insert(temp);
            temp = temp -> next;
        }
        temp = headB;
        while(temp != nullptr){
            // count 方法判断哈希表中是否存在 temp 关键字
            if(visited.count(temp)) return temp;
            else temp = temp -> next;
        }
        return nullptr;
    }
    // vector 法，vector 中元素为链表节点指针
    ListNode *getIntersectionNode3(ListNode *headA, ListNode *headB) {
        vector<ListNode *> visited;
        ListNode* temp = headA;
        while(temp != nullptr){
            visited.push_back(temp);
            temp = temp -> next;
        }
        temp = headB;
        while(temp != nullptr){
            // find 函数查找 vector 中是否存在 temp 元素
            if(visited.end() != find(visited.begin(), visited.end(), temp)) return temp;
            else temp = temp -> next;
        }
        return nullptr;
    }
    // 栈特性解法
    ListNode *getIntersectionNode4(ListNode *headA, ListNode *headB) {
        ListNode *l1 = headA;
        ListNode *l2 = headB;
        stack<ListNode* > st1, st2;
        while(headA != nullptr){
            st1.push(headA);
            headA = headA->next;
        }
        while(headB != nullptr){
            st2.push(headB);
            headB = headB->next;
        }
        ListNode* ans = nullptr;
        while(!st1.empty()&&!st2.empty()&&st1.top()==st2.top()){
            ans = st1.top();
            st1.pop();
            st2.pop();
        }
        return ans;
    } 
};

leetcode 61-旋转链表

leetcode 61-旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例1

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

解题思路：

将原来的链表首尾相连变成环，然后找倒数第 k 个点作为新的表头，即原来的表头向右移动 (n-1)-(k%n) 次后断开。

C++代码：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* cur = head;
        int n = 1;
        while(cur -> next != nullptr){
            cur = cur -> next;
            n += 1;
        } 
        cur -> next = head; // 将链表首尾相连变成环
        cur = head;
        int move = (n-1)-(k % n);
        while(move--){
            cur = cur -> next;
        }
        ListNode* ret = cur -> next;
        cur -> next = nullptr; // cur 向右移动 move 次后，断掉连接
        return ret;
    }
};

leetcode 24-两两交换链表中的节点

leetcode 24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路：

1，迭代法：关键是高清如何交换两个相邻节点，然后迭代交换即可。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

C++代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr) return nullptr;
        else if(head->next == nullptr) return head;
        ListNode* temp = new ListNode(-1);
        temp ->next = head;
        ListNode* pre = temp;
        while(pre->next != nullptr && pre->next->next != nullptr) {

            ListNode* cur = pre->next;
            ListNode* next = pre->next->next;

            pre->next = cur->next;
            cur->next = next->next;
            next->next = cur;
            pre = cur;
        }
        return temp->next;
    }
};

leetcode876-链表的中间节点

leetcode 876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

解题方法:

1. 数组法。
2. 快慢指针法：用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。值得注意的是，快指针可以前进的前提是当前快指针和当前快指针的下一个节点非空。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};