LeetCode+ 66 - 70 高精度、二分专题

加一

算法标签：数组、数学

  

给我们一个整数，这个整数是用一个数组来表示的，在这个整数的基础上加 1，加 1 之后还是用数组来表示，数组的最高位放到第 0 个位置，次高位放到第 1 个位置，假设这个数组是没有前导 0，其实就是给了一个很长的整数，模拟加法的过程

由于最高位可能会进位，所以需要先把数组翻转，要让个位在第 0 个位置，十位在第 1 个位置，从个位开始做，每次计算当前这一位的值是多少，看一下有没有进位，如果有进位就进一位

每一次当前位置上的数应该怎么计算呢？

个位上应该是原来位置上的数加上 1，再加上进位，加上 1 可以看成是前面进了一位，每一位的数字就可以看成是这一位原本的数字加上进位，进位可以是 0 也可以是 1，加上之后，当前位置的数就是这个数的和除以 10 的余数，进位就是这个数的和除以 10 的商

 快排、归并、浮点数二分、高精度加、减法_小雪菜本菜的博客-CSDN博客

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //翻转原数组
        reverse(digits.begin(),digits.end());
        //个位的进位是1
        int t = 1;
        //从前往后枚举每一位
        for(auto& x : digits) {
            t+= x;
            //当前位置
            x = t % 10;
            //下一位的进位
            t /= 10;
        }
        //如果最后有进位,就在最高位加上进位
        if(t) digits.push_back(t);
        //翻转数组
        reverse(digits.begin(),digits.end());
        return digits;
    }
};

二进制求和

算法标签：位运算、数学、字符串、模拟、高精度

在二进制的基础上列竖式，每一位上的数是第一个数的这一位和第二个数的这一位加上进位，进位可能是 0 可能是 1

从个位开始做，每次记录一下当前这个数的进位是多少

数据表示的时候高位在数组第一个位置，需要翻转一下，变成个位在数组第一个位置

class Solution {
public:
    string addBinary(string a, string b) {
        //翻转原数组
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
 
        //从前往后遍历 t 表示进位
        string c;
        for(int i = 0,t = 0;i < a.size() || i < b.size() || t;i++ ) {
            //当前这一位有数在总和里面加上这一位
            if(i < a.size()) t += a[i] - '0';
            if(i < b.size()) t += b[i] - '0';
            //当前位
            c += to_string(t % 2);
            //进位
            t /= 2;
        }
        //翻转结果数组
        reverse(c.begin(),c.end());
        return c;
    }
};

文本左右对齐

算法标签：数组、字符串、模拟

 

给了我们一堆单词，单词存储在 vector<string> 里面，要求对单词重新排版，使得单词左右对齐，每行总长度不能超过 maxWidth，每两个单词之间最少要用一个空格隔开

样例

样例 1 要求放这些单词，每行的长度不能超过 16

需要放顺序摆放，第一行可以放 3 个单词，如果放第 4 个单词就会越界，所以只能放 3 个单词，如果放 3 个单词需要让这个单词分布均匀，让相邻两个单词之间的空格数量尽可能均匀

某一行除了单词之外一共余下 t 个空格，但是一共只有 c 个间隙，每两个单词之间的间隙要分配 t / c 个空格，但是 t / c 不一定能除尽，如果不能除尽就让左边一半多一个，右边一半少一个

先给每个空隙分配 t / c 下取整的空格，余下 t % c 个空格，我们顺次从左边开始提供空格，一共提供 t % c 个空隙

一共有 11 个空格，有 3 个空隙，每一个空隙平均放 3 个空格，但是 11 / 3 不能除尽，最后余下两个空格怎么办呢？

需要顺次让左边多一个空格

最后得到第一个空隙有 4 个空格，第二个空隙有 4 个空格，第三个空隙有 3 个空格

接下来看一下如果要保证均匀需要怎么操作？

先看一行有多少个单词，然后看这一行有多少个空隙，看有多少个空余的位置，求每个空隙之间应该补多少个空格

特殊情况

文本的最后一行不需要左右对齐，全部移到最左边就可以了

例如最后一行剩下两个单词 a 和  b，最大长度是 100，我们只需要在两个单词之间放一个空格就可以了，不需要把 a 和 b 拉到两边

