头像

邓泽军


访客:27015

离线:25天前



邓泽军
7个月前

题目描述

整理一下思路,可以只对第一个数组进行划分,如果知道第一个的划分就可以知道第二个元素怎么划分的了,

需要注意的是:

  • 1.记录第一个数组划分的位置cut1左右的值L1和R1, 和第二个的划分cut2的左右元素值L2和R2.
  • 2.如果L1>R2,那么cut1需要左移,如果L2>R1说明cut1需要右移动.否则说明划分成功.
  • 3.如果为偶数个,那么中值是左边:max(L1, L2), 右边是:min(R1, R2).
  • 4.如果是奇数个,那么就是:min(R1, R2).

C++ 代码

/*
         L1  R1
nums1: 3 5 | 8 9
           L2  R2
nums2: 1 2 7 | 10 11 12

nums : 1 2 3 5 7 | 8 9 10 11 12

L1: cut1分割点左边的元素值
条件: L1 < R2
       L2 < R1
       L1 > R2  cut1左移
       L2 > R1  cut1右边移动


int cut1: 表示nums1分割点左边有多少个元素。
int cut2: 表示nums2分割点左边元素个数.

int cutL: 表示nums1二分的左端点。
int cutR: nums1二分右端点.


*/
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
        int len = n1 + n2;
        int cut1 = 0; //nums1分割点左边元素个数.
        int cut2 = 0; // nums2分割点左边元素个数.
        int cutL = 0;  //对nums1进行二分的左端点.
        int cutR = n1; //对nums1进行二分的右端点.
        while (cut1 <= n1) {
            cut1 = (cutR - cutL) / 2 + cutL;
            cut2 = len / 2 - cut1;
            double L1 = (cut1 == 0) ? INT_MIN : nums1[cut1 - 1]; //如果左边没有元素设置L1 = INT_MIN, 保证L1<R2.
            double L2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1]; //if : L2 = INT_MIN < R1
            double R1 = (cut1 == n1) ? INT_MAX : nums1[cut1];  //if : R1 = INT_MAX > L2
            double R2 = (cut2 == n2) ? INT_MAX : nums2[cut2];
            if (L1 > R2) {
                cutR = cut1 - 1; // 分割点需要左移动。
            }
            else if (L2 > R1) {
                cutL = cut1 + 1; // 分割点需要右边移动。
            }
            else {
                if (len % 2 == 0) {
                    L1 = L1 > L2 ? L1 : L2; //选择左边较大的
                    R1 = R1 < R2 ? R1 : R2; //和右边较小的。
                    return (L1 + R1) / 2;
                }
                else {
                    R1 = R1 < R2 ? R1 : R2; //偶数的话是右边较小的元素。
                    return R1;
                }
            }
        }
        return -1;
    }
};


活动打卡代码 AcWing 868. 筛质数

邓泽军
8个月前
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p;
    vector<bool> st(n + 1, false);
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) p.push_back(i);
        for (int j = 0; p[j] * i <= n; j ++) {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
    cout << p.size() << endl;
    return 0;
}


活动打卡代码 AcWing 867. 分解质因数

邓泽军
8个月前
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n;i ++) {
        int a;
        cin >> a;
        for (int i = 2; i <= a / i; i ++) {
            if (a % i == 0){
                int s = 0;
                while (a % i == 0) {
                    a /= i; s ++;
                }
                cout << i << ' ' << s << endl;
            }
        }
        if (a > 1) cout << a << ' ' << 1 << endl;
        cout << endl;
    }
    return 0;
}



邓泽军
8个月前
#include <bits/stdc++.h>
using namespace std;

bool check(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n / i; i ++) {
        if (n % i == 0) 
            return false;
    }
    return true;
}

int main() {
    int n; 
    int a;
    cin >> n;
    while (n --) {
        cin >> a;
        if (check(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}



邓泽军
8个月前

题目描述

和39题基本一样,只需要稍微改一点,每个数只能用一次。可以判断去重,也可以用set去重。

C++ 代码

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        set<vector<int>> res;
        vector<int> path;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, path, res);
        return vector<vector<int>> (res.begin(), res.end());
    }
    void dfs(vector<int>&a, int target, int start, vector<int>&path, set<vector<int>>&res) {
        if (target < 0) return;
        if (target == 0) {
            res.insert(path);
            return;
        }
        for (int i = start; i < a.size(); i ++) {
            path.push_back(a[i]);
            dfs(a, target - a[i], i + 1, path, res);//唯一的区别是上一题这里是从当前位置i枚举,这里从i+1枚举。
            path.pop_back();

        }
    }
};



