讨论/题目交流/🐱 第 24 场夜喵双周赛/
🐱 第 24 场夜喵双周赛
展开讨论

逐步求和得到正数的最小值

思路

  1. 首先阅读理解
  2. 题目的意思是,找一个开始值,然后以这个值开始加数组中的每一个数,中间每一步都要大于 1
  3. 加每一个数就是前缀和
  4. 如果要每一步都大于 1 ,只需要找到前缀和中最小的值

答题

    int minStartValue(vector<int>& nums) 
    {
        vector<int> a;
        partial_sum(nums.begin(), nums.end(), back_inserter(a));
        int ans = *min_element(a.begin(), a.end());
        return ans <= 0 ? 1 - ans : 1;
    }

和为 K 的最少斐波那契数字数目

思路

  1. 求出小于 K 的所有斐波那契数字
  2. 因为斐波那契的特点,Fn = Fn-1 + Fn-2 ,即每一个数都是前面两个数加起来的
  3. (所以感觉可以贪心,没时间证明了,先上车吧)
  4. 从后往前贪心选择数字

答题

    int findMinFibonacciNumbers(int k) 
    {
        vector<int> f(2, 1);
        while (f.back() < k)
        {
            f.push_back(f[f.size() - 2] + f[f.size() - 1]);
        }
        if (f.back() == k) return 1;
        int ans = 0;
        for (int i = f.size() - 1; i >= 0; i--)
        {
            if (k < f[i]) continue;
            k -= f[i];
            ans++;
            if (k == 0) break;
        }
        return ans;
    }

长度为 n 的开心字符串中字典序第 k 小的字符串

思路

  1. 像全排列一样
  2. 纯模拟做法
  3. 从后往前,对每个字母递增,如果字母与前一位重复了,或者超过上限 c 了,就进位
  4. 确定一个合法递增之后,将它后面的字母重置为初始情况
  5. 图例
    图片.png

答题

    string getHappyString(int n, int k) 
    {
        string s(n, 'a');
        for (int i = 1; i < n; i += 2)
        {
            s[i] = 'b';
        }
        k -= 1;

        bool flag = true;
        while (k-- > 0)
        {
            for (int i = s.size() - 1; i >= 0; i--)
            {
                flag = false;
                if (s[i] == 'd') break;

                s[i]++;
                s[i] += (i > 0 && s[i - 1] == s[i]);
                flag = !(s[i] == 'd');
                if (!flag) continue;

                for (int j = i + 1; j < s.size(); j++)
                {
                    s[j] = s[j - 1] == 'a' ? 'b' : 'a';
                }
                break;
            }
        }
        return flag ? s : "";
    }

恢复数组

学习中

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

2
展开全部 32 讨论