LeeCode 刷题总结

做题思路:

  1. 尝试思考10-20分钟,如果想不到方案就去看答案。补充知识点。
  2. easy阶段每天12道,medium8道,hard2-4道。(优先按照tag做题,总结规律)

leecode刷题注意

  1. 如果使用了全局变量,需要在函数入口处初始化一下,否则会有问题。(自验证能过,提交不能过)

规律总结:

二叉树

  1. 查询二叉树的中序遍历是升序的。

数字

  1. 奇偶性,奇数只能被1整除,奇 * 偶 = 偶 ,偶 * 偶 = 偶,奇 * 奇 = 奇

  2. 对结果模1000000007,取余数((dp(a - 1) + dp(a - 2)) % 1000000007 + dp(a - 3)) % 1000000007;

贪心算法

动态规划(英语:Dynamic programming,简称 DP)

  • 将一个给定问题拆分为子问题,根据子问题得出原问题的解。需要找到递归关系、初始值。
  • 当从上往下得到规律后,从下往上计算可能会更简单。

线段树

  • 「区间最长连续上升序列问题」和「区间最大子段和问题」
/*
对于一个区间 [l, r],我们可以维护四个量:
lSum 表示 [l, r]内以 l 为左端点的最大子段和
rSum 表示 [l, r]内以 r 为右端点的最大子段和
mSum 表示 [l, r]内的最大子段和
iSum 表示 [l, r]的区间和
*/
class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) return (Status) {a[l], a[l], a[l], a[l]};
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

c基础语法

  • 判断是否是野指针:*s == NULL
  • 内存的申请与释放
#if 0
typedef struct {
    
} NumArray;
# endif

typedef int NumArray;

NumArray* numArrayCreate(int* nums, int numsSize) {
    NumArray* arr = (NumArray*)malloc((numsSize + 1) * sizeof(NumArray));
    memset(arr, 0, (numsSize + 1) * sizeof(NumArray));
    arr[0] = 0;
    for (int i = 1; i <= numsSize; i++) {
        arr[i] = arr[i - 1] + nums[i - 1];
    }
    return arr;
}

int numArraySumRange(NumArray* obj, int i, int j) {
    return obj[j + 1] - obj[i];
}

void numArrayFree(NumArray* obj) {
    if (obj == NULL) {
        return;
    }
    free(obj);
    obj = NULL;
}
  • 字符串操作
strcpy(p, p1) // 复制字符串 p1复制给p
strncpy(p, p1, n) // 复制指定长度字符串
strcmp(p, p1) // 比较字符串
strncmp(p, p1, n) // 比较指定长度字符串
  • 排序
/*--------------------冒泡排序---------------------*/
void bubleSort(int data[], int n) {
    int i,j,temp;
    for(j=0;j<n-1;j++) {
        for(i=0;i<n-j-1;i++) {
            if(data[i]>data[i+1]) {
                temp = data[i];
                data[i] = data[i+1];
                data[i+1] = temp;
            }
        }
    }  
}
剑指 Offer
原文地址:https://www.cnblogs.com/kunlingou/p/12898969.html