网站建设企业宣传,在哪个网站可以查做项目中标的,个人做商贸网站,广州企业建站 网络服务有序数组的平方
方法一#xff1a;暴力求解 排序
暴力先求平方#xff0c;然后NT直接用sort这个方法首先对数组中的每个元素求平方#xff0c;然后进行排序。下面是对应的C代码#xff1a;
class Solution {
public:vectorint SortedSquare(vectorint暴力求解 排序
暴力先求平方然后NT直接用sort这个方法首先对数组中的每个元素求平方然后进行排序。下面是对应的C代码
class Solution {
public:vectorint SortedSquare(vectorint nums) {for (int i 0; i nums.size(); i){nums[i] * nums[i];}sort(nums.begin(),nums.end()); return nums;}
};
方法二双指针
这个方法使用双指针来对原始数组进行处理。通过双指针的方式将平方后的数组按从大到小的顺序填充到新的结果数组中
class Solution {
public:vectorint SortedSquare(vectorint nums) {int k nums.size() - 1;vectorint 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, vectorint 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, vectorint nums) {int result INT_MAX;int sublen 0;int sum 0;int i0;for (int j 0; j nums.size(); j) {sum nums[j];if (sum s) {sublen j - i 1;result resultsublen?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后//如果不再加上一句tmpnullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp会指向难以预想的内存空间tmpnullptr;_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 strto_string(num);int multi1;int sum0;for(char c:str){int tempc-0;sumtemp;multi*temp;}return multi-sum;}
};class Solution{public:int Subaddmultiply(int num ){int nnum;int multi1;int sum0;while(n){int xn%10;n/10;sumtemp;multi*temp;}return multi-sum;}
};//老六就爱简单题
用栈实现队列
输入栈与输出栈一个进栈一个出栈将后进先出反向组合变成了先进先出
class MyQueue {StackInteger stackIn;StackInteger 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());}}
}
