[数据结构与算法]剑指Offer算法题（C++）

面试题1：整数除法

基础知识：整数的数据类型包括 32位int(-2^31 ~ 2^31 -1) ， 16位short?(-2^15?~ 2^15?-1)

思路：?

一个很直观的想法是基于减法实现除法。例如，为了求 19/2 可以从 19 中不断减去 2，那么减去 9 个 2 以后就剩下 1，可以得到 19/2 = 9，但是效率很低，当被除数是 n,除数是 1 的时候，算法复杂度最差为 O(n)。如果将上述解法做一些调整，当被除数大于除数时，继续判断是不是大于除数的 2 倍？ 4 倍？ 8 倍？....如果被除数大于除数的 2^k 倍，那么将被除数减去除数的 2^ k 倍，之后再重复以上步骤。

举个例子 19/2，19 大于 2，也大于 4 (2 * 2 ^ (1))，也大于 8 (2 * 2 ^ (2))，也大于 16 (2 * 2 ^ (3))，但是小于 32 (2 * 2 ^ (4))，于是将 19 - 16 得到 3，并记录此时的答案 8，此时被除数变为 3，除数还是 2，重复上述结果得到此时答案为 1，剩下被除数 1，已经小于 2，最终结果为 8 + 1 = 9。算法复杂度为 O(logn)。

基于被除数和除数都是正整数，如果存在负整数则可以将他们先转化为正整数进行计算，最后根据符号调整结果。但是对于 32 位 int 来讲，最大的正数为 2^31-1,最小的负数为 -2^31,如果将负数转化为正数会溢出，所以可以将正数都转化为负数计算，核心部分就是对两个负数进行除法，返回的结果可以用无符号数返回，最后进行正负号调整。另外所有的结果中存在一种情况无法用 int 表示结果，那就是被除数为 -2^31，除数为 -1，这时候直接特殊判断输出 INT_MAX 就行。

class Solution {
public:
    
    // 整数相除
    // 1: a 被除数  b 除数
    // 方法： 2的倍数法 
    int divide(int a, int b) {
        // 对于有符号整型 （-2^-31 ~ 2 ^ 31 -1 ） 要考虑边界问题
        if (a == INT_MIN && b == -1) {
            // -2^-31 / -1 = 2^31 -1
            return INT_MAX;
        }

        // 有符号类型正数的绝对值都小于负数,所以都转化为负数求解, 保证相除不会出现溢出
        // 需要记录被除数和除数的正负号
        int negative = 2;
        if (a > 0) {
            negative--;
            a = a * (-1);
        }
         
        if (b > 0) {
            negative--;
            b = b * (-1);
        }

        // 倍数二分法求相除的结果
        unsigned int ret = divideCore(a, b); // 注意一定要写成无符号的
        return negative == 1 ? -ret : ret; 
    }

    int divideCore(int& a, int& b) {
        int res = 0;
        // 除数大于被除数则返回0
        while (a <= b) {   // 注意这里是负数做比较
            int value = b; // value 表示当前的除数累加值
            unsigned int cur = 1; // 当前的倍数 注意一定要写成无符号的
            // 二分法 让被除数一直去二分比较
            while (value >= 0xc0000000 && a <= value + value) {
                cur += cur; // 倍数累加
                value += value; // 除数累加 
            }
            res += cur; // 能除几倍, 商就是几
            a -= value; // 被除数更新 （减去被除的数）
        }
        return res;
    }
};

面试题2： 二进制加法

思路： 从低位 按位求和，计算进位。之后字符串去反。

class Solution {
public:
    string addBinary(string a, string b) {
        // 模拟字符串相加,逢2进1
        string res;
        int cur_sum = 0; // 当前位求和值
        int flag = 0; // 进位标志位

        int m = a.size() - 1;
        int n = b.size() - 1;
        while (m >=0 || n >= 0) {
            cur_sum += flag;
            if (m >= 0) {
                cur_sum += a[m] - '0';
                m--;
            }

            if (n >= 0) {
                cur_sum += b[n] - '0';
                n--;
            }

            flag = cur_sum / 2; // 计算当前位的进位值
            res += (cur_sum % 2) + '0'; // 字符串追加
            cur_sum = 0; 
        }

        if (flag > 0) {
            res += (flag % 2) + '0'; // 字符串追加
        }

        reverse(res.begin(), res.end());  // 反转字符串
        return res; 

    }
};

