# 【腾讯】2017暑期实习生

xiaoxiao2021-02-28  3

[编程题]构造回文

## 输出

2 2 将字符串颠倒，求原字符串和颠倒的字符串的公共子串，用动态规划 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { // 还是动态规划，求得是字符串和它翻转的公有子串长度 String str = in.nextLine(); // 翻转字符串 String str1 = new StringBuffer(str).reverse().toString(); // System.out.println(str1); char[] arr = str.toCharArray(); char[] arr1 = str1.toCharArray(); int[][] dp = new int[str.length() + 1][str.length() + 1]; // 第一行，第一列等于0 for (int i = 0; i < dp.length; i++) { dp[0][i] = 0; dp[i][0] = 0; } for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp.length; j++) { if (arr[i - 1] == arr1[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // dp[dp.length-1][dp.length-1]里面记录公有子串长度 // System.out.println(dp[dp.length-1][dp.length-1]); System.out.println(arr.length - dp[dp.length - 1][dp.length - 1]); } } }

[编程题]算法基础-字符移位

AkleBiCeilD

## 输出

kleieilABCD import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { String str = in.nextLine(); char[] arr = str.toCharArray(); String newString = ""; for (int i = 0; i < arr.length; i++) { if (arr[i] >= 97 && arr[i] <= 122) { newString += arr[i]; } } for (int i = 0; i < arr.length; i++) { if (arr[i] >= 65 && arr[i] <= 90) { newString += arr[i]; } } System.out.println(newString); } } }

[编程题]有趣的数字

## 输入

6 45 12 45 32 5 6

## 输出

1 2

import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int count = in.nextInt(); int num[] = new int[count]; for (int i = 0; i < count; i++) { num[i] = in.nextInt(); } Arrays.sort(num); // 如果数组中的值全相同，直接两两组合 if (num[0] == num[count - 1]) { int tmp = (count * (count - 1)) / 2; System.out.println(tmp + " " + tmp); return; } // 记录元素以及出现个数 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < num.length; i++) { // 存在个数就加一 if (map.containsKey(num[i])) { int temp = map.get(num[i]); map.put(num[i], temp + 1); } else { map.put(num[i], 1); } } // 遍历map如果value有大于1的那么最小的差就是0 int maxCount = 1; int min = 0, max = 0; Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> entry = it.next(); if(entry.getValue()>1){ min += (entry.getValue() * (entry.getValue() - 1)) / 2; } } //没有相等的 if(min==0){ int mintemp=Math.abs(num[0]-num[1]); for(int i=2;i<num.length;i++){ int temp=num[i]-num[i-1]; if(temp==mintemp){ min++; }else if(temp<mintemp){ min=1; mintemp=temp; } } } // 计算最大的对数，相差最大的对数=最小值的个数*最大值的个数 max = map.get(num[0]) * map.get(num[count - 1]); System.out.println(min + " " + max); } } }