网易春招Java编程题

import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNextLine()){ String line = scanner.nextLine(); char[] ch = line.toCharArray(); System.out.println(process(ch)); } scanner.close(); } private static String process(char[] ch) { List<Integer> list = new ArrayList<Integer>(); StringBuilder sb = new StringBuilder(); int high = 0; //high代表遍历的上限 for (int i = 0; i < ch.length; i++) { if (ch[i] == 'g' || ch[i] == '9') { list.add(i); high = high * 2 + 1 ; } } for (int i = 0; i <= high; i++) { for (int j = 0; j < list.size(); j++) { if (((i>>>j)&1) != 0) { ch[list.get(j)] = '9'; }else { ch[list.get(j)] = 'g'; } } sb.append(new String(ch)+","); } return sb.toString(); } } 我的代码。

简单的话递归就能写吧

全排列做

动态规划吧。。。

我思路是 先扫一遍字符串，统计9的个数，记为n，并将其下标存于一个长度为n的int数组里，记为index[]；可以看出问题的规模为2^n，所以n不会太大。。 如果n < 32，就可以用一个32位int的二进制来表示9和g的分布，相当于0和1，只要用位运算找到这个int整形数中1的分布，去index数组里去处下标，将对应的9改为g即可。。 for(int i = 0; i < 2^n; i++) { _str = str; //取一个源字符串的副本 for(int j = 0; j < n; j++) { //这里j不用取到32，因为i最大为2^n - 1   if((i & (1<<j) != 0) {//表明这一位上是1. _str[j] = 'g'; } } sysout(_str);//输出 }

我也做的这一题，‘g’和'9'相当于二进制0和1。 比如说两个位置，那么所有情况用二进制表示就是 00 01 10 11。换成g和9就相当于gg g9 9g 99。 思路就是先记录下g和9出现的位置。比如g和9共出现n次，那么就是分别判断从0到2^n  - 1这些数字的二进制表示中哪些位是0 哪些位是1。是0的位置用g代替，是1的位置用9代替，然后再修改原字符串。

要是这样连续的话，可以先分割，然后将9和g的部分使用全排列，再将全排列的结果加上其余部分