邓泽军
8个月前

题目描述

递归枚举,依次以每个点为起点枚举,每个点可以有一个或者多个,直到和大于等于target返回。

C++ 代码

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(candidates, target, 0, path, res);
        return res;
    }
    void dfs(vector<int> &a, int target, int start, vector<int> &path, vector<vector<int>> &res) {
        if (target < 0) return ;
        if (target == 0) {
            res.push_back(path); 
            return;
        }
        for (int i = start; i < a.size(); i ++) {
            path.push_back(a[i]);
            dfs(a, target - a[i], i, path, res); //i表示枚举的起点。
            path.pop_back();
        }
    }
};



邓泽军
8个月前

题目描述

从任意起点,找一条连续的路径,使得和为sum。

思路:

1.可以遍历每一条路径,在遍历的过程中,如果和为sum,那么res++
2.再依次删除这条路径之前加入的节点,如果和为sum,那么res ++。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        vector<TreeNode*> out;
        helper(root, sum, 0, out, res);
        return res;
    }
    void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>&out, int &res) {
        if (!node) return ;
        curSum += node->val;
        out.push_back(node);
        if (sum == curSum) res ++;
        int t = curSum;
        for (int i = 0; i < out.size() - 1; i ++) {// out,保存的当前路径,依次去掉路径中的点。
            t -= out[i]->val;
            if (t == sum) res ++;
        }
        helper(node->left, sum, curSum, out, res);
        helper(node->right, sum, curSum, out, res);
        out.pop_back();
    }
};



邓泽军
8个月前

题目描述

单调栈:LeetCode 42 和 85 题基本一样。将矩阵看成一个二维矩阵,以每一行为x轴,h[j]是该列的高度。

C++ 代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if (!n) return 0;
        int m = matrix[0].size();
        auto a = matrix;
        vector<int> h(m + 1, 0);
        int res = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++){
                if (a[i][j] == '0') h[j] = 0;
                else h[j] ++;
            }
            stack<int> st;
            h[m] = -1;//确保所有元素出栈。
            for (int j = 0; j <= m; j ++) {
                while (st.size() && h[st.top()] >= h[j]) {
                    int cur = st.top(); st.pop();
                    int w = st.empty() ? j : j - st.top() - 1;
                    if (w <= h[cur]) 
                        res = max(res, w * w);//如果长比宽大,那么就是宽的平方。
                    else 
                        res = max(res, h[cur] * h[cur]);
                }
                st.push(j);
            }
        }
        return res;
    }
};



邓泽军
8个月前

题目描述

1.这题不能直接求路径和最大,因为,如果走某一个点和小于等于0,就挂了。

2.可以倒着走,遇到公主后,血量最少为1.

f[i][j] = max(1, min(f[i + 1][j], f[i][j + 1]) - dungeon[i][i]);

  • f[i][j]表示到(i, j)点需要最少的血量。

  • 方便计算多添加一行一列。使f[n][m - 1] = 1, f[m][m - 1] = 1;

C++ 代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        if (!n) return 0;
        vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));
        f[n][m - 1] = 1, f[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; i --) {
            for (int j = m - 1; j >= 0; j --) {
                f[i][j] = max(1, min(f[i + 1][j], f[i][j + 1]) - dungeon[i][j]);
            }
        }
        return f[0][0];
    }
};



邓泽军
8个月前

题目描述

核心思想:记录当前的最大值和最小值。

因为,如果遇到负数,那么当前的最大值变成最小值,最小值会变成,最大值。

所以只需要记录当前最小值和最大值即可,不断的更新答案res。

C++ 代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxv = nums[0], minv = nums[0], res = nums[0];

        for (int i = 1; i < nums.size(); i ++) {
            int mx = maxv, mn = minv;
            maxv = max(nums[i], max(nums[i] * mx, nums[i] * mn));// 如果mx和mn为0,那么此时最大值为nums[i];
            minv = min(nums[i], min(nums[i] * mx, nums[i] * mn));
            res = max(res, maxv);
        }
        return res;
    }
};