# 生成回文串

## 思路

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]);
}
}

# 整数分解

2

10

5

5 2

No

## 代码实现

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;
}
}
}
}
}
}

# 牛牛的括号匹配

## 代码实现

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;
}
}

126 篇文章39 人订阅

0 条评论

## 相关文章

### web 直播流的解析

Web 进制操作是一个比较底层的话题，因为平常做业务的时候根本用不到太多，或者说，根本用不到。那什么情况会用到呢？ canvas、websocket、file....

8922

### 34:回文子串

34:回文子串 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个字符串，输出所有长度至少为2的回文子串。 回文子串即从左往右输出和从右往...

3756

2925

### 数字的陷阱

Java中对数字的处理，如四舍五入，如加减乘除，貌似是一个很基础很简单的知识点，但是如果你没有对他进行充分了解，很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

1918

1246

### 洛谷 P1598 垂直柱状图【字符串+模拟】

P1598 垂直柱状图 题目描述 写一个程序从输入文件中去读取四行大写字母（全都是大写的，每行不超过72个字符），然后用柱状图输出每个字符在输入文件中出现的次数...

3115

### [十七]基础类型BigDecimal简介

BigDecimal表示的数为: unscaledValue × 10的-scale 次幂

1133

2482

1161

1142