简介：wy的leetcode刷题记录_Day86声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 3 13前言@TOC2864. 最大二进制奇数今天的每日一题是：2864. 最大二进制奇数题目介绍给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。注意 返回的结果字符串 可以 含前导零。示例 1：输入：s = "010" 输出："001" 解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。示例 2：输入：s = "0101" 输出："1001" 解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100"。所以答案是 "1001"思路统计长度为n字符串s中1的个数num1，0的个数就为n num1，于是对于返回的字符串我们令高num1 1位位1接下来的n num1位为0，最低位为1即可。代码class Solution { public: string maximumOddBinaryNumber(string s) { int num1=0; int n=s.size(); int min_odd=9; string ans=""; for(int i=0;i<n;i++) { if((s[i] '0')==1) { num1++; } } for(int i=0;i<num1 1;i++) { ans+="1"; } for(int i=0;i<n num1;i++) { ans+="0"; } ans+="1"; return ans; } };官方题解：简介代码class Solution { public: string maximumOddBinaryNumber(string s) { int cnt = count(s.begin(), s.end(), '1'); return string(cnt 1, '1') + string(s.length() cnt, '0') + '1'; } }; 收获count统计字符串中字符的个数，以及巩固了string的构建函数。3. 无重复字符的最长子串3. 无重复字符的最长子串题目介绍给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。思路模拟滑动窗口，使用一个哈希表来记录当前窗口内的元素，如果滑动窗口向后扩张时下一个元素已存在于哈希表中，代表窗口内即将有冲突，这时候我们要将窗口前端的元素进行丢弃直到可以容纳下一个元素为止，在滑动窗口扩张的过程中我们维护最长长度即可得到答案。代码class Solution { public: int lengthOfLongestSubstring(string s) { int front=0,rear=0; int n=s.size(); if(n==0) return 0; unordered_map<char,int> hash; int ans=0; while(rear<n) { if(hash[s[rear]]) { while(hash[s[rear]]) { hash[s[front]] ; front++; } } ans=max(ans,rear front+1); hash[s[rear]]++; rear++; } return ans; } };收获复习滑动窗口。438. 找到字符串中所有字母异位词438. 找到字符串中所有字母异位词题目介绍给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。示例 1:输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是"abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 示例 2:输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab"的异位词。思路跟上一题相同本题也可以使用哈希表来保存滑动窗口内的不同元素对应的个数，但在上题中我们使用的是set类型的哈希表那是因为上一题明确无重复的字符，而本题有重复的字符只能使用map来映射，这里因为字母固定26位我才用vector(26)来进行保存。代码class Solution { public: vector<int> findAnagrams(string s, string p) { int n=s.size(); int m=p.size(); if(n<m) return vector<int>(); vector<int> s1(26),p1(26); vector<int> ans; for(int i=0;i<m;i++) { s1[s[i] 'a']++; p1[p[i] 'a']++; } if(p1==s1) { ans.emplace_back(0); } for(int i=0;i<n m;i++) { s1[s[i] 'a'] ; s1[s[i+m] 'a']++; if(s1==p1) { ans.emplace_back(i+1); } } return ans; } };收获一般滑动窗口需要配合哈希表来统计窗口内部的数据。560. 和为 K 的子数组560. 和为 K 的子数组题目介绍给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1：输入：nums = [1,1,1], k = 2 输出：2 示例 2：输入：nums = [1,2,3], k = 3 输出：2思路方法一：暴力解法：枚举所有的起点，在每个起点中再枚举重点计算和是否等于k方法二：前缀和+哈希表：前缀和可以是我们计算子数组之和的时间复杂度降低，哈希表记录前缀和出现的次数，后面的思路看下题解（只可意会不可言传）...代码class Solution { public: int subarraySum(vector<int>& nums, int k) { int count = 0; for (int start = 0; start < nums.size(); ++start) { int sum = 0; for (int end = start; end >= 0; end) { sum += nums[end]; if (sum == k) { count++; } } } return count; } }; class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> hash; hash[0]=1; int count=0,pre=0; int n=nums.size(); if(n==1) return nums[0]==k?1:0; for(auto x:nums) { pre+=x; if(hash.count(pre k)) count+=hash[pre k]; hash[pre]++; } return count; } };收获emmm头晕了。53. 最大子数组和53. 最大子数组和题目介绍给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。示例 1：输入：nums = [ 2,1, 3,4, 1,2,1, 5,4] 输出：6 解释：连续子数组 [4, 1,2,1] 的和最大为 6 。示例 2：输入：nums = [1] 输出：1 示例 3：输入：nums = [5,4, 1,7,8] 输出：23思路动态规划：我先放上原文（讲的巨好）。我自己的理解就是dp[i]表示前i个元素的最大和，而前i+1个元素的最大和与dp[i]和nums[i+1]有关。代码class Solution { public: int maxSubArray(vector<int>& nums) { int ans= 10000; int n=nums.size(); for(int start=0;start<n;start++) { int sum=0; for(int end=start;end<n;end++) { sum+=nums[end]; ans=max(ans,sum); } } return ans; } };优化空间：class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); int pre=0; int ans=nums[0]; for(int i=0;i<n;i++) { pre=max(pre+nums[i],nums[i]); ans=max(ans,pre); } return ans; } };收获动态规划全忘完咯！56. 合并区间56. 合并区间题目介绍以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。示例 1：输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。思路emm说实话我一开始没思路，看了一眼评论区才有思路。先用排序（根据起点开始排序），然后将第i个区间的右边界与排序后的第i+1个区间的左边界进行比较，如果大于则相交，否则不相交。相交将较小的左边界与较大的有边界装入新的ans中，再与下一个区间进行比较。代码class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int n=intervals.size(); if(n==0) return intervals; sort(intervals.begin(),intervals.end()); vector<vector<int>> ans; for(int i=0;i<n;i++) { if(!ans.size()||ans.back()[1]<intervals[i][0])//不相交 { ans.push_back({intervals[i][0],intervals[i][1]}); } else { ans.back()[1]=max(ans.back()[1],intervals[i][1]); } } return ans; } };收获无。189. 轮转数组189. 轮转数组题目介绍给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例 1:输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]示例2:输入：nums = [ 1, 100,3,99], k = 2 输出：[3,99, 1, 100] 解释: 向右轮转 1 步: [99, 1, 100,3] 向右轮转 2 步: [3,99, 1, 100]思路方法一：反转数组，样例1：1234567.。我们先整体反转7654321，再将前k个和剩余n k个反转得5671234，即可实现。方法二：使用额外数组来保存原数组反转后的位置，原数组的每个元素计算其在新数组中的位置然后赋值即可。代码class Solution { public: void reverse(vector<int>& nums,int start,int end) { while(start<end) { swap(nums[start],nums[end]); start++; end ; } } void rotate(vector<int>& nums, int k) { k=k%nums.size(); reverse(nums,0,nums.size() 1); reverse(nums,0,k 1); reverse(nums,k,nums.size() 1); } };class Solution { public: void rotate(vector<int>& nums, int k) { int n=nums.size(); k%=n; vector<int> a(n); for(int i=0;i<n;i++) { a[(i+k)%n]=nums[i]; } nums.assign(a.begin(),a.end()); } };收获巩固了反转数组和数组的一些赋值操作,vector.assigin(iterator,iterator)。238. 除自身以外数组的乘积238. 除自身以外数组的乘积题目介绍给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法，且在 O(n) 时间复杂度内完成此题。示例 1:输入: nums = [1,2,3,4] 输出: [24,12,8,6] 示例 2:输入: nums = [ 1,1,0, 3,3] 输出: [0,0,9,0,0]思路可恶啊，本来记录所有元素的乘积然后除以对应元素就可以得到答案，可恶的出题人不让用除法。这里我使用两个数组left和right分别记录i左边的乘积和和i右边的乘积和，left[i]*right[i]即为所求。代码class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> left(n,0),right(n,0); left[0]=1; right[n 1]=1; for(int i=1;i<n;i++) { left[i]=nums[i 1]*left[i 1]; } for(int i=n 2;i>=0;i ) { right[i]=nums[i+1]*right[i+1]; } for(int i=0;i<n;i++) { nums[i]=left[i]*right[i]; } return nums; } };收获无73. 矩阵置零73. 矩阵置零题目介绍给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。示例 1：输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]] 示例2：输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]思路直观的想法，分别用两个HashSet来保存需要清0的行和列，对整个矩阵进行遍历后得到hashset对hashset选中的行列进行清0即可。题解中给出了另外两种空间上优化解法，这里我只说第一种优化的，剩下那个没看....，我们一开始使用了两个HashSet来记录需要清0的空间，这里我们不需要额外的空间使用二维矩阵的第0行和第0列来表示是否需要对该行或者该列进行清空，这是我们丢失了原本第0行和第0列的信息，所以我们需要两个O（1）的变量来记录是否需要对第0行和第0列进行清空即可。代码class Solution { public: void setZeroes(vector<vector<int>>& matrix) { unordered_set<int> row,col; int n=matrix.size(); int m=matrix[0].size(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(matrix[i][j]==0) { row.insert(i); col.insert(j); } } } for(auto i:col) { for(int j=0;j<n;j++) { matrix[j][i]=0; } } for(auto i:row) { for(int j=0;j<m;j++) { matrix[i][j]=0; } } } };class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); int flag_col0 = false, flag_row0 = false; for (int i = 0; i < m; i++) { if (!matrix[i][0]) { flag_col0 = true; } } for (int j = 0; j < n; j++) { if (!matrix[0][j]) { flag_row0 = true; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (!matrix[i][j]) { matrix[i][0] = matrix[0][j] = 0; } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (!matrix[i][0] || !matrix[0][j]) { matrix[i][j] = 0; } } } if (flag_col0) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flag_row0) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } } }; 收获无

