头像

Darron




离线:11小时前


最近来访(40)
用户头像
玄澈_
用户头像
zufestudy6
用户头像
IER
用户头像
zhuzuojun
用户头像
Aze
用户头像
哈夫曼的amazing
用户头像
daftchris
用户头像
禾小青
用户头像
Arthur_5
用户头像
都督府升
用户头像
ZC最温柔
用户头像
Tianxn
用户头像
1176927355@qq.com
用户头像
嘶锅咦
用户头像
life_lzp
用户头像
tianming
用户头像
luxcgo
用户头像
星逐月丶
用户头像
云遮月酒亦寒
用户头像
教练....我想学算法

分享 二分法

Darron
2天前

二分

整数二分算法模板

二分并不一定要求单调性,而是如下图所示,左边满足某个性质,右边也满足某个性质,然后可以根据二分求边界点。

image-20211208113425041

二分思路如下:先暂时令mid = (l + r) / 2,如果check(mid) == true,那么说明mid满足某个性质。如果是左边那个性质,说明解在mid右边,因此左边的l更新为mid,如果不满足则r = mid - 1;如果是右边那个性质,说明解在mid左边,因此右边的r更新为mid,如果不满足则l = mid + 1;二分的时候最好画一下图,然后更新区间。

注意:如果check(mid) == true时更新的左边,需要回过头来更新mid = (l + r + 1) / 2,如下面两个模板。

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

例题

数的范围

给定一个按照升序排列的长度为 $n$ 的整数数组,以及 $q$ 个查询。

对于每个查询,返回一个元素 $k$ 的起始位置和终止位置(位置从 $0$ 开始计数)。

如果数组中不存在该元素,则返回 -1 -1

思路: 先查找范围的左端点,设置需要检查的性质为左端点以右的满足a[i] >= k,为啥不取左端点以左的性质呢?因为左端点以左的性质为a[i] < k,该性质左端点并不满足,所以搜到的不是左端点,而是左端点左边的一个点,因此搜索完之后还需要进一步处理;同理,再查找范围的右端点,设置需要检查的性质为右端点以右的满足a[i] <= k

#include <iostream>
using namespace std;

const int N = 100010;

int a[N];
// 查找范围的右端点,右端点以右的满足a[i] >= k
int b_search1(int l, int r, int k) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= k) r = mid;
        else l = mid + 1;
    }

    if (a[l] != k) return -1;
    return l;
}

// 查找范围的右端点,因为右端点以左的满足a[i] <= k
int b_search2(int l, int r, int k) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (a[mid] <= k) l = mid;
        else r = mid - 1;
    }
    if(a[l] != k) return -1;
    return l;
}

int main () {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    for (int i = 0; i < q; i ++ ) {
        int k;
        cin >> k;
        int l = b_search1(0, n - 1, k);
        int r = b_search2(0, n - 1, k);
        cout << l << " " << r << endl;
    }
}

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞

你必须实现时间复杂度为 O(log n)的算法来解决此问题。

示例 1:

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5 
解释:你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

思路:

题目中关键信息是 nums[-1] = nums[n] = -∞,这意味着不管 nums是升序还是降序都会有解,如果不是有序的也会有解,因此对于所有的 nums都会有解。这样我们就可以每次往相邻两个值较大的值走,比如如果 nums[mid] > nums[mid + 1],则往左边走,选择区间[l, mid],更新 r = mid,如果 nums[mid] < nums[mid + 1],则往右边走,选择区间 [mid + 1, r]

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


活动打卡代码 LeetCode 47. 全排列 II

Darron
9天前
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    void dfs(vector<int>& nums, vector<int> &visited, int p, int k) {
        if (k == 0) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i ++) {
            if (visited[i]) continue;
            path.push_back(nums[i]);
            visited[i] ++;
            dfs(nums, visited, i, k - 1);
            visited[i] --;
            path.pop_back();
            while (i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> visited(n);
        dfs(nums, visited, 0, n);
        return ans;
    }
};


活动打卡代码 AcWing 2060. 奶牛选美

Darron
12天前
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

vector<pair<int, int>> areas[2];

void find(vector<string> &strs, vector<vector<int>> &visited, int x, int y, int a) {
    int n = strs.size(), m = strs[0].size();
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;

    while (q.size()) {
        auto t = q.front();
        q.pop();
        areas[a].push_back(t);
        int x = t.first, y = t.second;
        for (int i = 0; i < 4; i ++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && !visited[xx][yy] && strs[xx][yy] == 'X') {
                q.push({xx, yy});
                visited[xx][yy] = 1;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> strs(n);
    int i = 0;
    while (i < n) {
        cin >> strs[i ++];
    }

    vector<vector<int>> visited(n, vector<int>(m));

    int a = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (!visited[i][j] && strs[i][j] == 'X') {
                find(strs, visited, i ,j, a);
                a ++;
            }
        }
    }

    int res = 1e9;
    for (auto& a: areas[0])
        for (auto& b: areas[1])
            res = min(res, abs(a.first - b.first) + abs(a.second - b.second) - 1);    

    cout << res;

    return 0;
}



