Skip to content

Files

Latest commit

masteryi-0018masteryi-0018
first commit
Jul 4, 2023
2807d35 · Jul 4, 2023

History

History
866 lines (750 loc) · 20.3 KB

基础班.md

File metadata and controls

866 lines (750 loc) · 20.3 KB

基础班第1节

一、位运算

  1. 打印32位整数的二进制表示 
#include <iostream>

// 打印32位整数二进制表示
void printBin(int n) {
    for (int i = 31; i > -1; i--) {
        if ((n & (1 << i)) == 0) {
            std::cout << 0;
        } else {
            std::cout << 1;
        }
    }
    std::cout << std::endl;
}

void printBin2(int n) {
    for (int i = 31; i > -1; i--) {
        std::cout << ((n & (1 << i)) == 0) ? 0 : 1;
    }
    std::cout << std::endl;
}

void printBin3(int n) {
    for (int i = 31; i > -1; i--) {
        std::cout << (((n & (1 << i)) == 0) ? 0 : 1);
    }
    std::cout << std::endl;
}

int main()
{
    printBin(0);
    printBin(65535);

    printBin2(0);
    printBin2(65535);

    printBin3(0);
    printBin3(65535);

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

二、算法复杂度

  1. 计算1! + 2! + ... + N!
#include <iostream>

// 计算 1! + 2! + ... + N!
int factorial(int n) {
    int res = 0;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
        res += ans;
    }
    return res;
}
// 这里换成long更好一些

