剑指offer题解

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

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

限制：
2 <= n <= 100000

解法

//#1
int findRepeatNumber(vector<int>& nums) {
    map<int,int> num_map;
    for (int i = 0; i < nums.size(); ++i) {
        if(num_map.find(nums[i]) != num_map.end()){
            return nums[i];
        }
        num_map[nums[i]]++;
    }
    return -1;
}
//#2
int findRepeatNumber(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    for(int i=1;i<nums.size();i++){
        if(nums[i-1] == nums[i]) return nums[i];
    }
    return -1;
}
//#3
int findRepeatNumber(vector<int>& nums) {
    int temp;
    for(int i=0;i<nums.size();i++){
        while (nums[i]!=i){
            if(nums[i]==nums[nums[i]]){
                return nums[i];
            }
            temp=nums[i];
            nums[i]=nums[temp];
            nums[temp]=temp;
        }
    }
    return -1;
}

2.在一个 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

解法

//#1
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    for (int i = 0; i < matrix.size(); ++i) {
        vector<int> list = matrix[i];
        int low = 0,high = list.size()-1,mid;
        while(low <= high){
            mid = (low+high)/2;
            if(list[mid] == target)
                return true;
            else if(list[mid] < target)
                low = mid+1;
            else
                high = mid-1;
        }
    }    
    return false; 
}    

1.从矩阵 matrix 左下角元素（索引设为 ($i, j$) ）开始遍历，并与目标值对比：
当 $matrix[i][j] > target$ 时，执行 $I—$ ，即消去第 $i$ 行元素；
当 $matrix[i][j] < target$ 时，执行 $j++$ ，即消去第 $j$ 列元素；
当 $matrix[i][j] = target$ 时，返回 true,代表找到目标值;

2.若行索引或列索引越界，则代表矩阵中无目标值，返回 false;

//#2
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    int i = matrix.size() - 1, j = 0;
    while(i >= 0 && j < matrix[0].size())
    {
        if(matrix[i][j] > target) i--;
        else if(matrix[i][j] < target) j++;
        else return true;
    }
    return false;
} 

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

示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：0 <= s 的长度 <= 10000

//#1
string replaceSpace(string s) {
    string array;
    for (auto& value : s) {
        if(value == ' '){
            array.push_back('%');
            array.push_back('2');
            array.push_back('0');
        }
        else array.push_back(value);
    }
    return array;
}

//#2
string replaceSpace(string s) {
    int count = 0, len = s.size();
    // 统计空格数量
    for (char c : s) {
        if (c == ' ') count++;
    }
    // 修改 s 长度
    s.resize(len + 2 * count);
    // 倒序遍历修改
    for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
        if (s[i] != ' ')
            s[j] = s[i];
        else {
            s[j - 2] = '%';
            s[j - 1] = '2';
            s[j] = '0';
            j -= 2;
        }
    }
    return s;
}

4.输入一个链表的头节点，从尾到头反过来返回每个节点的值.

//#1 递归法
vector<int> array;
vector<int> reversePrint(ListNode* head) {
    recur(head);
    return array;
}

void recur(ListNode* head){
    if(head == NULL){
        return;
    }
    recur(head->next);
    array.push_back(head->val);
}

//#2 辅助栈法
vector<int> array;
stack<int> stack;
vector<int> reversePrint(ListNode* head) {
    while(head != NULL){
        stack.push(head->val);
        head = head->next;
    }
    while(!stack.empty()){
        array.push_back(stack.top());
        stack.pop();
    }
    return array;
}