Leetcode第238场周赛 总结 +补题

文章目录

K 进制表示下的各位数字总和

题目链接
题目描述
给你一个整数 n n n(10 进制)和一个基数 k k k ,请你将 n n n 从 10 进制表示转换为 k k k 进制表示,计算并返回转换后各位数字的 总和 。
转换后,各位数字应当视作是 10 进制数字,且它们的总和也应当按 10 进制表示返回。
样例描述

输入:n = 34, k = 6
输出:9
解释:34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。

提示:
1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100
2 ≤ k ≤ 10 2 \leq k \leq 10 2≤k≤10

class Solution {
public:
    int sumBase(int n, int k) {
        string ans = "";
        while(n)
        {
            ans += (char)(n%k + '0');
            n /= k;
        }
        int tot = 0;
        for(int i = 0; i < ans.size(); i++)
            tot += (int)(ans[i] - '0');
        return tot;
    }
};

最高频元素的频数

题目链接
题目描述
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 n u m s nums nums 和一个整数 k k k 。在一步操作中,你可以选择 n u m s nums nums 的一个下标,并将该下标对应元素的值增加 1 。
执行最多 k k k 次操作后,返回数组中最高频元素的 最大可能频数 。
样例描述

输入:nums = [1,2,4], k = 5
输出:3
解释:对第一个元素执行 3 次递增操作,对第二个元素执 2 次递增操作,
此时 nums = [4,4,4] 。
4 是数组中最高频元素,频数是 3 。

提示:
1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105
1 ≤ n u m s [ i ] ≤ 1 0 5 1 \leq nums[i] \leq 10^5 1≤nums[i]≤105
1 ≤ k ≤ 1 0 5 1 \leq k \leq 10^5 1≤k≤105

解题思路
当时把这个题想成了 2019 年沈阳站那个二分题目,二分区间内 m i n min min ~ m a x max max,找到一个值,让更多区间内的数花费最小代价得到一个出现次数最多的数。

正确二分思路就是先把所有的数求一遍前缀和,二分给出二分左边端点 l l l 和 右边端点 r r r,通过每次放缩的 m i d mid mid 确定最终的区间左端点,因为枚举的时候是从左往右枚举,右端点总是确定的,二分求的只是为了确定左端点的那个数,然后每次二分更新一下最大值即可。

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        typedef long long ll;
        int len = nums.size();
        vector<ll> s(len+1);
        for(int i = 1; i <= len; i++)
            s[i] = s[i-1] + nums[i-1];
        int ans = 0;
        for(int i = 1; i <= len; i++)
        {
            int l = 1, r = i;
            while(l < r)
            {
                int mid = (l + r)>>1;
                ll t = (nums[i - 1]*(ll)(i - mid + 1));
                if(t - s[i] + s[mid - 1] <= k) r = mid;
                else l = mid + 1;
            }
            if(i - r + 1 > ans) ans = i - r + 1;
        }
        return ans;
    }
};

所有元音按顺序排布的最长子字符串

题目链接
题目描述
当一个字符串满足如下条件时,我们称它是 美丽的 :
所有 5 个英文元音字母 ( ′ a ′ , ′ e ′ , ′ i ′ , ′ o ′ , ′ u ′ ) ('a' ,'e' ,'i' ,'o' ,'u') (′a′,′e′,′i′,′o′,′u′) 都必须 至少 出现一次。
这些元音字母的顺序都必须按照 字典序 升序排布(也就是说所有的 ′ a ′ 'a' ′a′ 都在 ′ e ′ 'e' ′e′ 前面,所有的 ′ e ′ 'e' ′e′ 都在 ′ i ′ 'i' ′i′ 前面,以此类推)
比方说,字符串 " a e i o u " "aeiou" "aeiou" 和 " a a a a a a e i i i i o o u " "aaaaaaeiiiioou" "aaaaaaeiiiioou" 都是 美丽的 ,但是 " u a e i o " "uaeio" "uaeio" , " a e o i u " "aeoiu" "aeoiu" 和 " a a a e e e o o o " "aaaeeeooo" "aaaeeeooo" 不是美丽的 。
给你一个只包含英文元音字母的字符串 w o r d word word ,请你返回 w o r d word word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串,请返回 0
子字符串 是字符串中一个连续的字符序列。
样例描述

输入:word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出:13
解释:最长子字符串是 "aaaaeiiiiouuu" ,长度为 13 。

解题思路
枚举找最长的含有 a e i o u aeiou aeiou 的升序序列即可, 注意处理边界问题。

class Solution {
public:
    int longestBeautifulSubstring(string word) {
        string p = "aeiou";
        int len = word.size();
        int ans = 0;
        for(int i = 0; i < len; i++)
        {
            int j = 0, s = i, ok = 1;
            if(word[i] != 'a') continue;
            while(i < len)
            {
                if(word[i] == p[j]) i++;
                else
                {
                    if(word[i] == p[j+1]) j++,i++;
                    else ok = 0;
                }
                if(!ok) break;
            }
            if(j == 4) ans = max(ans, i - s);
            i--;
        }
        return ans;
    }
};