Darron
14天前
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL; 
        // 如果找到p或q,直接返回。比如如果找到p,说明q要么在p子树中,返回p说明p是最近公共祖先
        // 或者就在另外一棵树,返回p表示在左边这颗树找到了p。
        if (root == p || root == q) return root; 
        auto left = lowestCommonAncestor(root->left, p, q); // 左边查找p,q
        auto right = lowestCommonAncestor(root->right, p, q); // 右边查找p,q
        if (left && right) return root; // 左右两边都找到p或q,说明root为最近公共祖先
        if (left) return left; // 如果p,q都在左边,返回左边那个
        return right; // 如果p,q都在右边,返回右边那个
    }
};


活动打卡代码 AcWing 2041. 干草堆

Darron
15天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), S(n + 1);

    // 差分
    for (int i = 0; i < k; i ++) {
        int l, r;
        cin >> l >> r;
        a[l - 1] += 1;
        a[r] -= 1;
    }

    // 求前缀和
    for (int i = 1; i <= n; i ++) S[i] = S[i - 1] + a[i - 1]; 

    sort(S.begin() + 1, S.end());
    cout << S[(n + 1) >> 1];
    return 0;
}



Darron
15天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), S(n + 1);

    // 差分
    for (int i = 0; i < k; i ++) {
        int l, r;
        cin >> l >> r;
        a[l - 1] += 1;
        a[r] -= 1;
    }

    // 求前缀和
    for (int i = 1; i <= n; i ++) S[i] = S[i - 1] + a[i - 1]; 

    sort(S.begin() + 1, S.end());
    cout << S[(n + 1) >> 1];
    return 0;
}



Darron
15天前
#include<iostream>
using namespace std;

int atoi(string str, int base) {
    int n = str.size();
    int res = 0;
    for (int i = 0; i < n; i ++) {
        res = res * base + str[i] - '0';
    }
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size(), m = b.size();

    for (int i = 0; i < n; i ++) {
        char q = a[i];
        a[i] = (q - '0') ^ 1 + '0';
        int t = atoi(a, 2);
        for (int j = 0; j < m; j ++) {
            char p = b[j];
            b[j] = '0' + (p - '0' + 1) % 3;
            if (atoi(b, 3) == t) cout << t;
            b[j] = '0' + (p - '0' + 2) % 3;
            if (atoi(b, 3) == t) cout << t;
            b[j] = p;
        }
        a[i] = q;
    }

    return 0;
}


活动打卡代码 AcWing 2058. 笨拙的手指

Darron
15天前
#include<iostream>
using namespace std;

int atoi(string str, int base) {
    int n = str.size();
    int res = 0;
    for (int i = 0; i < n; i ++) {
        res = res * base + str[i] - '0';
    }
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size(), m = b.size();

    for (int i = 0; i < n; i ++) {
        char q = a[i];
        a[i] = (q - '0') ^ 1 + '0';
        int t = atoi(a, 2);
        for (int j = 0; j < m; j ++) {
            char p = b[j];
            b[j] = '0' + (p - '0' + 1) % 3;
            if (atoi(b, 3) == t) cout << t;
            b[j] = '0' + (p - '0' + 2) % 3;
            if (atoi(b, 3) == t) cout << t;
            b[j] = p;
        }
        a[i] = q;
    }


    return 0;
}



Darron
30天前
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> res;
        int i = 0, j = 0;
        while(i < m && j < n) {
            if (nums1[i] <= nums2[j]) res.push_back(nums1[i ++]);
            else res.push_back(nums2[j ++]);
        }

        while (i < m) res.push_back(nums1[i ++]);
        while (j < n) res.push_back(nums2[j ++]);

        for (int i = 0; i < m + n; i ++) nums1[i] = res[i];
    }
};


活动打卡代码 LeetCode 5. 最长回文子串

Darron
30天前
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        const int N = n + 10;
        int f[N];
        memset(f, 0, sizeof(int) * N);
        int size = 1;
        int idx = 0;
        int k = 0;
        for (int i = 0; i < n; i ++) {
            if (i + 1 < n && i - 1 >= 0) {
                k = 1;
                while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k ++;
                if (2 * k - 1 > size) {
                    size = 2 * k - 1;
                    idx = i;
                }

            } 
            if (i + 1 < n && i >= 0) {
                k = 0;
                while (i - k >= 0 && i + k + 1 < n && s[i - k] == s[i + k + 1]) k ++;
                if (2 * k > size) {
                    size = 2 * k;
                    idx = i;
                }
            }

        }


        string res(size, '\0');

        if (size % 2 != 0) {
            int l = 1;
            while (idx - l >= 0 && idx + l < n && s[idx - l] == s[idx + l]) l ++;
            l --;
            for (int i = idx - l; i <= idx + l; i ++) {
                res[i - (idx - l)] = s[i];
            }
        } else {
            int l = 0;
            while (idx - l >= 0 && idx + l + 1 < n && s[idx - l] == s[idx + l + 1]) l ++;
            l --;
            for (int i = idx - l; i <= idx + l + 1; i ++) {
                res[i - idx + l] = s[i];
            }
        }


        return res;

    }
};