京东2019春招Java工程师编程题题解

生成回文串

题目描述

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

例如"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;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯IVWEB团队的专栏

web 直播流的解析

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

8922
来自专栏数据结构与算法

34:回文子串

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

3756
来自专栏Java学习123

JAVA实现精确的加减乘除

2925
来自专栏java达人

数字的陷阱

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

1918
来自专栏mySoul

设计模式 里氏替换原则

在场景中,三毛需要什么枪支,就直接new 出一个枪支即可,然后其内通过抽象类获取到对象,然后对齐进行修饰

1246
来自专栏小樱的经验随笔

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

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

3115
来自专栏noteless

[十七]基础类型BigDecimal简介

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

1133
来自专栏wym

字符串--最长回文子串(暴力讲解+Manacher)

问题描述:给你一个字符串str,若子串s是回文串,则称s为str的回文子串,求s的最大长度

2482
来自专栏移动开发面面观

基于OpenGLES的Android相机预览

随着AR效果越来越普及,摄像头在Android中的应用越来越重要。通常摄像头的预览方案,通常使用SurfaceView的方案。

1161
来自专栏闻道于事

Java工具类之浮点精确计算

1142

扫码关注云+社区

领取腾讯云代金券