京东编程题Java岗编程题题解

思路可见博客：https://blog.csdn.net/carson0408/article/details/79873042

1.回文子串个数(暴力法超时，dp可解)

import java.util.ArrayList;
import java.util.Scanner;


public class Palindarome {
    //动态规划
    public static long solve1(String s)
    {
        int len=s.length();
        long[][] dp=new long[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];
            }
        }
        return dp[1][len];
    }
    //暴力求解
    public static int solve(String s) {  
        ArrayList<String> result = new ArrayList<String>();
        ArrayList<ArrayList<String>> lists=new ArrayList<>();
        for (int i = 1; i <= s.length(); i++) {  
            solution(s, i, result,lists);  
        }
        int ans=0;
        ArrayList<String> arrayList;
        for(int i=0;i<lists.size();i++)
        {
            arrayList=lists.get(i);
            
            if(isPalindrome(arrayList, 0, arrayList.size()-1))
                ans++;
            
        }
        return ans;
    }  
  
    public static void solution(String s, int m, ArrayList<String> result,ArrayList<ArrayList<String>> lists) {  
    
        if (m == 0) {  
            lists.add(new ArrayList<>(result));
             
            return;  
        }  
  
        if (s.length() != 0) {  
            // 选择当前元素  
            result.add(s.charAt(0) + "");  
            solution(s.substring(1, s.length()), m - 1, result,lists);  
            result.remove(result.size() - 1);  
            // 不选当前元素  
            solution(s.substring(1, s.length()), m, result,lists);  
        }  
    }  
 


    public static boolean isPalindrome(ArrayList<String> sb, int left, int right) {
        while (left <= right && sb.get(left).equals(sb.get(right)) ) {
            left++;
            right--;
        }
        if(left>right)
            return true;
        return false;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String string = sc.nextLine();
        System.out.println(solve1(string));
    }
    
}

2.拆分数字(注意数据范围，用long)

import java.util.Scanner;

public class Split {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner =new Scanner(System.in);
        int t=scanner.nextInt();
        for(int i=0;i<t;i++)
        {
            long N=scanner.nextLong();
            if(N%2==1)
                System.out.println("No");
            else {
                long Y=2;
                long X=N/2;
                while(X%2==0)
                {
                    Y*=2;
                    X/=2;
                }
                System.out.println(X+" "+Y);
            }
        }

    }

}

3.括号匹配(注意题目中的必须操作一次，当且仅当一次，有的没考虑必须操作一次的，可能只能90%)

import java.util.Scanner;


public class Brackets {
    public static String solve(String string)
    {
        int ls=string.length();
        int ans=0;
        int left=0;
        int right=0;
        boolean flag=false;
        for(int i=0;i<ls;i++)
        {
            if(string.charAt(i)=='(')
                left+=1;
            if(string.charAt(i)==')')
                right+=1;
            
            if(ans==2&&right-left==0)//考虑"))(("系列，比如"))((()"
                flag=true;
            if(flag)
            {
                if(right-left>0)
                    return "No";
            }
            ans=Math.max(ans, right-left);
            if(ans>2)
                return "No";
        }
        if(string.equals(")("))//考虑")(+合理"系列，比如“)(()”、"())(()"
            return "Yes";
        if(left==right&&ans<=2&&left>=2)
            return "Yes";
        return "No";
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        for(int i=0;i<t;i++)
        {
            String string=scanner.next();
            System.out.println(solve(string));
        }

    }

}

#笔试题目#