LeetCode算法刷题计划（1）— 基础50题

转x33g5p2x  于2021-10-06 转载在 其他  
字(13.0k)|赞(0)|评价(0)|浏览(343)

LeetCode算法刷题计划（1）— 基础50题

自己近几天在LeetCode上面刷的50道基础算法题，下面按照算法类型进行分类

一、malloc

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     vector<int> getConcatenation(vector<int>& nums) {
  6.         
  7.         int n=nums.size();
  8.         for(int i=0;i<n;i++){
  9.             nums.push_back(nums[i]);
  10.         }
  12.         return nums;
  13.     }
  14. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     vector<int> shuffle(vector<int>& nums, int n) {
  7.         for(int i=0;i<2*n;i++){
  8.             if(nums[i]>0){
  9.                 int j=i;
  10.                 while(nums[i]>0){
  11.                     j=j<n?2*j:2*(j-n)+1;
  12.                     swap(nums[i],nums[j]);
  13.                     nums[j]=-nums[j];
  14.                 }
  15.             }
  16.         }
  18.         for(auto &num:nums){
  19.             num=-num;
  20.         }
  22.         return nums;
  23.     }
  24. };

  1. //时间复杂度：O(10^n)
  2. //空间复杂度：O(10^n)
  3. class Solution {
  4. public:
  5.     vector<int> printNumbers(int n) {
  7.         vector<int>ans;
  8.         int side=0;
  10.         while(n--){
  11.             side=side*10+9;
  12.         }
  14.         for(int i=1;i<=side;i++){
  15.             ans.push_back(i);
  16.         }
  18.         return ans;
  19.     }
  20. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     vector<int> runningSum(vector<int>& nums) {
  7.         for(int i=1;i<nums.size();i++){
  8.             nums[i]=nums[i]+nums[i-1];
  9.         }
  11.         return nums;
  12.     }
  13. };

  1. //时间复杂度：O(n*logn)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
  7.         vector<pair<int,int>>pairs;
  9.         for(int i=0;i<nums.size();i++){
  10.             pairs.push_back(make_pair(nums[i],i));
  11.         }
  12.         sort(pairs.begin(),pairs.end());
  14.         vector<int>ans(nums.size());
  15.         int pre=-1;
  16.         for(int i=0;i<pairs.size();i++){
  17.             if(pre==-1||pairs[i].first!=pairs[i-1].first){
  18.                 pre=i;
  19.             }
  20.             ans[pairs[i].second]=pre;
  21.         }
  23.         return ans;
  24.     }
  25. };

二、位运算

  1. //时间复杂度：O(2^n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  6.     int ans=0;
  8.     void dfs(int val,int idx,vector<int>&nums){
  9.         if(idx==nums.size()){
  10.             ans+=val;
  11.             return;
  12.         }
  13.         dfs(val^nums[idx],idx+1,nums);
  14.         dfs(val,idx+1,nums);
  15.     }
  17.     int subsetXORSum(vector<int>& nums) {   
  18.         dfs(0,0,nums);
  19.         return ans;
  20.     }
  21. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     vector<int> decode(vector<int>& encoded, int first) {
  7.         vector<int>ans(encoded.size()+1);
  9.         ans[0]=first;
  10.         for(int i=1;i<=encoded.size();i++){
  11.             ans[i]=encoded[i-1]^ans[i-1];
  12.         }
  14.         return ans;
  15.     }
  16. };

  1. //时间复杂度：O(1)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     vector<int> swapNumbers(vector<int>& numbers) {
  7.         numbers[0]=numbers[0]^numbers[1];
  8.         numbers[1]=numbers[0]^numbers[1];
  9.         numbers[0]=numbers[0]^numbers[1];
  11.         return numbers;
  12.     }
  13. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.      int hammingWeight(uint32_t n) {
  6.         
  7.         int count=0;
  9.         while(n!=0){
  10.             if((n&1)==1){
  11.                 count++;
  12.             }
  13.             n>>=1;
  14.         }
  16.         return count;
  17.     }
  18. };

  1. //时间复杂度：O(logn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int rangeBitwiseAnd(int left, int right) {
  7.         int count=0;
  9.         while(left<right){
  10.             left>>=1;
  11.             right>>=1;
  12.             count++;
  13.         }
  15.         return left<<count;
  16.     }
  17. };

  1. //时间复杂度：O(logn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     uint32_t reverseBits(uint32_t n) {
  6.         
  7.         uint32_t ans=0;
  9.         for(int i=0;i<32&&n>0;i++){
  10.             ans |= (n&1) << (31-i);
  11.             n >>= 1; 
  12.         }
  13.         
  14.         return ans;
  15.     }
  16. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     vector<int> countBits(int n) {
  7.         vector<int>dp(n+1,0);
  9.         for(int i=1;i<=n;i++){
  10.             dp[i]=dp[i>>1]+(i&1);
  11.         }
  13.         return dp;
  14.     }
  15. };

