Weekly Contest 107 AC思路-阿里云开发者社区

开发者社区> laijh_go> 正文

Weekly Contest 107 AC思路

简介: Weekly Contest 107 AC思路
+关注继续查看

比赛题目链接:https://leetcode-cn.com/contest/weekly-contest-107/

第一题:925. 长按键入
原题链接:https://leetcode-cn.com/contest/weekly-contest-107/problems/long-pressed-name/

思路:看题目的话,会分析出一个出来一个思路就是,对字符串进行压缩,举例分析
abbccca
序号 字符 出现次数
1 a 1
2 b 2
3 c 3
4 a 1

那么,我们可以对name和typed字符串进行压缩,存储到切片里(或数组),然后进行比较

// 定义一个结构体
type longScan struct {
    num int    // 次数
    char byte // 字符
}

// 定义存储变量
nScan, tScan := []longScan{}, []longScan{}

// 压缩存储name
// 压缩存储typed
// 比较nScan, tScan
for i := 0;i < len(nScan);i++ {
        if nScan[i].char != tScan[i].char || nScan.num > tScan.num {
                  return false
        }
}
return false

第一题的整体思路就这样了
我AC代码链接:https://github.com/laijinhang/acm-go/blob/master/leetcode_go/%E6%AF%94%E8%B5%9B/925.%20%E9%95%BF%E6%8C%89%E9%94%AE%E5%85%A5.go

第二题:926. 将字符串翻转到单调递增
原题链接:https://leetcode-cn.com/contest/weekly-contest-107/problems/flip-string-to-monotone-increasing/

思路:分析题目,可以知道最终结果第一次出现1的地方开始后都要为1
思路一:
那么转化成出现1的地方要么 1-> 0,要么 1 -> 1。
第一种操作的话,加上翻转次数,继续往下找到出现1的地方,重复这个步骤
第二种操作的话,计算后面出现0的个数,判断是否为最小,是的话,就值替换

思路二:
1)先将字符串进行压缩

type MonoIncr struct {
    num int    // 次数
    char byte // 字符
}

2)然后对压缩之后的内容计算,要么 1->0,要1->1后面全部变1,计算翻转次数

我AC代码链接:https://github.com/laijinhang/acm-go/blob/master/leetcode_go/%E6%AF%94%E8%B5%9B/926.%20%E5%B0%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BF%BB%E8%BD%AC%E5%88%B0%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E.go

会发现很像01背包问题

题目三:927. 三等分
原题链接:https://leetcode-cn.com/contest/weekly-contest-107/problems/three-equal-parts/

思路:分析题目,要得到三等分,那么三个区间1的个数要能整除3,而且每一个区间1的个数要相等
1)如果A的长度小于3,则直接返回[-1,-1]
2)如果A中1的个数%3不等于0,则直接返回[-1,-1]

一个二进制数出现第一个1之前出现的0都不算在二进制数里面

3)计算A中1的个数
4)设a1、a2、a3、a4、a5、a6,意思分别表示a1的第一个区间第一次出现1的下标值,a2是从a1开始出现第num/3个1的下标值,a3表示a2+1开始第一次出现1的下标值,a4表示从a3开始出现第num/3个1的下标值,a5表示a4+1开始第一次出现1的下标值,a6表示从a5开始第num/3个1的下标值。
5)分别计算出a1、a2、a3、a4、a5、a6的值
6)要满足len(A) - a6 - 1 + a2 < a3 && len(A) - a6 - 1 + a4 < a5,不满足则返回[-1,-1]
7)比较A[a1:a2+1],A[a3:a4+1],A[a5:a6+1],如果相同则返回[len(A) - a6 - 1 + a2, len(A) - a6 + a4],不同则返回[-1,-1]

我AC代码链接:https://github.com/laijinhang/acm-go/blob/master/leetcode_go/%E6%AF%94%E8%B5%9B/927.%20%E4%B8%89%E7%AD%89%E5%88%86.go

简书博客链接:https://www.jianshu.com/p/bbb0744f70a4

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
6915 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
2852 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4485 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7758 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
5458 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
9426 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
2141 0
+关注
laijh_go
三年编程经验,热爱技术,专注GO语言相关技术,喜欢研究算法实现
35
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载