美团笔试 3.23

1.略

2.字符串删除若干字符后，保证没有长度为偶数的回文子串。思路：保证相邻两个字符不同即可。

3.长度为n的数组，只包含1到n，且每个元素不同。每个元素都被染成红色或白色。白色元素保持不动，红色元素可以两两调换，经过若干次调换，数组变成非递减排序，求最少得调换次数。
思路：非递减排序只能是1,2,3…n

4.字符串如“a(2)b(3)c(2)”，代表"aabbbcc"。并定义一个字符串的价值为：元素种类*字符串长度。给定一个字符串和一个价值k，问该字符串最多可以分割成多少个价值不低于k的子字符串。
思路：贪心

5.给定一棵树和两个节点s，t，现在需要从s走到t，每次经过一个节点，都会等概率选择下一个相邻节点，访问过的节点除外。问从s走到t的概率。
思路：想到用dfs，但一直没通过。