备赛蓝桥杯--算法题目(1)
1. 链表求和
. - 力扣（LeetCode）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr, *tail = nullptr;
int carry = 0;
while (l1 || l2) {
int n1 = l1 ? l1->val: 0;
int n2 = l2 ? l2->val: 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);
}
return head;
}
};
2. 分割链表
. - 力扣（LeetCode）
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* shead=new ListNode;
ListNode* srear=shead;
ListNode* bhead=new ListNode;
ListNode* brear=bhead;
ListNode* tmp=head;
while(tmp)
{
if((tmp->val)>=x)
{
if(bhead==nullptr)
{
bhead=brear=tmp;
}
else{
brear->next=tmp;
brear=brear->next;
}
}
else{
if(shead==nullptr)
{
shead=srear=tmp;
}
else{
srear->next=tmp;
srear=srear->next;
}
}
tmp=tmp->next;
}
brear->next=nullptr;
srear->next=bhead->next;
return shead->next;
}
};3. 最小栈
. - 力扣（LeetCode）
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
s1=new stack<int>;
s2=new stack<int>;
}
void push(int x) {
s1->push(x);
if(s2->empty())
{
s2->push(x);
}
else{
if(x<=s2->top())
{
s2->push(x);
}
}
}
void pop() {
if(s1->top()==s2->top())
{
s2->pop();
}
s1->pop();
}
int top() {
return s1->top();
}
int getMin() {
return s2->top();
}
private:
stack<int>* s1;
stack<int>* s2;
};4. 二叉树的前序，中序，后序遍历
. - 力扣（LeetCode）
#include<stack>
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> tmp;
if(root!=nullptr)
{
TreeNode* head=root;
stack<TreeNode*> s;
s.push(head);
while(!s.empty())
{
head=s.top();
tmp.push_back(head->val);
s.pop();
if(head->right!=nullptr)
{
s.push(head->right);
}
if(head->left!=nullptr)
{
s.push(head->left);
}
}
}
return tmp;
}
};. - 力扣（LeetCode）
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> tmp;
stack<TreeNode*> s;
TreeNode* head=root;
while(!s.empty()||head!=nullptr)
{
while(head!=nullptr)
{
s.push(head);
head=head->left;
}
head=s.top();
tmp.push_back(head->val);
s.pop();
head=head->right;
}
return tmp;
}
};. - 力扣（LeetCode）
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> tmp;
stack<TreeNode*> s;
TreeNode* head=root;
TreeNode* ptr=root;
while(!s.empty()||head!=nullptr)
{
while(head!=nullptr)
{
s.push(head);
head=head->left;
}
head=s.top();
s.pop();
if(head->right==nullptr||head->right==ptr)
{
tmp.push_back(head->val);
ptr=head;
head=nullptr;
}
else{
s.push(head);
head=head->right;
}
}
return tmp;
}
};5. 设计循环队列
. - 力扣（LeetCode）
class MyCircularQueue {
private:
int front;
int rear;
int capacity;
vector<int> elements;
public:
MyCircularQueue(int k) {
this->capacity = k + 1;
this->elements = vector<int>(capacity);
rear = front = 0;
}
bool enQueue(int value) {
if (isFull()) {
return false;
}
elements[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
bool deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
return true;
}
int Front() {
if (isEmpty()) {
return -1;
}
return elements[front];
}
int Rear() {
if (isEmpty()) {
return -1;
}
return elements[(rear - 1 + capacity) % capacity];
}
bool isEmpty() {
return rear == front;
}
bool isFull() {
return ((rear + 1) % capacity) == front;
}
};6. 排序数组
. - 力扣（LeetCode）
static int first,last;
class Solution {
vector<int> tmp;
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
int i = l, j = mid + 1;
int cnt = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[cnt++] = nums[i++];
}
else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {
tmp[cnt++] = nums[i++];
}
while (j <= r) {
tmp[cnt++] = nums[j++];
}
for (int i = 0; i < r - l + 1; ++i) {
nums[i + l] = tmp[i];
}
}
void randomized_quicksort(vector<int>& nums, int l, int r) {
if (l < r) {
int j = rand() % (r - l + 1) + l;
first=l,last=r;
int i=l,x=nums[j];
while(i<=last)
{
if(nums[i]==x)
{
i++;
}
else if(nums[i]<x)
{
swap(nums[first++],nums[i++]);
}
else{
swap(nums[last--],nums[i]);
}
}
int left=first,right=last;
randomized_quicksort(nums, l, left - 1);
randomized_quicksort(nums, right + 1, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL));
tmp.resize((int)nums.size(), 0);
//mergeSort(nums, 0, (int)nums.size() - 1);
randomized_quicksort(nums,0,(int)nums.size() - 1);
return nums;
}
};7. 求数组第k个最大元素
. - 力扣（LeetCode）
static int first,last;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int m=nums.size()-k;
srand((unsigned)time(NULL));
return test(nums,m);
}
int test(vector<int>& nums,int i)
{
int ans = 0;
for (int l = 0, r =nums.size() - 1; l <= r;) {
partition(nums, l, r, nums[l + rand()%(r-l+1)]);
if (i < first) {
r = first - 1;
} else if (i > last) {
l = last + 1;
} else {
ans = nums[i];
break;
}
}
return ans;
}
void partition(vector<int>& nums, int l, int r, int x) {
first = l;
last = r;
int i = l;
while (i <= last) {
if (nums[i] == x) {
i++;
} else if (nums[i] < x) {
swap(nums[first++],nums[i++]);
} else {
swap(nums[last--],nums[i]);
}
}
}
};