简介：wy的leetcode刷题记录_Day75声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 1 23前言TOC2765. 最长交替子数组今天的每日一题是：2765. 最长交替子数组题目介绍给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：m 大于 1 。s1 = s0 + 1 。下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m 1) %2] 一样。也就是说，s1 s0 = 1 ，s2 s1 = 1 ，s3 s2 = 1 ，s4 s3 = 1，以此类推，直到 s[m 1] s[m 2] = ( 1)m 。请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 1 。子数组是一个数组中一段连续 非空 的元素序列。示例 1：输入：nums = [2,3,4,3,4] 输出：4 解释：交替子数组有 [3,4] ，[3,4,3] 和 [3,4,3,4] 。最长的子数组为 [3,4,3,4] ，长度为4 。 示例 2：输入：nums = [4,5,6] 输出：2 解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。提示：2 <= nums.length <= 1001 <= nums[i] <= 104思路方法一：暴力法解决：使用二重循环，外层循环遍历子数组的起始位置，内层循环遍历子数组。每当内层循环中子数组遇到不符合条件的字符，推出内层循环，更新最大长度。方法二：优化暴力：一重循环，接上述方法一，我们在内层循环中已经找到本次子数组中不符合条件的字符，当我们按照方法一让下一个字符作为子数组的开始时我们发现因为其满足上一子数组的条件所以不符合，同理直到我们找到的错字符，因此我们只需要以本次不符合条件的字符为子数组新的开始继续遍历即可。感觉自己说的不清楚这里放上别人的话：链接代码class Solution { public: int alternatingSubarray(vector<int>& a) { int n=a.size(); int ans= 1; for(int i=0;i<n 1;i++) { for(int j=i+1;j<n;j++) { int length=j i+1; if(a[j] a[i]==(length 1)%2) { ans=max(ans,length); } else break; } } return ans; } };class Solution { public: int alternatingSubarray(vector<int>& nums) { int n=nums.size(); int ans= 1; int first=0; for(int i=1;i<n;i++) { int length=i first+1; if(nums[i] nums[first]==(length 1)%2) ans=max(ans,length); else { if(nums[i] nums[i 1]==1) { first=i 1; ans=max(ans,2); } else{ first=i; } } } return ans; } };收获稍微复杂一点的模拟题

