什么样的网站需要数据库,佛山网站建设推荐,网站推广外包公司哪家好,长春建站模板厂家1.
要找俩个数使其相加等于一个数#xff0c;那么俩个数从头尾出发#xff0c;先动一边#xff0c;假设是尾先动#xff0c;一开始俩个数相加大于sum#xff08;小于的话就动头#xff09;#xff0c;那么总有一时刻俩数相加小于sum#xff0c;则就在那一刻停下来那么俩个数从头尾出发先动一边假设是尾先动一开始俩个数相加大于sum小于的话就动头那么总有一时刻俩数相加小于sum则就在那一刻停下来然后动头那一边去逼近sum最坏情况就是俩个数字相遇了时间复杂度就为ON
2.
可以通过一直替换T(n-1)使其变成常数每次降低一次就为有里面减一到外面来因为时间复杂度看的是最大级所以是0N 3 . 思路一
在开俩个数组去存放数据一个存放k个一个存放numsSize-k个先把它们分隔开然后再都放进原来的数组里就可以达到要求
代码实现
void rotate(int* nums, int numsSize, int k) {int k1k%numsSize;int* a(int*)malloc(sizeof(int)*(numsSize-k1));int* b(int*)malloc(sizeof(int)*k1);for(int i0;inumsSize-k1;i){a[i]nums[i];}for(int j0;jk1;j){b[j]nums[numsSize-k1j];}for(int z0;zk1;z){nums[z]b[z];}for(int t0;tnumsSize-k1;t){nums[tk1]a[t];}
}
思路二
先转置整个数组数字然后在转置k-1个元素最后转置k到numsSize的数组数字这样就调换了以k分成俩边数组的位置
代码实现
void reverse(int* nums, int begin, int end)
{while (begin end){int tmp nums[begin];nums[begin] nums[end];nums[end] tmp;begin;--end;}
}// 三趟逆置倒的思路
void rotate(int* nums, int numsSize, int k) {if (k numsSize){k % numsSize;}reverse(nums, 0, numsSize - 1);reverse(nums, 0, k - 1);reverse(nums, k, numsSize - 1);
}4. 思路
要找到确失的数字可以把这个数全部加起来然后再重新创建一个不却数字的数组把这个也加起来然后俩个相减得到值就是缺少的值
代码实现
int missingNumber(int* nums, int numsSize){int b0;int c0;int* a(int*)malloc(sizeof(int)*(numsSize1));for(int i0;inumsSize;i){a[i]i;}for(int i0;inumsSize;i){bnums[i];}for(int i0;inumsSize;i){ca[i];}return c-b;
}5. 思路一
总数-k为正数第几个把总数算出来在和k相减就可以知道在哪一个位置
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
int gettree(struct ListNode* head)
{int size0;while(head){headhead-next;size;}return size;
}int kthToLast(struct ListNode* head, int k){struct ListNode* curhead;int agettree(head);int ca-k;while(c--){curcur-next;}return cur-val;
}思路二
快慢指针先让fast走k步后让fast和slow一起走slow一共会走总数-k步也可以走到对应位置
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {struct ListNode* slow pListHead;struct ListNode* fast slow;while (k--){if (fast)fast fast-next;elsereturn NULL;}while (fast){slow slow-next;fast fast-next;}return slow;}
}; 6. 思路 1
快慢指针先找到中间结点然后逆置中间后面的结点最后跟前半部分对比
代码实现
这一步是找中间结点
while(fastfast-next){slowslow-next;fastfast-next-next;}
这一步是逆置中间后面的结点然后把连接方向改变
ListNode* curNULL;ListNode* nextA;while(slow){nextslow-next;slow-nextcur;curslow;slownext;}把前半部分和后半部分进行对比
nextA;while(cur){if(next-val!cur-val){return false;}nextnext-next;curcur-next;}return true; 总代码
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {ListNode* fastA;ListNode* slowA;while(fastfast-next){slowslow-next;fastfast-next-next;}ListNode* curNULL;ListNode* nextA;while(slow){nextslow-next;slow-nextcur;curslow;slownext;}nextA;while(cur){if(next-val!cur-val){return false;}nextnext-next;curcur-next;}return true;}
};
思路二
可以把值都放进数组里面但是如果题目没告诉链表最大值就不能使用这个方法
放进数组后把头尾的值取出来进行对比一直往中间
代码实现 class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint a[900] { 0 };ListNode* cur A;int n 0;//保存链表元素while (cur){a[n] cur-val;cur cur-next;}//判断数组是否为回文结构int begin 0, end n - 1;while (begin end){if (a[begin] ! a[end])return false;begin;--end;}return true;}
}; 7. 思路
因为俩个链表长度有可能不一样长所以需要让长的链表先走使得出发时俩个俩个链表等长 就可以找到最后一个相等的结点(不是找第一个相等的而是找最后一个)
代码实现
计算俩个链表计数 int a0;int b0;struct ListNode* aaheadA;struct ListNode* bbheadB;while(aa){a;aaaa-next;}while(bb){b;bbbb-next;} 找到俩个链表的长的哪一个可以用假设法可以节省很多步骤先假设1大2小不是就调整非常方便
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int a0;int b0;struct ListNode* aaheadA;struct ListNode* bbheadB;while(aa){a;aaaa-next;}while(bb){b;bbbb-next;}int ca-b0?a-b:b-a;struct ListNode* long1headA;struct ListNode* short1headB;if(ab){long1headB;short1headA;}while(c--){long1long1-next;}while(short1long1){if(short1long1){return long1;}else{long1long1-next;short1short1-next;}}return NULL;
}8. 思路
因为要复制出一个与原链表一样的东西出来所以可以在每个结点后面跟一个新结点 代码实现
1.创建新结点连在原链表的后面并把val值也复制过去 struct Node* curhead;while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;copy-nextcur-next;cur-nextcopy;curcopy-next;}
2 .把random的也复制过去
curhead;struct Node* copyheadNULL;struct Node* copytailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curnext;}
3.把复制的链表从原链表上拆下来 curhead;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(copytailNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopytail-next;}cur-nextnext;curnext;}return copyhead;
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* curhead;while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;copy-nextcur-next;cur-nextcopy;curcopy-next;}curhead;struct Node* copyheadNULL;struct Node* copytailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curnext;}curhead;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;if(copytailNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopytail-next;}cur-nextnext;curnext;}return copyhead;
}
