Leetcode 题型和框架代码总结

while(cin>>a>>b);
// 主要是按照类型来进行cin，操作应该是通过空格来分割的。
// 按照我们执行的次数来进行指定次数的读取操作
以指定符号分割的字符串输入
char str[3][11]; 
cin.getline(str[0], 11, ',');  //接收最多10个字符 ,以‘，’作为结束符
cin.getline(str[1], 11, ',');
cin.getline(str[2], 11);     //默认结束符 enter

class Solution {
public:
    int rand10() {
        int col, row, idx;
        do {
            row = rand7();
            col = rand7();
            idx = (row-1) * 7 + col;
        } while (idx > 40);
        return 1 + idx % 10;
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        // 考虑两种情况：普通的匹配和*号匹配
        // 建立DP-table 考虑初始情况
        int m = s.size() + 1; int n = p.size() + 1;
        vector<vector<bool>> DP(m, vector<bool>(n, false));
        DP[0][0] = true;
        // 下面这个可以转换成&&语句可能会更好看点
        for (int i = 2; i < n; i+=2) {
            if(p[i-1] == '*') DP[0][i] = DP[0][i-2];
        }
        // 下面开始状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (p[j - 1] == '*') {
                    // 其实就是考虑两种情况: 最后的不同，第一个方式是我们抛弃前一个元素，第二个方式就是正常匹配，用了且过，第三个方式是我们用了且保留，那么就会出现一种情况，也就是在i的上一个时刻，已经和我们当前的*匹配了，但是我们还在继续匹配，这里要注意，这里不是和dp[i-1][j-1]比，和这个比的话，实际上就是正常的对比了，看下面的else，i-1 *中包含了i-2 * ，所以前面的我们就不需要再重复考虑了
                    DP[i][j] = DP[i][j - 1] || DP[i][j - 2]  || DP[i - 1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.');
                    
                }
                else {
                    // 如果没有*号的特殊情况下的时候，考虑就是前面的相等以及当前的相等，或者说就是.
                    DP[i][j] = DP[i - 1][j - 1] && (p[j - 1] == s[i - 1] || p[j-1] == '.');
                }
            }
        }
        return DP[m - 1][n - 1];
    }
};

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 实际上这题已经很熟悉了，这里需要做的就是构建一个DP table，以及状态转移
        // 切分的状态就是string的index
        if(word1.empty()) return word2.size();
        if(word2.empty()) return word1.size();
        // 建立dp table
        size_t len1 = word1.size();
        size_t len2 = word2.size();
        vector<int> dp(len2+1);
        // 初始化base-case，当一个是空，另一个不是空的情况
        
        for(int i =0; i<=len2;i++) dp[i] = i;
        // 通过转移方程确定搜索的方向，从而确定遍历的方向，建立状态转移方程
        int prec, temp;
        for(int i =1; i<=len1;i++){
            prec = dp[0]; dp[0] = i;
            for(int j =1; j<=len2;j++){
                // dp i,j 象征着word1到i 变换到word2 需要的变换操作数，
                // 当当前的值相等的时候
                temp = dp[j];
                if(word1[i-1] == word2[j-1]) dp[j] = prec;
                else{
                    // 插入一个才能变道j
                    dp[j] = min(min(dp[j-1],dp[j]),prec)+1;
                }
                prec = temp;
            }
        }
        return dp[len2];
    }
};

