20221025联想数开笔试

20221025联想数开笔试

写在前面：前几天投的，今天接到笔试，在这里记录下，有点遗憾，第一题本来有思路，但是怎么改都过不了，实在受不了就交了，后来试了下，是最后判断的时候出了一点问题……还是得有耐心，这里只记算法题，题型是60分选择，40分编程

算法一

翻转硬币，给你一堆硬币，然后你可以从左翻，也可以从右翻，但是无论左右，都必须从左边第一个或者右边第一个开始翻（也就是说得翻从第一个位置到当前位置的所有硬币），然后左边翻的代价为x，右边翻的代价为y，求最小代价，解法如下，直接看源代码吧，dp

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int[] data = new int[N];
        for(int i = 0;i<N;++i){
            data[i] = sc.nextInt();
        }
        int[] dpleftzero = new int[N];//变成0的dp
        dpleftzero[0] = data[0]==0?0:x;
        int[] dpleftone = new int[N];//变成1的dp
        dpleftone[0] = data[0]==1?0:x;

        for(int i = 1;i<N;++i){
            if(data[i]==0){
                dpleftzero[i] = Math.min(dpleftzero[i-1],dpleftone[i-1]+x);
            }else{
                dpleftzero[i] = Math.min(dpleftone[i-1]+x,dpleftzero[i-1]+2*x);
            }
            if(data[i]==1){
                dpleftone[i] = Math.min(dpleftone[i-1],dpleftzero[i-1]+x);
            }else{
                dpleftone[i] = Math.min(dpleftzero[i-1]+x,dpleftone[i-1]+2*x);
            }
        }
        int[] dprightzero = new int[N];//变成0的dp
        dprightzero[N-1] = data[N-1]==0?0:y;
        int[] dprightone = new int[N];//变成1的dp
        dprightone[N-1] = data[N-1]==1?0:y;
        for(int i = N-2;i>=0;--i){
            if(data[i]==0){
                dprightzero[i] = Math.min(dprightzero[i+1],dprightone[i+1]+y);
            }else{
                dprightzero[i] = Math.min(dprightone[i+1]+y,dprightzero[i+1]+2*y);
            }

            if(data[i]==1){
                dprightone[i] = Math.min(dprightone[i+1],dprightzero[i+1]+y);
            }else{
                dprightone[i] = Math.min(dprightzero[i+1]+y,dprightone[i+1]+2*y);
            }
        }
        int reszero = Math.min(dpleftone[N-1],dprightzero[0]);
        int resone = Math.min(dpleftone[N-1],dprightone[0]);
        for(int i = 1;i<N-1;++i){
            reszero = Math.min(Math.min(Math.min(reszero,dpleftone[i]+x+dprightzero[i+1]),dpleftzero[i]+dprightone[i+1]+y),dpleftzero[i]+dprightzero[i+1]);
            resone = Math.min(Math.min(Math.min(resone,dpleftzero[i]+x+dprightone[i+1]),dpleftone[i]+dprightzero[i+1]+y),dpleftone[i]+dprightone[i+1]);
        }
        System.out.println(Math.min(resone,reszero));

    }
}

算法二：红包排序

一堆人抢红包，给你的数据格式是，一行两个数据，第一个是名字，然后第二个是红包金额，一共n个，然后要你排序，排序从大到小，根据红包大小排，但是排序要是稳定的，也就是说红包金额想等的话排名先后不能变，这里直接条件排序秒了，代码如下

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[][] data = new String[n][2];
        for(int i = 0;i<n;++i){
            data[i][0] = sc.next();
            data[i][1] = sc.nextInt()+"";
        }
        Arrays.sort(data, (o1, o2) -> Integer.parseInt(o2[1])-Integer.parseInt(o1[1]));
        for(String[] inner:data){
            System.out.println(inner[1]);
        }
    }



}

第一题18 第二题100
以上
希望对后来者有所帮助
持续更新状态