基础题

反转链表

/******************************************************************************
* File:             reverse_list.cpp
*
* Author:           yychi  
* Created:          2022-12-29 20:35 
* Description:      Reverse a linked list.
*****************************************************************************/
#include <cstdio>
#include <time.h>
#include <stdlib.h>
 
 
struct ListNode
{
    ListNode(int _val): val(_val), next(nullptr) {}
    int val;
    ListNode* next;
    void print()
    {
        printf("%d", val);
        if (next)
        {
            printf("->");
            next->print();
        }
        else
        {
            printf("\n");
        }
    }
};
 
 
ListNode* ReverseList(ListNode* head)
{ // O(n) time, O(1) space
    if (!head || !head->next) return head;
    ListNode *a = head, *b = head->next;
    while (b)
    {
        ListNode* tmp = b->next;
        b->next = a;
        a = b;
        b = tmp;
    }
    head->next = nullptr;
    return a; 
}
 
 
ListNode* ReverseListRecursive(ListNode* head)
{ // O(n^2) time
    if (!head || !head->next) return head;
    ListNode* ret = ReverseListRecursive(head->next);
    ListNode* p = ret;
    while (p->next)
    {
        p = p->next;
    }
    p->next = head;
    head->next = nullptr;
    return ret;
} // 如果每一步返回尾后指针，走到底的时候记录下原来那个最末尾指针作为返回值（反转后指针的头），就可以把复杂度降下来啦
 
// update 2024/9/25, 返回尾后指针的版本
struct ReverseListFunctor
{
    ListNode* head;
    ListNode* operator()(ListNode* head)
    {
        // base case
        if (!head || !head->next) return head;
        helper(head)->next = nullptr;
        return this->head;
    };
 
    // give the last element of the reversed list
    ListNode* helper(ListNode* head)
    {
        if (head && !head->next)
        {
            this->head = head;
            return head;
        }
        helper(head->next)->next = head;
        return head;
    }
};
 
 
int main()
{
    srand(time(NULL));
    ListNode head(345);
    ListNode* p = &head;
    for (int i = 0; i < 10; ++i)
    {
        int x = rand() % 99;
        // auto node = ListNode(x);
        // p->next = &node;
        p->next = new ListNode(x);
        p = p->next;
    }
    head.print();
 
    printf("recursive way:\n");
    ListNode* rhead = ReverseListRecursive(&head);
    rhead->print();
 
    printf("iterative way:\n");
    ReverseList(rhead)->print();
    return 0;
}

合并有序链表

猛击此处获取live demo.

/******************************************************************************
* File:             lisuan.cpp
*
* Author:           yychi  
* Created:          2022-08-10 22:44 
* Description:      merge two sorted link list, iteratively and recursively.
*****************************************************************************/
#include <stdio.h>
 
 
struct ListNode
{
    ListNode(int _val): val(_val), next(nullptr) {}
    int val;
    ListNode* next;
 
    void print()
    {
        printf("%d", val);
        if (next)
        {
            printf("->");
            next->print();
        }
        else
        {
            printf("\n");
        }
    }
};
 
 
ListNode* MergeLinkList(ListNode* a, ListNode* b)
{
    // two base cases.
    if (!a) return b;
    if (!b) return a;
 
    ListNode ret(0);
    ret.next = a;
 
    ListNode* pa = &ret;
    for (; a && b; )
    {
        if (a->val <= b->val)
        {
            pa = a;
            a = a->next;
        }
        else
        {
            ListNode* b_nex = b->next;
            pa->next = b;
            b->next = a;
            pa = b;
            b = b_nex;
        }
    }
 
    // append tail
    if (!a && b) pa->next = b;
    return ret.next;
}
 
 
/**
 * Recursive way.
 */