int n = arr.length;
int[][] dp = new dp[n][n];

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j++) {
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(...)
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 根据受伤是否持有股票来进行运算，存放第i天能获取的最大利益；
        vector<vector<int>> dp(n, vector<int>(2, 0));
        // 可以先将购买消耗掉
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            // 容易出错的就是买卖的最终价格计算
            dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
};

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    // vector 全填入 0，base case 已初始化
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i-1] < 0) {
                // 当前背包容量装不下，只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                               dp[i - 1][w]);
            }
        }
    }

    return dp[N][W];
}

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        backtrack(res, nums, 0, nums.size());
        return res;

    }
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len) {
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; i++) {
            swap(output[i], output[first]);
            backtrack(res, output, first + 1, len);
            swap(output[i], output[first]);
        }
    }
};

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll(); // 访问队列中的当前节点
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

    // 记录一维字符串的相邻索引
    vector<vector<int>> neighbor = {
        { 1, 3 },
        { 0, 4, 2 },
        { 1, 5 },
        { 0, 4 },
        { 3, 1, 5 },
        { 4, 2 }
    };

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    /****** 分 ******/
    // 对数组的两部分分别排序
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);
    /****** 治 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
}

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if (nums.empty()) return;
        // 直接进行值的改变是不是好一点，然后在后面进行添加就好了
        int index1 = 0; int index2 = 0;
        while(index2 < nums.size()) {
            if (nums[index2] != 0) {
                nums[index1] = nums[index2];
                if (index1 != index2) nums[index2] = 0;
                index1++;
            }
            index2++;
        }
        return;
    }
};

左侧边界： >=
<: l=mid+1 
>= : r = mid-1
检测左侧边界是否合理
return l；

左侧边界：>
<=: l=mid+1 
> : r = mid-1
检测左侧边界是否合理
return l；

右侧边界：<
<: l=mid+1 
>= : r = mid-1
检测右侧边界是否合理
return r；

for (int i = 0; i < n; i++)
    if (isOK(i))
        return answer;

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++; // 初始化状态，便于搜索

    int left = 0, right = 0;
    int valid = 0;  // 统计满足情况的数有多少，和需要的匹配时更新答案
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty()) return {};
        // 考虑到出现重复字符的情况，所以需要有一个int进行计数
        unordered_map<char, int> need, windows;
        int l = 0, r = 0, n = s.size();
        // 统计需要的每个字符的数量
        for (char c : t) need[c]++;

        int valid = 0, needv = need.size();
        int start = 0, lens = INT_MAX;
        
        while (r < n) {
            char temp = s[r];
            r++; // 每次就进行所有的缩减边界的行为
            if (need.count(temp)) {
                windows[temp]++;
                // 只在这里进行状态的变换，不进行判断
                if (windows[temp] == need[temp]) {
                    valid++;
                }
            }
            // cout<<r<<"now , l "<<l<<endl;
            // 左闭右开区间
            while (valid == needv &&l < r) {
                if (r - l < lens) {
                    start = l; lens = r - l;
                    cout<<lens<<endl;
                }

                char temp2 = s[l];
                if (need.count(temp2)) {
                    if (windows[temp2] == need[temp2]) valid--;
                    windows[temp2]--;
                }
                l++;
            }

        }
        return lens==INT_MAX?"":s.substr(start,lens);
    }
};

// shell 排序
# include<vector>
using namespace std;
const int INCRGAP = 2;
void shellsort(vector<int>nums)
{
    int insertNum = 0;
    // 首先计算出各个GAP，然后基于GAP进行插入排序
    unsigned int gap = nums.size()/INCRGAP;
    // GAP>=1
    while(gap){
        // 实现插入排序；每一个树按照gap去找其前面的数
        for(unsigned int i = gap; i<nums.size();i++ ){
            int temp = nums[i];
            unsigned int j = i;
            while(j>=gap && nums[j-gap]>temp){
                nums[j] = nums[j-gap];
                j-=gap;
            }
            // 当数字到了最前面或者第一个比他小的时候，插入
            nums[j] = temp;
        }
        gap /= INCRGAP;
    }
    
}

int main(){
    vector<int> a = {1,3,41,23,5,23,53,123,1};
    shellsort(a);
    for(auto i:a)	cout<<i<<"  ";
    cout<<endl;
    return 0;
}

void abjust_heap(vector<int>& nums, int index, int lens) {
    // 根据二叉树的性质，索引到子节点的坐标
    // TODO:但是还要判断越不越界(这里由于我们不是堆，而是一个排序的过程，长度在变，所以需要这个参数的输入)
    int n = lens;
    int left = (2 * index) < n ? 2 * index : index, right = (2 * index + 1) < n ? (2 * index + 1) : index;
    // 如果越界就赋予原值，也就是不改变。

    int max_child = nums[left] > nums[right] ? left : right;
    // 和其中比较大的那个值互换，如果越界了是自己，和自己换
    if (nums[index] < nums[max_child]) {

        swap(nums[index], nums[max_child]);
        // FIXME: 如果位置变了，要对变换的位置进行继续的递归
        abjust_heap(nums, max_child, n);
    }
    return;
}

void heapsort(vector<int>& nums) {
    // 通过下标索引来建立堆
    // 由于二叉树的叶节点一定是总数的一半左右（len/2 or len/2+1）
    // 然后再根据数值和坐标的映射关系-1.可以知道非叶子节点的坐标是(len/2-1)
    int n = nums.size();
    // 首先进行建堆的过程
    for (int i = (n >> 1) - 1; i >= 0; i--) {
        // 从倒数第二层开始一个个的进行交换
        abjust_heap(nums, i,n);
    }
    // 然后依次弹出头部元素进行测试；
    for (int i = n - 1; i >= 0; i--) {
        swap(nums[0], nums[i]);
        abjust_heap(nums, 0, i);
    }
}

int quickSortPartition(vector<int>& s, int l, int r) {
    //Swap(s[l], s[(l + r) / 2]); //若以中间数为基准，则先将中间的这个数和第一个数交换即可
    int i = l, j = r, x = s[l]; //将最左元素记录到x中
    while (i < j)
    {
        // 从右向左找第一个<x的数
        // 无需考虑下标越界（有i的约束）
        while (i < j && s[j] >= x)
            j--;
        if (i < j) // 满足这个条件实际上就是说，已经找到了。不满足就是没找到、
            s[i++] = s[j]; //直接替换掉最左元素，如果没找到的话，就不需要换。因为上面有约束

        // 从左向右找第一个>x的数
        while (i < j && s[i] <= x)
            i++;
        if (i < j)
            //替换掉最右元素(已在最左元素中有备份）
            //最左元素一定被覆盖过，若没有，则表明右侧所有元素都>x，那么算法将终止
            s[j--] = s[i];
    }
    s[i] = x;  //i的位置放了x，所以其左侧都小于x，右侧y都大于x
    return i;
}

void quickSort(vector<int>& s, int l, int r)
{
    //数组左界<右界才有意义，否则说明都已排好，直接返回即可
    if (l >= r) {
        return;
    }

    // 划分，返回基准点位置
    int i = quickSortPartition(s, l, r);

    // 递归处理左右两部分，i处为分界点，不用管i了
    quickSort(s, l, i - 1);
    quickSort(s, i + 1, r);
}

def QuickSort(list_):
    if len(list_) <= 1:
        return list_
    # 左边数组
    left = []
    # 右边数组
    right = []
    # 基准数
    base = list_.pop()
    # 对原数组进行划分
    for x in list_:
        if x < base:
            left.append(x)
        else:
            right.append(x)
    # 递归调用
    return QuickSort(left) + [base] + QuickSort(right)

my version quicksort
int quickSortPartition(vector<int>& s, int l, int r) {
    //Swap(s[l], s[(l + r) / 2]); //若以中间数为基准，则先将中间的这个数和第一个数交换即可
    int i = l, j = r, x = s[l]; //将最左元素记录到x中
    while (i < j)
    {
        // 从右向左找第一个<x的数
        // 无需考虑下标越界（有i的约束）
        while (i < j && s[j] >= x)
            j--;
        // 从左向右找第一个>x的数
        while (i < j && s[i] <= x)
            i++;
        if (i < j) swap(s[i], s[j]);
    }
    swap(s[i],s[l]);  //i,j的位置放了x，所以其左侧都小于x，右侧y都大于x,可以分析，当前的地方存放的一定是小于base的数字，所以直接和base进行一个交换，然后返回当前的坐标即可
    return i;
}

void quickSort(vector<int>& s, int l, int r)
{
    //数组左界<右界才有意义，否则说明都已排好，直接返回即可
    if (l >= r) {
        return;
    }

    // 划分，返回基准点位置
    int i = quickSortPartition(s, l, r);

    // 递归处理左右两部分，i处为分界点，不用管i了
    quickSort(s, l, i - 1);
    quickSort(s, i + 1, r);
}

void _sort(int n,int a[],int l,int r){
    int mid = (l+r)/2;
    int tem[n];
    if(l == r)
        return;
    _sort(n,a,l,mid);
    _sort(n,a,mid+1,r);
    //归并，将l→mid 和 mid+1→r 两部分有序的数组归并成一个数组
    int la = l,lb = mid+1;int k=l;
    while(la<=mid && lb<=r){
        if(a[la]<a[lb]) { tem[k] = a[la];k++;la++;}
        else  { tem[k] = a[lb];k++;lb++;}
    }
    while(la>mid && lb<=r){ tem[k] = a[lb];k++;lb++;}
    while(lb>r && la<=mid){ tem[k] = a[la];k++;la++;}
    for(int i=l;i<=r;i++){
        a[i] = tem[i];
    }
}
————————————————
版权声明：本文为CSDN博主「驰骋光束」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37184747/article/details/72764628