get+二分
lc2674
快慢指针
while (f->next != list && f->next->next != list)
得到的slow节点 中/偏前
ListNode* second = s->next;
// 后半 头节点
class Solution {
public:
vector<ListNode*> splitCircularLinkedList(ListNode* list)
{
vector<ListNode*> ret;
ListNode* s = list;
ListNode* f = list;
//f->next != list && f->next->next != list
while (f->next != list && f->next->next != list)
{
f = f->next->next;
s = s->next;
}
ListNode* second = s->next;
// 后半 头节点
s->next = list; // 前半 循环
ListNode* tail = second;
while (tail->next != list)
tail = tail->next;
tail->next = second;//后半 循环
return {list, second};
}
};
lc1428
逐行对每行链表用二分找首个1的列号
取所有行结果的最小列号，无1则返回-1。
class Solution {
public:
int leftMostColumnWithOne(BinaryMatrix &m) {
auto d = m.dimensions();
int r = d[0], c = d[1], res = -1;
auto bs = [&](int i, int r) {
int l = 0, k = -1;
while (l <= r)
{
int mid = l + ((r - l) >> 1);
if (m.get(i, mid) == 0)
l = mid + 1;
else
{
k = mid;
r = mid - 1;
}
}
return k;
};
for (int i = 0; i < r; i++) {
int k = bs(i, c - 1);
if (k >= 0) {
if (res == -1)
res = k;
else
res = min(res, k);
}
}
return res;
}
};