头像

copy_right

1




离线:1小时前


最近来访(6)
用户头像
zst_2001
用户头像
零落L
用户头像
bcwing
用户头像
emmmml
用户头像
北大的大佬
用户头像
ephemeral.


copy_right
11小时前

leetcode 41~45

41. 缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for(int i = 0; i < n; ++ i)
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);

        for(int i = 0; i < n; ++ i)
            if(nums[i] != i + 1)
                return i + 1;

        return n + 1;
    }
};

42. 接雨水

https://www.acwing.com/solution/content/121/

简单易懂,yyyds,就是直接挨个求每个柱子上的空间可以盛放多少水

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        if(n == 0) return n;

        vector<int> left(n),right(n);
        left[0] = height[0];
        right[n - 1] = height[n - 1];

        for(int i = 1; i < n; i ++){
            left[i] = max(left[i - 1],height[i]);
        }

        for(int i = n - 2; i >=  0; i --){
            right[i] = max(right[i + 1],height[i]);
        }

        int ans = 0;
        for(int i = 0; i < n; i ++){
            ans += min(left[i],right[i]) - height[i];
        }

        return ans;
    }
};
这种就是直接对于一个长方形进行计算获取面积

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0;
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && height[st.top()] <= height[i]) {
                int top = st.top();
                st.pop();
                if (st.empty()) break;
                ans += (i - st.top() - 1) 
                        * (min(height[st.top()], height[i]) - height[top]);
            }
            st.push(i);
        }
        return ans;
    }
};

43. 字符串相乘

999 * 999 = 998,001
100 * 100 = 10000

位数最多为 n + m位

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> a,b;
        int n = num1.size(),m = num2.size();
        for(int i = n - 1; i >= 0 ;i--) a.push_back(num1[i] - '0');
        for(int i = m - 1; i >= 0 ;i--) b.push_back(num2[i] - '0');

        vector<int> c(n + m);
        for(int i = 0 ; i < n ; i ++)
            for(int j = 0 ; j < m; j ++)
                c[i + j] += a[i] * b[j];


        for(int i = 0,t = 0; i < c.size() ; i ++){
            t += c[i];
            c[i] = t % 10;
            t = t / 10;
        }

        int k = c.size() - 1;
        while(k > 0 && !c[k]) k--;

        string res = "";
        while(k >= 0) res += c[k -- ] + '0';
        return res;
    }
};

44. 通配符匹配

留白

45. 跳跃游戏 II

https://www.acwing.com/solution/content/107/


class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int ans = 0, cur = 0, dis = 0;

        while (dis < n - 1) {
            int next = 0;
            while (cur <= dis) {
                next = max(next, cur + nums[cur]);
                cur++;
            }
            ans++;
            dis = next;
        }
        return ans;
    }
};



36. 有效的数独

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool st[9]; // 判断数组

        // 判断行
        for (int i = 0; i < 9; i ++ ) {
            memset(st, 0, sizeof st);
            for (int j = 0; j < 9; j ++ ) {
                if (board[i][j] != '.') {
                    if (st[board[i][j] - '1']) return false;
                    st[board[i][j] - '1']= true;
                }
            }
        }

        // 判断列
        for (int i = 0; i < 9; i ++ ) {
            memset(st, 0, sizeof st);
            for (int j = 0; j < 9; j ++ ) {
                if (board[j][i] != '.') {
                    if (st[board[j][i] - '1']) return false;
                    st[board[j][i] - '1'] = true;
                }
            }
        }

        // 判断九宫格
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                memset(st, 0, sizeof st);
                for(int k = 0 ; k < 3; k ++){
                    for(int s = 0; s < 3; s ++){
                        if (board[i + k][j + s] != '.') {
                            if (st[board[i + k][j + s] - '1']) return false;
                            st[board[i + k][j + s] - '1'] = true;
                        }
                    }
                }
            }
        }

        return true;

    }
};

37. 解数独

class Solution {
public:

    bool row[9][9],col[9][9],cell[3][3][9];