三、计数

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int numIdenticalPairs(vector<int>& nums) {
  6.         
  7.         int ans=0;
  8.         unordered_map<int,int>mp;
  9.         mp[nums[0]]=1;
  11.         for(int i=1;i<nums.size();i++){        
  12.             ans+=mp[nums[i]];
  13.             mp[nums[i]]++;     
  14.         }
  16.         return ans;
  17.     }
  18. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     bool checkIfPangram(string sentence) {
  7.         int ans=0;
  9.         for(auto c:sentence){
  10.             ans|=1<<(c-'a');
  11.             if((ans^0x3ffffff)==0){
  12.                 return true;
  13.             }
  14.         }
  16.         return false;
  17.     }
  18. };

四、字符串

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int finalValueAfterOperations(vector<string>& operations) {
  7.         int x=0;
  9.         for(auto str:operations){
  10.             if(str=="++X"||str=="X++"){
  11.                 x++;
  12.             }else{
  13.                 x--;
  14.             }
  15.         }
  17.         return x;
  18.     }
  19. };

  1. //时间复杂度：O(n^2)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     string defangIPaddr(string address) {
  7.         for(int i=0;i<address.length();i++){
  8.             if(address[i]=='.'){
  9.                 address.insert(i+1,"]");
  10.                 address.insert(i,"[");
  11.                 i++;
  12.             }
  13.         }
  15.         return address;
  16.     }
  17. };

  1. //时间复杂度：O(n^2)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int countConsistentStrings(string allowed, vector<string>& words) {
  7.         int count=0;
  8.         unordered_set<char>s;
  10.         for(auto c:allowed){
  11.             s.insert(c);
  12.         }
  13.         for(auto word:words){
  14.             int flag=1;
  15.             for(auto c:word){
  16.                 if(s.count(c)==0){
  17.                     flag=0;
  18.                     break;
  19.                 }
  20.             }
  21.             if(flag)
  22.                 count++;
  23.         }
  25.         return count;
  26.     }
  27. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     void reverseString(vector<char>& s) {
  6.         for(int i=0,j=s.size()-1;i<j;i++,j--){
  7.             swap(s[i],s[j]);
  8.         }
  9.     }
  10. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     string reverseLeftWords(string s, int n) {
  7.         string ans=s;
  9.         for(int i=0;i<s.length();i++){
  10.             ans[(i+s.length()-n)%s.length()]=s[i];
  11.         }
  13.         return ans;
  14.     }
  15. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
  7.         string s1="",s2="";
  9.         for(auto word:word1){
  10.             s1+=word;
  11.         }
  12.         for(auto word:word2){
  13.             s2+=word;
  14.         }
  16.         return s1==s2;
  17.     }
  18. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     string complexNumberMultiply(string num1, string num2) {
  7.         string s1_z="",s1_f="",s2_z="",s2_f="";
  8.         int flag=1;
  9.         for(int i=0;i<num1.length();i++){
  10.             if(num1[i]!='+'&&flag){
  11.                 s1_z+=num1[i];
  12.             }else{
  13.                 flag=0;
  14.             }
  15.             if(num1[i]=='+')
  16.                 continue;
  17.             if(flag==0&&num1[i]!='i'){
  18.                 s1_f+=num1[i];
  19.             }
  20.         }
  21.         flag=1;
  22.         for(int i=0;i<num2.length();i++){
  23.             if(num2[i]!='+'&&flag){
  24.                 s2_z+=num2[i];
  25.             }else{
  26.                 flag=0;
  27.             }
  28.             if(num2[i]=='+')
  29.                 continue;
  30.             if(flag==0&&num2[i]!='i'){
  31.                 s2_f+=num2[i];
  32.             }
  33.         }
  34.         int n1_z=stoi(s1_z),n1_f=stoi(s1_f),n2_z=stoi(s2_z),n2_f=stoi(s2_f);
  36.         string ans=to_string(n1_z*n2_z-n1_f*n2_f)+"+"+to_string(n1_f*n2_z+n1_z*n2_f)+"i";
  38.         return ans;
  39.     }
  40. };

