1 合唱團(動态規劃)

分析

要求n個學生中選擇k個，使這k個學生的能力值乘積最大。這是一個最優化的問題。

另外，在優化過程中，提出了相鄰兩個學生的位置編号差不超過d的限制。

如果不用遞歸或者動态規劃，問題很難入手，并且，限制條件d也需要對每一個進行限制，程式設計十分複雜

是以，解決的方法是采用動态規劃（原因：1.最優化問題2.可分解為最優子結構）

分解

1.對該問題的分解是關鍵。

從n個學生中，選擇k個，可以看成是：先從n個學生裡選擇最後1個，然後在剩下的裡選擇k-1個，并且讓這1個和前k-1個滿足限制條件

2.數學描述

記第k個人的位置為one,則可以用f[one][k]表示從n個人中選擇k個的方案。

然後，它的子問題，需要從one前面的left個人裡面，選擇k-1個，這裡left表示k-1個人中最後一個（即第k-1個）人的位置，是以，子問題可以表示成f[left][k-1].

學生能力數組記為arr[n+1],第i個學生的能力值為arr[i]

one表示最後一個人，其取值範圍為[1,n];

left表示第k-1個人所處的位置，需要和第k個人的位置差不超過d，是以

max{k-1,one-d}<=left<=one-1

在n和k定了之後，需要求解出n個學生選擇k個能力值乘積的最大值。因為能力值有正有負，是以

當one對應的學生能力值為正時，

f[one][k] = max{f[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);

當one對應的學生能力值為負時

f[one][k] = max{g[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);

此處g[][]是存儲n個選k個能力值乘積的最小值數組

程式設計實作

import java.util.Scanner;

/**
 * @author shishusheng
 */
public class NetEaseOne {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {

            //總人數
            int n = sc.nextInt();

            //學生能力值，第i個人的直接對應arr[i]
            int[] arr = new int[n + 1];
            //初始化
            for (int i = 1; i <= n; i++) {
                arr[i] = sc.nextInt();
            }

            //選擇的學生數
            int kk = sc.nextInt();

            //間距
            int dd = sc.nextInt();

            /**
             * 遞推的時候，以f[one][k]的形式表示
             * 其中：one表示最後一個人的位置，k為包括這個人，一共有k個人
             * 原問題和子問題的關系：f[one][k] = max{ f[left][k-1]*arr[one], g[left][k-1]*arr[one] }
             */
            //動态規劃數組
            //人直接對應坐标,n和kk都要+1
            long[][] f = new long[n + 1][kk + 1];
            long[][] g = new long[n + 1][kk + 1];

            //初始化k=1的情況
            for(int one = 1;one<=n;one++){
                f[one][1] = arr[one];
                g[one][1] = arr[one];
            }
            //自底向上遞推
            for(int k=2;k<=kk;k++){
                for(int one = k;one<=n;one++){
                    //求解當one和k定的時候，最大的分割點
                    long tempMax = Long.MIN_VALUE;
                    long tempMin = Long.MAX_VALUE;
                    for(int left = Math.max(k-1,one-dd);left<=one-1;left++){
                        if(tempMax<Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){
                            tempMax=Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one]);
                        }
                        if(tempMin>Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){
                            tempMin=Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one]);
                        }
                    }
                    f[one][k] = tempMax;
                    g[one][k] = tempMin;
                }
            }
            //n選k最大的需要從最後一個最大的位置選
            long result = Long.MIN_VALUE;
            for(int one = kk;one<=n;one++){
                if(result<f[one][kk]){
                    result = f[one][kk];
                }
            }
            System.out.println(result);
        }
    }
}

import java.util.Scanner;