    void solveSudoku(vector<vector<char>>& board) {
        memset(row,0,sizeof row);
        memset(col,0,sizeof col);
        memset(cell,0,sizeof cell);

        for(int i = 0 ; i < 9; i ++){
            for(int j = 0 ; j < 9; j ++){
                if(board[i][j] != '.'){
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
            }
        }
        dfs(board,0,0);
    }

    bool dfs(vector<vector<char>>& board,int x,int y){
        if(y == 9) x ++,y = 0;
        if(x == 9) return true;

        if(board[x][y] != '.') return dfs(board,x ,y + 1);
        for(int i = 0; i < 9; i ++){
            if(!row[x][i] && !col[y][i] && !cell[x/3][y/3][i]){
                board[x][y] = '1' + i;
                row[x][i] = col[y][i] = cell[x/3][y/3][i] = true;
                if(dfs(board,x,y + 1)) return true;
                board[x][y] = '.';
                row[x][i] = col[y][i] = cell[x/3][y/3][i] = false;
            }
        }
        return false;
    }
};

38. 外观数列

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        for(int i = 0 ; i < n - 1; i ++){
            string t;
            for(int j = 0 ; j < s.size();){
                int k = j + 1;
                while(k < s.size() && s[k] == s[j]) k ++;
                t += to_string(k - j) + s[j];
                j = k;
            }
            s = t;
        }
        return s;
    }
};

39. 组合总和

class Solution {
public:

    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum(vector<int>& c, int target) {
        dfs(c,0,target);
        return ans;
    }

    void dfs(vector<int>& c,int u,int target){
        // 如果出现target == 0,那么说明有解
        if(target == 0){
            ans.push_back(path);
            return;
        }
        // 到最后没有得出结果直接return
        if(u == c.size()) return;

        // 查看可以存在多少个
        for(int i = 0; i * c[u] <= target; i ++){
            dfs(c,u + 1,target - i * c[u]);
            path.push_back(c[u]);
        }

        // 恢复现场
        for (int i = 0; c[u] * i <= target; i ++ ) {
            path.pop_back();
        }
    }
};

40. 组合总和 II

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum2(vector<int>& c, int target) {
        sort(c.begin(),c.end());
        dfs(c,0,target);
        return ans;
    }

    void dfs(vector<int>& c,int u,int target){
        if(target == 0){
            ans.push_back(path);
            return;
        }
        if(u == c.size()) return;

        // 添加数字个数要求
        int k = u + 1;
        while(k < c.size() && c[k] == c[u]) k ++;
        int cnt = k - u;

        for(int i = 0; i * c[u] <= target && i <= cnt; i ++){
            dfs(c, k ,target - i * c[u]);
            path.push_back(c[u]);
        } 

        for (int i = 0; c[u] * i <= target && i <= cnt; i ++ ) {
            path.pop_back();
        }
    }
};


活动打卡代码 LeetCode 35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if (target > nums[n - 1]) return n;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};



class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return vector<int> {-1,-1};
        vector<int>res;

        int l = 0,r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        // 查看有没有找到,如果找到就进行下一步,没有找到直接输出 -1 -1
        if(nums[l] == target){
            res.push_back(l);
            l = 0,r = nums.size() - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            res.push_back(l);
        }else return vector<int> {-1,-1};

        return res;
    }
};


活动打卡代码 AcWing 4722. 数列元素

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 410;
int q[N];

int main()
{
    int c;
    cin >> c;

    for(int i = 1;i <= 400;i ++){
        q[i] = q[i - 1] + i;
        if(q[i] == c){
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
    return 0;
}



31.下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        /*
            in: 
                k: 驼峰,
                t: 驼峰右边第一个比 nums[ k - 1 ] 小的数字

            breakthrough:
                需要动最右侧第一个驼峰的左边的数字
        */
        int k = nums.size() - 1;
        while(k > 0 && nums[k - 1] >= nums[k]) k --;  // k-1正好是0
        if(k <= 0){ // 没有找到
            reverse(nums.begin(),nums.end());
        }else{
            // 找出 t
            int t = k;
            while(t < nums.size() && nums[t] > nums[ k - 1]) t ++;
            swap(nums[t - 1],nums[k - 1]);
            reverse(nums.begin() + k,nums.end());
        }
    }
};

32.最长有效括号