五、递归

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  4. class Solution {
  5. public:
  7.     unordered_set<int>s;
  9.     void search(TreeNode *root){
  10.         if(root!=NULL){
  11.             s.insert(root->val);
  12.             search(root->left);
  13.             search(root->right);
  14.         }
  15.     }
  17.     int numColor(TreeNode* root) {
  18.         search(root);
  19.         return s.size();
  20.     }
  21. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int count=0;
  6.     int numberOfSteps(int num) {
  7.         if(num%2==0&&num!=0){
  8.             count++;
  9.             numberOfSteps(num/2);
  10.         }
  11.         if(num%2==1){
  12.             count++;
  13.             numberOfSteps(num-1);
  14.         }
  16.         return count;
  17.     }
  18. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(H)
  3. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
  4. class Solution {
  5. public:
  7.     int maxdepth=-1,ans=0;
  9.     void dfs(TreeNode *root,int depth){
  10.         if(root==NULL){
  11.             return;
  12.         }
  13.         if(depth>maxdepth){
  14.             ans=root->val;
  15.             maxdepth=depth;
  16.         }else if(depth==maxdepth){
  17.             ans+=root->val;
  18.         }
  19.         dfs(root->left,depth+1);
  20.         dfs(root->right,depth+1);
  21.     }
  23.     int deepestLeavesSum(TreeNode* root) {
  24.         dfs(root,1);
  25.         return ans;
  26.     }
  27. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(H)
  3. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  4. class Solution {
  5. public:
  6.     int maxDepth(TreeNode* root) {
  7.         if(root==NULL){
  8.             return 0;
  9.         }
  10.         int left_dep=maxDepth(root->left);
  11.         int right_dep=maxDepth(root->right);
  12.         return max(left_dep,right_dep)+1;
  13.     }
  14. };

六、公式

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int sum=0;
  6.     int sumNums(int n) {
  7.         n>0&&(sum=n+sumNums(n-1));
  8.         return sum;
  9.     }
  10. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int multiply(int A, int B) {
  6.         if(B==1){
  7.             return A;
  8.         }
  9.         return A+multiply(A,B-1);
  10.     }
  11. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  6.     int fib(int n) {
  7.         if(n<2){
  8.             return n;
  9.         }
  10.         int p=0,q=1,ans;
  11.         for(int i=2;i<=n;i++){
  12.             ans=p+q;
  13.             p=q;
  14.             q=ans;
  15.         }
  16.         return ans;
  17.     }
  18. };

  1. //时间复杂度：O(sqrt(n))
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int kthFactor(int n, int k) {
  7.         int ans;
  9.         for(ans=1;ans<=sqrt(n);ans++){
  10.             if(n%ans==0){
  11.                 k--;
  12.                 if(k==0){
  13.                     return ans;
  14.                 }
  15.             }
  16.         }
  17.         ans--;
  18.         if(ans*ans==n){
  19.             ans--;
  20.         }
  21.         for(;ans>0;ans--){
  22.             if(n%ans==0){
  23.                 k--;
  24.                 if(k==0){
  25.                     return n/ans;
  26.                 }
  27.             }
  28.         }
  30.         return -1;
  31.     }
  32. };

  1. //时间复杂度：O(n^2)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int countTriples(int n) {
  7.         int count=0;
  8.         for(int i=1;i<=n;i++){
  9.             for(int j=1;j<=n;j++){
  10.                 int c=sqrt(i*i+j*j);
  11.                 if(c<=n&&c*c==i*i+j*j){
  12.                     count++;
  13.                 }
  14.             }
  15.         }
  16.         return count;
  17.     }
  18. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  6.     int gcd(int a,int b){
  7.         int t;
  8.         while(t!=0){
  9.             t=a%b;
  10.             a=b;
  11.             b=t;
  12.         }
  13.         return a;
  14.     }
  16.     int findGCD(vector<int>& nums) {
  17.         int maxn=-1,minn=5555;
  18.         for(int i=0;i<nums.size();i++){
  19.             maxn=max(maxn,nums[i]);
  20.             minn=min(minn,nums[i]);
  21.         }
  22.         return gcd(maxn,minn);
  23.     }
  24. };

  1. //时间复杂度：O(n^3)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  6.     double area(vector<int>a,vector<int>b,vector<int>c){
  7.         return 0.5*abs(a[0]*b[1]+b[0]*c[1]+c[0]*a[1]-a[1]*b[0]-b[1]*c[0]-c[1]*a[0]);
  8.     }
  10.     double largestTriangleArea(vector<vector<int>>& points) {
  12.         double maxarea=0;
  13.         int n=points.size();
  15.         for(int i=0;i<n;i++)
  16.             for(int j=i+1;j<n;j++)
  17.                 for(int k=j+1;k<n;k++)
  18.                     maxarea=max(maxarea,area(points[i],points[j],points[k]));
  20.         return maxarea;
  21.     }
  22. };

