备赛蓝桥杯--算法题目(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]);}}}
};