class Solution
{
public:
bool hasCycle(ListNode *head)
{
unordered_set<ListNode *> hash;
while (head != nullptr)
{
if (hash.find(head) != hash.end())
return true;
hash.insert(head);
head = head->next;
}
return false;
}
};
class Solution
{
public:
bool hasCycle(ListNode *head)
{
if (head == nullptr)
return false;
ListNode *slow = head;
ListNode *fast = head->next;
while (fast && fast->next)
{
if (slow == fast)
return true;
slow = slow->next;
fast = fast->next->next;
}
return false;
}
};
class Solution
{
public:
ListNode *removeNthFromEnd(ListNode *head, int n)
{
ListNode *next = head;
ListNode *nth_pre = head;
int i = 0;
while (next)
{
i++;
if (i > n + 1)
nth_pre = nth_pre->next;
next = next->next;
}
if (n == i)
return head->next;
ListNode *tmp = nth_pre->next;
nth_pre->next = nth_pre->next->next;
delete tmp;
return head;
}
};
class Solution
{
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode res(0);
ListNode *l3 = &res;
int digit, rest = 0;
while (l1 || l2 || rest)
{
digit = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + rest;
rest = digit / 10;
l3->next = new ListNode(digit % 10);
l3 = l3->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return res.next;
}
};
class Solution
{
public:
ListNode *reverseList(ListNode *head)
{
ListNode *pre = nullptr;
ListNode *cur = head;
while (cur)
{
ListNode *tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
class Solution
{
public:
ListNode *reverseList(ListNode *head)
{
if (!head || !head->next)
return head;
ListNode *tmp = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return tmp;
}
};
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode tmp(0);
ListNode *cur = &tmp;
while (l1 != nullptr && l2 != nullptr)
{
if (l1->val < l2->val)
{
cur->next = l1;
cur = l1;
l1 = l1->next;
} else
{
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}
if (l1 == nullptr)
cur->next = l2;
else
cur->next = l1;
return tmp.next;
}
};
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int,int> index;
for(int i = 0; i<nums.size(); i++)
{
int element = target - nums[i];
if(index.find(element)!=index.end())
{
return vector<int>{i,index[element]};
}
index[nums[i]] = i;
}
}
};
class Solution
{
public:
int myAtoi(string str)
{
int sign = 1, base = 0, i = 0;
while (str[i] == ' ')
i++;
if (str[i] == '-' || str[i] == '+')
sign = 1 - 2 * (str[i++] == '-');
while (str[i] >= '0' && str[i] <= '9')
{
if (base > INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7))
{
if (sign == 1)
return INT_MAX;
else
return INT_MIN;
}
base = 10 * base + (str[i++] - '0');
}
return base * sign;
}
};
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
int left = 0, right = nums.size() - 1;
while (true)
{
int pos = partition(nums, left, right);
if (pos == k - 1) return nums[pos];
else if (pos > k - 1) right = pos - 1;
else left = pos + 1;
}
}
int partition(vector<int>& nums, int left, int right)
{
int pivot = nums[left], l = left + 1, r = right;
while (l <= r)
{
if (nums[l] < pivot && nums[r] > pivot)
{
swap(nums[l++], nums[r--]);
}
if (nums[l] >= pivot) ++l;
if (nums[r] <= pivot) --r;
}
swap(nums[left], nums[r]);
return r;
}
};
class Solution
{
public:
int findKthLargest(vector<int> &nums, int k)
{
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < k; i++)
pq.push(nums[i]);
for (int i = k; i < nums.size(); i++)
{
if (nums[i] > pq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};
class Solution
{
public:
int search(vector<int> &nums, int target)
{
int start = 0, end = nums.size() - 1;
while (start <= end)
{
int mid = (end + start) / 2;
if (nums[mid] == target)
return mid;
if (nums[start] <= nums[mid])
{
int res = binary_search(nums, start, mid, target);
if (res == -1)
start = mid + 1;
else
return res;
} else
{
int res = binary_search(nums, mid + 1, end, target);
if (res == -1)
end = mid - 1;
else
return res;
}
}
return -1;
}
int binary_search(vector<int> &nums, int start, int end, int target)
{
while (start <= end)
{
int mid = (start + end) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
start = mid + 1;
if (nums[mid] > target)
end = mid - 1;
}
return -1;
}
};
class Solution
{
public:
long long reversePairs(vector<int> &A)
{
if (!A.size())
return 0;
long long counter = 0;
vector<int> tmp(A);
merge(A, tmp, 0, A.size() - 1, counter);
return counter;
}
void merge(vector<int> &A, vector<int> &tmp, size_t l, size_t r, long long &counter)
{
if (l >= r) return;
size_t mid = (r - l + 1) / 2 + l;
merge(A, tmp, l, mid - 1, counter);
merge(A, tmp, mid, r, counter);
size_t i = l, l1 = l, l2 = mid;
while (l1 <= mid - 1 && l2 <= r)
{
if (tmp[l1] <= tmp[l2])
{
A[i++] = tmp[l1++];
} else
{
A[i++] = tmp[l2++];
counter += mid - l1;
}
}
while (l1 <= mid - 1)
A[i++] = tmp[l1++];
while (l2 <= r)
A[i++] = tmp[l2++];
tmp = A;
}
};
class Solution
{
public:
int counter = 0;
int res = 0;
int kthSmallest(TreeNode* root, int k)
{
if(root == nullptr)
return 0;
kthSmallest(root->left,k);
counter++;
if(counter==k)
res = root->val;
kthSmallest(root->right,k);
return res;
}
};
class Solution
{
public:
int res = INT_MIN;
int maxPathSum(TreeNode* root)
{
fun(root);
return res;
}
int fun(TreeNode* root)
{
if(!root)
return 0;
int left = max(0,fun(root->left));
int right = max(0,fun(root->right));
res = max(res, root->val + left + right);
return max(left,right)+root->val;
}
};
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
vector<vector<int>> res;
if(root==0) return res;
queue<TreeNode*> que;
que.push(root);
int size = 1, level = 0;
while(!que.empty())
{
int nextSize = 0;
vector<int> currLevelNodes;
for(int i=0; i<size; ++i)
{
TreeNode* curr = que.front();
currLevelNodes.push_back(curr->val);
if(curr->left!=0)
{
que.push(curr->left); nextSize++;
}
if(curr->right!=0)
{
que.push(curr->right); nextSize++;
}
que.pop();
}
res.push_back(currLevelNodes);
level++; size = nextSize;
}
return res;
}
};
class Solution
{
public:
bool isBalanced(TreeNode* root)
{
if (!root)
return true;
if (abs(getDepth(root->left) - getDepth(root->right)) > 1)
return false;
return isBalanced(root->left) && isBalanced(root->right);
}
int getDepth(TreeNode* root)
{
if (!root)
return 0;
return 1 + max(getDepth(root->left), getDepth(root->right));
}
};
class MinStack
{
public:
MinStack()
{
Min = INT_MAX;
}
void push(int x)
{
Min = Min < x ? Min : x;
s1.push(x);
s2.push(Min);
}
void pop()
{
s1.pop();
s2.pop();
if(!s2.empty())
Min = s2.top();
else
Min = INT_MAX;
}
int top()
{
return s1.top();
}
int getMin()
{
return s2.top();
}
stack<int> s1;
stack<int> s2;
int Min;
};
二叉树最远两节点
问题：请给出一个时间为O(nlgk)，用来将k个已排序数组合并为一个排序数组的算法。此处的n为所有输入数组中元素的总数。（提示：用一个最小堆来做k路合并）
编程思路：
（1）取k个元素建立最小堆，这k个元素分别是k个数组的第一个元素。建堆的时间复杂度O(k)。
（2）堆顶元素就是k个数组中最小的那个元素，取出它。时间复杂度O(1)。
（3）若堆顶元素所在数组不为空，则取下一个元素放到堆顶位置，这可能破坏了最小堆性质，所以进行堆调整。堆调整时间复杂度O(lgk)。若为空，则此子数组已经被合并完毕，则删除最小堆的堆顶元素，此时最小堆的heapSize减小了1 。删除指定元素时间复杂度O(lgk)。
有 25 匹马和 5 条赛道，赛马过程无法进行计时，只能知道相对快慢。问最少需要几场赛马可以知道前 3 名。
先把 25 匹马分成 5 组，进行 5 场赛马，得到每组的排名。再将每组的第 1 名选出，进行 1 场赛马，按照这场的排名将 5 组先后标为 A、B、C、D、E。可以知道，A 组的第 1 名就是所有 25 匹马的第 1 名。而第 2、3 名只可能在 A 组的 2、3 名，B 组的第 1、2 名，和 C 组的第 1 名，总共 5 匹马，让这 5 匹马再进行 1 场赛马，前两名就是第 2、3 名。所以总共是 5+1+1=7 场赛马。
A 组：1，2，3，4，5
B 组：1，2，3，4，5
C 组：1，2，3，4，5
D 组：1，2，3，4，5
E 组：1，2，3，4，5
一栋楼有 100 层，在第 N 层或者更高扔鸡蛋会破，而第 N 层往下则不会。给 2 个鸡蛋，求 N，要求最差的情况下扔鸡蛋的次数最少。
分析：试着从10楼开始扔鸡蛋，然后是20层，30层。。。。。100层
如果鸡蛋1在第十层（随便举例子的一个数值也可以是别的数，看到后面就会知道这个值应该取14，但是刚开始分析谁也不知道该取14不是么）扔下，鸡蛋摔碎。那么第二个鸡蛋只需要从1-9层依次扔下去试就能试出来是1-10中的第几层，所以最差在恰好在第十层才能摔碎，结果是1+9=10次
如果鸡蛋1在第100层是才摔碎，实验楼层依次是：10层、20层、30层、、、100层，试验了10次。在第90层时鸡蛋没有摔碎，但是在100层摔碎了。这说明N在[90,100]区间内，所以鸡蛋2只需要从91层楼开始试验，最差一直试验到99层必然会测试出N的值。最差次数：鸡蛋1的次数10次 + 鸡蛋2的次数9次 = 19次。
设计一种扔鸡蛋的方法，使得扔鸡蛋1的次数无论是第一次还是最后一次扔下的次数越稳定越好。
负载均衡方法：扔鸡蛋 1的次数 和扔鸡蛋2的次数的和 不论什么时候都是一样的，鸡蛋1多扔一次鸡蛋2 就少扔一次，假如开始扔鸡蛋1的初始楼层是x层，那么扔鸡蛋2初始楼层是由扔鸡蛋1是否摔碎决定的。即，鸡蛋1摔碎的那一楼层 和 扔鸡蛋1的摔碎之前扔的那一次楼层数之间的差值减1（假设鸡蛋1从20层开始扔下，没碎；从30层扔下，碎了，那么鸡蛋2 就得从21层开始扔，最差一直扔到29层就能判断出N的值了），如果在x层扔下没碎，那么下一次扔的楼层就是x+x-1层（第一次是20层，下一次就是20+20-1=39层）鸡蛋2的次数相应的就减去1次；第二次没碎，下次从x+ x-1 + x-2层扔下（承接上面括号的例子：20+19+18 = 57层），依次类推.....
也就是 ： x + (x-1)+ (x-2)+。。。+1=100求一下x值 x = 14.先从14层往下扔，没碎的前提下再从14+13=27层往下扔。最差的情况下就是第一次在14层恰好摔碎了，鸡蛋2只需要从1-13层个扔一次就能判断出N的值了
对一批编号为1-100，全部开关朝上（开）的灯进行以下操作：凡是1的倍数反方向拨一次开关；2的倍数反方向又拨一次开关；3的倍数反方向又拨一次开关……问：最后为关熄状态的灯的编号是哪些？
熄灭的灯需要开关奇数次，对于任意只一个整数c，如果c能被a整除，那么必然也能被c/a整除，但是对于平方数而言c/a == a所以它们总共有奇数个约数而其他的数的约数个数都为偶数。所以关熄的灯的编号为1、4、9、16、25、36、49、64、81、100。
char * strcpy(char *dst, const char *src)
{
assert(dst && src);
char *ret = dst;
while ((*dst++=*src++)!='\0');
return ret;
}
int strcmp(const char *str1, const char *str2)
{
assert(str1 && str2);
int ret=0;
while( !(ret = *(unsigned char*)str1 - *(unsigned char*)str2 ) && *str1 )
{
str1++;
str2++;
}
if(ret < 0)
return -1;
else if(ret > 0)
return 1;
return 0;
}
char *strcat(char *str1, char *str2)
{
assert(str1 && str2);
char *res = str1;
while(*str1!='\0') str1++;
while(*str2!='\0') *str1++ = *str2++;
*str1 = '\0';
return res;
}
void* memcpy(void* dst, const void* src, size_t n)
{
assert(dst && src);
char *p1 = (char*)dst;
char *p2 = (char*)src;
while(n--)
*p1++ = *p2++;
return dst;
}
void* memmove(void* dst, const void* src, size_t n)
{
assert(dst && src);
char* p1 = (char*)dst;
char* p2 = (char*)src;
if(p1>p2 && (p2+n>p1))
{
p1 += n-1;
p2 += n-1;
while(n--)
*p1-- = *p2--;
}else
{
while(n--)
*p1++ = *p2++;
}
return dst;
}
if ( (a>0) && (a & (a-1)==0 )
#include <iostream>
#include <memory>
template<typename T>
class SmartPointer {
private:
T* _ptr;
size_t* _count;
public:
SmartPointer(T* ptr = nullptr) :
_ptr(ptr) {
if (_ptr != nullptr) {
_count = new size_t(1);
} else {
_count = new size_t(0);
}
}
SmartPointer(const SmartPointer& ptr) {
if (this != &ptr) {
this->_ptr = ptr._ptr;
this->_count = ptr._count;
(*this->_count)++;
}
}
SmartPointer& operator=(const SmartPointer& ptr) {
if (this->_ptr == ptr._ptr) {
return *this;
}
if (this->_ptr != nullptr) {
(*this->_count)--;
if (*this->_count == 0) {
delete this->_ptr;
delete this->_count;
}
}
this->_ptr = ptr._ptr;
this->_count = ptr._count;
(*this->_count)++;
return *this;
}
T& operator*() {
assert(this->_ptr == nullptr);
return *(this->_ptr);
}
T* operator->() {
assert(this->_ptr == nullptr);
return this->_ptr;
}
~SmartPointer() {
(*this->_count)--;
if (*this->_count == 0) {
delete this->_ptr;
delete this->_count;
}
}
size_t use_count(){
return *this->_count;
}
};
#include <iostream>
#include <list>
class MemoryPool {
public:
MemoryPool(size_t size, int blockCount = 50) {
chunkSize_ = size;
if(chunkSize_ < sizeof(Node))
chunkSize_ = sizeof(Node);
size *= blockCount;
allocMemorySize_ = size;
// 预分配内存
pool_ = operator new(size);
// 初始化空闲链表
freeList_ = nullptr;
char* p = static_cast<char*>(pool_);
for(int i = 0; i < blockCount; ++i) {
Node* node = reinterpret_cast<Node*>(p);
node->next = freeList_;
freeList_ = node;
p += chunkSize_;
}
}
~MemoryPool() {
operator delete(pool_);
}
// 分配内存
void* alloc(size_t size) {
if(size > chunkSize_ || freeList_ == nullptr)
return nullptr;
Node* node = freeList_;
freeList_ = node->next;
return node;
}
// 释放内存
void dealloc(void* p) {
Node* node = static_cast<Node*>(p);
node->next = freeList_;
freeList_ = node;
}
private:
// 定义链表节点
struct Node {
Node* next;
};
void* pool_; // 预分配的内存
Node* freeList_; // 空闲链表
size_t chunkSize_; // 预分配内存的块大小
size_t allocMemorySize_; // 预分配的内存大小
};
int main() {
// 创建一个容纳50个int的内存池
MemoryPool intPool(sizeof(int), 50);
// 分配一个int
int* p1 = static_cast<int*>(intPool.alloc(sizeof(int)));
*p1 = 20;
std::cout << "*p1: " << *p1 << std::endl;
// 释放一个int
intPool.dealloc(p1);
return 0;
}
template<typename T>
class Queue {
public:
T pop() {
std::unique_lock<std::mutex> mlock(mutex_);
while (queue_.empty()) {
cond_.wait(mlock);
}
auto item = queue_.front();
queue_.pop();
return item;
}
void push(const T& item) {
std::unique_lock<std::mutex> mlock(mutex_);
queue_.push(item);
mlock.unlock();
cond_.notify_one();
}
Queue()=default;
Queue(const Queue&) = delete; // disable copying
Queue& operator=(const Queue&) = delete; // disable assignment
private:
std::queue<T> queue_;
std::mutex mutex_;
std::condition_variable cond_;
};
#include <vector>
#include <queue>
#include <atomic>
#include <future>
#include <thread>
#include <functional>
#include <stdexcept>
class ThreadPool {
public:
ThreadPool(size_t);
template<class F, class... Args>
auto enqueue(F&& f, Args&&... args)
-> std::future<typename std::result_of<F(Args...)>::type>;
~ThreadPool();
private:
// 线程池
std::vector< std::thread > workers;
// 任务队列
std::queue< std::function<void()> > tasks;
// 同步
std::mutex queue_mutex;
std::condition_variable condition;
bool stop;
};
inline ThreadPool::ThreadPool(size_t threads)
: stop(false)
{
for(size_t i = 0;i<threads;++i)
workers.emplace_back(
[this]
{
for(;;)
{
std::function<void()> task;
{
std::unique_lock<std::mutex> lock(this->queue_mutex);
this->condition.wait(lock,
[this]{ return this->stop || !this->tasks.empty(); });
if(this->stop && this->tasks.empty())
return;
task = std::move(this->tasks.front());
this->tasks.pop();
}
task();
}
}
);
}
// add new work item to the pool
template<class F, class... Args>
auto ThreadPool::enqueue(F&& f, Args&&... args)
-> std::future<typename std::result_of<F(Args...)>::type>
{
using return_type = typename std::result_of<F(Args...)>::type;
auto task = std::make_shared< std::packaged_task<return_type()> >(
std::bind(std::forward<F>(f), std::forward<Args>(args)...)
);
std::future<return_type> res = task->get_future();
{
std::unique_lock<std::mutex> lock(queue_mutex);
// don't allow enqueueing after stopping the pool
if(stop)
throw std::runtime_error("enqueue on stopped ThreadPool");
tasks.emplace([task](){ (*task)(); });
}
condition.notify_one();
return res;
}
// the destructor joins all threads
inline ThreadPool::~ThreadPool()
{
{
std::unique_lock<std::mutex> lock(queue_mutex);
stop = true;
}
condition.notify_all();
for(std::thread &worker: workers)
worker.join();
}