二刷《剑指Offer》记录贴

到4月份了，打算开一个帖子记录一下《剑指Offer》学习笔记，顺便打败一下拖延症之类的......
要求：
1. 阅读书本，并使用MarkDown做笔记
2. 对于面试题，使用MarkDown进行记录（其他的也行，感觉MarkDown还是用不太习惯......）
3. 面试题的记录内容包括：

• 题目描述
• 解题思路（最好是自己的，如果不是的话那只能抄书本了）
• 代码（C++实现和Java实现）
• 难度排名（三颗星以上需要在5月份刷第三遍，总共5颗星。超出3颗星的星星数对应重刷的遍数）
  

4. 争取每天做点儿题.....怕被打脸，但还是希望每天三到六题。毕竟已经刷过一遍了。

我要向大伙证明，即使我这么笨，通过不断的重复我也能会做题！
我的代码能力一定会提高的！加油！

。。。。好心相劝，刷这个书的效果远不如刷leetcode。

555555菜鸡真的好难，但是我会加油的！

我这俩月刷了三遍 可能是因为我比较懒直接看最优解所以速度快吧。。

kingsighed 发表于 2020-4-14 23:25
我这俩月刷了三遍 可能是因为我比较懒直接看最优解所以速度快吧。。

好厉害呀！

https://blog.csdn.net/janeyane/article/details/105524250

????
C++的推荐书：
《Effective C++》
《C++ Primer》
《深度探索C++对象模型》
《The C++ Programming Language》

C#的推荐书：
《Professional C#》
《CLR Via C#》

Mark慢慢看吧
看C++好了，不看C#了本来学的也不咋地。

面试题03. 数组中重复的数字
题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：
2 或 3
限制：
2 <= n <= 100000

解题思路
1.        数组排序（纯暴力），时间复杂度O(nlogn)
2.        哈希，时间复杂度O(n)，空间复杂度O(n)（哈希表辅助）
3.        注意到数组中的数字是在0到n-1之间的，那么可以想一下，如果这个数组没有重复数字，那么排好序的数组中，i会出现在下标为i的位置。所以说，如果下标为i的位置的数字经过排序之后不是i，就说明出现了重复数字。
从头到尾依次扫描数组中的每个数字，当扫描到下标为i的数字时，首先比较这个数字m是不是等于i。如果相等则扫描下一个数字，否则将m和下标为m的数字进行比较，如果两者相等则找到了重复数字，如果不等，则把m和下标为m的数字交换，重复比较直到找到重复的数字。对于每个数字，最多只需要交换两次，因此总时间复杂度是O(n)。而且所有步骤都在输入的数组上进行，所以不需要额外分配内存，空间复杂度为O(1)。
这种方法也称作数组的“原地置换”。

C++版本
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int length = nums.size();
        if(length <= 0)
            return false;
        //这里书本写的很好，对异常进行了判断
        for(int i = 0; i < length; i++)
        {
            if(nums < 0 || nums >= length)
                return false;
        }
        //接下来开始循环比较
        for(int i = 0; i < length; i++)
        {
            //对于数组中的一个数来讲，经过最多两次交换一定可以交换到它对应的位置，因此不会是死循环
            while(nums != i)
            {
                //将m，也就是nums，与nums[m]，也就是nums[nums]做比较，如果相同则找到了重复数字
                if(nums == nums[nums])
                {
                    return nums;
                }
                //否则，交换两者的位置
                int t = nums;
                nums = nums[t];
                nums[t] = t;
            }
        }
        return false;
    }
};

Java版本
class Solution {
    public int findRepeatNumber(int[] nums) {
        if(nums.length <= 0)
            return -1;
        //同样还是需要判断异常情况
        for(int i = 0; i < nums.length; i++)
        {
            if(nums >= nums.length || nums < 0)
                return -1;
        }
        //原地置换
        for(int i = 0; i < nums.length; i++)
        {
            while(i != nums)
            {
                if(nums == nums[nums])
                {
                    return nums;
                }
                int t = nums;
                nums = nums[t];
                nums[t] = t;
            }
        }
        return -1;
    }
}

本题难度：✭✭✭

CSDN博客地址：https://blog.csdn.net/janeyane/article/details/105569251

wangdiao01 发表于 2020-4-17 03:28
。。。。好心相劝，刷这个书的效果远不如刷leetcode。

感谢您的劝导！
主要是我现在太懒了于是想先拿这本书来开刀</捂脸>

面试题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
解题思路
emmmmm这道题没啥好说的？可以暴力也可以取巧？好吧我把它归为取巧方法......
确实很巧妙啊，这个数组的数组元素每行每列都相对有序。
以下摘自《剑指Offer》：
首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除该数字所在的行。
C++版本
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0)
            return false;
        int rows = matrix.size();
        int columns = matrix[0].size();
        if(rows > 0 && columns > 0)
        {
            int row = 0;
            int column = columns - 1;
            while(row < rows && column >= 0)
            {
                if(matrix[row][column] == target)
                    return true;
                else if(matrix[row][column] > target)
                    column --;
                else
                    row ++;
            }
        }
        return false;
    }
};
Java版本
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length == 0)
            return false;
        int rows = matrix.length - 1;
        int cols = matrix[0].length;
        int row = 0;
        int col = cols - 1;
        while(row <= rows && col >= 0)
        {
            if(matrix[row][col] == target)
                return true;
            else if(matrix[row][col] > target)
                col --;
            else
                row ++;
        }
        return false;
    }
}
本题难度：★


CSDN链接：https://blog.csdn.net/janeyane/article/details/105591152