腾讯音乐笔试4道题

1、一颗二叉树，节点权值各不相同，每次操作可以交换任意两个节点的权值，要使得二叉树先序遍历的序列为一个升序数组，求最小操作次数，节点数量小于10^5

2、n个数ai，构造长为n的数组，满足相邻两个数之和都是素数，共有多少种不同的数组构造方案，1<=n<=12，1<=ai<=10^9,
3、一个仅由“red”三种字符组成的字符串，将'r'变为'e'，'e'变为'd'，'d'变为'r'，返回变化后的字符串，字符串长度小于10^5
4、定义一个数为“好数”，当且仅当该数的数位中，奇数的个数等于偶数，如“3368”是一个好数，求区间[L, R]的好数个数，其中1<=l<=r<=10^18
菜鸟只A出来第三题😅

- 第一题我想的是先把整棵树先序遍历一遍得到一个先序数组（原），然后将该数组排序（新），排序后与原数组挨个比较，如 {1,3,2} 中1不动，交换2和3的位置只操作一次，{2,3,1}需要依次交换（2,3）和（3,1），需要操作两次，，，结果思路是错的只过了测试用例
- 第二题我想的是permutation+剪枝，先用dfs求排列数，期间如果(i,j)交换位置后使得(i-1,i) (i,i+1) (j-1,j) (j,j+1)位置上的数之和不为素数，则提前返回，但是没想到如果i==j的情况该怎么破，交换也不是不交换也不是，噶在这儿了（可能还是思路有问题）
- 第三题暴力遍历没什么好说的
- 第四题听说是动态规划，找规律也没找到，只发现了二、四、六等偶数位数的数可以构成好数，10-99有45个，1000-9999有3375个，但没找到规律....