最高建筑高度

题目链接
题目描述
在一座城市里,你需要建 n n n 栋新的建筑。这些新的建筑会从 1 到 n n n 编号排成一列。
这座城市对这些新建筑有一些规定:

每栋建筑的高度必须是一个非负整数。
第一栋建筑的高度 必须 是 0 。
任意两栋相邻建筑的高度差 不能超过  1 。

除此以外,某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 r e s t r i c t i o n s restrictions restrictions 的形式给出,其中 r e s t r i c t i o n s [ i ] restrictions[i] restrictions[i] = [ i d i , m a x H e i g h t i ] [id_i, maxHeight_i] [idi​,maxHeighti​] ,表示建筑 i d i id_i idi​ 的高度 不能超过 m a x H e i g h t i maxHeight_i maxHeighti​ 。
题目保证每栋建筑在 restrictions 中 至多出现一次 ,同时建筑 1 不会 出现在 r e s t r i c t i o n s restrictions restrictions 中。
请你返回 最高 建筑能达到的 最高高度 。
样例描述
Leetcode第238场周赛 总结 +补题

输入:n = 5, restrictions = [[2,1],[4,1]]
输出:2
解释:上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,1,2] ,最高建筑的高度为 2 。

解题思路
首先将 [ 1 , 0 ] [1, 0] [1,0] 这个点插入,然后从小到大排序,处理区间右端点,看右端点是否等于 n n n,因为题目是说 1... n 1...n 1...n 栋楼从左到右排列且第一幢楼的高度是 0 ,所以对于区间左端点和右边端点分别是 1 和 n n n,如果 n n n 不在集合中,那么插入即可,高度可以赋 i n t int int 类型的最大值。
设直线 :
l 1 l_1 l1​: y y y = x 1 x_1 x1​ + b 1 b_1 b1​
l 2 l_2 l2​: y y y = x 2 x_2 x2​ + b 2 b_2 b2​
求截距 b 1 b_1 b1​ 和 b 2 b_2 b2​
因为集合中 0 号位置就是 x x x 轴的 1 号点,所以 b 1 [ 0 ] = − 1 b{_1}[0] = -1 b1​[0]=−1, b 2 [ 0 ] = 1 b{_2}[0] = 1 b2​[0]=1。
直线 l 1 l_1 l1​ 方向左上方,对于每个点的截距只需要和前一个点的截距取一个 m i n min min 即可。
直线 l 2 l_2 l2​ 方向左下方,对于每个点的截距只需要和后一个点的截距取一个 m i n min min 即可。

直线 l 1 l_1 l1​ 和 和 l 2 l_2 l2​ 的交点判断交点是否合法。
h [ i ] [ 0 ] = x h[i][0] =x h[i][0]=x
h [ i ] [ 1 ] = y h[i][1] = y h[i][1]=y
交点坐标 m i d mid mid = b 1 [ i − 1 ] b{_1}[i-1] b1​[i−1] + b 2 [ i ] b{_2}[i] b2​[i] >> 1
以直线 l 2 l2 l2 为例:
y ′ y' y′ = − x ′ -x' −x′ + b 2 b_2 b2​ ==> x ′ x' x′ = b 2 b_2 b2​ - y y y
x ′ x' x′ 是否在 h [ i − 1 ] [ 0 ] h[i-1][0] h[i−1][0] 和 h [ i ] [ 0 ] h[i][0] h[i][0] 区间内,若在则更新一下最大值即可
最后更新一下最大值 和 直线 l 1 l_1 l1​ 和 l 2 l_2 l2​ 取 m i n min min 的最大值即可。

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& h) {
        h.push_back({1,0});
        sort(h.begin(),h.end());
        if(h.back()[0] != n) h.push_back({n,n-1});
        int len = h.size();
        typedef long long ll;
        vector<ll>L(len+1,1e18), R(len+1,1e18);
        //h[0][0] = 1 截距 -1
        L[0] = -1;
        for(int i = 1; i < len; i++)  // y = x + b
        {
            int x = h[i][0], y = h[i][1];
            L[i] = min(L[i-1],(ll)(y-x));
        }
        //h[0][0] = 1 截距 1
        R[0] = 1;
        for(int i = len - 1; i; --i)  // y = -x + b
        {
            int x = h[i][0], y = h[i][1];
            R[i] = min(R[i+1],(ll)(x+y));
        }

        ll ans = 0;
        for(int i = 0; i < len; i++)
        {
            int x = h[i][0];
            if(i)  // y = -x + b
            {
                ll Y = (L[i-1]+R[i]) >> 1;
                ll X = R[i] - Y;
                if(X >= h[i-1][0] && X <= h[i][0])
                    ans = max(ans,Y);
            }
            ans = max(ans,min(x+L[i],-x+R[i]));
        }
        return ans;
    }
};

总结

最后一个题不会,然后就是第二题思路想的是二分, 只是二分思路想偏了,补了第二题和第四题,第四题建议动手画图,然后码代码思路就清晰了。

上一篇:QT 中QTreeWidget


下一篇:01-Java内存模型