class Solution {
public:
    int longestValidParentheses(string s) {
        /*
            breakthrough:
                看视频,看讲解[doge]
        */
        stack<int> stk;
        int res = 0 ;
        for(int i = 0,start = -1; i < s.size(); i ++){
            if(s[i] == '(') 
                stk.push(i);
            else{
                if(stk.size()){
                    stk.pop();
                    if(stk.size()){
                        // 不空的话就更到栈顶元素
                        res = max(res,i - stk.top());
                    }else{
                        // 匹配结束之后为空说明可以匹配到起点
                        res = max(res,i - start);
                    }
                }else{
                    // 更新起点
                    start = i;
                }
            }
        }
        return res;
    }
};

33. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        // 求驼峰
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 判断 target 属于左半段还是右半段
        if (target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() - 1;

        // 普通的二分找出下标
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        // 找出来了就输出每天找出来,就输出-1
        if (nums[r] == target) return r;
        return -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return vector<int> {-1,-1};
        vector<int>res;

        int l = 0,r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        // 查看有没有找到,如果找到就进行下一步,没有找到直接输出 -1 -1
        if(nums[l] == target){
            res.push_back(l);
            l = 0,r = nums.size() - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            res.push_back(l);
        }else return vector<int> {-1,-1};

        return res;
    }
};

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if (target > nums[n - 1]) return n;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};



class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        if (target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() - 1;

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[r] == target) return r;
        return -1;
    }
};


活动打卡代码 LeetCode 32. 最长有效括号

class Solution {
public:
    int longestValidParentheses(string s) {
        /*
            breakthrough:
                看视频,看讲解[doge]
        */
        stack<int> stk;
        int res = 0 ;
        for(int i = 0,start = -1; i < s.size(); i ++){
            if(s[i] == '(') 
                stk.push(i);
            else{
                if(stk.size()){
                    stk.pop();
                    if(stk.size()){
                        // 不空的话就更到栈顶元素
                        res = max(res,i - stk.top());
                    }else{
                        // 匹配结束之后为空说明可以匹配到起点
                        res = max(res,i - start);
                    }
                }else{
                    // 更新起点
                    start = i;
                }
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        /*
            in: 
                k: 驼峰,
                t: 驼峰右边第一个比 nums[ k - 1 ] 小的数字

            breakthrough:
                需要动最右侧第一个驼峰的左边的数字
        */
        int k = nums.size() - 1;
        while(k > 0 && nums[k - 1] >= nums[k]) k --;  // k-1正好是0
        if(k <= 0){ // 没有找到
            reverse(nums.begin(),nums.end());
        }else{
            // 找出 t
            int t = k;
            while(t < nums.size() && nums[t] > nums[ k - 1]) t ++;
            swap(nums[t - 1],nums[k - 1]);
            reverse(nums.begin() + k,nums.end());
        }
    }
};



[toc]

1. 增
    a. 增加一个数据库
        1). CREATE DATABASE < 数据库名称 > ;
    b. 增加一个表
        1). create table 表名 (属性以及各类属性,限制条件常见有 定长字符类型 CHAR,非定长字符类型 VARCHER, 整数类型 INTEGRE, 非空属性 NOT NULL)
    c. 增加一列
        1).ALTER TABLE < 表名 > ADD COLUMN < 列的定义 >;


2. 删除
    a. 删除一个数据库
        1). DROP DATABASE < 数据库名称 >;
    b. 删除一个表
        1). DROP  table < 表名 >;
    c. 删除一个列
        1). ALTER TABLE < 表名 > DROP COLUMN < 列名 >;
    d. 删除整个表内容
        1). truncate table <表名>;
    e.  删除符合条件的数据
        1). DELETE FROM <表名>  <条件>;


3. 改
    a. update
        1).update <表名>
          SET <列名> = <表达式> [, <列名2>=<表达式2>...];  
          WHERE <条件>;  -- 可选,非常重要。  
          ORDER BY 子句;  --可选
          LIMIT 子句; --可选

    b. AS 
        1).select product_id AS id



4. 查
    a. select  
    b. distinct
        i. select distinct product_type from product;

<>  和~不相等
希望选取NULL记录时,需要在条件表达式中使用IS NULL运算符。希望选取不是NULL的记录时,需要在条件表达式中使用IS NOT NULL运算符。

例子
    create table Addressbook 
    (regist_no INTEGER NOT NULL,
    name VArCHAR(128) NOT NULL,
    address VARCHAR(256) NOT NULL,
    tel_no CHAR(10),mail_address CHAR(20),
    -- 指定主键
    PRIMARY KEY (regist_no));