int main()
{
    int res = factorial(5);
    std::cout << res << std::endl;

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

三、排序算法

  1. 选择排序
  2. 冒泡排序
    • 冒泡排序有一些改进，如：
    • 如果某一次遍历中发现没有元素发生交换，则表明前面的部分已经有序，退出循环；参考做法：设置变量sorted记录是否发生交换
    • 记录前一次遍历过程中最后一次交换的元素位置，则之后的部分已经有序，下一次循环的结束条件可以提前；参考做法：设置变量end记录上一次交换的位置
  3. 插入排序
#include <iostream>

void swap(int* arr, int i, int j);

// 选择排序，每次选择最小元素放在第i个位置
void selectSort(int* arr, int length) {
    for (int i = 0; i < length-1; i++) {
        int min = i;
        for (int j = i+1; j < length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        swap(arr, i, min);
    }
}

// 冒泡排序，相邻元素中大的往后换，放在倒数第i个位置
void bubbleSort(int* arr, int length) {
    for (int i = 0; i < length-1; i++) {
        for (int j = 1; j < length-i; j++) {
            if (arr[j-1] > arr[j]) {
                swap(arr, j-1, j);
            }
        }
    }
}

// 插入排序，拿到一张牌向右比较找到适合的位置，使用了while
void insertSort(int* arr, int length) {
    for (int i = 1; i < length; i++) {
        int j = i;
        while (j-1 > -1 && arr[j] < arr[j-1]) {
            swap(arr, j-1, j);
            j--;
        }
    }
}

void swap(int* arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 对数器暂时没有

int main()
{
    int arr1[] = {8,4,5,3,1,7,9,0,2,6};
    int length = sizeof(arr1) / sizeof(arr1[0]);
    selectSort(arr1, length);
    for (int i = 0; i < length; i++) {
        std::cout << arr1[i] << ' ';
    }
    std::cout << std::endl;

    int arr2[] = {8,4,5,3,1,7,9,0,2,6};
    bubbleSort(arr2, length);
    for (int i = 0; i < length; i++) {
        std::cout << arr2[i] << ' ';
    }
    std::cout << std::endl;

    int arr3[] = {8,4,5,3,1,7,9,0,2,6};
    insertSort(arr3, length);
    for (int i = 0; i < length; i++) {
        std::cout << arr3[i] << ' ';
    }
    std::cout << std::endl;

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

基础班第2节

一、数据结构

  1. 前缀和数组（适合频繁查找范围和）
    • 略，注意一维数组及二维数组，都可能涉及题目

二、随机数发生器

  1. 有函数f1可以等概率生成1-5的随机数，如何生成等概率随机数1-7
  2. 有函数f1可以以不等概率返回01，如何等概率返回01
    • 调用2次f1函数，结果是01返回0，结果是10返回1，其他情况重新调用函数
#include <iostream>
#include <ctime>

// 随机数发生器
int f1() {
    // rand()会返回一随机数值，范围在0至RAND_MAX间
    // RAND_MAX定义在stdlib.h，其值为2147483647
    return rand() % 5 + 1;
}

int f2() {
    // 将1-5随机数发生器转变为01发生器
    int ans = f1();
    while (ans == 3) {
        ans = f1();
    }
    return (ans < 3) ? 0 : 1;
}

int f3() {
    // 将01发生器作为二进制编码，理论上可以产生任何随机数发生器
    // 这里将0-7中0的情况重复，可以得到1-7
    int res = (f2() << 2) + (f2() << 1) + (f2() << 0);
    while (res == 0) {
        res = (f2() << 2) + (f2() << 1) + (f2() << 0);
    }
    return res;
}

int main()
{
    srand((int)time(0));

    for (int i = 0; i < 10; i++) {
        std::cout << f3() << std::endl;
    }

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

知道了这个方法叫做拒绝采样，力扣：470. 用 Rand7() 实现 Rand10()

三、对数器

用来生成长度随机值随机的数组，并验证排序算法是否正确，这里直接与排序算法的代码放在一起

#include <iostream>
#include <ctime>
#include <algorithm>

void swap(int* arr, int i, int j);

// 选择排序，每次选择最小元素放在第i个位置
void selectSort(int* arr, int length) {
    for (int i = 0; i < length-1; i++) {
        int min = i;
        for (int j = i+1; j < length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        swap(arr, i, min);
    }
}

// 冒泡排序，相邻元素中大的往后换，放在倒数第i个位置
void bubbleSort(int* arr, int length) {
    for (int i = 0; i < length-1; i++) {
        for (int j = 1; j < length-i; j++) {
            if (arr[j-1] > arr[j]) {
                swap(arr, j-1, j);
            }
        }
    }
}

// 插入排序，拿到一张牌向右比较找到适合的位置，使用了while
void insertSort(int* arr, int length) {
    for (int i = 1; i < length; i++) {
        int j = i;
        while (j-1 > -1 && arr[j] < arr[j-1]) {
            swap(arr, j-1, j);
            j--;
        }
    }
}

void swap(int* arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 对数器
int* genRanArr(int len, int maxVal) {
    // 在函数中定义的数组在函数执行完后已经被系统释放掉了
    // 解决办法就是动态分配内存，在函数中 new 一个数组
    int* arr = new int[len];
    for (int i = 0; i < len; i++) {
        arr[i] = rand() % maxVal;
    }
    return arr;
}

int* copyArr(int* arr, int len) {
    int* cArr = new int[len];
    for (int i = 0; i < len; i++) {
        cArr[i] = arr[i];
    }
    return cArr;
}

bool isSorted(int* arr, int len) {
    if (len < 2) {
        return true;
    }
    for (int i = 1; i < len; i++) {
        if (arr[i] < arr[i-1]) {
            return false;
        }
    }
    return true;
}

bool isEqual(int* arr1, int* arr2, int len1, int len2) {
    if (len1 != len2) {
        return false;
    }
    for (int i = 0; i < len1; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

void printArr(int* arr, int len) {
    // 当数组传入函数时，传入的是指针，指针仅指向数组头arr[0]
    // 不带有任何长度信息，所以在传入数组时，要把数组长度同时传入函数
    for (int i = 0; i < len; i++) {
        std::cout << arr[i] << ' ';
    }
    std::cout << std::endl;
}

int main()
{
    srand((int)time(0));

    int testTime = 10000;
    int maxLen = 100;
    int maxVal = 100;
    for (int i = 0; i < testTime; i++) {
        // 函数只能返回指针，所以长度要先设置
        int len = rand() % maxLen;
        int* arr1 = genRanArr(len, maxVal);
        int* arr2 = copyArr(arr1, len);
        int* arr3 = copyArr(arr1, len);
        int* arr4 = copyArr(arr1, len);

        selectSort(arr1, len);
        bubbleSort(arr2, len);
        insertSort(arr3, len);
        if (!isSorted(arr1, len)) {
            std::cout << "选择排序出错" << std::endl;
        }
        if (!isSorted(arr2, len)) {
            std::cout << "冒泡排序出错" << std::endl;
        }
        if (!isSorted(arr3, len)) {
            std::cout << "插入排序出错" << std::endl;
        }

        // 如果有暴力法或者其他保证结果正确的方法，可以使用isEqual进行对比验证
        // 这里使用系统的sort函数进行验证
        std::sort(arr4, arr4 + len);
        if (!isEqual(arr1, arr4, len, len)) {
            std::cout << "选择排序出错" << std::endl;
        }
        if (!isEqual(arr2, arr4, len, len)) {
            std::cout << "冒泡排序出错" << std::endl;
        }
        if (!isEqual(arr3, arr4, len, len)) {
            std::cout << "插入排序出错" << std::endl;
        }
    }

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

基础班第3节

一、二分查找

  1. 基础版
  2. 找到不大于num的最右元素
  3. 找到不小于num的最左元素 
#include <iostream>
using namespace std;

// 二分查找v1
int binSearch1(int* arr, int len, int num) {
    int left = 0;
    int right = len-1;
    while (left <= right) {
        // 防止越界
        int mid = left + ((right-left) >> 1);
        // 左侧比较1次，右侧比较2次，常数系数为1.5，可以用Fibonacci优化常数时间
        if (arr[mid] < num) {
            left = mid+1;
        } else if (arr[mid] > num) {
            right = mid-1;
        } else {
            return mid;
        }
    }
    // 没有找到
    return -1;
}

// 二分查找v2，找到不大于num的最右元素
int binSearch2(int* arr, int len, int num) {
    int left = 0;
    int right = len-1;
    // 未找到
    int ans = -1;
    while (left <= right) {
        int mid = left + ((right-left) >> 1);
        if (arr[mid] <= num) {
            // 只有满足的条件才更新ans
            ans = mid;
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    return ans;
}

// 二分查找v3，找到不小于num的最左元素
int binSearch3(int* arr, int len, int num) {
    int left = 0;
    int right = len-1;
    int ans = -1;
    while (left <= right) {
        int mid = left + ((right-left) >> 1);
        if (arr[mid] >= num) {
            ans = mid;
            right = mid-1;
        } else {
            left = mid+1;
        }
    }
    return ans;
}

int main()
{
    int arr[8] = {1,2,2,2,4,6,8,9};
    int len = sizeof(arr) / sizeof(arr[0]);
    int num = 2;

    int idx1 = binSearch1(arr, len, num);
    cout << idx1 << endl;

    int idx2 = binSearch2(arr, len, num);
    cout << idx2 << endl;

    int idx3 = binSearch3(arr, len, num);
    cout << idx3 << endl;

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}
  1. 局部最小值问题
#include <iostream>
#include <ctime>
using namespace std;

// 局部最小值
int findLocalMin(int* arr, int len) {
    if (len == 0) {
        return -1;
    } else if (len == 1) {
        return 0;
    } else if (arr[0] < arr[1]) {
        return 0;
    } else if (arr[len-2] > arr[len-1]) {
        return len-1;
    }
    int left = 0;
    int right = len-1;
    int ans = -1;
    while (left < right-1) {
        int mid = left + ((right-left) >> 1);
        if (arr[mid-1] > arr[mid] && arr[mid] < arr[mid+1]) {
            return mid;
        } else if (arr[mid-1] < arr[mid]) {
            right = mid-1;
        } else {
            left = mid+1;
        }
    }
    return arr[left] < arr[right] ? left : right;
}

int* genRanArr(int len, int maxVal) {
    if (len == 0) {
        return nullptr;
    }
    int* arr = new int[len];
    arr[0] = rand() % maxVal;
    for (int i = 1; i < len; i++) {
        do {
            arr[i] = rand() % maxVal;
        } while (arr[i] == arr[i-1]);
    }
    return arr;
}

bool check(int* arr, int len, int idx) {
    if (len == 0) {
        return idx == -1;
    }
    int left = idx - 1;
    int right = idx + 1;
    bool leftBigger = left > -1 ? arr[left] > arr[idx] : true;
    bool rightBigger = right < len ? arr[right] > arr[idx] : true;
    return leftBigger && rightBigger;
}

int main()
{
    srand((int)time(0));

    int testTime = 10000;
    int maxLen = 10;
    int maxVal = 20;
    for (int i = 0; i < testTime; i++) {
        int len = rand() % maxLen;
        int* arr = genRanArr(len, maxVal);
        int idx = findLocalMin(arr, len);
        if (!check(arr, len, idx)) {
            cout << "出错了" << endl;
        }
    }

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

二、其他数据结构

  1. 动态数组
    • 扩容均摊到每次操作的时间复杂度为O(1)
    • C++中即vector
  2. 哈希表、有序表（略）

基础班第4节

一、反转链表

  1. 反转单链表
#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(): val(0) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode* ptr): val(x), next(ptr) {}
};

ListNode* createList(int len) {
    if (len == 0) {
        return nullptr;
    }
    ListNode* lst = new ListNode(1);
    ListNode* head = lst;
    for (int i = 1; i < len; i++) {
        lst->next = new ListNode(i+1);
        lst = lst->next;
    }
    return head;
}

void printList(ListNode* lst) {
    while (lst != nullptr) {
        cout << lst->val << ' ';
        lst = lst->next;
    }
    cout << endl;
}

// 迭代
ListNode* reverseList1(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* next;
    while (head != nullptr) {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

// 递归
ListNode* reverseList2(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newhead = reverseList2(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newhead;
}

int main()
{
    int len = 5;
    ListNode* head = createList(len);
    printList(head);

    ListNode* newhead = reverseList1(head);
    printList(newhead);

    ListNode* newhead2 = reverseList2(newhead);
    printList(newhead2);

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}
  1. 反转双链表
#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode* pre;
    ListNode(): val(0) {}
    ListNode(int x): val(x), next(nullptr), pre(nullptr) {}
    ListNode(int x, ListNode* nPtr, ListNode* pPtr): val(x), next(nPtr), pre(pPtr) {}
};

// 返回多个值可以封装成类，但是2个值可以直接用pair
pair<ListNode*, ListNode*> createList(int len) {
    if (len == 0) {
        return {nullptr, nullptr};
    }
    ListNode* lst = new ListNode(1);
    ListNode* head = lst;
    ListNode* pre;
    for (int i = 1; i < len; i++) {
        lst->next = new ListNode(i+1);
        pre = lst;
        lst = lst->next;
        lst->pre = pre;
    }
    return {head, lst};
}

void printForward(ListNode* lst) {
    while (lst != nullptr) {
        cout << lst->val << ' ';
        lst = lst->next;
    }
    cout << endl;
}

void printBackword(ListNode* lst) {
    while (lst != nullptr) {
        cout << lst->val << ' ';
        lst = lst->pre;
    }
    cout << endl;
}

// 迭代
pair<ListNode*, ListNode*> reverseList1(ListNode* head) {
    ListNode* ori = head;
    ListNode* pre = nullptr;
    ListNode* next;
    while (head != nullptr) {
        next = head->next;
        head->next = pre;
        head->pre = next;
        pre = head;
        head = next;
    }
    return {pre, ori};
}

// 递归，不会做 -.-

int main()
{
    int len = 5;
    pair<ListNode*, ListNode*> result = createList(len);
    ListNode* head = result.first;
    ListNode* tail = result.second;
    printForward(head);
    printBackword(tail);

    pair<ListNode*, ListNode*> newresult = reverseList1(head);
    ListNode* newhead = newresult.first;
    ListNode* newtail = newresult.second;
    printForward(newhead);
    printBackword(newtail);

    // std::cout << "Hello World" << std::endl;
    // system("pause");
    return 0;
}

二、设计数据结构

  1. 单链表实现队列
  2. 单链表实现栈
  3. 双链表实现双端队列

三、链表题

  1. 力扣：21. 合并两个有序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 迭代，使用哑节点
        ListNode* dummy = new ListNode();
        ListNode* head = dummy;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                dummy->next = list1;
                list1 = list1->next;
            } else {
                dummy->next = list2;
                list2 = list2->next;
            }
            dummy = dummy->next;
        }
        dummy->next = list1 != nullptr ? list1 : list2;
        return head->next;
    }
};

迭代版本不是很优秀，可以直接借鉴官方答案的版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 递归
        ListNode* dummy = new ListNode();
        recur(dummy, list1, list2);
        return dummy->next;
    }
    void recur(ListNode* head, ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) {
            head->next = list2;
            return;
        }
        if (list2 == nullptr) {
            head->next = list1;
            return;
        }
        if (list1->val <= list2->val) {
            head->next = list1;
            recur(head->next, list1->next, list2);
            return;
        } else {
            head->next = list2;
            recur(head->next, list1, list2->next);
            return;
        }
    }
};
  1. 力扣：2. 两数相加
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 这个好像没看到递归版本
        // 使用左神的方法需要遍历3次链表，但是空间占用低
        ListNode* dummy = new ListNode();
        ListNode* head = dummy;
        int c = 0;
        int num = 0;
        while (l1 != nullptr && l2 != nullptr) {
            num = (l1->val + l2->val + c) % 10;
            c = (l1->val + l2->val + c) / 10;
            dummy->next = new ListNode(num);
            dummy = dummy->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1 != nullptr) {
            num = (l1->val + c) % 10;
            c = (l1->val + c) / 10;
            dummy->next = new ListNode(num);
            dummy = dummy->next;
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            num = (l2->val + c) % 10;
            c = (l2->val + c) / 10;
            dummy->next = new ListNode(num);
            dummy = dummy->next;
            l2 = l2->next;
        }
        dummy->next = c == 1 ? new ListNode(1) : nullptr;
        return head->next;
    }
};
  1. 这里将水塘抽样也加进来