1.:輸入一個(gè)字符串扯俱，對(duì)其進(jìn)行逐詞的反轉(zhuǎn)后废膘，然后返回
輸入："the sky is blue"
輸出："blue is sky the"
注意： 1）“詞”是指：任何不含空格的連續(xù)字符串
　　　 2）輸入字符串可以有首尾空格，但是返回的字符串不能有首尾空格
　　　 3）輸入字符串中兩個(gè)詞之間可以有多個(gè)空格，但是返回的字符串中詞只能用單個(gè)空格隔開

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String ss=sc.nextLine();char[] ch=ss.toCharArray();
        int n=ch.length;
        Stack stack=new Stack();
        if(n==0){
            return;
        }
        /*去首尾空格*/
        int i=0;
        /*這里要加上判斷條件i<n，否則如果輸入的全是空格的話數(shù)組會(huì)越界*/
        while(i<n&&Character.isWhitespace(ch[i])){
            i++;
        }
        int j=n-1;
        while(j>-1&&Character.isWhitespace(ch[j])){
            j--;
        }
        
        while(j>=i){
            /*如果判斷到原字符串的第一個(gè)單詞，此時(shí)將棧中字母彈出即可附迷，不需要輸出空格*/
            if(j==i){
                /*這里要記得把第一個(gè)字符壓入棧*/
                stack.push(ch[j]);
                int size=stack.size();
                for(int k=0; k<size; k++){
                    System.out.print(stack.pop());
                }
            }else if(Character.isSpace(ch[j])){
                /*如果是空格惧互，并且棧不是空，則彈出棧中所有字母挟秤，并輸出一個(gè)空格壹哺。
                  這里的棧是否為空判斷是為了避免輸出可能的多余空格*/
                if(stack.size()!=0){
                    int size=stack.size();
                    for(int k=0; k<size; k++){
                        System.out.print(stack.pop());
                    }
                    System.out.print(" ");
                }
            }else{
                /*是字母的話直接入棧即可*/
                stack.push(ch[j]);
            }
            j--;
        }
    }
}

2.3. LISP語言唯一的語法就是括號(hào)要配對(duì)。形如 (OP P1 P2 ...)艘刚，括號(hào)內(nèi)元素由單個(gè)空格分割管宵。其中第一個(gè)元素OP為操作符，后續(xù)元素均為其參數(shù)攀甚，參數(shù)個(gè)數(shù)取決于操作符類型

注意：參數(shù) P1, P2 也有可能是另外一個(gè)嵌套的 (OP P1 P2 ...)箩朴，當(dāng)前OP類型為 quote / reverse / search / combine 字符串相關(guān)的操作：

• quote: 引用一個(gè)字符串，即返回字符串本身內(nèi)容秋度，參數(shù)個(gè)數(shù) 1

• reverse: 把字符串反轉(zhuǎn)炸庞，并返回，參數(shù)個(gè)數(shù) 1

• search: 在第一個(gè)字符串中查找第二個(gè)字符串的第一次出現(xiàn)荚斯，返回從這開始到結(jié)束的所有字符串埠居，如果查找不到，返回空字符串事期，參數(shù)個(gè)數(shù) 2

• combine: 把所有字符串組合起來滥壕，參數(shù)個(gè)數(shù)不定，但至少 1 個(gè)