/**
 * @author shishusheng
 */

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        //注意while處理多個case
        while (in.hasNext()) {
            int x = in.nextInt();
            int y = in.nextInt();

            char[][] points = new char[x][y];
            int[][] tar = new int[x][y];
            for (int i = 0; i < x; i++) {
                String str = in.next();
                points[i] = str.toCharArray();
            }
            int startX = in.nextInt();
            int startY = in.nextInt();
            int k = in.nextInt();
            int[] stepX = new int[k];
            int[] stepY = new int[k];
            for (int i = 0; i < k; i++) {
                stepX[i] = in.nextInt();
                stepY[i] = in.nextInt();
            }
            Queue<Integer> xQueue = new LinkedList<>();
            Queue<Integer> yQueue = new LinkedList<>();

            //引入隊列是為了周遊到最後不能走為止

            xQueue.add(startX);
            yQueue.add(startY);

            //起始點通路标記；1表示已經通路
            tar[startX][startY] = 1;
            while (!xQueue.isEmpty() && !yQueue.isEmpty()) {
                //取隊首
                startX = xQueue.remove();
                startY = yQueue.remove();
                for (int i = 0; i < k; i++) {
                    //不出界
                    if (startX + stepX[i] < x && startX + stepX[i] >= 0 && startY + stepY[i] < y && startY + stepY[i] >= 0) {
                        if (tar[startX + stepX[i]][startY + stepY[i]] == 0) {
                            if (points[startX + stepX[i]][startY + stepY[i]] == '.') {
                                tar[startX + stepX[i]][startY + stepY[i]] = tar[startX][startY] + 1;
                                xQueue.add(startX + stepX[I]);
                                yQueue.add(startY + stepY[I]);
                            } else {
                                //通路點為X
                                tar[startX + stepX[i]][startY + stepY[i]] = -1;
                            }

                        }
                    }

                }
            }
            int max = 0;
            int getRoad = 1;
            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    if (points[i][j] == '.' && tar[i][j] == 0) {
                        //有存在沒有被通路的“.”說明不能周遊完全，有些出口到不了。
                        getRoad = 0;
                    }
                    max = Math.max(max, tar[i][j]);
                }
            }
            if (getRoad == 0) {
                System.out.println(-1);
            } else {
                System.out.println(max - 1);
            }

        }
    }
}

3Fibonacci數列

import java.util.Scanner;

/**
 * @author shishusheng
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int a = 0, b = 1;
        //程式将b與N作比較，b>N時結束循壞
        //這是就能找到N最接近的兩個Fibonacci數，再找出最近的那個
        while (b <= N) {
            /**
             * 爬樓梯思路，自底向上計算
             * 等價于
             * b = a+b;
             * a = b-a;
             */
            int temp = a + b;
            a = b;
            b = temp;
        }
        //最後比較與a，b的位置，得出最近
        System.out.print((b - N) > (N - a) ? N - a : b - N);
    }
}

4數字反轉

import java.util.Scanner;

/**
 * 2018/3/25
 * @author shishusheng
 */
public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int x = input.nextInt();
        int y = input.nextInt();
        System.out.println(rev(rev(x)+ rev(rev(y))));

    }

    public static int rev(int num){
        int temp = 0;
        while(num>0){
            //精妙之處！！！
            temp = temp*10+num%10;
            num/=10;
        }
        return temp;
    }

}

5下廚房

import java.util.HashSet;
import java.util.Scanner;

/**
 * @author shishusheng
 */
public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        //去除重複元素
        HashSet<String> set = new HashSet<>();

        while (in.hasNext()) {
            String str = in.nextLine();
            String[] arr = str.split(" ");
            for (int i = 0; i < arr.length; i++) {
                set.add(arr[i]);
            }
        }

        System.out.println(set.size());
        set.clear();
    }
}

import java.util.Scanner;
/**
 * 隻要考慮兩個條件
 *      第一，總數一定能被牛的數量整除
 *      第二，每頭牛比平均值多出來的蘋果數一定能被2整除，
 * 不滿足這兩個條件的輸出-1
 * 滿足的情況下，将比平均值多出的蘋果數除2，就是移動次數
 * @author shishusheng
 * @date 2018/3/25
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int num = in.nextInt();
            int[] apples = new int[num];
            //蘋果總數
            int sum = 0;
            for (int i = 0; i < num; i++) {
                int a = in.nextInt();
                sum += a;
                //每頭牛的蘋果數
                apples[i] = a;
            }
            //蘋果牛均數
            int avg = sum / num;
            //分的不均勻
            if (sum % num != 0) {
                System.out.println(-1);
                return;
            }
            int res = 0;
            //對每頭牛的蘋果數
            for (int n : apples) {
                if (n > avg) {
                    //超出平均的部分
                    int over = n - avg;
                    if (over % 2 != 0) {
                        System.out.print(-1);
                        return;
                    } else {
                        res += over / 2;
                    }
                }
            }
            System.out.println(res);
        }
    }
}

6

import java.util.*;

/**
 * @author shishusheng
 */
public class Main {

