算法训练---Day2

一：逆置字符串

链接：逆置字符串

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

二：字符串相关

链接：统计回文

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意：

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

三：动态规划问题

链接：连续最大和

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

内容结束！