其中P1, P2 等參數(shù)可能是帶雙引號(hào)的字符串,如 "abc"兽泣，也有可能是另外一個(gè) (OP P1 P2 ...)绎橘，上述字符串包括引號(hào)；引號(hào)中間的所有字符唠倦，均為 ASCII 可打印字符称鳞，且不會(huì)再出現(xiàn)引號(hào) (")，輸出也為帶雙引號(hào)的字符串

舉例:
輸入字符串 輸出結(jié)果
(quote "!@#%"
(reverse "a b c") "c b a"
(search "abcdef" "cd" ) "cdef"
(search "abcdef" "xy" ) ""
(combine "a" "b" "cde) ") "abcde) "
(search (combine "1234567890" "abcdefgh" "1234567890") (reverse "dc")) cdefgh1234567890

輸入描述:
合法C字符串稠鼻，字符串長(zhǎng)度不超過512冈止；用例保證了無語法錯(cuò)誤.

輸出描述:
合法C字符串，需要帶括號(hào)

輸入例子:
(search "huawei" "we")

輸出例子:
"wei"

思路：利用棧結(jié)構(gòu)枷餐，遇到 "(" 靶瘸、操作符、操作數(shù)都?jí)喝霔Ｃ撸龅?)" 持續(xù)出棧 直至彈出一個(gè) "("， 計(jì)算結(jié)果屋剑，再將這個(gè)結(jié)果壓入棧润匙。

類似的C++
[編程|300分] 仿LISP字符串運(yùn)算
題目描述
LISP語言唯一的語法就是括號(hào)要配對(duì)。
形如 (OP P1 P2 …)唉匾，括號(hào)內(nèi)元素由單個(gè)空格分割孕讳。
其中第一個(gè)元素OP為操作符匠楚，后續(xù)元素均為其參數(shù)，參數(shù)個(gè)數(shù)取決于操作符類型
注意：參數(shù) P1, P2 也有可能是另外一個(gè)嵌套的 (OP P1 P2 …)
當(dāng)前OP類型為add/sub/mul/div(全小寫)厂财，分別代表整數(shù)的加減乘除法芋簿。簡(jiǎn)單起見，所以O(shè)P參數(shù)個(gè)數(shù)為2
舉例
-輸入：(mul 3 -7)輸出：-21
輸入：(add 1 2) 輸出：3
輸入：(sub (mul 2 4) (div 9 3)) 輸出 ：5
輸入：(div 1 0) 輸出：error
常規(guī)方法是用兩個(gè)棧分別存放操作數(shù)和操作符璃饱，本文用一個(gè)棧來實(shí)現(xiàn)与斤，首先從后往前提取操作數(shù)和操作符存放在vector，然后判斷荚恶。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String ss=sc.nextLine();
        Stack<String> stack=new Stack<String>();
        StringBuilder temp1=new StringBuilder();  //字符串緩存撩穿，用來判斷累積讀入的字符是否構(gòu)成一個(gè)操作數(shù)/操作符
        List<String> temp2=new ArrayList<String>(); //用于存儲(chǔ)棧彈出來的操作數(shù)
        char[] chars=ss.toCharArray();
        int n=chars.length;
        /*從左往右掃描字符數(shù)組*/
        for(int i=0;i<n;i++){
            /*如果是 ( ，要判斷是否實(shí)在操作數(shù)中谒撼，是的話加入緩存字符串食寡，不是的話直接入棧*/
            if(chars[i]=='('){
                if(temp1.indexOf("\"")==-1){
                    stack.push("(");
                }else{
                    temp1.append('(');
                }
            }
            /*如果是 ) ，要判斷是否實(shí)在操作數(shù)中廓潜，是的話加入緩存字符串抵皱，不是的話出棧至遇到一個(gè) ( */
            else if(chars[i]==')'){
                /*根據(jù)緩存字符串中有沒有 " 來判斷是否在一個(gè)操作數(shù)中*/
                if(temp1.indexOf("\"")!=-1){
                    temp1.append(')');
                }else{
                    String back=stack.pop();
                    while(!back.equals("(")){
                        temp2.add(back);
                        back=stack.pop();
                    }
                    String operator=temp2.get(temp2.size()-1);
                    switch(operator){
                        case "quote":
                            stack.push("\""+(temp2.get(0)).replaceAll("\"","")+"\"");
                        break;
                        case "search":
                            stack.push(search(temp2.get(1),temp2.get(0)));
                        break;
                        case "reverse":
                            stack.push(reverse(temp2.get(0)));
                        break;
                        case "combine":
                            String stringComb=combine(temp2.subList(0,temp2.size()-1));
                            stack.push(stringComb);
                        break;
                    }
                    temp2.clear();
                }
            }
            /*如果是空格，判斷空格是否在操作數(shù)字符串中辩蛋，不是的話原先的字符串緩存已經(jīng)構(gòu)成一個(gè)操作數(shù)/符呻畸，壓入棧。
              是的話加入到字符串緩存中*/
            else if(chars[i]==' '){
                if(temp1.indexOf("\"")!=-1){
                    temp1.append(chars[i]);                
                }else{
                    if(temp1.length()>0){
                        String tempString=temp1.toString();
                        stack.push(tempString);
                        temp1.setLength(0);
                    }
                }
            }
            /*如果遇到成對(duì)的 " 堪澎，表明緩存的是一個(gè)操作符/數(shù)擂错，將其壓入棧*/
            else if((chars[i]=='\"')&&(temp1.indexOf("\"")!=-1)){
                if(temp1.length()>0){
                        temp1.append('\"');
                        String tempString=temp1.toString();
                        stack.push(tempString);
                        temp1.setLength(0);
                    }
            }
            /*字母或者數(shù)字的情況直接加入到字符串緩存*/
            else{
                temp1.append(chars[i]);
            }
        }
        for(int i=0;i<stack.size();i++){
            System.out.print(stack.pop());
        }
    }
    
    static String search(String s1,String s2){
        s1=s1.replaceAll("\"","");
        s2=s2.replaceAll("\"","");
        if(s1.indexOf(s2)!=-1){
            return "\""+s1.substring(s1.indexOf(s2))+"\"";
        }else{
            return  "\""+ "\"";
        }
    }
    
    static String reverse(String s){
        s=s.replaceAll("\"","");
        StringBuilder sb=new StringBuilder();
        char[] chars=s.toCharArray();
        for(int i=chars.length-1;i>=0;i--){
            sb.append(chars[i]);
        }
        return "\""+sb.toString()+"\"";
    }
    
    static String combine(List<String> l){
        StringBuilder sb=new StringBuilder();
        for(int i=l.size()-1;i>=0;i--){
            String s=(l.get(i)).replaceAll("\"","");
            sb.append(s);
        }
        return "\""+sb.toString()+"\"";
    }
}

