房产网站的建设,哪个网站建设,成年做羞羞的视频网站,英文wordpress转中文本栏目记录本人每周写的力扣题的相关学习总结。 虽然开新的栏目都没有完成 70.爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
解题思路#xff1a; 斐波那契数列递归
class Solution {…本栏目记录本人每周写的力扣题的相关学习总结。 虽然开新的栏目都没有完成 70.爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
解题思路 斐波那契数列递归
class Solution {
public:int climbStairs(int n) {int a0,b0,c1;if(n2)return n;for(int i 1;in;i){ab,bc,cab;}return c;}
};1.两数之和 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解题思路 暴力枚举
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int i,j;for(i0;inums.size()-1;i){for(ji1;jnums.size();j){if(nums[i]nums[j]target){return {i,j};}}}return {i,j};};
};88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
解题思路最后必须返回的是nums1数组wa了2发把nums2数组加到nums1数组后面然后进行排序即可。
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int temp;for(int im,j0;inm;i,j){nums1[i]nums2[j];}sort(nums1.begin(),nums1.end());}
};移动零 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
解题思路采用双指针左指针指向已处理好的数组尾部有指针指向未处理的部分右指针向右 遇到非零数左右指针交换同时左指针右移。 左指针左边均为非零数 右指针左边直到左指针处均为零。
class Solution {
public:void moveZeroes(vectorint nums) {int n nums.size(), left 0, right 0;while (right n) {if (nums[right]) {swap(nums[left], nums[right]);left;}right;}}
};448. 找到所有数组中消失的数字 给你一个含 n 个整数的数组 nums 其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字并以数组的形式返回结果。
解题思路哈希表记录数组内的数字 记录后再用哈希表检查[1,n]中的每一个数是否出现从而找到缺失的数字。
class Solution {
public:vectorint findDisappearedNumbers(vectorint nums) {vectorint v;int nnums.size();for(auto i:nums){int x(i-1)%n;nums[x]n;}for(int i 0;in;i){if(nums[i]n){v.push_back(i1);}}return v;}
};21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路分治排序
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1NULL){return list2;}if(list2NULL){return list1;}if(list1-vallist2-val){list1-next mergeTwoLists(list1-next,list2);return list1;}list2-nextmergeTwoLists(list1,list2-next);return list2;}
};83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。
解题思路判断是否与下一个节点元素相同 如果相同删除下一个节点。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(headNULL) return head;ListNode* node head;while(node-next!NULL){if(node-next-valnode-val){node-nextnode-next-next;}elsenode node-next;}return head;}
};21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路分治排序
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1NULL){return list2;}if(list2NULL){return list1;}if(list1-vallist2-val){list1-next mergeTwoLists(list1-next,list2);return list1;}list2-nextmergeTwoLists(list1,list2-next);return list2;}
};141. 环形链表 142.环形链表2 给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
解题思路 利用哈希集合判断链表中的每个节点并将它记录下来一旦遇到了此前遍历过的节点就可以判定链表中存在环。借助哈希表可以很方便地实现。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {unordered_setListNode * s;while(head!NULL){if(s.count(head))return true;s.insert(head);headhead-next;}return false;}
};160. 相交链表
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交
题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。 解题思路 判断两个链表是否相交可以使用哈希集合存储链表节点。
首先遍历链表 headA并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB对于遍历到的每个节点判断该节点是否在哈希集合中
如果当前节点不在哈希集合中则继续遍历下一个节点
如果当前节点在哈希集合中则后面的节点都在哈希集合中即从当前节点开始的所有节点都在两个链表的相交部分因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点返回该节点。
如果链表 headB 中的所有节点都不在哈希集合中则两个链表不相交返回 null
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_setListNode * s;ListNode* node headA;while(node!nullptr){s.insert(node);nodenode-next;}node headB;while(node!nullptr){if(s.count(node)){return node;}s.insert(node);nodenode-next;}return nullptr;}
};206.反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。
解题思路: 创建新链表记录值并传给栈利用栈先进后出的特性赋值给链表。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* L;L head;stackint s;while(L!nullptr){s.push(L-val);LL-next;} Lhead;while(L!nullptr){L-vals.top();s.pop();LL-next;} return head;}
};234. 回文链表 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
解题思路 传进数组内遍历比较。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* L;Lhead;vectorint s;while(L!nullptr){s.push_back(L-val);LL-next;}int j s.size()-1;for(int i 0;is.size()/2;i,j--){if(s[i]!s[j])return false;}return true;}
};876. 链表的中间结点 给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。 解题思路 创建链表数组返回一半。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* middleNode(ListNode* head) {vectorListNode* A {head};while (A.back()-next ! NULL)A.push_back(A.back()-next);return A[A.size() / 2];}
};
感谢观看
