生成回文串

題目描述

對(duì)于一個(gè)字符串，從前開始讀和從后開始讀是一樣的，我們就稱這個(gè)字符串是回文串。

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

牛牛特別喜歡回文串，他手中有一個(gè)字符串s,牛牛在思考能否從字符串中移除部分(0個(gè)或多個(gè))字符使其變?yōu)榛匚拇?#xff0c;并且牛牛認(rèn) 為空串不是回文串。

牛牛發(fā)現(xiàn)移除的方案可能有很多種，希望你來幫他計(jì)算一下一共有多少種移除方案可以使s變?yōu)榛匚拇?#xff0c;對(duì)于兩種移除方案如果移除的字符依次構(gòu)成的序列不一樣就是不同的方法。

輸入描述

輸入包括一個(gè)字符串s(1 <= iength(s) <= 50)，s中只包含大寫字母。

輸出描述

對(duì)于每個(gè)測(cè)試用例，輸出一個(gè)正整數(shù)表示方案數(shù)。

思路

dp[l][r]表示區(qū)間 [l, r] 內(nèi)的回文串?dāng)?shù)目。于是dp[l][r] = dp[l][r - 1] + dp[l + 1][r],根據(jù)s[l] 是否等于 s[r], 來看是+1還是減掉重復(fù)的部分。

代碼實(shí)現(xiàn)

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;elsedp[l][r] -= dp[l + 1][r - 1];}}System.out.println(dp[1][len]);} }

整數(shù)分解

題目描述

小Q的數(shù)學(xué)老師給了小Q一個(gè)整數(shù)N,問小Q能否將W分解為兩個(gè)整數(shù)X和Y相乘，并且滿足X為奇數(shù)，Y為偶數(shù)，即能否找到奇數(shù)X和偶數(shù)Y滿足X * Y = N,小Q被這個(gè)問題難住了，希望能你來幫助他計(jì)算。

輸入描述:

輸入的第一行包含一個(gè)正整數(shù)t( 1<= t <= 1000 )，表示測(cè)試樣例數(shù)。接下來的t行，每行一個(gè)正整數(shù)N (2 <= N < 2^63)，表示給出的N。保證不是2的冪次。

輸出描述:

如果能找到這樣的X，Y,則依次輸出X,Y,如果有多解輸出Y最小的那組解，以空格分割,否則輸出"No"。

示例1

輸入

2

10

5

輸出

5 2

No

思路

先判斷N是不是奇數(shù)，是的話直接返回No，然后Y從2開始，每次乘2，判斷X是不是奇數(shù)。

代碼實(shí)現(xiàn)

package jingdong.demo2;import java.util.Scanner;/*** 整數(shù)分解* 先判斷N是不是奇數(shù)，是的話直接返回No* 然后Y從2開始，每次加2，判斷X是不是奇數(shù)*/ 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;}}}}} }

牛牛的括號(hào)匹配

題目記不清了，和HDU 5831差不多。

思路

用一個(gè)計(jì)數(shù)量 cnt 統(tǒng)計(jì)左括號(hào)數(shù)量就行，匹配到右括號(hào)，就另 cnt--，如果 cnt < 0 就認(rèn)為不匹配。其次，如果左括號(hào)數(shù)不等于右括號(hào)數(shù)，可以直接認(rèn)為不匹配，不進(jìn)行計(jì)算。

代碼實(shí)現(xiàn)

package jingdong.demo3;import java.util.*;/*** 牛牛的括號(hào)匹配*/ 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;} }

轉(zhuǎn)載于:https://www.cnblogs.com/wupeixuan/p/8765934.html

總結(jié)

以上是生活随笔為你收集整理的京东2019春招Java工程师编程题题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。