注：

判斷StringBuilder是否為空：temp1.length()>0，通過長(zhǎng)度是否大于0來判斷樱蛤，以及利用setLength(0)來清空StringBuilder中的內(nèi)容

import java.util.Stack;
 
public class problem {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        String string = "(div 2 (sub 5 (add 3 2)))";//這里改成標(biāo)準(zhǔn)輸入
        
        StringBuffer inputString = new StringBuffer(string);
        
        Stack<Integer> numberBuffer = new Stack<Integer>();
        Stack<String> operationBuffer = new Stack<String>();
        int mark = 0;
        int ParameterOne = 0;
        int ParameterTwe = 0;
        
        for(int index = 0;index<inputString.length();index++) {
            if('(' == inputString.charAt(index)) {
                operationBuffer.push(inputString.substring(index+1, index+4));
                index+=4;
                mark = index+1;
            }else if (')' == inputString.charAt(index)) {
                if(mark<index) {
                    numberBuffer.push(Integer.parseInt(inputString.substring(mark, index)));
                    index++;
                    mark = index+1;
                }
                ParameterTwe = numberBuffer.pop();
                ParameterOne = numberBuffer.pop();
                
                switch(operationBuffer.pop()) {
                case "add":
                    numberBuffer.push(ParameterOne + ParameterTwe);
                    break;
                case "sub":
                    numberBuffer.push(ParameterOne - ParameterTwe);
                    break;
                case "mul":
                    numberBuffer.push(ParameterOne * ParameterTwe);
                    break;
                case "div":
                    if(ParameterTwe == 0) { 
                        System.out.println("error");//這里是error輸出
                        return;
                        }
                    else{
                        numberBuffer.push(ParameterOne / ParameterTwe);
                        }
                    break;
                }
                
            }else {
                if(' ' == inputString.charAt(index)) {
                    if(mark<index) {
                numberBuffer.push(Integer.parseInt(inputString.substring(mark, index)));
                //index++;
                mark = index+1;
                }
                }
            }
        }
        
        while(!operationBuffer.isEmpty()) {
            ParameterTwe = numberBuffer.pop();
            ParameterOne = numberBuffer.pop();
            
            switch(operationBuffer.pop()) {
            case "add":
                numberBuffer.push(ParameterOne + ParameterTwe);
                break;
            case "sub":
                numberBuffer.push(ParameterOne - ParameterTwe);
                break;
            case "mul":
                numberBuffer.push(ParameterOne * ParameterTwe);
                break;
            case "div":
                if(ParameterTwe == 0) { 
                    System.out.println("error");
                    }
                else{
                    numberBuffer.push(ParameterOne / ParameterTwe);
                    }
                break;
            }
            
        }
        
