100 lines
2.3 KiB
Org Mode
100 lines
2.3 KiB
Org Mode
#+title: Inbox
|
|
* 1. two sum
|
|
#+begin_src c++
|
|
class Solution {
|
|
public:
|
|
vector<int> twoSum(vector<int> &nums, int target) {
|
|
vector<pair<int, int>> rev;
|
|
// Fix 1 & 2: Loop over nums.size() and push nums[i]
|
|
for (int i = 0; i < nums.size(); i++) {
|
|
rev.push_back({nums[i], i});
|
|
}
|
|
|
|
std::sort(rev.begin(), rev.end());
|
|
|
|
for (int i = 0; i < rev.size(); i++) {
|
|
int want = target - rev[i].first;
|
|
// Fix 3: Pass the SORTED vector 'rev' to the search
|
|
int j = bs(rev, want, i + 1);
|
|
if (j >= 0) {
|
|
int a = rev[i].second;
|
|
int b = rev[j].second;
|
|
return vector<int>{min(a, b), max(a, b)};
|
|
}
|
|
}
|
|
return {};
|
|
}
|
|
|
|
// Updated to handle vector of pairs
|
|
using PairIter = vector<pair<int, int>>::iterator;
|
|
|
|
PairIter lower_bound(PairIter l, PairIter r, int target) {
|
|
while (l < r) {
|
|
PairIter mid = l + (r - l) / 2;
|
|
if (mid->first >= target) { // Access value via .first or ->first
|
|
r = mid;
|
|
} else {
|
|
l = mid + 1;
|
|
}
|
|
}
|
|
return l;
|
|
}
|
|
|
|
int bs(vector<pair<int, int>> &indexedNums, int target, int offset) {
|
|
auto it =
|
|
lower_bound(indexedNums.begin() + offset, indexedNums.end(), target);
|
|
if (it == indexedNums.end() || it->first != target) {
|
|
return -1;
|
|
}
|
|
return it - indexedNums.begin();
|
|
}
|
|
};
|
|
#+end_src
|
|
|
|
~using PairIter = vector<pair<int, int>>::iterator;~
|
|
what is using?
|
|
|
|
we need to write binary search, lower bound search
|
|
|
|
learn about binary search functions the natural one by god
|
|
|
|
|
|
keep
|
|
#+begin_src c++
|
|
class Solution {
|
|
public:
|
|
int findMaxConsecutiveOnes(vector<int>& nums) {
|
|
bool state = false;
|
|
int prev = 0;
|
|
int best = 0;
|
|
nums.push_back(0);
|
|
for (int i=0; i<nums.size(); i++) {
|
|
if (!state && nums[i]==1) {
|
|
prev = i;
|
|
state = true;
|
|
} else if (state && nums[i]==0) {
|
|
best = std::max(best, i-prev);
|
|
state = false;
|
|
}
|
|
}
|
|
return best;
|
|
}
|
|
};
|
|
#+end_src
|
|
|
|
|
|
* TODO study: why min doesn't work with Fenwick tree (no inverse, update breaks on increase)
|
|
|
|
* Binary search
|
|
#+begin_src python
|
|
def bs(a, x, l, r):
|
|
if l >= r:
|
|
return l
|
|
|
|
m = l + (r-l) // 2
|
|
if (a[m] < x):
|
|
return bs(a, x, m+1, r);
|
|
else:
|
|
return bs(a, x, l, m)
|
|
#+end_src
|