本文共 3274 字，大约阅读时间需要 10 分钟。

1、最大字典子序列

给一个字符串，从里面选取子序列，求新组成的最大字典序列。如“ABCAB”，最大字典子序为“CB”。（2018春-爱奇艺）

思路一：先遍历一遍，找到最大的字符C，第二趟从C右边开始遍历，找到最大的字符B，再从B右边开始遍历，右边没有了，结束。时间复杂度为$O(n^2)$

思路二：单调栈，时间复杂度为$O(n)$

import java.util.Scanner;import java.util.Stack;public class AiQYI1 {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        String s=in.nextLine();        Stack
   
     stack=new Stack<>();        int len=s.length();        for(int i=len-1;i>=0;i--){
  //从后往前遍历            if(stack.isEmpty()||stack.peek()
   

2、放n种糖果进盒子

有n种糖果，每种糖果最少放min[i]个，最多放max[i]个$(0\leq i<n)$，盒子里面需要放m个糖果，一共有多少种放法。（2018春-爱奇艺）

思路：先把每种最少需要放的糖果放进去，变成多重背包问题。 来自

import java.util.Scanner;public class AiQYI3 {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();// 颜色种类        int m = scanner.nextInt();// 盒子放置m个糖果        int[] l = new int[n];        int[] r = new int[n];        int least = 0;        int[] avaliable = new int[n];// 表示每一种颜色剩余可以加的        for (int i = 0; i < r.length; i++) {            l[i] = scanner.nextInt();            r[i] = scanner.nextInt();            least += l[i];            avaliable[i] = r[i] - l[i];        }        int target = m - least; //dp[i][j]表示前i种糖果装满容量为j的背包的方法数。一定要用long，不然会爆，只能过70%         long[][] dp = new long[n + 1][target + 1];        for (int i = 0; i < dp.length; i++) {            dp[i][0] = 1;//初始化        }        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= target; j++) {                for (int k = 0; k <= avaliable[i - 1]; k++) {                    if (j - k >= 0)                        dp[i][j] += dp[i - 1][j - k];                }            }        }        System.out.println(dp[n][target]);    }}

3、给两个人分糖果

有一堆糖果，每个糖果重量不一定一样，分给两个人，两个人的糖果数量之差不超过1，求两个人分到的糖果的最小重量之差。（2018春-科大讯飞）

思路：找其中一份的重量之和与sum/2的最小之差

//转换为求其中一份与sum/2的最小值min，真实最小值为2*minpublic class KDXF {    //全局变量    static float min=Integer.MAX_VALUE;//其中一份与sum/2的最小值min    static float half;//sum/2    public static void main(String[] args) {        //重量数组        float[] weight= {
  1,2,3,4,5,100,6};        //sum/2        half=(float) (sum(weight)/2.0);        //其中一份糖果重量  如果总数为奇数，为少的那一份        float[] a=new float[weight.length/2];        //回溯        back( weight.length/2,-1,weight, a );        System.out.println((int)(min*2));    }    //回溯  n为还需要选几个    i为上一次选取的糖果下标，这个是增序选择的     weight为所有糖果重量    a存放已经选取的糖果重量，倒叙存放，先放a[a.length-1]最后放a[0]    public static void back(int n,int i,float[] weight,float[] a ) {        if(n==0) {
  //当把数组a填满了就计算，计算回溯结束时此路径的min            if(Math.abs(sum(a)-half)

4、求x^y的结果对N取余

（2018春-快手）

思路：直接累乘，线性时间复杂度不可取。二分，时间复杂度为$O(logn)$。

import java.util.Scanner;public class Kuaishou1 {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        long x = in.nextLong();        long y = in.nextLong();        long N = in.nextLong();        if(y<0){            System.out.println((int)1/pow(x,-y));        }else {            System.out.println(pow(x,y,N));        }    }    public static long pow(long a,long b,long N){        if(b==0)return 1;        if(b==1)return a;        if(b%2==0){            return pow(a*a,b/2,N)%N;        }else {            return (pow(a*a,b/2,N)*a)%N;        }    }}

转载地址：http://aehci.baihongyu.com/