    /**
     * 判斷是否根據長度排序
     *
     * @param strings
     * @return false:不是根據長度排的
     */
    public static boolean isLenOrder(String[] strings) {
        int length = strings[0].length();
        for (int i = 1; i < strings.length; i++) {
            //直接比較相鄰項長度
            if (length <= strings[i].length()) {
                length = strings[i].length();
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * 判斷是否根據字典序排列
     *
     * @param strArr
     * @return false:不是根據字母順序 true:根據字母順序
     */
    public static boolean isCharOrder(String[] strArr) {
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < strArr.length; i++) {
            list.add(strArr[i]);
        }
        //JDK自帶的按字典序的标準結果
        Collections.sort(list);
        String[] strHelpArr = new String[strArr.length];
        for (int i = 0; i < strHelpArr.length; i++) {
            //整理出标準對照數組
            strHelpArr[i] = list.get(i);
        }
        for (int i = 0; i < strHelpArr.length; i++) {
            //與标準對照比較
            if (strArr[i] != strHelpArr[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        while (s.hasNext()) {
            int n = s.nextInt();
            String[] strings = new String[n];
            for (int i = 0; i < n; i++) {
                strings[i] = s.next();
            }
            if (isLenOrder(strings) & isCharOrder(strings)) {
                System.out.println("both");
            } else if (isLenOrder(strings) == false & isCharOrder(strings) == true) {
                System.out.println("lexicographically");
            } else if (isLenOrder(strings) == true & isCharOrder(strings) == false) {
                System.out.println("lengths");
            } else {
                System.out.println("none");
            }
        }
    }
}

7喜歡的數字

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        String str="";
        Scanner input = new Scanner(System.in);
        while (input.hasNext()){
            str =input.next();
        }
        char[] a = str.toCharArray();
        for (int i = 0; i < a.length; i++) {
            if(a[i]<'A' || a[i]>'Z'){
                System.out.println("Dislikes");
                return;
            }
            if (i<a.length-1 &&a[i]==a[i+1]){
                System.out.println("Dislikes");
                return;
            }

        }
        System.out.println("Likes");
        return;
    }
}

方法二

import java.util.Scanner;

/**
 * @author shishusheng
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String word = sc.next();

            if (isAllInitCapital(word) && isConEql(word) && isThrEql(word)) {
                System.out.println("Likes");
            } else {
                System.out.println("Dislikes");
            }
        }
    }

    /**
     * 條件1:單詞每個字母都是大寫字母
     *
     * @param word
     * @return
     */
    public static boolean isAllInitCapital(String word) {
        return word.matches("[A-Z]+");
    }

    /**
     * 條件2:單詞沒有連續相等的字母
     *
     * @param word
     * @return
     */
    public static boolean isConEql(String word) {
        return !word.matches(".*(.)(\\1).*");
    }

    /**
     * 單詞沒有形如“xyxy”
     * 這裡的x，y指的都是字母，并且可以相同)這樣的子序列，子序列可能不連續。
     * 
     * @param word
     * @return
     */
    public static boolean isThrEql(String word) {
        return !word.matches(".*(.).*(.)(.*\\1)(.*\\2).*");
    }
}

8買蘋果

//複雜度O(1)方法

import java.util.*;

/**
 *
 * O(1)
 * 對數字特征進行分析。
 *
 * 6,8都是偶數。是以，能湊出的個數也是偶數。
 * 程式中若蘋果總數是奇數，直接傳回-1。
 *
 * 再次，偶數個蘋果數對8取模，其結果隻可能為0,2,4,6。
 * 若餘數為6或者0，則可以直接用6包裝情況處理，不需要回溯購買8包裝的情況。
 * 若餘數為4，隻需回溯1次即可，因為8+4=12, 12%6 = 0。
 * 若餘數為2，隻需回溯2次即可，因為8+8+2=18, 18%6 = 0。
 *
 * 綜上，可以采用如下思路進行處理。（由于數字6和8的特征，本方法隻适用于本題）
 *
 * 情況1：若num不是偶數，則直接傳回-1
 * 情況2：若num%8 = 0，則傳回num/8
 * 情況3：若num%8 != 0，則隻需回溯1次或者2次8包裝購買個數，就可以求解。
 * 回溯1次，其結果為n/8-1+2 = n/8+1；
 * 回溯2次，其結果為n/8-2+3 = n/8+1。
 * 是以，可以情況3下，可以傳回n/8+1。
 * @author shishusheng
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            System.out.println(count(n));
        }
    }

    public static int count(int n) {
        if (n % 2 != 0 || n == 10 || n < 6) {
            //一定是偶數（6，8都是）,最小是6，10以上偶數都可以；
            return -1;
        }
        if (n % 8 == 0) {
            //如果拿八個拿完最好
            return n / 8;
        }
        //對于10以上的偶數，隻要對8取餘數不為0，就要從前面的1或者2個8中拿出2個，把餘數補為6（本來餘數就是6，就不用拿）。是以+1；
        return 1 + n / 8;
    }
}

網易17校招程式設計筆試題Java解法賞析（更新至第9題）1 合唱團(動态規劃)程式設計實作3Fibonacci數列4數字反轉5下廚房67喜歡的數字8買蘋果9

1 合唱團(動态規劃)

分析

分解

程式設計實作

3Fibonacci數列

4數字反轉

5下廚房

6

7喜歡的數字

8買蘋果

9

繼續閱讀

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

無人機--飛控科普

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method