欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客编程巅峰赛S1第7场-整理

程序员文章站 2022-06-15 19:44:52
...

前言:7月份开始参加牛客编程赛,难度适中,希望每次可以好好对待并整理下来,做到每次完成及时整理。小菜鸟不对的地方还请大家指正。

  1. 数组元素交换
    牛客编程巅峰赛S1第7场-整理
import java.util.*;
public class Solution {
    /**
     * 
     * @param a int整型一维数组 原始数组a
     * @param n int整型 第n大
     * @param m int整型 第m大
     * @return int整型一维数组
     */
     //思路:使用Map存储,按照大小进行排序,最后进行修改
    public int[] sovle (int[] a, int n, int m) {
        // write code here
        HashMap<Integer,Integer> num = new HashMap<Integer,Integer>();//标号,数字
        for(int i=0;i<a.length;i++){
            num.put(i,a[i]);
        }
        List<Map.Entry> sortMapList = new ArrayList<Map.Entry>(num.entrySet());
        Collections.sort(sortMapList,new Comparator<Map.Entry>(){
            @Override
            public int compare(Map.Entry o1, Map.Entry o2) {
                return (int)o2.getValue()-(int)o1.getValue();
            }
        });
        m=m-1;n = n-1;
        int index_m = (int)sortMapList.get(m).getKey();
        int index_n = (int)sortMapList.get(n).getKey();
        //交换
        int tmp = a[index_m];
        a[index_m] = a[index_n];
        a[index_n] = tmp;
        return a;
    }
}

算法优化:不用使用Map去将所有的数字和编号进行保存,可以采用之前优先队列存储排序的方法,直接利用值,对数字编号进行排序

    public int[] sovle (int[] a, int n, int m) {
         //之前优先队列保存index的方法
        Integer[] index = new Integer[a.length];
        for(int i=0;i<a.length;i++){
            index[i] = i;
        }
        Arrays.sort(index,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return a[o2]-a[o1];
            }
        });
        m = m-1;
        n = n-1;
        int tmp = a[index[m]];
        a[index[m]] = a[index[n]];
        a[index[n]] = tmp;
        return a;
     }

  1. 牛牛打怪兽
    牛客编程巅峰赛S1第7场-整理
import java.awt.*;
import java.util.*;
import java.util.List;
/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 返回牛牛能到达终点且不被淘汰的路径数
     * @param n int整型
     * @param Edge Point类一维数组
     * @param f int整型一维数组
     * @return int整型
     */
     //思路:使用回溯(即DFS思想)进行寻找,重点即最终的结束条件
    int res ;
    public int solve (int n, Point[] Edge, int[] f) {
        // write code here
        HashMap<Integer,List<Integer>> node = new HashMap<Integer,List<Integer>>();
        for(int i=0;i<Edge.length;i++){
            int index1 = Edge[i].x;
            int index2 = Edge[i].y;
            List<Integer> tmp =  new ArrayList<Integer>();
            if(node.containsKey(index1)){
                tmp = node.get(index1);
            }
            tmp.add(index2);
            node.put(index1,tmp);
            tmp = new ArrayList<Integer>();
            if(node.containsKey(index2)){
                tmp = node.get(index2);
            }
            tmp.add(index1);
            node.put(index2,tmp);
        }
        Set<Integer> visited = new HashSet<Integer>();
        res = 0;
        visited.add(1);
        backtrack(1,node,visited,f,2-f[0]);//从1开始,targer为2
        return res;
    }

    public void backtrack(int root , HashMap<Integer,List<Integer>> nodes,Set<Integer> visited,int[] f,int target){
        //代表已经跟root打过了,输赢不清楚
        if(target<0) return ;//表示打输了,不能下去
        //开始选择
        List<Integer> childs = new ArrayList<Integer>();//拿到与其相连的节点
        for(int tmp:nodes.get(root)){
            //去掉存在于
            if(!visited.contains(tmp)){childs.add(tmp);}
        }
        if(childs.isEmpty()){
            res++;return;
        }
        else{
            for(int tmp:childs){
                visited.add(tmp);
                backtrack(tmp,nodes,visited,f,target-f[tmp-1]);
                //visited.remove(tmp);
            }
        } 
    }
}

遇到的问题与总结:

  • 因为案例,下意识写成了二叉树,创建了Node节点,进行递归遍历
  • 回溯结束条件写错,大意的将“遍历的集合与总个数相等”作为了判定条件之一
  • n==1的情况未单独拎出来,导致一直没通过

  1. 牛牛冰淇淋
    牛客编程巅峰赛S1第7场-整理
import java.util.*;


public class Solution {
    /**
     * 两个数表示答案
     * @param n int整型 一次运输的冰激凌数量
     * @param m int整型 总冰激凌数
     * @param t int整型 一次运输的时间
     * @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
     * @return int整型一维数组
     */
     //思路:动态规划,注意c数组,是每个冰淇淋完成的时间点(先按照时间顺序排列),然后取每次运送的最短时间作为状态进行转移。
    public int[] icecream (int n, int m, int t, int[] c) {
        // write code here
        Arrays.sort(c);
        int [][]dp = new int[m+1][2];
        for(int i=1;i<=m;i++){
            Arrays.fill(dp[i],Integer.MAX_VALUE);
            for(int j=1;j<=n && j<=i;j++){//计算前面每个可以装入的车,然后取最小的值
                int index = i-j;
                //装入index后的一辆车,所在的车所要花费的时间:原来index的时间是dp[index][0]
                //现在需要等待该时间完成,dp[index][0]//往返回来,c[i-1]//c是完成的时间点
                int cost = Math.max(dp[index][0],c[i-1])+2*t;
                
                if(cost<dp[i][0]){//如果小,更新该状态下的花销
                    dp[i][0] = cost;
                    dp[i][1] = dp[index][1]+1;
                }else if(cost == dp[i][0] && dp[i][1] > dp[index][1] + 1){
                    //如果与之前的值相同并且不是在index基础上+1;此时为了运输次数最少,进行改变
                    dp[i][1] = dp[index][1]+1;
                }
            }
        }
        return new int[]{dp[m][0] - t, dp[m][1]};
    }
}