首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >第96场周赛

第96场周赛

作者头像
用户1145562
发布2020-10-23 12:10:54
3000
发布2020-10-23 12:10:54
举报
文章被收录于专栏:LC刷题LC刷题

传送门

####

883. 三维形体投影面积

题解:根据描述,只需要分别求出底面,侧面,正面的面积即可。

底面的面积通过观察可以看出,是矩阵A[i][j]中不为0的个数,侧面是每一列的最大值总和,正面是每一行的最大值总和。

int projectionArea(vector<vector<int>>& grid) {
        int bottom = 0,left=0,front = 0;
        for(auto i:grid){
            int tmp = 0;
            for(auto j:i){
                tmp = max(tmp,j);
                if(j!=0)bottom+=1;
            }
            left+=tmp;
        }
        for(int i=0;i<grid[0].size();i++){
            int tmp=0;
            for(int j=0;j<grid.size();j++){
                tmp = max(tmp,grid[j][i]);
            }
            front+=tmp;
        }
        return front+left+bottom;
    }
881. 救生艇

题解:根据描述,每次只要尽可能的塞进去两个,就能保证救生艇数量最少。塞哪两个呢,当然是最大和最小的那两个,如果不能塞入两个,就塞入最大的那一个。

int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(),people.end());
        int left=0,right = people.size()-1;
        int ret=0;
        int tmp = people[right];
        while(left<right){
            tmp += people[left];
            if(tmp>limit){
                ret++;
                right--;
                tmp = people[right];
            }
            else{
                ret++;
                right--;
                left++;
                tmp = people[right];
            }
        }
        return left==right?ret+1:ret;
    }
880. 索引处的解码字符串

题解:跟据描述,只要把字符串按照要求解码得到新的字符串,然后按秩访问新的字符串即可。但可惜的是,某些情况会爆内存。

如果我们有一个像 appleappleappleappleappleapple 这样的解码字符串和一个像 K=24 这样的索引,那么如果 K=4,答案是相同的。 一般来说,当解码的字符串等于某个长度为 size 的单词重复某些次数(例如 apple 与 size=5 组合重复6次)时,索引 K 的答案与索引 K % size 的答案相同。 我们可以通过逆向工作,跟踪解码字符串的大小来使用这种洞察力。每当解码的字符串等于某些单词 word 重复 d 次时,我们就可以将 k 减少到 K % (Word.Length)。 算法 首先,找出解码字符串的长度。之后,我们将逆向工作,跟踪 size:解析符号 S[0], S[1], …, S[i] 后解码字符串的长度。 如果我们看到一个数字 S [i],则表示在解析 S [0],S [1],…,S [i-1] 之后解码字符串的大小将是 size / Integer(S[i])。 否则,将是 size - 1。 作者:LeetCode 链接:https://leetcode-cn.com/problems/decoded-string-at-index/solution/suo-yin-chu-de-jie-ma-zi-fu-chuan-by-leetcode/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

string decodeAtIndex(string S, int K) {
        long long len = 0;
        string ret = "";
        for(auto i:S){
            if(isdigit(i)) len = len*(i-'0');
            else len++;
        }
        for(int i=S.size()-1;i>=0;i--){
            K = K%len;
            if(K==0&&(isalpha(S[i]))){
                ret = S[i];
                return ret;
            }
            if(isdigit(S[i])) len = len/(S[i]-'0');
            else len--;    
        }
        return "";
    }
882. 细分图中的可到达结点
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-08-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 883. 三维形体投影面积
  • 881. 救生艇
  • 880. 索引处的解码字符串
  • 882. 细分图中的可到达结点
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档