Weekly-contest-208
- 第一次四题全部AC，排名第一次突进前三百，主要可能还是因为题目是相对来说比较简单的，就是题目描述的比较冗余和不清晰
1/5523. 文件夹操作日志搜集器
class Solution {
// 刚开始使用 == 对String进行对比， String是对象，==操作符比较的是地址
// 使用equals则正确
public int minOperations(String[] logs) {
int result = 0;
for(int i=0; i<logs.length; i++){
if(logs[i].equals("../")){
if(result!=0)result--;
}else if(!logs[i].equals("./")){
result++;
}
}
return result;
}
}
2/5524. 经营摩天轮的最大利润
class Solution {
// 什么鬼，难道还有人在摩天轮上也不转了吗
public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
int maxPro = -1;
int times = 0;
int proNow = 0;
int len = customers.length;
int p = 0;
int waitPeople = 0;
while(p < len || waitPeople!=0){
if(p<len){
waitPeople += customers[p];
}
//判断该轮 上摩天轮人数
if(waitPeople>4){
waitPeople -= 4;
proNow = proNow + (4*boardingCost) - runningCost;
}else{
proNow = proNow + (waitPeople*boardingCost) - runningCost;
waitPeople = 0;
}
if(proNow>maxPro){
maxPro = proNow;
times = p;
}
p++;
}
return maxPro>=0 ? times+1:-1;
}
}
3/5525. 皇位继承顺序
- 这种类型的题是第一次做，还是挺有意思的，但是由于是初见，所以花了比较多的时间，但好算是一次AC了
- 首先是每个人有一个自己的名字，可以拥有一些孩子，并且要维护一个是否死亡的状态，所以应该为“人”建立一个对象
- 因为外部调用时只会使用人物的名字，所以要在ThroneInheritance类中维持一个哈希表，可以通过名字获取到人物对象
- 这题的本质其实是多叉树的遍历
class ThroneInheritance {
//数据结构 Person
//通过递归遍历Person确定继承顺序
//Person有3个字段 1.child 2.death 3.name
//定义一个map，key-value : name-Person
class Person{
String name;
List<Person> child = new ArrayList<>();
boolean death;
public Person(String name){
this.name = name;
}
public String getName(){
return name;
}
public void addChild(Person thisChild){
child.add(thisChild);
}
public List<Person> getChildren(){
return child;
}
public void setDeath(){
death = true;
}
public boolean isDeath(){
return death;
}
}
Map<String, Person> nameToPerson = new HashMap<>();
String firstOrder;
List<String> inheritanceOrder;
public ThroneInheritance(String kingName) {
Person king = new Person(kingName);
nameToPerson.put(kingName, king);
firstOrder = kingName;
}
public void birth(String parentName, String childName) {
Person child = new Person(childName);
nameToPerson.put(childName, child);
Person parent = nameToPerson.get(parentName);
parent.addChild(child);
}
public void death(String name) {
nameToPerson.get(name).setDeath();
}
//队列不行，继承顺序为深度优先遍历，使用递归比较方便
public List<String> getInheritanceOrder() {
inheritanceOrder = new ArrayList<>();
traverse(nameToPerson.get(firstOrder));
return inheritanceOrder;
}
public void traverse(Person now){
if(!now.isDeath()){
inheritanceOrder.add(now.getName());
}
for(Person child:now.getChildren()){
traverse(child);
}
}
}
4/5526. 最多可达成的换楼请求数目
- 本题看起来是跟图有关系，但根据限制条件分析后能发现，一系列请求有没有效果只和所有“楼”的出度入度是否相等有关，即如果所有楼出去的人和进来的人数量相等，那就请求就满足
- 分析后发现实现就很简单了，不考虑剪枝的情况下，使用回溯/状态压缩，枚举每一种请求组合情况，对每种组合判断是否有效，有效则更新最大请求数目，下面是比赛时没有进行剪枝的暴力做法
class Solution {
//每一栋楼都是一个节点
//动态建立出度入度表，当此时所有节点的出度入度都相等时，则满足请求
//（回溯，进行多种选择，每次回溯回溯到底，借此判断能满足的最大请求数量）
int node;
int[] indegree;
int[] outdegree;
int maxRequest = 0;
int requestNum = 0;
public int maximumRequests(int n, int[][] requests) {
node = n;
indegree = new int[n];
outdegree = new int[n];
requestNum = requests.length;
for(int i=0; i<requestNum; i++){
dfs(requests, i, 1);
}
return maxRequest;
}
//考虑剪枝，当请求的可能性已经小于maxRequest时，剪枝
public void dfs(int[][] requests,int index, int request){
indegree[requests[index][1]]++;
outdegree[requests[index][0]]++;
if(requestVaild()){
maxRequest = Math.max(maxRequest, request);
}
for(int i=index+1; i<requestNum; i++){
dfs(requests, i, request+1);
}
indegree[requests[index][1]]--;
outdegree[requests[index][0]]--;
}
//当前请求有效
public boolean requestVaild(){
for(int i=0; i<node;i++){
if(indegree[i]!=outdegree[i])
return false;
}
return true;
}
}
- 下面的题解改善了DFS结构，并且根据当前获取到的相对大的请求数目后，据此对剩下的分支进行剪枝判断
class Solution {
int node;
int[] indegree;
int[] outdegree;
int maxRequest = 0;
public int maximumRequests(int n, int[][] requests) {
node = n;
indegree = new int[n];
outdegree = new int[n];
dfs(requests, 0, 0);
return maxRequest;
}
public void dfs(int[][] requests,int index, int request){
if(requestVaild()){
maxRequest = Math.max(maxRequest, request);
}
for(int i=index; i<requests.length; i++){
// 剪枝
if(requests.length-i+request < maxRequest)break;
indegree[requests[i][1]]++;
outdegree[requests[i][0]]++;
dfs(requests, i+1, request+1);
indegree[requests[i][1]]--;
outdegree[requests[i][0]]--;
}
}
public boolean requestVaild(){
for(int i=0; i<node;i++){
if(indegree[i]!=outdegree[i])
return false;
}
return true;
}
}
两种题解时间差距大概能达到一倍