        System.out.println(numberBuffer.pop().toString());//這里改成標(biāo)準(zhǔn)輸出
        return;
    }
 
}

面試題一:獲取最長(zhǎng)對(duì)稱串的長(zhǎng)度
題目描述：

輸入一個(gè)字符串钮呀，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度，比如輸入字符串“12213”昨凡，由于該
字符串里最長(zhǎng)的對(duì)稱子字符串是“1221”爽醋，因此輸出為4.
輸入描述：
連續(xù)的字符串，字符串長(zhǎng)度不超過64便脊，只包含數(shù)字和字母
輸出描述：
最長(zhǎng)的對(duì)稱字符串長(zhǎng)度
示例1：
輸入
12321abc
輸出

5

import java.util.Scanner;
 
public class Main {
    /**
     * 華為2019春招面試編程題：獲取最長(zhǎng)的對(duì)稱字符串長(zhǎng)度
     * @param str
     * @return
     */
    public static int GetlongestSymStr(String str){  
        int n=str.length();  
        boolean[][] dp=new boolean[n][n];  
        int maxLen=0;  
        for(int i=0;i<n;i++){  
            for(int j=i;j>=0;j--){   
                if(str.charAt(i)==str.charAt(j) && (i-j<2 || dp[j+1][i-1]==true)){  
                    dp[j][i]=true;  
                    maxLen=Math.max(maxLen, i-j+1);  
                }  
            }  
        }  
        return maxLen;  
    } 
    public static void main(String[] args){ 
        Scanner sc = new Scanner(System.in);    
        String s = sc.nextLine();  
        System.out.println(GetlongestSymStr(s));  
    }
}

面試題二：IPV6地址分類

題目描述：

ipv6地址為128位蚂四，完整的文本格式寫成8段16位的形式，例如：
2001:1002：FFFF:ABCD:1234:1234:0000:0001
簡(jiǎn)寫時(shí)哪痰，會(huì)將其中全0的字段壓縮遂赠，例如：
2001:0000:0000:0000:0000:0000:0000:0001會(huì)簡(jiǎn)寫成2001::0001
0000:0000:0000:0000:0000:0000:0000:0001會(huì)簡(jiǎn)寫成::0001或者::1
ipv6地址包括以下類型：
地址類型 地址前綴(二進(jìn)制) ipv6前綴標(biāo)識(shí)
單播地址 未指定地址 00....0(128 bits) ::/128
環(huán)回地址 00...1(128 bits) ::1/128
鏈路地址 1111111010 FE80::/10
站點(diǎn)本地地址 1111111011 FEC0::/10
全球單播地址 其他形式
組播地址 11111111 FF00::/8

任播地址 從單播地址空間進(jìn)行分配，使用單播地址的格式

備注：地址標(biāo)識(shí)中一般以“/"后帶的數(shù)字來表示掩碼晌杰，例如上面的"FF00::/8"表示的是前8比特為1跷睦，后面120比特為任意值。請(qǐng)實(shí)現(xiàn)一段代碼肋演，來判斷輸入的IPV6地址字符串的類型
輸入描述：
一行字符串抑诸，完整形式的IPV6地址
輸出描述：
輸出一個(gè)字符串烂琴，表示是何種類型的IPV6地址，輸出可以是：
Unspecified 未指定地址
Loopback 環(huán)回地址
LinkLocal 鏈路本地地址
SiteLocal 站點(diǎn)本地地址
GlobalUnicast 全球單播地址
Multicast 組播地址
Error 錯(cuò)誤的地址蜕乡，或者非完整形式IPV6地址的字符串
示例1：
輸入：
FE81:0001:0000:0000:FF01:0203:0405:0607
輸出:
LinkLocal

（代碼帶更新）
面試題目三：應(yīng)用下載順序

題目描述：

