Darron

2.9万

zufestudy6
IER
zhuzuojun
Aze

daftchris

Arthur_5

ZC最温柔
Tianxn
1176927355@qq.com

life_lzp
tianming
luxcgo

Darron
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;
}


## 例题

### 数的范围

#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 = [1,2,3,1]



输入：nums = [1,2,1,3,5,6,4]

或者返回索引 5， 其峰值元素为 6。


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;
}
};


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;
}
};


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都在右边，返回右边那个
}
};


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;
}


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];
}
};


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;

}
};