算法复健-第六天

昨天周末决定休息了一天

Math-Easy-增减字符串匹配

题面

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

• 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
• 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'

给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

示例 1：

输入：s = "IDID"
输出：[0,4,1,3,2]

示例 2：

输入：s = "III"
输出：[0,1,2,3]

示例 3：

输入：s = "DDI"
输出：[3,2,0,1]

提示：

• 1 <= s.length <= 10^5
• s 只包含字符 "I" 或 "D"

解答过程

本题采用贪心的思想，每次遇到I，则给这一位插入目前最小的数，每次遇到D，则给这一位插入目前最大的数，最后再加上剩下的那一个数就是答案

代码

vector<int> diStringMatch(string s) {
        vector<int> perm;
        int nmax = s.size(), nmin = 0;
        for (size_t i = 0; i < s.size(); i++)
        {
            if (s[i] == 'I')
            {
                perm.push_back(nmin);
                nmin++;
            }
            else if (s[i] == 'D')
            {
                perm.push_back(nmax);
                nmax--;
            }
        }
        perm.push_back(nmin);
        return perm;
    }

Math-Easy-数组形式的整数加法

题面

整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。

• 例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。

给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。

示例 1：

输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：

输入：num = [2,7,4], k = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：

输入：num = [2,1,5], k = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

提示：

• 1 <= num.length <= 10^4
• 0 <= num[i] <= 9
• num 不包含任何前导零，除了零本身
• 1 <= k <= 10^4

解答过程

本题除了一位一位相加模拟进位之外，也可以直接把加数加到最后一位上，然后再向前进位，也可以解决问题

代码

   vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> ans;
        int n = num.size();
        for (int i = n - 1; i >= 0 || k > 0; --i, k /= 10) {
            if (i >= 0) {
                k += num[i];
            }
            ans.push_back(k % 10);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }