速刷算法#Day-02

 

有序数组的平方

方法一：暴力求解 + 排序

暴力先求平方，然后NT直接用sort这个方法首先对数组中的每个元素求平方，然后进行排序。下面是对应的C++代码：

class Solution {
public:vector<int> SortedSquare(vector<int>& nums) {for (int i = 0; i < nums.size(); i++){nums[i] *= nums[i];}sort(nums.begin(),nums.end());  return nums;}
};

方法二：双指针

这个方法使用双指针来对原始数组进行处理。通过双指针的方式，将平方后的数组按从大到小的顺序填充到新的结果数组中

class Solution {
public:vector<int> SortedSquare(vector<int>& nums) {int k = nums.size() - 1;vector<int> result(nums.size(), 0);for (int i = 0, j = nums.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素if (nums[i] * nums[i] < nums[j] * nums[j])  {result[k--] = nums[j] * nums[j];j--;}else {result[k--] = nums[i] * nums[i];i++;}}return result;}
};

长度最小的子数组

方法一：暴力解法

这个方法通过两遍循环暴力地遍历子数组来寻找满足条件的最小子数组长度：

  int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; // 最终的结果int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s，更新resultsubLength = j - i + 1; // 取子序列的长度result = result < subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break}}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}

方法二：滑动窗口

这个方法使用滑动窗口来寻找满足条件的最小子数组长度：

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT_MAX;int sublen = 0;int sum = 0;int i=0;for (int j = 0; j < nums.size(); j++) {sum += nums[j];if (sum >= s) {sublen = j - i + 1;result = result<sublen?result:sublen;sum -= nums[i++];}}return result == INT_MAX ? 0 : result;}
};

移除链表元素

方法一：分情况考虑头节点

这个方法首先考虑了头节点是否需要被移除，然后遍历链表中间和尾部，删除对应的节点：

class Solution{
public:ListNode* removeElements(ListNode* head, int val) {// 删除头部所有值为 val 的节点while (head != NULL && head->val == val) {ListNode* tmp = head;head = head->next;delete tmp;}// 遍历链表删除中间和尾部值为 val 的节点ListNode* cur = head;while (cur != NULL && cur->next != NULL) {if (cur->next->val == val) {ListNode* p = cur->next;cur->next = cur->next->next;delete p;} else {cur = cur->next;}}return head; // 返回处理后的链表头节点}
};

方法二：设置虚拟头结点

设置虚拟头结点即可将原头结点一视同仁

class Solution{
public:ListNode* removeElements(ListNode* head, int val) {// 创建一个虚拟节点作为头节点的前驱，简化处理ListNode* dummy = new ListNode(0);dummy->next = head;// 使用 cur 遍历链表ListNode* cur = head;while (cur != NULL && cur->next != NULL) {if (cur->next->val == val) {ListNode* p = cur->next;cur->next = cur->next->next;delete p; // 删除节点} else {cur = cur->next;}}// 更新头节点并释放虚拟节点head = dummy->next;delete dummy;return head; // 返回处理后的链表头节点}
};

设计链表

加入了虚拟头结点，方便一致操作，不用特殊讨论

这个部分是关于设计链表的实现，主要包括初始化、获取节点、在链表头和尾插入节点、在指定位置插入节点、删除节点等操作。

class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化链表MyLinkedList() {_dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点_size = 0;}// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}LinkedNode* cur = _dummyHead->next;while(index--){ // 如果--index 就会陷入死循环cur = cur->next;}return cur->val;}// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度，则返回空// 如果index小于0，则在头部插入节点void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;        LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode* cur = _dummyHead;while(index--) {cur = cur ->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;//delete命令指示释放了tmp指针原本所指的那部分内存，//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间tmp=nullptr;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur = _dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}
private:int _size;LinkedNode* _dummyHead;};

 整数的各位积和之差

转化为字符串，解决~

class Solution{public:int Subaddmultiply(int num ){string str=to_string(num);int multi=1;int sum=0;for(char c:str){int temp=c-'0';sum+=temp;multi*=temp;}return multi-sum;}
};class Solution{public:int Subaddmultiply(int num ){int n=num;int multi=1;int sum=0;while(n){int x=n%10;n/=10;sum+=temp;multi*=temp;}return multi-sum;}
};//老六就爱简单题

用栈实现队列

输入栈与输出栈一个进栈，一个出栈，将后进先出反向组合，变成了先进先出

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;/** Initialize your data structure here. */public MyQueue() {stackIn = new Stack<>(); // 负责进栈stackOut = new Stack<>(); // 负责出栈}/** Push element x to the back of queue. */public void push(int x) {stackIn.push(x);}/** Removes the element from in front of queue and returns that element. */public int pop() {    dumpstackIn();return stackOut.pop();}/** Get the front element. */public int peek() {dumpstackIn();return stackOut.peek();}/** Returns whether the queue is empty. */public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中private void dumpstackIn(){if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}