華為應(yīng)用市場(chǎng)舉辦安裝應(yīng)用獎(jiǎng)勵(lì)金幣活動(dòng)奸绷，不同的應(yīng)用下載、試玩需要的流量大小不同层玲，獎(jiǎng)勵(lì)的金幣數(shù)量也不同号醉，同一個(gè)應(yīng)用多次下載只獎(jiǎng)勵(lì)一次金幣，小花月末有一定的余量称簿，計(jì)算下載哪些應(yīng)用可以獲取的金幣最多扣癣？相同金幣情況下，優(yōu)先排名靠前的應(yīng)用
輸入描述：
輸入分三行
第一行：流量數(shù)憨降，單位MB,整數(shù)
第二行：應(yīng)用排名順序父虑，下載、試玩需要流量數(shù)授药，單位MB,整數(shù)
第三行：應(yīng)用獎(jiǎng)勵(lì)的金幣數(shù)
輸出描述：
輸出應(yīng)用列表：建議下載的應(yīng)用順序號(hào)士嚎，用一個(gè)空格分隔
示例1：
輸入
40
12 13 23 36
11 11 20 30
輸出：
1 3
說明：

注意輸出：開頭、末尾沒有空格

思路分析：

本題實(shí)際是一個(gè)01背包模型悔叽，具體分析參考我的另一篇有關(guān)背包問題的文章莱衩。

import java.util.Scanner;
 
public class Main{
    /**
     * 華為2019春招面試編程題：應(yīng)用下載順序
     * @param numOfLL 剩余流量數(shù)
     * @param needLL 下載應(yīng)用排名及消耗流量數(shù)
     * @param reword 下載獎(jiǎng)勵(lì)金幣數(shù)
     * @return
     */
    public static String SequenceOfDownload(int numOfLL,int[] needLL,int[] reword){
        
        return ZeroOnePack(numOfLL,needLL.length,needLL,reword);
    }
    /**
     * @param V 背包容量
     * @param N 物品種類
     * @param weight 物品重量
     * @param value 物品價(jià)值
     * @return
     */
    public static String ZeroOnePack(int V,int N,int[] weight,int[] value){
        
        //初始化動(dòng)態(tài)規(guī)劃數(shù)組
        int[][] dp = new int[N+1][V+1];
        //為了便于理解,將dp[i][0]和dp[0][j]均置為0，從1開始計(jì)算
        for(int i=1;i<N+1;i++){
            for(int j=1;j<V+1;j++){
                //如果第i件物品的重量大于背包容量j,則不裝入背包
                //由于weight和value數(shù)組下標(biāo)都是從0開始,故注意第i個(gè)物品的重量為weight[i-1],價(jià)值為value[i-1]
                if(weight[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
            }
        }
        //則容量為V的背包能夠裝入物品的最大值為
        int maxValue = dp[N][V];
        //逆推找出裝入背包的所有商品的編號(hào)
        int j=V;
        String numStr="";
        for(int i=N;i>0;i--){
            //若果dp[i][j]>dp[i-1][j],這說明第i件物品是放入背包的
            if(dp[i][j]>dp[i-1][j]){
                numStr = i+" "+numStr;
                j=j-weight[i-1];
            }
            if(j==0)
                break;
        }
        return numStr;  
    }
    public static void main(String[] args){ 
        Scanner sc = new Scanner(System.in);  
        int numOfLL = Integer.parseInt(sc.nextLine());
        String str2 = sc.nextLine();
        String str3 = sc.nextLine();
        String[] needLL;
        String[] reword;
        needLL= str2.split(" ");
        reword = str3.split(" ");
        
        int[] Reword = new int[needLL.length];
        int[] NeedLL = new int[reword.length];
        for(int i=0;i<needLL.length;i++){
            NeedLL[i] = Integer.parseInt(needLL[i]);
            Reword[i] = Integer.parseInt(reword[i]);
        }
        String result = SequenceOfDownload(numOfLL,NeedLL,Reword);
        result = result.substring(0,result.length()-1);
        System.out.println(result); 
        sc.close();  
    }
}

今年華為優(yōu)招筆試總共三道編程題

一 娇澎、歌唱打分

青年歌手大賽評(píng)委打分笨蚁，打分規(guī)則是去掉一個(gè)最高分和一個(gè)最低分，然后計(jì)算平均分趟庄。

輸入描述：輸入數(shù)據(jù)有多組括细，每組占一行，每行第一個(gè)數(shù)n表示評(píng)委人數(shù)戚啥，然后是n個(gè)評(píng)委的打分

輸出描述：輸出保留兩位小數(shù)奋单，每組輸出一行

示例：

輸入：

3 99 98 97

4 100 99 98 97

輸出：

98.00

98.50

二、猜數(shù)字

xAyB猜字游戲猫十，輸入兩組數(shù)字览濒，每組數(shù)字包含4個(gè)非負(fù)整數(shù)，同一組中的四個(gè)數(shù)字互不相同拖云，數(shù)字間以空格分隔贷笛。

第一組數(shù)字為猜數(shù)字游戲的正確答案，第二組數(shù)字為玩家所猜的答案宙项，根據(jù)以下規(guī)則輸出猜數(shù)字的結(jié)果xAyB昨忆。

規(guī)則1：如果數(shù)字相同，且位置相同杉允，則得到一個(gè)A

規(guī)則2：如果數(shù)字相同邑贴，且位置不同，則得到一個(gè)B

輸入描述：兩組數(shù)字叔磷，每組數(shù)字包含4個(gè)非負(fù)整型數(shù)字拢驾，同一組中的四個(gè)數(shù)字互不相等，數(shù)字以空格分隔

輸出描述：xAyB

示例：

輸入：

1 2 3 4

1 2 5 3

輸出：

2A1B

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        String[] array1 = s1.split(" ");
        String[] array2 = s2.split(" ");
        int stateA = 0;
        int stateB = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array2.length; j++) {
                if (array1[i].equals(array2[j])) {
                    if (i == j) {
                        stateA++;
                    } else {
                        stateB++;
                    }
                }
            }
        }
        System.out.printf("%dA%dB",stateA,stateB);
    }
}

