leetcode209，leetcode1202

1. 竞赛共有4道题，其中必须完成3道。第一题我通过了一次，但是第二题因为数组的开位置不对而尴尬了一段时间，但是在模拟第三题的时候突然想出了正确答案，直接调试就通过了。多少次。上次调试时间有点长，没时间看第四题，就放弃了。

2. 如果我们拆分两个字符串并得到回文，我们会得到两个长度相同的字符串a 和b。选择一个下标来分隔具有相同下标的两个字符串。从a我们得到两个满足a=aprefix + asuffix的字符串aprefix和asuffix，同样从b我们得到满足b=bprefix + bsuffix的两个字符串bprefix和bsuffix。判断aprefix + bsuffix 或bprefix + asuffix 能否构成回文串。

将字符串s 拆分为sprefix 和ssuffix 时，ssuffix 或sprefix 可以为空。例如， s='abc' 那么'' + 'abc' 、 'a' + 'bc' 、 'ab' + 'c' 和'abc' + '' 都是合法分区。

如果可以形成回文字符串，则返回true，否则返回false。

请注意，x + y 表示字符串x 和y 的串联。

示例1：

输入：a='x'，b='y'

输出：真

解释：如果a 或b 是回文，则答案一定为真，因为它可以如下拆分：

前缀=''，后缀='x'

bprefix='', bsuffix='y'

在这种情况下，aprefix + bsuffix='' + 'y'='y' 是一个回文字符串。

示例2：

输入：a='ulacfd'，b='jizalu'

输出：真

描述：按索引3 拆分：

前缀='ula'，后缀='cfd'

b前缀='jiz', b后缀='alu'

那么aprefix + bsuffix='ula' + 'alu'='ulaalu' 就是一个回文字符串。

暗示：

1=a.length, b.length=105a.length==b.length a 和b 都只包含小写字母。 2.4 统计子树中城市之间的最大距离（我们放弃）给我们从1开始编号的n个城市。到n.同时，我们得到一个大小为n-1 的数组边。这里edges[i]=[ui, vi]表示城市ui和vi之间有一条双向边。这个问题确保任何城市之间只存在一条路线。换句话说，所有的城市都是一棵树。

子树是城市的子集，子集中的任何城市都可以通过子集中的其他城市或边到达。如果两个子树中至少有一个城市存在于其中一个子树中而另一个子树中不存在，则认为两个子树是不同的。

对于从1 到n-1 的d，求城市间最大距离恰好为d 的所有子树的数量。

返回大小为n-1 的数组。这里，第d个元素（下标从1开始）是城市之间最大距离恰好等于d的子树的数量。

请注意，两个城市之间的距离定义为需要在它们之间通过的边的数量。

示例1：

输入：n=4，边=[[1,2],[2,3],[2,4]]

输出：[3,4,0]

解释：子树{1,2}、{2,3} 和{2,4} 的最大距离为1。

子树{1,2,3}、{1,2,4}、{2,3,4} 和{1,2,3,4} 的最大距离为2。

城市之间不存在最大距离为3 的子树。

示例2：

输入：n=2，边=[[1,2]]

输出：[1]

示例3：

输入：n=3，边=[[1,2],[2,3]]

输出：[2,1]

暗示：

2=n=15edges.length==n-1edges[i].length==21=ui, vi=n 在这个问题中，我们验证(ui, vi) 表示的边彼此不同。 3. 想法

使用模拟来解决这个问题会使分离字符串变得很麻烦。当然，我一开始就是这么做的。

在同一位置剪切两个字符串a 和b，然后再次将它们连接起来。例如，原词是mn和xy，但拼写为my和nx。

所以我们从字符串a的左侧和字符串b的右侧开始遍历。

同样，从字符串a的右侧和字符串b的左侧开始遍历。

4 代码类解决方案{public: string sa1,sa2,sb1,sb2; string s1,s2; bool checkPalindromeFormation(string a, string b) { if(a.length()==1)return true; int case1=0,case2=0; for(int i=0;i0; }};