爱奇艺笔试第一题

老哥们第一题具体可以参考leetcode46题全排列我觉着差不多😂，我还没写第二题呢

同求代码

或者编程思路怎么弄？总不能全排列啊然后一个个排除啊。。也许有规律的吧

求第一题思路

暴力全排列只过了36%

😂

第一题暴力

dp可以过

两道题都只A了36%....以为是语言的问题，py换了CPP还是一样，放弃了

都只A了一点点 import java.util.*; import java.io.*; public class Main1 { public static void main(String[] args) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { int n = cin.nextInt(); int[] aNums = new int[n-1]; for (int i = 0; i < n-1; ++i) { aNums[i] = cin.nextInt(); } int[] sum = new int[1]; sum[0] = 0; List<Integer> tmp = new LinkedList<>(); genNums(n, tmp, sum, aNums); System.out.println(sum[0]); } } public static void genNums(int n, List<Integer> tmp, int[] sum, int[] aNums) { if (tmp.size() == n) { sum[0] = sum[0] + 1; } else { for (int i = 1; i < n+1; ++i) { if (!tmp.contains(i)) { if (check(tmp, i-1, aNums)) { tmp.add(i); genNums(n, tmp, sum, aNums); tmp.remove(tmp.size()-1); } } } } } public static boolean check(List<Integer> tmp, int i, int[] aNums) { if (tmp.isEmpty()) return true; int pre = tmp.get(tmp.size()-1); int index = tmp.size() - 1; if (aNums[index] == 0) { if (pre < i + 1) { return true; } } else { if (pre > i + 1) { return true; } } return false; } } # ac 27% def solver(n, m): def genNums(n, m, cur): nonlocal tmp, total, dem, retA if m == 0 and n == 0: dem += 1 if check(tmp): retA += 1 else: for i in range(cur, total): p = ['A', 'B', 'C'][cur % 3] if n > 0: tmp.append(p+'0') genNums(n-1, m, i+1) tmp.pop() if m > 0: tmp.append(p+'1') genNums(n, m-1, i + 1) tmp.pop() tmp = [] total = m + n dem = 0 retA = 0 genNums(n, m, 0) ret = float('%.5f' % (retA / dem)) return ret def check(tmp): retA = 0 for n in tmp: # print(n) if n[1] == '0' and n[0] == 'A': retA += 1 break elif n[1] == '0' and n[0] == 'B': break return retA