快手校招真题六

最小代价爬楼梯

你需要爬上一个N层的楼梯，在爬楼梯过程中， 每阶楼梯需花费非负代价，第i阶楼梯花费代价表示为cost[i]， 一旦你付出了代价，你可以在该阶基础上往上爬一阶或两阶。
你可以从第 0 阶或者 第 1 阶开始，请找到到达顶层的最小的代价是多少。
N和cost[i]皆为整数，且N∈[2,1000]，cost[i]∈ [0, 999]。

输入描述:
输入为一串半角逗号分割的整数，对应cost数组，例如

10,15,20
输出描述:
输出一个整数，表示花费的最小代价

因为这里不一定要上升到，最后一个台阶，所以可能之前的最大值得选择，在最后因为少选择一个而变成了最小值，所以需要在求最大值的大小，比较得出最小的代价

import java.util.*;

public class Main {

    // 统计第一大

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] numStrs = in.nextLine().split(",");
        int[] nums = new int[numStrs.length];
        for (int i = 0;i<numStrs.length;i++){
            nums[i] = Integer.parseInt(numStrs[i]);
        }
        int costLeft = 0;
        int costRight = 0;
        int index = -1;
        // 这里不能纯粹的比较，可能因为之前的和在加入最后一个后变了大小
        while (index < numStrs.length-2){
           if(nums[index+1] < nums[index + 2]){
               costLeft += nums[index + 1];
               index = index + 1;
           }else {
               costLeft += nums[index + 2];
               index = index + 2;
           }
        }
        index = -1;
        while (index < numStrs.length-2){
            if(nums[index+1] > nums[index + 2]){
                costRight += nums[index + 1];
                index = index + 1;
            }else {
                costRight += nums[index + 2];
                index = index + 2;
            }
        }
        System.out.println(Math.min(costLeft,costRight));
    }

}

动态规划的解题思路

import java.util.*;

public class Main {

    // 统计第一大

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] numStrs = in.nextLine().split(",");
        int[] nums = new int[numStrs.length];
        for (int i = 0;i<numStrs.length;i++){
            nums[i] = Integer.parseInt(numStrs[i]);
        }
        // 动态规划解题

        int first = nums[0]; int second = nums[1];
        int tmp = 0;
        for (int i=2;i<nums.length;i++){
             tmp = Math.min(first,second) + nums[i];
             first = second;
             second = tmp;
        }
        System.out.println(Math.min(first,second));
    }

}

鸡鸭分类

农场有n只鸡鸭排为一个队伍，鸡用“C”表示，鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整，使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻，需要调整队形两次。

输入描述:
输入一个长度为N，且只包含C和D的非空字符串。
输出描述:
使得最后仅有一对鸡鸭相邻，最少的交换次数

CCDCC

2

这里只需要统计原位置和新位置之差

import java.util.*;

public class Main {

    // 统计第一大

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        int count = 0;
        int iCount = 0;
        for (int i = 0;i<line.length();i++){
            if (line.charAt(i) == 'C'){
                iCount += i;
                count++;
            }
        }
        int m = (count * (count-1))/2;
        System.out.println(iCount - m);
    }

}

比特币最佳买卖的时机

给定一个正整数数组，它的第 i 个元素是比特币第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一次），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入比特币前卖出。

输入描述:
正整数数组，为以空格分隔的n个正整数
输出描述:
最大利润

7 1 5 3 6 4

5

import java.util.*;

public class Main {

    // 股票交易的问题

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] lines = in.nextLine().split(" ");
        int[] nums = new int[lines.length];
        for (int i=0;i<lines.length;i++){
            nums[i] = Integer.parseInt(lines[i]);
        }
        int dp_i_0 = -nums[0];
        int dp_i_1 = 0;
        for (int i=1;i<nums.length;i++){
            dp_i_1 = Math.max(dp_i_1,dp_i_0 + nums[i]);
            dp_i_0 = Math.max(dp_i_0,-nums[i]);
        }
        System.out.println(Math.max(dp_i_0,dp_i_1));
    }

}