剑指offer打卡

今天预答辩被大佬虐了，再加上最近面试笔试题做的都不太好，所以刷一下题目吧

剑指03-06

03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        //利用数组作原地hash 
        for(int i = 0;i<nums.size();i++){
            while(i!=nums[i]){//
                if(nums[i]==nums[nums[i]])return nums[i];//两个下标对应的元素相同
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp; 
            }
        } 
        return -1;
    }
};

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。

限制：
0 <= n <= 1000
0 <= m <= 1000

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //从右上角观察 是一个二叉排序树的结构
        if(matrix.size()==0)return false;
        int row = 0;
        int col = matrix[0].size()-1;
        while(row<matrix.size()&&col>=0){
            if(matrix[row][col]<target)row++;
            else if(matrix[row][col]>target)col--;
            else return true;
        }
        return false;
    }
};

5. 替换空格

6.

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


    vector<int> reversePrint(ListNode* head) {
        head = reverse_node(head);
        vector<int> res;
        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        return res;
    }
};