三改基、獨(dú)木橋

在河上有一座獨(dú)木橋繁疤，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子秕狰，青蛙很討厭踩在這些石子上稠腊。由于橋的長(zhǎng)度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0鸣哀，1架忌，……，L（其中L是橋的長(zhǎng)度）我衬。坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)叹放，坐標(biāo)為L(zhǎng)的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始挠羔，不停的向終點(diǎn)方向跳躍井仰。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為L(zhǎng)的點(diǎn)時(shí)破加，就算青蛙已經(jīng)跳出了獨(dú)木橋俱恶。

題目給出獨(dú)木橋的長(zhǎng)度L，青蛙跳躍的距離范圍S,T范舀，橋上石子的位置合是。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)尿背。

輸入描述：輸入文件river.in的第一行有一個(gè)正整數(shù)L（1 <= L <= 10^9）端仰，表示獨(dú)木橋的長(zhǎng)度。第二行有三個(gè)正整數(shù)S田藐，T荔烧，M，分別表示青蛙一次跳躍的最小距離汽久，最大距離鹤竭，及橋上石子的個(gè)數(shù)，其中1 <= S <= T <= 10景醇，1 <= M <= 100臀稚。第三行有M個(gè)不同的正整數(shù)分別表示這M個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開三痰。

輸出描述：輸出文件river.out只包括一個(gè)整數(shù)吧寺，表示青蛙過河最少需要踩到的石子數(shù)窜管。

示例：

輸入：

10

2 3 5

2 3 5 6 7

輸出：

2

參考這位大神的帖子：https://blog.csdn.net/zero_from/article/details/52958796

第一題：

找出輸入字符串中的重復(fù)字符，在根據(jù)ASCII把重復(fù)的字符從小到大排列（字符串長(zhǎng)度不超過100）

示例：輸入：ABCABCdd 輸出： ABCd

代碼：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int main()
{
    string str;
    cin>>str;
    int len=str.size();
    vector<int> v(126);
    for(int i=0;i<len;i++)
    {
           v[(int)(str[i])]++;
    }
    for(int j=0;j<126;j++)
    {
        if(v[j]>1)
            cout<<(char)j;
    }
    cout<<endl;
    return 0;
}

第二題：

給定一串字符稚机，里面有些字符有連續(xù)出現(xiàn)的特點(diǎn)幕帆，請(qǐng)尋找這些連續(xù)出現(xiàn)字符中最長(zhǎng)的串。如果最長(zhǎng)的串有多個(gè)赖条，請(qǐng)輸入字符ASCII碼最小的那一串

示例：aaabbbccccccccccccczzzz 輸出：ccccccccccccc

