京东笔试

1. 求非最大数字的个数

2. x可以拆成x-1,1 或 a,b (a*b=x) ; 将数组中每个数字全拆成1的最少次数 （考试时糊里糊涂的，最后没写完，考完以后用递归写了，不知道会不会超时）

import java.security.Principal;
import java.util.*;
public class Main {
    public static int getValue(int i){
        // 判断i最少多少次
        if(i==1){
            return 0;
        }
        int minValue = i-1;
        for(int j=2;j<=i/2;j++){
            if(i%j==0){
                if(minValue > getValue(j)+getValue(i/j)){
                    minValue  = getValue(j)+getValue(i/j)+1;
                }
            }
        }
        return minValue;

    } 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        int res = 0;
        List list = new LinkedList();
        for(int i = 0; i < n; i++){
            list.add(sc.nextInt()); 
        } 
        // 找到最小i+j，使得i*j = m 
        for(int i=0;i<n;i++){
            res += getValue(list.get(i));
        }
        System.out.println(res);
    }
}

3. 括号字符串所有子串的权值和（合法括号的个数*2），只过了22%,不知道为啥，超时？

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();
        int res = 0;
        // 长度为1的子串没有合法的，从2开始
        for(int i=0;i<n;i++){
            int flag = 0;
            int now = 0; // 现在权值
            for(int j=i;j<n;j++){
                char ch = s.charAt(j);
                if(ch=='('){
                    flag++;
                }
                else if(flag >= 1 && ch==')'){
                    now += 2;
                    flag--;
                }
                res += now;
            }
        }
        System.out.println(res);
    }
}

看了大佬的写法，tql,更新一下子

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();
        int res = 0;
        Stack<Integer> stack = new Stack<Integer>();
        // 考察每对括号对res的贡献
        for(int i=0;i<n;i++){
            char ch = s.charAt(i);
            if(ch=='('){
                stack.add(i);
            }
            else{
                res = res + 2*(stack.pop()+1)*(n-i);
            }
        }
        System.out.println(res);
    }
}