七、枚举

  1. //时间复杂度：O(n)。这里用一重循环对n个数字进行异或。
  2. //空间复杂度：O(1)。这里只是用了常量级别的辅助空间。
  3. class Solution {
  4. public:
  5.     int xorOperation(int n, int start) {
  7.         int ans=0;
  9.         for(int i=0;i<n;i++){
  10.             ans=ans^(start+2*i);
  11.         }
  13.         return ans;
  14.     }
  15. };

  1. //时间复杂度：O(logn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int subtractProductAndSum(int n) {
  7.         int sum=0,mut=1;
  9.         while(n!=0){
  10.             sum+=(n%10);
  11.             mut*=(n%10);
  12.             n/=10;
  13.         }
  15.         return mut-sum;
  16.     }
  17. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int findNumbers(vector<int>& nums) {
  7.         int count=0;
  8.         for(auto num:nums){
  9.             if((int)(log10(num)+1)%2==0){
  10.                 count++;
  11.             }
  12.         }
  14.         return count;
  15.     }
  16. };

  1. //时间复杂度：O(logn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int search(vector<int>& nums, int target) {
  7.         int n=nums.size();
  8.         int left=0,right=n-1;
  10.         while(left<=right){
  11.             int mid=(left+right)/2;
  12.             if(nums[mid]==target){
  13.                 return mid;
  14.             }else if(nums[0]<=nums[mid]){
  15.                 if(target>=nums[0]&&target<=nums[mid]){
  16.                     right=mid-1;
  17.                 }else{
  18.                     left=mid+1;
  19.                 }
  20.             }else{
  21.                 if(target>=nums[mid]&&target<=nums[n-1]){
  22.                     left=mid+1;
  23.                 }else{
  24.                     right=mid-1;
  25.                 }
  26.             }
  27.         }
  29.         return -1;
  30.     }
  31. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int countKDifference(vector<int>& nums, int k) {
  6.     
  7.         unordered_map<int,int>mp;
  8.         int count=0;
  10.         for(int i=0;i<nums.size();i++){
  11.             int a=nums[i]+k,b=nums[i]-k;
  12.             if(mp.find(a)!=mp.end()){
  13.                 count+=mp[a];
  14.             }
  15.             if(mp.find(b)!=mp.end()){
  16.                 count+=mp[b];
  17.             }
  18.             mp[nums[i]]++;
  19.         }
  20.         
  21.         return count;
  22.     }
  23. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int numJewelsInStones(string jewels, string stones) {
  7.         unordered_set<char>s;
  8.         int count=0;
  10.         for(auto jewel:jewels){
  11.             s.insert(jewel);
  12.         }
  13.         for(auto stone:stones){
  14.             if(s.count(stone)){
  15.                 count++;
  16.             }
  17.         }
  19.         return count;
  20.     }
  21. };

  1. //时间复杂度：O(n^2)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  5.     int sumOddLengthSubarrays(vector<int>& arr) {
  7.         int n=arr.size();
  8.         int dp[n];
  9.         int sum=arr[0];
  10.         dp[0]=arr[0];
  12.         for(int i=1;i<n;i++){
  13.             sum+=arr[i];
  14.             dp[i]=dp[i-1]+arr[i];
  15.         }
  16.         for(int i=0;i<n-1;i++){
  17.             for(int j=i+1;j<n;j++){
  18.                 if((j-i+1)%2==1){
  19.                     sum+=dp[j]-dp[i]+arr[i];                   
  20.                 }
  21.             }
  22.         }
  24.         return sum;
  25.     }
  26. };