简介：wy的leetcode刷题记录_Day74声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 1 22前言@TOC670. 最大交换今天的每日一题是：670. 最大交换题目介绍给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。示例 1 :输入: 2736 输出: 7236 解释: 交换数字2和数字7。 示例 2 :输入: 9973 输出: 9973 解释: 不需要交换。注意:给定数字的范围是 [0, 108]思路贪心寻找：根据题意我们只能做一次交换，通过寻找到第一个不符合降序排列的前一个数位就是交换的高位，然后高位之后中靠后的最大数的数位是交换的低位，做出交换。具体：二重循环，首先判断当前字符是否是所有后缀中最大的，若是则跳转到下一个字符；若不是则寻找到靠后的最大数进行交换。代码class Solution { public: int maximumSwap(int num) { string nums=to_string(num); int n=nums.size(); int max=nums[0]; int index=0; int ans=0; int flag=0; for(int i=0;i<n;i++) { max=nums[i]; for(int j=i;j<n;j++) { if(nums[j]>max) { flag=1; max=nums[j]; index=j; } } for(int j=i;j<n;j++) { if(nums[j]==max) { index=j; } } if(flag==1) { nums[index]=nums[i]; nums[i]=max; break; } } for (int i = 0; i < n; i++) { ans += (nums[i] 48) * pow(10, n i 1); } return ans; } };收获本来想着俩三分钟就有思路了但是还是做了好久，一两个星期没写代码有点生疏了，还是得常写常练啊。

