当前位置：首页 > news >正文

8.3 字符串中等 306 Additive Number 423 Reconstruct Original Digits from English

news 来源：原创 2024/9/20 9:02:27

306 Additive Number

在这里插入图片描述

//累加数：除了前两个数，其余数都等于前两个加起来，至少包括三个数
//难点找到前两个数
//条件1：至少包括三个数–>确定前两个数字的最大长度 len = n/3 × 看下方注意1
//条件2：遇到0默认归属于他前面那个数字-------------》用于排除一些错误搭配isValid中的第一个条件语句
//主体：先分段再遍历-----------》先确定前两个数，再得到和，再进行比较
//难点：尝试所有可能的分段组合：分别尝试每种可能的前两个数字的长度组合，检查是否满足累加数的条件。

【默写】
注意1：确定前两个数字的长度，如果是123+1 = 124的情况，按照原思路：n = 7 n/3 = 2 但很明显是片面的。所以按照下方思路来：【积累】

在这里插入图片描述
注意2：题目中num.length 最大35 所以承载n1 n2两个数使用longlong类型。

class Solution {
public:bool isValid(const string& num , int len1 ,int len2){//条件2： 0不做开头 for num1 num2if((num[0] == '0' && len1 > 1 )|| (num[len1] == '0' && len2 > 1)){return false;}string num1 = num.substr(0, len1);string num2 = num.substr(len1,len2);string sum;//num最大长度35 所以int不得行long long n1 = stoll(num1) , n2 = stoll(num2);for(int start = len1+len2 ; start != num.size() ; start+=sum.size()){//斐波那契数列n2 = n1+n2;n1 = n2-n1;sum = to_string(n2);if((start + sum.size() > num.size())||(num.substr(start , sum.size())!=sum)){return false;}}return true;}bool isAdditiveNumber(string num) {int n = num.size();//条件1：确定前两个数的长度for(int i = 1 ; i <= n/2 ; i++){for(int j = 1 ; j <= (n-i)/2 ; j++){if(isValid(num , i , j)){return true;}}}return false;}
};

c++代码学习

string.substr(start,length);
取的是string中从start位置开始长度为length的子字符串。

423 Reconstruct Original Digits from English

在这里插入图片描述
读题：打乱顺序的字母串—>建立字母表，s is valid—>s刚好可以被全部用完，res需要按顺序输出数字
难点：找到每个数字对应的个数并顺序输出 —>核心还是思考s is valid—>s刚好可以被全部用完这个条件。
【原思路】建立字母表，顺序遍历0-9的字母表示，并保证第一个字母是该数字与其他数字的不同（但肯定会有重复的 one nine 就重复了两个字母），最后依次遍历下方这个num pair<string ,char>数组，找到每个数字的英文字母出现的最低频率min，按顺序append到res。
【规范思路】建立字母表，按下方思路建立<string,char>，很明显，按照下方顺序就不能顺序输出数字了，所以多增加一个Digitcount(10,0)用于记录每个数字的min值。主体：确定字母表内容，先遍历num pair数组确定min值输入到digitcount中，最后再遍历一遍digitcount并将数字顺序append到res字符串中。
~~太乱的话，看最下面的图片。~~
在这里插入图片描述

class Solution {
public:string originalDigits(string s) {vector<pair<string, char>> num = {{"zero", '0'}, {"two", '2'}, {"four", '4'}, {"six", '6'}, {"eight", '8'}, {"one", '1'}, {"three", '3'}, {"five", '5'}, {"seven", '7'}, {"nine", '9'}};vector<int> count(26, 0);vector<int> digitCount(10, 0);// 字母表的创建for (char ch : s) {count[ch - 'a']++;}// 遍历特殊标记数字的字母，确保数字顺序正确for (const auto &p : num) {string n = p.first;int min = INT_MAX;for (char ch : n) {min = min < count[ch - 'a'] ? min : count[ch - 'a'];}// 更新每个数字的出现次数digitCount[p.second - '0'] = min;// 更新 count 数组for (char ch : n) {count[ch - 'a'] -= min;}}string res = "";for (int i = 0; i < 10; ++i) {res.append(digitCount[i], '0' + i);}return res;}
};