八、进制

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. /** * 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) {} * }; */
  4. class Solution {
  5. public:
  6.     int getDecimalValue(ListNode* head) {
  7.         int ans=0;
  8.         while(head!=NULL){
  9.             ans|=head->val;
  10.             ans<<=1;
  11.             head=head->next;
  12.         }
  13.         ans>>=1;
  14.         return ans;
  15.     }
  16. };

  1. //时间复杂度：O(logn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int sumBase(int n, int k) {
  6.         
  7.         int sum=0;
  9.         while(n!=0){
  10.             sum+=(n%k);
  11.             n/=k;
  12.         }
  14.         return sum;
  15.     }
  16. };

  1. //时间复杂度：O(1)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int addDigits(int num) {
  6.         if(num>0&&num%9==0){
  7.             return 9;
  8.         }
  9.         return num%9;
  10.     }
  11. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     string convertToBase7(int num) {
  7.         string s="";
  8.         int  flag=0;
  10.         if(num<0){
  11.             flag=1;
  12.             num=-num;
  13.         }
  14.         if(num==0){
  15.             return "0";
  16.         }
  17.         while(num!=0){
  18.             s+=(num%7)+'0';
  19.             num/=7;
  20.         }
  21.         reverse(s.begin(),s.end());
  22.         if(flag){
  23.             s.insert(0,"-");
  24.         }
  26.         return s;
  27.     }
  28. };

  1. //时间复杂度：O(k) k为十六进制的位数
  2. //空间复杂度：O(k)
  3. class Solution {
  4. public:
  5.     string toHex(int num) {
  7.         if(num==0){
  8.             return "0";
  9.         }
  11.         string s="";
  12.         for(int i=7;i>=0;i--){
  13.             int tmp=(num>>(4*i))&15;
  14.             if(tmp>0||s.length()>0){
  15.                 s+=tmp<10?(tmp+'0'):('a'+tmp-10);
  16.             }
  17.         }
  19.         return s;
  20.     }
  21. };

九、排序

  1. //时间复杂度：O(nlogn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     vector<int> sortArray(vector<int>& nums) {
  6.         sort(nums.begin(),nums.end());
  7.         return nums;
  8.     }
  9. };

  1. //时间复杂度：O(nlogn)
  2. //空间复杂度：O(n)
  3. class Solution {
  4. public:
  6.     static bool cmp(pair<char,int>a,pair<char,int>b){
  7.         return a.second>b.second;
  8.     }
  10.     string frequencySort(string s) {
  12.         unordered_map<char,int>mp;
  13.         vector<pair<char,int>>pairs;
  14.         string ans="";
  15.         
  16.         for(auto c:s){
  17.             mp[c]++;
  18.         }
  19.         for(auto it:mp){
  20.             pairs.push_back(it);
  21.         }
  22.         sort(pairs.begin(),pairs.end(),cmp);
  23.         for(auto [ch,num]:pairs){
  24.             for(int i=0;i<num;i++){
  25.                 ans+=ch;
  26.             }
  27.         }
  29.         return ans;
  30.     }   
  31. };

  1. //时间复杂度：O(nlogn)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int firstMissingPositive(vector<int>& nums) {
  7.         int cnt=1,idx=0;
  9.         sort(nums.begin(),nums.end());
  11.         while(idx<nums.size()&&nums[idx]<=0){
  12.             idx++;
  13.         }
  15.         for(int i=idx;i<nums.size();i++){
  16.             if(nums[i]!=cnt){
  17.                 return cnt;
  18.             }
  19.             if(i+1<nums.size()&&nums[i]!=nums[i+1]){
  20.                 cnt++;
  21.             }else if(i+1==nums.size()){
  22.                 cnt++;
  23.             }
  24.                 
  25.         }
  27.         return cnt;
  28.     }
  29. };

十、思维

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int arraySign(vector<int>& nums) {
  6.         
  7.         int flag=1;
  8.         
  9.         for(auto num:nums){
  10.             if(num==0){
  11.                 return 0;
  12.             }
  13.             if(num<0){
  14.                 flag=-flag;
  15.             }
  16.         }
  18.         return flag;
  19.     }
  20. };

  1. //时间复杂度：O(1)
  2. //空间复杂度：O(1)
  3. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
  4. class Solution {
  5. public:
  6.     void deleteNode(ListNode* node) {
  7.         node->val=node->next->val;
  8.         node->next=node->next->next;
  9.     }
  10. };

  1. //时间复杂度：O(n)
  2. //空间复杂度：O(1)
  3. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
  4. class Solution {
  5. public:
  6.     ListNode* deleteNode(ListNode* head, int val) {
  8.         ListNode *h=head;
  10.         if(head->val==val){
  11.             return head->next;
  12.         }
  13.         while(h!=NULL){
  14.             if(h->next->val==val){
  15.                 h->next=h->next->next;
  16.                 return head;
  17.             }
  18.             h=h->next;
  19.         }
  21.         return head;
  22.     }
  23. };

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_47511190/article/details/120601406

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com