生成回文串

题目描述

对于一个字符串，从前开始读和从后开始读是一样的，我们就称这个字符串是回文串。

例如"ABCBA","AA","A"是回文串，而"ABCD","AAB"不是回文串。

牛牛特别喜欢回文串，他手中有一个字符串s,牛牛在思考能否从字符串中移除部分(0个或多个)字符使其变为回文串，并且牛牛认 为空串不是回文串。

牛牛发现移除的方案可能有很多种，希望你来帮他计算一下一共有多少种移除方案可以使s变为回文串，对于两种移除方案如果移除的字符依次构成的序列不一样就是不同的方法。

输入描述

输入包括一个字符串s(1 <= iength(s) <= 50)，s中只包含大写字母。

输出描述

对于每个测试用例，输出一个正整数表示方案数。

思路

dp[l][r]表示区间 [l, r] 内的回文串数目。于是dp[l][r] = dp[l][r - 1] + dp[l + 1][r],根据s[l] 是否等于 s[r], 来看是+1还是减掉重复的部分。

代码实现

package jingdong.demo1;
import java.util.Scanner;
/**
 * 生成回文串
 */
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = 0; i <= len; i++)
            dp[i][i] = 1;
        for (int i = 2; i <= len; i++) {
            for (int l = 1; l <= len - i + 1; l++) {
                int r = l + i - 1;
                dp[l][r] += dp[l + 1][r];
                dp[l][r] += dp[l][r - 1];
                if (s.charAt(l - 1) == s.charAt(r - 1))
                    dp[l][r] += 1;
                else
                    dp[l][r] -= dp[l + 1][r - 1];
            }
        }
        System.out.println(dp[1][len]);
    }
}

整数分解

题目描述

小Q的数学老师给了小Q一个整数N,问小Q能否将W分解为两个整数X和Y相乘，并且满足X为奇数，Y为偶数，即能否找到奇数X和偶数Y满足X * Y = N,小Q被这个问题难住了，希望能你来帮助他计算。

输入描述:

输入的第一行包含一个正整数t( 1<= t <= 1000 )，表示测试样例数。接下来的t行，每行一个正整数N (2 <= N < 2^63)，表示给出的N。保证不是2的幂次。

输出描述:

如果能找到这样的X，Y,则依次输出X,Y,如果有多解输出Y最小的那组解，以空格分割,否则输出"No"。

示例1

输入

2

10

5

输出

5 2

No

思路

先判断N是不是奇数，是的话直接返回No，然后Y从2开始，每次乘2，判断X是不是奇数。

代码实现

package jingdong.demo2;
import java.util.Scanner;
/**
 * 整数分解
 * 先判断N是不是奇数，是的话直接返回No
 * 然后Y从2开始，每次加2，判断X是不是奇数
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        long[] arr = new long[t];
        for (int i = 0; i < t; i++) {
            arr[i] = sc.nextLong();
        }
        for (long N : arr) {
            if (N % 2 != 0) {
                System.out.println("No");
                break;
            }
            long X;
            long Y;
            for (int i = 1; i <= N / 2; i++) {
                Y = i * 2;
                if (N % Y == 0) {
                    X = N / Y;
                    if (X % 2 != 0) {
                        System.out.println(X + " " + Y);
                        break;
                    }
                }
            }
        }
    }
}

牛牛的括号匹配

题目记不清了，和HDU 5831差不多。

思路

用一个计数量 cnt 统计左括号数量就行，匹配到右括号，就另 cnt--，如果 cnt < 0 就认为不匹配。其次，如果左括号数不等于右括号数，可以直接认为不匹配，不进行计算。

代码实现

package jingdong.demo3;
import java.util.*;
/**
 * 牛牛的括号匹配
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        while (N-- > 0) {
            String s = in.next();
            char[] chars = s.toCharArray();
            System.out.println(check(chars) ? "Yes" : "No");
        }
    }
    private static boolean check(char[] chars) {
        int lCnt = 0, rCnt = 0;
        for (char c : chars) {
            if (c == '(') lCnt++;
            else rCnt++;
        }
        if (lCnt != rCnt) return false;
        for (int i = 1; i < chars.length; i++) {
            for (int j = 0; j < i; j++) {
                swap(chars, i, j);
                if (isPalindrome(chars)) return true;
                swap(chars, i, j);
            }
        }
        return false;
    }
    private static boolean isPalindrome(char[] chars) {
        int cnt = 0;
        for (char c : chars) {
            if (c == '(') cnt++;
            else {
                if (cnt <= 0) return false;
                cnt--;
            }
        }
        return cnt == 0;
    }
    private static void swap(char[] chars, int i, int j) {
        char t = chars[i];
        chars[i] = chars[j];
        chars[j] = t;
    }
}