招商银行信用卡2018春季招聘研发(第一批)编程题

题目一

给出一个非空字符串，判断这个字符串是否是由它的一个子串多次首尾拼接构成的。

输入描述：

非空字符串

输出描述：

如果字符串满足上述条件，则输出最长的满足条件的子串；如果不满足条件，则输出false。

样例

in:

abcabc

out:

abc

解析

枚举子串的长度，从串长减一枚举到一，然后在数组中循环判断就行了，核心代码：

str.charAt(i) == str.charAt(i % ans)

代码

import java.util.*;
public class Main {
   public Scanner cin = new Scanner(System.in);
   Main() {
       while (cin.hasNext()) {
           String str = cin.next();
           int ans = str.length() - 1;
           for (int i = 0; ans > 0; ans--) {
               for (i = 0; str.length() % ans == 0 && i < str.length()
                       && str.charAt(i) == str.charAt(i % ans); i++) {
               }
               if (i == str.length())
                   break;
           }
           System.out.println(ans != 0 ? str.substring(0, ans) : "false");
       }
   }
   public static void main(String[] args) {
       new Main();
   }
}

题目二

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[

 "((()))",

 "(()())",

 "(())()",

 "()(())",

 "()()()"

]

输入描述：

输入为1个正整数

输出描述：

输出为所有合法的字符串，用英文逗号隔开

样例

in:

2

out:

(()),()()

解法一：

class Solution {
public:
   vector<string> generateParenthesis(int n) {
       this->n = n;
       vector<string> ret;
       dfs(0, 0, 0, "", ret);
       return ret;
   }
private:
   int n;
   void dfs(int x, int l, int r, string str, vector<string> &ret)
   {
       if (x == 2 * n) {
           ret.push_back(str);
           return ;
       }
       if (l < n)
           dfs(x + 1, l + 1, r, str + "(", ret);
       if (r < n && l > r)
           dfs(x + 1, l, r + 1, str + ")", ret);
   }
};

解析

给出一个整数n，那么生成的合法括号串的长度是2 * n，那么运用递归去枚举每个位置上的可能出现的字符(，)，枚举的时候要注意，当前位置可以放(，但是能不能放)就要看到目前为止放了多少个)，如果(的个数比)多，那么当前位置就可以放)，这其实和用栈验证括号串的合法性的思想是一样的。

解法二：

import java.util.*;
public class Main {
   public Scanner cin = new Scanner(System.in);
   public int n;
   public ArrayList<String> ans = new ArrayList<String>();
   public void dfs(int x, int l, int r, String str) {
       if (x == 2 * n) {
           ans.add(str);
           return ;
       }
       if (l < n)
           dfs(x + 1, l + 1, r, str + "(");
       if (r < n && l > r)
           dfs(x + 1, l, r + 1, str + ")");
   }

   Main() {
       while (cin.hasNext()) {
           n = cin.nextInt();
           ans.clear();
           dfs(0, 0, 0, "");
           for (int i = 0; i < ans.size(); i++)
               System.out.print(ans.get(i) + (i != ans.size() - 1 ? "," : "\n"));
       }
   }

   public static void main(String[] args) {
       new Main();
   }
}

题目三

给出一个整数n，将n分解成至少两个整数之和，使得这些整数的乘积最大化，输出能获得的最大的乘积。

输入描述：

输入为一个整数

输出描述：

输出为一个整数

样例

in:

10

out:

36

解析

这个题还是要一丁点数学知识的，给你一个数n = a + b，a * b何时最大，那必然是a和b尽量靠近时才最大，现在这个n可以分解成多个数字相加，那么这些数字相乘什么时候最大呢，和两个数字一样，这些数字肯定也是都靠在一起才最大，什么叫靠在一起呢，就是任意两个数只差的绝对值小于等于1，那么这些数字必然可以分解成x, x, x, ...,x + 1, x + 1, ...这种形式。这么一想，这个代码就好写了，枚举其中的从1到n / 2枚举x，先看看可以分解成多少个数字，结果是n / x，还剩下n % x，把n % x一个一个分配到之前的x中，这里要特别注意，n % x有可能大于n / x，这说明，把n % x分配完，还有剩下的，不符合要求，而且这种情况肯定会在枚举x = x + 1时会处理，因此过滤掉这种x就行了。

代码

import java.util.*;
public class Main {
   public Scanner cin = new Scanner(System.in);

   Main() {
       while (cin.hasNext()) {
           long n = cin.nextLong(), ans = n / 2 * (n - n / 2);
           for (int i = 1; i <= n / 2; i++) {
               if (n / i <= n % i)
                   continue;
               ans = (long) Math.max(ans, Math.pow(i + 1, n % i) * Math.pow(i, n / i - (n % i)));
           }
           System.out.println(ans);
       }
   }

   public static void main(String[] args) {
       new Main();
   }
}