#软件开发笔面经#第一题 贪心:public static void Q1(int n, int k) { StringBuilder sb = new StringBuilder(); for (int i = 0; i if (i sb.append(i + 1); } else { sb.append(n + k - i - 1); } if (i != n) { sb.append(" "); } } System.out.println(sb.toString());}第二题: 暴力超时,改成dp,记录以每个i为结尾的奇偶个字符串的奇偶次变化的数目public static void Q2(int n, String str) { int rs = 0; int[][][] dp = new int[n][2][2]; for (int i = 0; i if (i == 0) { dp[i][1][1] = 0; dp[i][1][0] = 1; continue; } if (str.charAt(i) != str.charAt(i - 1)) { dp[i][1][1] = dp[i - 1][0][0]; dp[i][1][0] = dp[i - 1][0][1] + 1; dp[i][0][1] = dp[i - 1][1][0]; dp[i][0][0] = dp[i - 1][1][1]; } else { dp[i][1][1] = dp[i - 1][0][1]; dp[i][1][0] = dp[i - 1][0][0] + 1; dp[i][0][1] = dp[i - 1][1][1]; dp[i][0][0] = dp[i - 1][1][0]; } } for (int i = 0; i if (str.charAt(i) == '1') { rs += dp[i][1][1]; } else { rs += dp[i][1][0]; } } System.out.println(rs); }第三题:极限最后两分钟做完,一直在模拟各种情况,纯纯屎山,自己都看不懂了public static long Q3(long m, long n, long k) { if (m == 1) { return n > k ? n - k : 0; } long rs = n * Q3(m - 1, n); String kStr = String.valueOf(k); if (kStr.length() return rs; } if (kStr.length() > m) { return 0; } HashSet set = new HashSet<>(); for (int i = 0; i long count = 0; boolean con = true; for (int j = 0; j if (j == 0 && i == 0) { continue; } if (set.contains(j)) { continue; } if (j >= (kStr.charAt(i) - '0')) { set.add(j); con = false; if (j != (kStr.charAt(i) - '0')) { rs -= count * Q3(m - i - 1, n - i); return rs; } if(m == i + 1){ count++; } break; } else { count++; } } rs -= count * Q3(m - i - 1, n - i); if(con){ break; } } return rs; } public static long Q3(long m, long n) { if(m == 0){ return 1; } long rs = 1; while (m > 0) { rs = rs * n; n--; m--; } return rs; }第四题 贪心从最右边开始减:public static long Q4(int n, int k, long sum, long[] a) { long rs = 0; long tmp = 0; for (int i = 0; i tmp += a[i]; } for (int i = k - 1; i if (i != k - 1) { tmp -= a[i - k]; } tmp += a[i]; int j = i; while (tmp > sum) { long minus = Math.min(a[j], tmp - sum); rs += minus; tmp -= minus; a[j] -= minus; j--; } } return rs; }