騰訊2017暑期實習生程式設計題 JAVA題解

1.構造回文

給定一個字元串s，你可以從中删除一些字元，使得剩下的串是一個回文串。如何删除才能使得回文串最長呢？

輸出需要删除的字元個數。

輸入描述:

輸入資料有多組，每組包含一個字元串s，且保證:1<=s.length<=1000.

輸出描述:

對于每組資料，輸出一個整數，代表最少需要删除的字元個數。

輸入例子1:

abcda
google
      

輸出例子1:

2
2      

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s = sc.next();
            int n = s.length();
            int [][]arr = new int [1005][1005];
            StringBuilder s1 = new StringBuilder(s);
            StringBuilder s2 = new StringBuilder(s);
            s2.reverse();
            for(int i = 1;i <= n;i ++) {
                for(int j = 1;j <= n;j ++) {
                    if(s1.charAt(i-1) == s2.charAt(j-1)) {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }else {
                        arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
                    }
                }
            }
            System.out.println(n - arr[n][n]);
        }
   }
}
           

2.字元移位

小Q最近遇到了一個難題：把一個字元串的大寫字母放到字元串的後面，各個字元的相對位置不變，且不能申請額外的空間。

你能幫幫小Q嗎？

輸入描述:

輸入資料有多組，每組包含一個字元串s，且保證:1<=s.length<=1000.

輸出描述:

對于每組資料，輸出移位後的字元串。

輸入例子1:

AkleBiCeilD
      

輸出例子1:

kleieilABCD      

import java.util.*;
public class Main{
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	while(sc.hasNext()) {
    		String s = sc.next();
    		for(int i = 0;i < s.length();i ++) {
    			if(check(s.charAt(i))) System.out.print(s.charAt(i));
    		}
    		for(int i = 0;i < s.length();i ++) {
    			if(!check(s.charAt(i))) System.out.print(s.charAt(i));
    		}
    		System.out.println();
    	}
   }
   static boolean check(char c) {
	   return c >= 'a' && c <= 'z';
   }
}
           

3.有趣的數字

小Q今天在上廁所時想到了這個問題：有n個數，兩兩組成二進制組，相差最小的有多少對呢？相差最大呢？

輸入描述:

輸入包含多組測試資料。

對于每組測試資料：

N - 本組測試資料有n個數

a1,a2...an - 需要計算的資料

保證:

1<=N<=100000,0<=ai<=INT_MAX.

輸出描述:

對于每組資料，輸出兩個數，第一個數表示差最小的對數，第二個數表示差最大的對數。

輸入例子1:

6
45 12 45 32 5 6
      

輸出例子1:

1 2