如果最大长度是 100，有一个单词的长度是 98，在这种情况下也需要左对齐，左边放单词，后面补两个空格

r 应该是 rest 的缩写，表示这一行（除了words) 剩下的字符（即空格），cnt 就是间隙数。第一个while循环就是处理空格多 1 的情况，例如，11个空格，3 个间隙，那么前两个间隙就是 4 个空格；第二个 while 循环就是不多一个空格，也就是例子中的第三个间隙只有 3 个空格

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        //定义答案
        vector<string> res;
        //从前往后枚举每一个单词
        for(int i = 0;i < words.size();i++ ) {
            //看当前这一行可以放哪些单词 j 从下一个单词开始看
            int j = i + 1;
            //当前这一行单词的长度
            int len = words[i].size();
            //当前长度加上空格加上下一个单词长度小于等于最大长度就可以放下一个单词   更新长度
            while(j < words.size() && len + 1 + words[j].size() <= maxWidth) len += 1 + words[j ++ ].size();
            //这样我们可以放的单词就是从 i ~ j - 1
            string line;
            //在最后一行应该是左对齐 一行只放一个单词也需要左对齐
            if(j == words.size() ||j == i + 1) {
                //左对齐需要把所有的单词用空格隔开
                //先加上第一个单词
                line += words[i];
                //把后面的单词分别添加到这一行的后面 每次添加的时候先加一个空格,再加入当前这个单词
                for(int k = i + 1;k < j;k++ ) line += ' ' + words[k];
                //当长度不足最大长度要在后面补上空格
                while(line.size() < maxWidth) line += ' ';
            } else {
                //第二种情况需要左右对齐
                //先求一共有多少个空隙 单词数量为 j - i,空隙数量 j - i - 1,5 个单词就会有 4 个空隙
                int cnt = j - i - 1;
                //当前一共有多少个剩余的空格可以使用 len包含了j-i个单词的总长度以及cnt个空隙 注意加上每个空隙里面包含的一个空格
                int  r = maxWidth - len + cnt;
                //先加上第一个单词
                line += words[i];
                //从第 0 个位置开始
                int k = 0;
                while (k < r % cnt) line += string(r / cnt + 1, ' ') + words[i + k + 1], k ++ ;
                while (k < cnt)     line += string(r / cnt, ' ') + words[i + k + 1], k ++ ;
 
            }
            //把这一行加到答案里面,同时更新 i
            res.push_back(line);
            //从 i ~ j - 1 已经用过了,需要把 i 更新成 j - 1
            i = j - 1;
        }
        return res;
    }
};

x 的平方根

算法标签：数组、二分查找

 

求 x 的平方根下取整的结果，找到一个最大的 y，使得 y^2 小于等于 x，由于 y^2 具有单调性所以可以二分

如果 mid^2 ≤ x，最大的平方小于等于 x 那个数应该是在 mid 的位置或者在 mid 右边，不可能在 mid 左边，否则答案一定在 mid 左边

class Solution {
public:
    int mySqrt(int x) {
        //定义二分的左右端点
        int l = 0,r = x;
        int mid;
        while(l < r)
        {
            //注意数据范围 
            mid = l + r + 1ll >> 1;
            //避免越界
            if(mid <= x / mid) l = mid; 
            else r = mid - 1;
        }
        return l; 
    }
};

爬楼梯

算法标签：记忆化搜索、数学、动态规划

要从 1 楼爬到 n 楼，每次可以爬一个或者爬两个台阶，问我们一共有多少种不同的方式爬到顶楼？

从 0 级台阶开始跳，跳到第三级台阶的方案有两种，最后一步跳一级和最后一步跳两级，从 2 跳过来有 2 种方案，从 1 跳过来有 1 种方案，一共有 3 种方案，可以发现每一个数都等于前两个数的和

可以发现求的其实是斐波那契数列第 n 项的值，可以用两个变量滚动

如果 n = 1，一次都不执行，如果 n = 2 执行一次，所以会执行 n - 1 次

b 一开始在 1 这个位置，如果想求第 n 项，要把 a 和 b 往后移动 n - 1 次

class Solution {
public:
    int climbStairs(int n) {
        int a = 1,b = 1;
        //执行 n - 1 次
        while(--n) {
            //计算
            int c = a + b;
            a = b,b = c;
        }
        return b;
    }
};