1.构造回文
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
代码
可以删除不连续的字符，所以可以将字符串反转，求两个字符串的最长公共子序列，像这种字符串比较一般都可以使用动态规划求解。
有关字符串比较的可以看文本比较算法Needleman/Wunsch算法，动态规划算法之：最长公共子序列 & 最长公共子串（LCS）。
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
while(in.hasNext()){
String str1=in.nextLine();
String str2=new StringBuilder(str1).reverse().toString();
System.out.println(str1.length()-LCS(str1,str2));
}
in.close();
}
public static int LCS(String str1,String str2){
// 设置字符串长度
int len1= str1.length();
int len2=str2.length(); // 具体大小可自行设置
// 构造二维数组记录子问题x[i]和y[i]的LCS的长度
int[][] record = new int[len1 + 1][len2 + 1];
// 从后向前，动态规划计算所有子问题。
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1))
record[i][j] = record[i-1][j-1] + 1;// 状态转移方程
else{
record[i][j] = Math.max(record[i-1][j], record[i][j-1]);// 状态转移方程
//record[i][j] = Math.max(tmp,record[i-1][j-1]);
}
}
}
return record[len1][len2];
}
}
2.算法基础-字符移位
小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。
你能帮帮小Q吗？
代码
这道题不能采用额外的空间，所以必须两两进行交换，所以采用类似于冒泡的算法，把小写字符冒到大写字母之前就可以了。
import java.util.Scanner;
public class Main{
public static void main(String[] arg){
Scanner in=new Scanner(System.in);
while(in.hasNextLine()){
String s=in.nextLine();
StringBuilder sb=new StringBuilder(s);
System.out.println(change(sb));
}
in.close();
}
public static String change(StringBuilder sb){
int len=sb.length();
for(int i=1;i<len;i++){
if(isLowerCase(sb.charAt(i))){
int x=i;
while(x>=1 && !isLowerCase(sb.charAt(x-1))){
char tmp=sb.charAt(x-1);
sb.setCharAt(x-1, sb.charAt(x));
sb.setCharAt(x, tmp);
x=x-1;
}
}
}
return sb.toString();
}
public static boolean isLowerCase(char c){
if(c>='a' && c<='z')
return true;
return false;
}
}
3. 有趣的数字
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？
代码
这道题刚开始我用的是先排序，再统计，时间复杂度是nlogn。过后我发现有些人用的是map来统计，最优情况下时间复杂度更好一些，算差最大的对数就是最小的个数乘以最大数的个数，算差最小的对数要区分是否有重复的数，如果没有需要先排序，再相邻两个数最小的差。
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
int n=in.nextInt();
int[] nums=new int[n];
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<n;i++){
nums[i]=in.nextInt();
if(map.containsKey(nums[i]))
{
int t=map.get(nums[i]);
map.put(nums[i], ++t);
}
else
{
map.put(nums[i], 1);
}
}
int minResult=getMinResult(map);
int maxResult=getMaxResult(nums, map);
System.out.println(minResult+" "+maxResult);
}
in.close();
}
public static int getMaxResult(int[] nums,Map<Integer,Integer> map){
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++)
{
if(nums[i]>max)
max=nums[i];
if(nums[i]<min)
min=nums[i];
}
int maxNumberCount=map.get(max);
int minNumberCount=map.get(min);
int maxResult=maxNumberCount*minNumberCount;
return maxResult;
}
public static int getMinResult(Map<Integer,Integer> map){
int minResult=0;
boolean containSameNumber=false;
Set<Integer> keySet=map.keySet();
Iterator<Integer> it=keySet.iterator();
//查看是否有重复数字
while(it.hasNext())
{
int t=it.next();
int times=map.get(t);
if(times>1)
{
containSameNumber=true;
minResult+=times*(times-1)/2;
}
}
//如果没有重复，进行排序.找相邻最小的对数
if(!containSameNumber)
{
ArrayList<Integer> list=new ArrayList<Integer>();
list.addAll(keySet);
Collections.sort(list);
int distance=Integer.MAX_VALUE;
for(int i=0;i<list.size()-1;i++)
{
int x=list.get(i+1) - list.get(i);
if( x<distance)
{
distance = x;
minResult=1;
}
else if(x == distance)
{
minResult++;
}
}
}
return minResult;
}
}
评论区