Derolol Blog

2024 360 秋招提前批 最大曼哈顿距离

给定一个包含若干个点的集合，求其中任意两点之间的最大/最小曼哈顿距离。

题解

由上述式子可得：

整理合并可得：

所以，问题转换为比较点和点的横纵坐标和与差。 在遍历各个点的时候分别计算横纵坐标的和与差，且分别排序。 将最大值减去最小值得到两种情况下的最大曼哈顿距离，然后再从中选择最大的曼哈顿距离作为最终答案。

vector<int> d1;
vector<int> d2;
for (int i = 0; i < points.size(); i ++)
    d1.push_back(points[i][0] - points[i][1])
    d2.push_back(points[i][0] + points[i][1])
sort(d1.begin(), d1.end())
sort(d2.begin(), d2.end())

cout << max(d1[d1.size() - 1] - d1[0], d2[d2.size() - 1] - d2[0]))

相似题型

1014. 最佳观光组合

leetcode172 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。 提示

int trailingZeroes(int n) {
    int times = 0;
    for (int i = 5; i <= n; i += 5) {
        int count = i;
        while (count && count % 5 == 0) {
            times ++;
            count /= 5;
        }
    }
    return times;
}

leetcode201 数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

题解

相邻两个数相与，末尾的 0 将会被消除，通过移位找公共前缀得到区间相与结果

int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    // 找到公共前缀
    while (left < right) {
        left >>= 1;
        right >>= 1;
        ++shift;
    }
    return left << shift;
}

leetcode1823 找出游戏的获胜者

思路

• 单链表模拟

• 取余推测

  leetcode 题解

leetcode29 两数相除

思路

• 特殊情况处理
• 除数左移位，与被除数比较

leetcode238 除自身以外数组的乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

题解

正反向前缀积，使用中间变量记录累积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size());
        int mul = nums[0];
        ret[0] = 1;
        for (int i = 1; i < nums.size(); i ++) {
            ret[i] = mul;
            mul *= nums[i];
        }
        mul = nums[nums.size() - 1];
        for (int i = nums.size() - 2; i >= 0; i --) {
            ret[i] *= mul;
            mul *= nums[i];
        }
        return ret;
    }
};

leetcode69 x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

题解

官方题解

乘方拆解

leetcode50 Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，）。

题解

将拆解为

其中，式子可转换为

double myPow(double x, int n) {
    // 特殊情况
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1 / x;

    bool flag = n < 0;
    long nn = n;
    if (flag) nn = -1 * nn;

    double temp = x;
    double res = 1;

    // 将 n 次累乘拆解为 logn 次
    while (nn > 1) {

        long times = 2;
        temp = x;

        while (true) {
            temp *= temp;
            if (times * 2 <= nn) times *= 2;
            else break;
        }

        nn -= times;
        res *= temp;

    }

    for (long i = 0; i < nn; i ++) res *= x;

    return flag ? 1 / res : res;
}

二进制位计数

leetcode137 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

题解

统计每个二进制位 1 的出现次数，若只出现一次的数在该为为 0，那么统计次数应为 3 的倍数，否则有余数

int singleNumber(vector<int>& nums) {
    int ret = 0;
    for (int i = 0; i < 32; i ++) {
        int count = 0;
        for (auto n : nums) {
            count += n >> i & 1;
        }
        if (count % 3) ret += 1 << i;
    }
    return ret;
}

另一种方法通过状态机的思想，用一个两位二进制数统计当前二进制位的状态，00 -> 01 -> 10 -> 00

int singleNumber(vector<int>& nums) {
    // n1 表示二进制的低位
    // n2 表示二进制的高位
    int n1 = 0, n2 = 0;
    for (auto n : nums) {
        // 若高位 n2 为 0，则低位 n1 只与当前值 n 有关；否则计数已满 3，低位直接置 0
        n1 = ~n2 & n1 ^ n;
        // 若低位 n1 为 0，则高位 n2 只与当前值 n 有关，若 n 为 1，则表示要进位，否则表示计数已满；若低位为 1，那么高位只能为 0
        n2 = ~n1 & n2 ^ n;
    }
    // 若计数满 3，低位应为 0，若计数除以 3 余 1，则低位应为 1，所以返回低位
    return n1;
}

leetcode169 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

排序后中值必包含多数元素

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

摩尔投票法

参考题解推荐了这种方法，思考方向为若与当前假设的众数相同，则投赞成票 1，否则投否认票-1，当得票为 0 时，则继续进行假设，多数元素将获得更多投票将投票值稳定为正；另外，从代码上理解，多数元素总有更多数量的连续元素

int majorityElement(vector<int>& nums) {
    int x = 0, votes = 0;
    for (int num : nums){
        if (votes == 0) x = num;
        votes += num == x ? 1 : -1;
    }
    return x;
}

集合类题目

leetcode2306 公司命名