时间线：3.14 一面3.22 二面3.28 三面4.01 四面4.10 oc

时间线：3.21 一面3.27 二面4.01 oc

题目：给定一棵树，每个节点值为0或1，每次操作可以选择一个节点，将其值与1异或，并且所有与该节点距离为偶数的节点的值也与1异或。问最少需要多少次操作，可以使所有节点值都为0？思路：1. 随意选择一个节点作为根节点，根节点的高度为0，是偶数，则其他所有节点都有一个高度，高度的奇偶性可以确定。2. 如果一个节点值为0，则与1异或后，节点值变为1；反之亦然。所以，节点值与1异或其实就是做了翻转操作。3. 如果有两个同一条路径上的高度为奇数（或偶数）的节点都做了翻转操作，则该路径上接下来高度为奇数（或偶数）的节点不需要翻转。所以可以采用DFS，用一个变量oddReverse表示奇数高度的节点需要翻转，另一个变量evenReverse表示偶数高度的节点需要翻转。遍历当前节点时，首先判断当前节点的高度是奇数还是偶数。以奇数为例，如果oddReverse为真，如果节点本身是1，则正常翻转即可，如果节点本身是0，则翻转后变为1不符合要求，所以需要再次翻转，即操作次数加1，oddReverse变为假；如果oddReverse为假，如果节点本身是1，则需要翻转，即操作次数加1，oddReverse变为真，如果节点本身是0，则不需要翻转。最后遍历所有子节点，将高度加1，oddReverse和evenReverse作为参数传递进递归函数。

题目：给定一个仅由'0'和'1'组成的字符串，分别求长度为奇数和偶数的子串压缩后是回文串的个数，字符串压缩是指将连续且相同的字符仅保留1个，例如011000110压缩后为01010，是回文串。思路：如果一个子串两端的字符相同，则压缩后一定是回文串，否则，压缩后一定不是回文串。所以通过一次遍历，用4个变量记录遍历中遇到的奇数位和偶数位的'0'和'1'的个数，再根据当前位的奇偶性和值，给结果增加对应的数值即可。时间复杂度为O(n)。补充解释：例如当前位是奇数位，且值为'0'，之前已经记录的奇数位且值为0的个数是odd0，偶数位且值为'0'的个数是even0，则到目前为止odd0变为odd0+1，even0不变。然后要返回的结果中，奇数长度的回文串的个数加上odd0，偶数长度的回文串的个数加上even0。