ListNode* MergeLinkListRecursive(ListNode* a, ListNode* b)
{
    if (!a) return b;
    if (!b) return a;
 
    if (a->val <= b->val)
    {
        a->next = MergeLinkListRecursive(a->next, b);
        return a;
    }
    else
    {
        b->next = MergeLinkListRecursive(a, b->next);
        return b;
    }
}
 
 
// test
int main()
{
    ListNode* a = new ListNode(3);
    ListNode* pa = a;
    pa->next = new ListNode(5);
    pa = pa->next;
    pa->next = new ListNode(19);
    pa = pa->next;
    pa->next = new ListNode(21);
    pa = pa->next;
    pa->next = new ListNode(30);
 
    ListNode* b = new ListNode(1);
    ListNode* pb = b;
    pb->next = new ListNode(4);
    pb = pb->next;
    pb->next = new ListNode(6);
    pb = pb->next;
    pb->next = new ListNode(8);
    pb = pb->next;
    pb->next = new ListNode(10);
    pb = pb->next;
    pb->next = new ListNode(45);
 
    // print a, b
    a->print();
    b->print();
 
    printf("before call a=%p, b=%p, a.next=%p, b.next=%p\n", a, b, a->next, b->next);
    MergeLinkList(a, b)->print();
    printf("after call a=%p, b=%p, a.next=%p, b.next=%p\n", a, b, a->next, b->next);
    // MergeLinkListRecursive(a, b)->print();
    return 0;
}

最大子数组的和

see: https://leetcode.com/problems/maximum-subarray/description/

从头开始累加，关键是什么时候丢弃当前的累加进度，重新开始。答：当累加和小于当前元素的时候，不如丢弃累加和，直接从当前元素再开始累加。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ret = INT_MIN, sum = 0;
        for (int e : nums)
        {
            sum = max(sum+e, e);
            ret = max(ret, sum);
        }
        return ret;
    }
};

最大子数组的乘积

see: https://leetcode.com/problems/maximum-product-subarray/description/

和上面的问题类似，但是这里多了负负得正的情况，所以处理起来比较麻烦。关键点在于：每次遍历，记录当前最大乘积和当前最小乘积（因为最小乘积可能呈乘一个负数翻正从而比最大乘积更大）。然后更新全局最大乘积。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ret = INT_MIN;
        int pmin = 1, pmax = 1, n, m;
        for (auto e : nums)
        {
            n = pmin * e;
            m = pmax * e;
            pmin = min({n, m, e});
            pmax = max({n, m, e});
            ret = max(pmax, ret);
        }
        return ret;
    }
};

字符串相乘

see: https://leetcode.com/problems/multiply-strings/description/

本质上是模拟竖式相乘，直接模拟即可，需要注意细节。

class Solution {
public:
 
/**
 * 考虑竖式乘法中，单个位置上的结果累加，考虑循环进位。
 */
void add_by_carrier(string& o, size_t index, int value)
{
    if (value <= 0 || index >= o.size()) return;
    int p = value + (o[index] - '0');
    o[index] = '0' + (p % 10);
    add_by_carrier(o, index+1, p/10);
}
 
string multiply(string num1, string num2)
{
    std::reverse(num1.begin(), num1.end());
    std::reverse(num2.begin(), num2.end());
    string ret(num1.size() + num2.size(), '0');
 
    for (size_t i = 0; i < num1.size(); ++i)
    {
        int p1 = num1[i] - '0';
        for (size_t j = 0; j < num2.size(); ++j)
        {
            add_by_carrier(ret, i+j, p1 * (num2[j]-'0'));
        }
    }
    while (ret.size() > 1 && ret.back() == '0')
        ret.pop_back();
 
    std::reverse(ret.begin(), ret.end());
    return ret;
}
 
};

二分查找

leetcode cn #704 https://leetcode.cn/problems/binary-search/description/

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

变种

如果存在多个目标值，要求返回索引最大/最小的那个。

#define GREEDY true
 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        return my_binary_search(nums, target);
    }
 
 
int my_binary_search(const vector<int>& arr, int target)
{
    int beg = 0, end = arr.size(), mid = 0;
    while (beg + 1 < end)
    {
        mid = (beg + end) / 2;
        if (target == arr[mid])
        {
#if GREEDY
            // in case of the array is not monotone increasing (i.e., it contains
            // some duplicated elements), we want the maximal index `i' such that
            // arr[i] = target.
            beg = mid;
#else
            return mid;
#endif
        }
        if (target < arr[mid])
        {
            end = mid;
        }
        if (target > arr[mid])
        {
            beg = mid;
        }
    }
    if (target == arr[beg]) return beg;
    return -1;
}
};