阿里（淘天）一面笔试算法原题

阿里撤资 "车来了"

近日，国内实时公交产品"车来了"关联公司武汉元光科技有限公司发生工商变更，阿里巴巴（中国）网络技术有限公司退出股东行列。

这很好理解，符合近期阿里收缩战线的行为一致性。

毕竟自己一手打造的"饿了么"都被数次传出「摆上货架」的消息。

那些被阿里投资的项目，自然更是首当其冲。

但阿里这个级别的公司，容易造成领头羊效应，成为引发雪崩的第一个初始雪球。

那些前期被阿里领投，现如今可能不是自身业务问题，但却遭遇阿里撤资的项目，失去的可能并不只是阿里的投资，大概率还会包括那些前期跟随大公司步伐进行跟投的资金。

一个企业目前没有稳定的盈利业务（仅政企 + 广告），可能还是靠融资活着，如果原计划的资金超过 30% 不能及时到位，意味着资金链断裂，公司只能是面临裁员，甚至破产倒闭。

考虑到"车来了"是轻资产类型的公司，因此大胆预计近期会发生裁员，再撑一段时间。

后续如果没有特别变化的话，比较好的出路应该会被其他互联网巨头收购，作为地位比地图低两个档次的基础设施而存在。

但说句很残忍的话，如果真的沦落到被收购，大概率会被贱卖，目前比较好的潜在卖家腾讯、百度、字节。

...

回归主线，来一道读者投稿的「阿里」一面算法原题。

读者反馈，阿里的题面并不如此，但意思和解法完全一致，属于换皮原题。

题目描述

平台：LeetCode

题号：1457

给你一棵二叉树，每个节点的值为 1 到 9 。

我们称二叉树中的一条路径是「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。

请你返回从根到叶子节点的所有路径中伪回文路径的数目。

示例 1：

输入：root = [2,3,1,3,1,null,1]

输出：2 

解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
     在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。

示例 2：

输入：root = [2,1,1,1,3,null,null,null,null,null,1]

输出：1 

解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
     这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。

示例 3：

输入：root = [9]

输出：1

提示：

给定二叉树的节点数目在范围 $[1, 10^5]$ 内
$1 <= Node.val <= 9$

DFS + 位运算

“伪回文”是指能够通过重新排列变成“真回文”，真正的回文串只有两种情况：

长度为偶数，即出现次数为奇数的字符个数为 $0$ 个
长度为奇数，即出现次数为奇数的字符个数为 $1$ 个（位于中间）

因此，我们只关心路径中各个字符（数字 0-9）出现次数的奇偶性，若路径中所有字符出现次数均为偶数，或仅有一个字符出现次数为奇数，那么该路径满足要求。

节点值范围为 $[1, 9]$ ，除了使用固定大小的数组进行词频统计以外，还可以使用一个 int 类型的变量 cnt 来统计各数值的出现次数奇偶性：若 $cnt$ 的第 $k$ 位为 $1$ ，说明数值 $k$ 的出现次数为奇数，否则说明数值 $k$ 出现次数为偶数或没出现过，两者是等价的。

例如 $cnt = (0001010)_2$ 代表数值 $1$ 和数值 $3$ 出现次数为奇数次，其余数值没出现过或出现次数为偶数次。

翻转一个二进制数字中的某一位可使用「异或」操作，具体操作位 cnt ^= 1 << k。

判断是否最多只有一个字符出现奇数次的操作，也就是判断一个二进制数字是为全为 $0$ 或仅有一位 $1$ ，可配合 lowbit 来做，若 cnt 与 lowbit(cnt) = cnt & -cnt 相等，说明满足要求。

考虑到对 lowbit(x) = x & -x 不熟悉的同学，这里再做简单介绍：lowbit(x) 表示 x 的二进制表示中最低位的 $1$ 所在的位置对应的值，即仅保留从最低位起的第一个 $1$ ，其余位均以 $0$ 填充：

x = 6，其二进制表示为 $(110)_2$ ，那么 $lowbit(6) = (010)_2 = 2$
x = 12，其二进制表示为 $(1100)_2$ ，那么 $lowbit(12) = (100)_2 = 4$

Java 代码：

class Solution {
    int ans = 0;
    public int pseudoPalindromicPaths (TreeNode root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode root, int cnt) {
        if (root.left == null && root.right == null) {
            cnt ^= 1 << root.val;
            if (cnt == (cnt & -cnt)) ans++;
            return ;
        }
        if (root.left != null) dfs(root.left, cnt ^ (1 << root.val));
        if (root.right != null) dfs(root.right, cnt ^ (1 << root.val));
    }
}

C++ 代码：

class Solution {
public:
    int ans;
    int pseudoPalindromicPaths(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* root, int cnt) {
        if (!root->left && !root->right) {
            cnt ^= 1 << root->val;
            if (cnt == (cnt & -cnt)) ans++;
            return;
        }
        if (root->left) dfs(root->left, cnt ^ (1 << root->val));
        if (root->right) dfs(root->right, cnt ^ (1 << root->val));
    }
};

Python 代码：

class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(root, cnt):
            nonlocal ans
            if not root.left and not root.right:
                cnt ^= 1 << root.val
                ans += 1 if cnt == (cnt & -cnt) else 0
                return 
            if root.left:
                dfs(root.left, cnt ^ (1 << root.val))
            if root.right:
                dfs(root.right, cnt ^ (1 << root.val))
        dfs(root, 0)
        return ans

TypeScript 代码：

function pseudoPalindromicPaths (root: TreeNode | null): number {
    let ans = 0;
    const dfs = function (root: TreeNode, cnt: number): void {
        if (root.left == null && root.right == null) {
            cnt ^= 1 << root.val;
            if (cnt == (cnt & -cnt)) ans++;
            return ;
        }
        if (root.left) dfs(root.left, cnt ^ (1 << root.val));
        if (root.right) dfs(root.right, cnt ^ (1 << root.val));
    }
    dfs(root, 0);
    return ans;
};

时间复杂度： $O(n)$
空间复杂度： $O(\log{n})$

我是宫水三叶，每天都会分享算法题解，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