代碼：

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()
{
    vector<int> vec(256, 0);
    vector<int> vec1(256, 0);
    string charm;
    while (cin >> charm)
    {
        if (charm.size() == 0)
            return 0;
        if (charm.size() == 1)
        {
            cout << charm[0];
            return 0;
        }
    /*  for (int i = 0;i<charm.size();i++)
        {
            vec[charm[i]] = vec[charm[i]] + 1;
        }*/
        int count = 0;
        int flag = 0;
        for (int i = 0;i<charm.size()-1;i++)
        {
            count++;
            if (charm[i] != charm[i + 1]|| flag)
            {
                if(vec[charm[i]]<count)
                    vec[charm[i]] = count;
                count = 0;
            }
        }
        if (charm[charm.size() - 2] == charm[charm.size() - 1])
        {
            count++;
            if (vec[charm[charm.size() - 2]] < count)
            {
                vec[charm[charm.size() - 2]] = count;
                count = 0;
            }
        }
        if (charm[charm.size() - 2] != charm[charm.size() - 1])
        {
            if (vec[charm[charm.size() - 1]] < 1)
            {
                vec[charm[charm.size() - 1]] = 1;
            }
        }
 
        auto max = max_element(vec.begin(), vec.end());
        int index = 0;
        for (int i = 0;i<256;i++)
        {
            if (*max == vec[i])
            {
                index = i;
                break;
            }
        }
        for (int i = 0;i<*max;i++)
        {
            cout << (char)index;
        }
        for (int i = 0;i<256;i++)
        {
            vec[i] = 0;
        }
        cout << endl;
        int i = 0;
    }
}
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int main()
{
    vector<int> vec(126,0);
    string s1;
    cin>>s1;
    int len=s1.size();
    int max=0;
    int index=0;
    for(int i=0;i<len;i++)
    {
        vec[int(s1[i])]++;
    }
    for(int i=0;i<126;i++)
    {
        if (vec[i]>max)
        {
            max=vec[i];
            index=i;
        }
    }
    for(int i=max;i>0;i--)
    {
        cout<<(char)index;
    }
}

8.15：

知道問題所在了失乾，加入字符串是aaabbbbbbbbbbbbbaaaccccccccaaaaaaaa；

代碼中把a(bǔ)疊加起來了纬乍，這是不對(duì)的

第三題：屬于郵局問題（動(dòng)態(tài)規(guī)劃）

已知某小鎮(zhèn)的房子沿直線分布碱茁，給定一個(gè)有序整型數(shù)組arr，里面的每個(gè)值代表小鎮(zhèn)每棟房子的一維坐標(biāo)點(diǎn)仿贬。

現(xiàn)在需要建N個(gè)廣告牌纽竣，廣告牌只能建在這些坐標(biāo)點(diǎn)上，使得每個(gè)坐標(biāo)點(diǎn)離廣告牌的總距離最短诅蝶，請(qǐng)返回這個(gè)最短的總距離退个。

#include <iostream>
 
#include <string.h>
 
#include <stdio.h>
 
#include <vector>
 
 
 
using namespace std;
 
const int INF = ~0U >> 1;
 
const int N = 305;
 
 
 
int w[N][N];
 
int dp[N][35];
 
int a[N];
 
int n, m;
 
 
 
void Init(int a[], int n)
 
{
 
    memset(w, 0, sizeof(w));
 
    for (int i = 1; i <= n; i++)
 
    for (int j = i + 1; j <= n; j++)
 
        w[i][j] = w[i][j - 1] + a[j] - a[(i + j) >> 1];
 
}
 
 
 
int Work()
 
{
 
    for (int i = 1; i <= n; i++)
 
    {
 
        dp[i][i] = 0;
 
        dp[i][1] = w[1][i];
 
    }
 
    for (int j = 2; j <= m; j++)
 
    {
 
        for (int i = j + 1; i <= n; i++)
 
        {
 
            dp[i][j] = INF;
 
            for (int k = j - 1; k<i; k++)
 
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + w[k + 1][i]);
 
        }
 
    }
 
    return dp[n][m];
 
}
 
 
 
int main()
 
{
 
    vector<int> arr;
    int x;
    
    while (cin >> x)
    {
        arr.push_back(x);
    }
    int len = arr.size();
     m = arr[len - 1];
     n = len - 1;
        for (int i = 1; i <= n; i++)
 
            a[i]=arr[i-1];
 
        Init(a, n);
 
        printf("%d\n", Work());
 
    
 
 
 
}