3:?找出数组中重复的数字。

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

思路： hash

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> hash_map;
        for (int i = 0; i < nums.size(); i++) {
            hash_map[nums[i]]++;
            if (hash_map[nums[i]] >= 2)
                return nums[i];
        }
        return nums[nums.size() - 1];
    }
};

面试题4：二维数组中的查找

思路：从后往前看。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows == 0) return false;
        int cols = matrix[0].size();

        int i = 0;
        int j = cols - 1;
        while (i < rows && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j = j - 1; // 向前看一列
            } else {
                i = i + 1; // 向下看一行
            }
        }
        return false;
    }
};

空格替换：

class Solution {
public:
    string replaceSpace(string s) {
        if (s.empty()) 
            return "";

        string std = "%20";
        string res;
        int len = s.size();
        int i = 0;
        while(i < len) {
            if (s[i] != ' ') {
                res += s[i]; 
            } else  {
                res += std;
            }
            i++;
        }
        return res;
    }
};

5： 面试题5：?单词长度的最大乘积

#define max(a, b) ((a) > (b))? (a) : (b)
class Solution {
public:
    int maxProduct(vector<string>& words) {

        // 每个单词用一个掩码表示
        int lenghts = words.size();
        vector<int> mask(lenghts); // mask数组有length个元素

        // 临时存放当前单词 和 单词长度
        string tmp_words;
        int tmp_words_length;

        for (int i = 0; i < lenghts; i++) {
            tmp_words = words[i];
            tmp_words_length = tmp_words.size();
            // 
            for (int j = 0; j < tmp_words_length; j++) {
                // 计算每个单词的掩码
                // 掩码计算规则： 字符串每一位做左移自身的长度, 之后做或运算
                mask[i] |= 1 << (tmp_words[j] - 'a');
            }
        }

        // 两次遍历循环求解
       int max_words_len = 0;
        for (int i = 0; i < lenghts; i++) {
            for  (int j = i + 1; j < lenghts; j++) {
                // 两个单词的掩码进行与运算, 等于0则说明没有相同的元素
                if ((mask[i] & mask[j]) == 0) 
                    max_words_len = max(max_words_len, (words[i].size() * words[j].size()));
            }
        }

        return max_words_len;
    }
};

6： 面试题6?排序数组中两个数字之和

思路： 由于是排序好的数组，所以通过双指针，一个指向头，一个指向尾。通过和目标的比较移动指针，实现数组的遍历。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 因为是排序好的, 所以双指针, 一个从头, 一个从尾去遍历数组
        int  start = 0;
        int  end = numbers.size() - 1;
        int  cur = 0;
        vector<int> res;
        while (start < end) {
            cur = numbers[start] + numbers[end];
            if (cur == target) {
                res.push_back(start);
                res.push_back(end);
                break;
            } else if (cur < target) {
                start++; // 前移
            } else {
                end--; // 后移
            }
        }
        return res;
    }
};

7：??数组中和为 0 的三个数

思路： 先排序，后双指针找目标值。要去重。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 思路： 先排序, 这样就可以利用双指针去找目标值。由于是3个数, 先确定一个数，之后用双指针去确定后两个数
        vector<vector<int>> res;
        int start = 0;
        int end = nums.size() - 1;
        int target = 0;
        
        // 排序
        sort(nums.begin(), nums.end()); 

        for (int i = 0; i < nums.size(); i++) {
            target = -nums[i];
            // 去重
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            // 双指针找目标值
            start = i+ 1;
            end = nums.size() - 1;
            while (start < end) {
                if (nums[start] + nums[end] == target) {
                    res.push_back({nums[i], nums[start], nums[end]});
                    // 去重
                    while (start < end && nums[start] + nums[end] == target) {
                        start++;
                        continue;
                    }
                    while (start < end && nums[start] + nums[end] == target) {
                        end--;
                        continue;
                    }
                } else if (nums[start] + nums[end] < target) {
                    start++;
                } else {
                    end--;
                }
            }
        }

        return res;
    }
};