面试算法题

记录部分手撕题目，给出核心代码，一般是从头开始写

1、相交链表

class Solution { // lc 160
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A; // 交点或者空指针
    }
};

2、三数之和

class Solution { // lc 15
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end()); // 排序后用双指针
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) return res; // 超出范围
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.size() - 1; // 双指针，结合去重
            while (left < right) { // 有两个数，所以无等号
                if (nums[i] + nums[left] + nums[right] < 0) left++;
                else if (nums[i] + nums[left] + nums[right] > 0) right--;
                else {
                    res.push_back({nums[i], nums[left], nums[right]});
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    // 找到答案后左右收缩
                    right--;
                    left++;
                }
            }
        }
        return res;
    }
};

3、数组中第k个最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k]; // 直接排序，时间复杂度O(nlogn)
    }
};

// 提高时间复杂度，快速排序加筛选
class Solution {
public:
    int findKthLarrgest(vector<int>& nums, int k) {
        return quickSelect(num, k);
    }
    int quickSelect(vector<int>& nums, int k) {
        int pivot = nums[rand() % nums.size()];
        vector<int> big, equal, small;
        for (int num : nums) {
            if (num > pivot) big.push_back(num);
            else if (num < pivot) small.push_back(num);
            else equal.push_back(num); // 去除重复元素
        }
        if (k <= big.size()) return quickSelect(big, k); // 第k大的元素在big中
        if (nums.size() - small.size() < k) return quickSelect(small, k - (nums.size() - small.size())); // 第k大的元素在small中
        return pivot; // 第k大的元素在equal中，直接返回
    }
};

原文地址：https://blog.csdn.net/qq_43818724/article/details/142723641

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！