简介：wy的leetcode刷题记录_Day72声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：前言@TOC2397. 被列覆盖的最多行数今天的每日一题是：2397. 被列覆盖的最多行数题目介绍给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：对于满足 matrixrow == 1 的每个单元格 matrixrow（0 <= col <= n 1），col 均存在于 s 中，或者row 中 不存在 值为 1 的单元格。你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。示例 1：输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2 输出：3 解释：图示中显示了一种覆盖 3 行的可行办法。 选择 s = {0, 2} 。第 0 行被覆盖，因为其中没有出现 1 。第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。第 2 行未被覆盖，因为 matrix2 == 1 但是 1 未存在于 s 中。第 3 行被覆盖，因为 matrix2 == 1 且 2 存在于 s 中。 因此，可以覆盖 3 行。 另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。示例 2：输入：matrix = [[1],[0]], numSelect = 1 输出：2 解释：选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。 所以我们返回 2 。思路暴力法解决：二进制枚举：使用二进制来表示每一行的1的分布情况以及搜寻情况，具体如下：使用mask[i]表示第i行中的1的分布情况，若mask[i]的二进制数位上为1其对应的矩阵中也为1。threshold用来表示当前遍历的选择列的情况，若threshold的二进制数位上为1则对应列被选中。代码class Solution { public: int maximumRows(vector<vector<int>>& matrix, int numSelect) { int row=matrix.size(); int col=matrix[0].size(); vector<int> mask(row,0);//表示当前行中1的情况 //初始化mask for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { mask[i]+=matrix[i][j]<<(col j 1); } } int curr=0; int ans=0; int threshold=(1<<col); for(int i=1;i<=threshold;i++) { curr=0; if(__builtin_popcount(i)!=numSelect) { continue; } for(int j=0;j<row;j++) { if((mask[j]&i)==mask[j]) { curr++; } } ans=max(curr,ans); } return ans; } };收获通过使用二进制数可以表达的含义有很多可以简化很多操作。1137. 第 N 个泰波那契数1137. 第 N 个泰波那契数题目介绍泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2给你整数 n，请返回第 n 个泰波那契数 Tn 的值。示例 1： 输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2：输入：n = 25 输出：1389537思路其实这道题就是对斐波那契数列的一个重定义，只是递归条件增加，递归方程式需要改变一下即可。对于矩阵快速幂也是同理，重新梳理一下递推矩阵即可。代码递归（超时）：class Solution { public: int tribonacci(int n) { if(n<=1) return n; if(n==2) return 1; return tribonacci(n 1)+tribonacci(n 2)+tribonacci(n 3); } };递推（剩去了计算多余的fib数列）:class Solution { public: int tribonacci(int n) { if(n<=1) return n; if(n==2) return 1; int a=0;int b=1;int c=1; int ans=0; for(int i=3;i<=n;i++) { ans=a+b+c; a=b; b=c; c=ans; } return ans; } };矩阵快速幂： class Solution { public: //矩阵乘法 vector<vector<long>> martix_mutiply(vector<vector<long>> &a,vector<vector<long>>& b) { vector<vector<long>> c{{0,0,0},{0,0,0},{0,0,0}}; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]+a[i][2]*b[2][j]; } } return c; } //快速幂 vector<vector<long>> martix_rapid_pow(vector<vector<long>> &a,int n) { vector<vector<long>> ret{{1,0,0},{0,1,0},{0,0,1}}; while(n>0) { if(n&1) { ret=martix_mutiply(ret,a); } n>>=1; a=martix_mutiply(a,a); } return ret; } int tribonacci(int n) { //矩阵快速幂 if (n < 2) { return n; } vector<vector<long>> q{{1, 1,1}, {1, 0,0},{0,1,0}}; vector<vector<long>> res = martix_rapid_pow(q, n 1); return res[0][0]; } }; 收获重温矩阵快速幂。

简介：wy的leetcode刷题记录_Day71声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 1 3（补）前言@TOC2487. 从链表中移除节点今天的每日一题是：2487. 从链表中移除节点题目介绍给你一个链表的头节点 head 。移除每个右侧有一个更大数值的节点。返回修改后链表的头节点 head 。示例 1：> 输入：head = [5,2,13,3,8] 输出：[13,8] 解释：需要移除的节点是 5 ，2 和 3 。> 节点 13 在节点 5 右侧。节点 13 在节点 2 右侧。节点 8 在节点 3 右侧。示例 2：输入：head = [1,1,1,1] 输出：[1,1,1,1] 解释：每个节点的值都是 1 ，所以没有需要移除的节点。思路方法一：暴力解：通过两重嵌套循环来寻找新链表，具体如下：1.每一轮循环寻找当前链表的最大值将最大值加入新链表2.每一轮循环从上一次循环寻找到的加入新链表的节点开始遍历。（超时，时间复杂度n的2次方）方法二：换个思路：本题其实应该在考察寻找出链表中的右往左找非递减序列 可以从序列尾部开始遍历，俩种做法递归或者模拟栈。方法三：延续方法二的思路，这次我们不使用栈而是直接将链表反转来进行操作最后将符合条件的条件在进行一次反转即可。部分思路参考作者：力扣官方题解代码方法一：暴力/** * 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* removeNodes(ListNode* head) { int maxVal=0; ListNode* maxValPointer=nullptr; ListNode* newHeader=nullptr; ListNode* temp=nullptr; int count=0; while(head) { count++; maxVal=0; maxValPointer=nullptr; while(head) { if(head >val>maxVal) { maxVal=head >val; maxValPointer=head; } head=head >next; } head=maxValPointer >next;//下一次遍历从新节点开始 if(count==1)//如果是头节点则创建新链表 { newHeader=maxValPointer; temp=newHeader; newHeader >next=nullptr; } else//如果是尾节点则加入新链表 { temp >next=maxValPointer; temp=temp >next; temp >next=nullptr; } } return newHeader; } };方法二：递归class Solution { public: ListNode* removeNodes(ListNode* head) { if (head == nullptr) { return nullptr; } head >next = removeNodes(head >next); if (head >next != nullptr && head >val < head >next >val) { return head >next; } else { return 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* removeNodes(ListNode* head) { //换个思路：本题其实应该在考察寻找出链表中的右往左找非递减序列 可以从序列尾部开始遍历 stack<ListNode* > stk; for(;head!=nullptr;head=head >next) { stk.push(head); } while(!stk.empty()) { if(head==nullptr||stk.top() >val>=head >val) { stk.top() >next=head; head=stk.top(); } stk.pop(); } return head; } };方法三：反转链表：class Solution { public: ListNode *reverse(ListNode *head) { ListNode dummy; while (head != nullptr) { ListNode *p = head; head = head >next; p >next = dummy.next; dummy.next = p; } return dummy.next; } ListNode* removeNodes(ListNode* head) { head = reverse(head); for (ListNode *p = head; p >next != nullptr; ) { if (p >val > p >next >val) { p >next = p >next >next; } else { p = p >next; } } return reverse(head); } }; 收获通过暴力模拟提高了解题的速度，手速题秒杀！后续的对时间复杂度的改进是通过对题目的深度解读，发现了另一种思路，转换思路之后得出了一种更为简洁的解法以及时间优化度更高的方法，通过模拟栈和递归俩种写法加深的对函数调用的理解。509. 斐波那契数动态规划基础篇之——509. 斐波那契数题目介绍斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n 1) + F(n 2)，其中 n > 1给定 n ，请计算 F(n) 。示例 1：输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2：输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3：输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3思路同之前的爬楼梯那一题十分相似都可以采用对应的递归方法或者递推方法以及矩阵快速幂...代码递归：class Solution { public: int fib(int n) { if(n==0||n==1) return n; return fib(n 1)+fib(n 2); } };递推:class Solution { public: int fib(int n) { int a=0; int b=1; int c=a+b; for(int i=2;i<=n;i++) { c=a+b; a=b; b=c; } return c; } };矩阵快速幂：class Solution { public: //矩阵乘法 vector<vector<int>> martix_mutiply(vector<vector<int>> &a,vector<vector<int>>& b) { vector<vector<int>> c{{0,0},{0,0}}; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]; } } return c; } //快速幂 vector<vector<int>> martix_rapid_pow(vector<vector<int>> &a,int n) { vector<vector<int>> ret{{1,0},{0,1}}; while(n>0) { if(n&1) { ret=martix_mutiply(ret,a); } n>>=1; a=martix_mutiply(a,a); } return ret; } int fib(int n) { //矩阵快速幂 if (n < 2) { return n; } vector<vector<int>> q{{1, 1}, {1, 0}}; vector<vector<int>> res = martix_rapid_pow(q, n 1); return res[0][0]; } };收获巩固矩阵快速幂！