一：逆置字符串
链接：逆置字符串
1.题目
将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I
2.解题
2.1思路分析
先将整个字符串逆序，然后再将每个单词进行逆序即可。
2.2代码实现
java代码
import java.util.*;
public class Main{
public static void reverse(char array[],int start,int end){
while(start < end){
char tmp = array[start];
array[start] = array[end];
array[end] = tmp;
start++;
end--;
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
char[] arr = str.toCharArray();
reverse(arr,0,arr.length-1);
int len = arr.length;
int i = 0;
int j = 0;
while(i<len){
while(j < len && arr[j] != ' '){
j++;
}
if(j < len){
reverse(arr,i,j-1);
i = j+1;
j++;
} else {
reverse(arr,i,j-1);
i = j;
}
}
String return_Str = new String(arr);
System.out.println(return_Str);
}
}
二：字符串相关
链接：统计回文
1.题目
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：
- 在第一个字母之前: “baba” 不是回文
- 在第一个字母‘a’之后: “abba” 是回文
- 在字母‘b’之后: “abba” 是回文
- 在第二个字母’a’之后: “abab” 不是回文
所以满足条件的答案为2
2.解题
2.1思路分析
首先将字符串B插入到zifuchuanA的各个位置，提供两种思路：
1.使用字符串截取和拼接；
2.将String转化为StringBuffer，使用insert()方法。
然后判断，当前字符串是否是回文串，提供两种思路：
1.将当前字符串反转，判断是否与原来的字符串相同；
2.从两边开始，依次比较当前字符是否相同，直到比较到最中间的字符。
2.2代码实现
java代码
思路一：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int len = str1.length();
int n = 0;
for (int i = 0; i <= len; i++) {
// 将字符串2插入到字符串1的每个位置，再判断是否是回文
StringBuffer str = new StringBuffer(str1);
str.insert(i, str2);
//注意这里，不能直接StringBuilder str3 = str.reverse();
//因为这样str本身又变了。
StringBuilder tmp = new StringBuilder(str);
StringBuilder str3 = tmp.reverse();
if (str.toString().equals(str3.toString())) {
n++;
}
}
System.out.println(n);
}
}
注意：
1.reverse()会使str也翻转；
2.StringBuffer类对象不能直接用equals()比较，而是需要先用toString()进行转化。
思路二：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLine()){
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
int len1 = s1.length();
int len2 = s2.length();
int sum = 0;
for (int i = 0; i <= len1; i++) {
String start = s1.substring(0,i);
String end = s1.substring(i,len1);
String target = start+s2+end;
boolean flag = judgestr(target);
if(flag == true){
sum++;
}
}
System.out.println(sum);
}
}
private static boolean judgestr(String target) {
int len = target.length();
int i = 0;
int j = len-1;
while(i < j){
char c1 = target.charAt(i);
char c2 = target.charAt(j);
if(c1 != c2){
return false;
} else {
i++;
j--;
}
}
return true;
}
}
三：动态规划问题
链接：连续最大和
1.题目
描述
一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
输入描述：
输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。
输出描述：
所有连续子数组中和最大的值。
2.解题
2.1思路分析
典型的动态规划问题，关键是找到递推式。每次都寻找以array[i]结尾的最大和，遍历完整个数组后，找出所有最大和中最大的那个，就是问题的答案。
2.2代码实现
java代码
import java.util.Scanner;
public class Main {
public static int GetMax(int a, int b){
return (a) > (b) ? (a) : (b);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] array = new int[size];
for(int i = 0; i< size;i++) {
array[i] = scanner.nextInt();
}
int sum = array[0];
int max = array[0];
for(int i = 1;i < size;i++) {
sum = GetMax(sum + array[i], array[i]); //状态方程式
if (sum >= max)
max = sum;
}
System.out.println(max);
}
}
内容结束！
