讨论/题目交流/🐱 第 24 场夜喵双周赛/
🐱 第 24 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2020-04-18
最近编辑于 2020-04-18
共 32 个讨论

我完了 只会做第一道题...放弃 上床睡觉!

7

罚时太痛了,以后要记住末尾情况和应该用long long的地方。
下午脑袋坑了,思路正确WA了两次不敢继续提交了。
第二题应该是斐波那契那道题是有数学证明的,Zeckendorf's theorem指出任意正整数都可表示为一个或多个不同的斐波那契数之和。所以直接贪心就可以。
这个定理本身用数学归纳法就可以证明。

补充一下证明:
k=1k=1是显然成立.
假设k=1Nk=1…N都成立.
k=N+1k=N+1时,如果kk是斐波那契数,自然成立,否则会有Fibm<k<Fibm+1Fib_{m} < k < Fib_{m+1}.
容易知道0<kFibm<Fibm+1Fibm=Fibm10<k-Fib_m<Fib_{m+1}-Fib_m=Fib_{m-1}.
又因为归纳条件kFibmk-Fib_m可以表示为不同的斐波那契数之和,这些斐波那契数厘米显然不包括FibmFib_m.
所以k=N+1k=N+1也可以表示为不同的斐波那契数之和.
不仅不同,而且还是不连续的斐波那契数之和.

5

日常死于第四题...

5

第一次做完四题,激动得睡不着了😂😂

3

我只想知道第一那个神仙是咋6分钟ak的....

3

第一题提交了显示金币 +5,我以为通过了。
被第四题卡住之后就摸鱼去了,结束前 2 分钟来看发现第 1 题没过???白给了 400 名

2

题3
n = 1, 1 ~ 1 * 3
n = 2, 2 ~ 2 * 3
...
n = n, 2^(n-1) ~ 2^(n-1) * 3
所以k = 9, 由8, 1, 1组成 = c + a + b

public String getHappyString(int n, int k) {
    int val = (int)Math.pow(2, n-1);
    if ( k > val * 3 ) {
        return "";
    }
    char c = 'a';
    int step = 0;
    StringBuilder sb = new StringBuilder();
    int i = 1;
    while ( sb.length() < n ) {
        val = (int)Math.pow(2, n - i);
        step = 0;
        while ( true ) {
            if ( sb.length() > 0 && c + step == sb.charAt(sb.length() - 1) ) {
                step = (step + 1) % 3;
            }
            if (val >= k) {
                sb.append((char) (c + step));
                break;
            } else {
                k -= val;
                step = (step + 1) % 3;
            }
        }
        ++ i;
    }
    return sb.toString();
}
2

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

思路

  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

第四题的测试用例简直是不给穷举法的本菜鸡留活路。

本菜鸡终于做出来了,穷举+缓存,算是耍赖么

class Solution {
    public int numberOfArrays(String s, int k) {
        int[] n=new int[s.length()+1];
        for(int i=0;i<n.length;i++){
            n[i]=-1;
        }
        int res=func(s,0,k,n);
        return res;
    }
    
    public int func(String s,int l,int k,int[] arr){
        if(l>=s.length()){
            return 1;
        }
        if(s.charAt(l)=='0'){
            return 0;
        }
        int n=0;
        int res=0;
        for(int i=l;i<s.length();i++){
            int n2=Integer.parseInt(s.charAt(i)+"");
            if(n*1.0<=(k-n2)/10.0){
                if(arr[i+1]==-1){
                    arr[i+1]=func(s,i+1,k,arr);
                }
                res+=arr[i+1];
                if(res>=1000000007){
                    res%=1000000007;
                }
            }
            else{
                break;
            }
            n=n*10+n2;
        }
        return res;
    }
}
1

占坑。

估计打了下午的比赛感觉晚上的简单好多了。

T1. 逐步求和得到正数的最小值
按照题意扫一遍找到所有前缀和的最小值 vv. 然后ans=max(1,1v)ans = max(1, 1 - v).

T2. 和为 K 的最少斐波那契数字数目
因为fibonacci数列增长的很快, 我们直接将小于1e9的所有项列出来就行。 然后贪心的从大往小减就行。

至于为什么这么做是对的。

因为fib数列中, 2an=an+1+an22a_n = a_{n+1} + a_{n-2}. 因此, 先取大的一定不会让小的取2次以上更优。

T3.长度为 n 的开心字符串中字典序第 k 小的字符串
因为n非常小, 直接生成出所有的“开心字符串”就行, 最后排序取字典序第k个即可。
这道题n最大为10, 可以求出最多有 3 * 2^9 = 1536个字符串, 完全可以暴力求解。

时间复杂度 O(n3n)O(n3^n)
空间复杂度 O(3n)O(3^n)

T4. 恢复数组
显然是一个很简单的dp

设f(i)为前i位可能存在的方案数, 我们有:
f(i)=j=0i1f(j)s[j...i1]<=kf(i) = \sum_{j = 0}^{i - 1} {f(j) | s[j...i-1] <= k}

因为这里k最多为1e9, 所以我们只需要搜前面9位就可以了。

时间复杂度 O(nlogk)O(nlogk)
空间复杂度 O(n)O(n)

1