头像

h_s

庆阳一中


访客:2218

离线:9小时前



h_s
1天前
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
          sort(target.begin(),target.end());
          sort(arr.begin(),arr.end());
          if(arr==target)return true;
          return false;
    }
};



h_s
1天前

一串01串,k为01串的长度,当i>=k的时候,当前表示的数字你就减去第一个数字,第一个数字是s[i-k]-‘0’,由于左面是高位,所以要减去高位乘以对应的进制的次方吧,使用位运算.使用set来维护这个集合

class Solution {
public:
    bool hasAllCodes(string s, int k) {

       unordered_set<int>sm;
       for(int i=0,w=0;i<s.size();i++)
       {
           w=w*2+s[i]-'0';
           if(i>=k)
           {
               w=w-(s[i-k]-'0'<<k);
           }
           if(i>=k-1)sm.insert(w);
       }
       return sm.size()==(1<<k);

    }
};


新鲜事 原文

h_s
2天前
再次水一条帖子,有人假期一起刷进阶指南吗(最近期末季哎)
图片 图片


新鲜事 原文

h_s
2天前
java快考试了,有啥常用的API或者小技巧吗,求分享!(顺便试一试新功能)求评论


活动打卡代码 LeetCode 9. 回文数

h_s
4天前
int number=x;
        if(x<0)return false;
        else if(x==0)return true;

        else{
           long long  num=0;
            while(x)
            {
              num=num*10+(x%10);
              x/=10;
            }
            if(number==num)return true;
            else return false;
        }



活动打卡代码 LeetCode 7. 整数反转

h_s
4天前
class Solution {
public:
    int reverse(int x) {
        long long res = 0;
        while(x)
        {
            res = res * 10 + x % 10;
            x /= 10;
        }
        if (res < INT_MIN || res > INT_MAX) return 0;
        return res;
    }
};



h_s
5天前

题目描述

给定一个字符串,请你求出其中的最长回文子串的长度。

例如,给定字符串 Is PAT&TAP symmetric?,最长回文子串为 s PAT&TAP s,其长度是 11。

输入格式
包含一个非空字符串。

输出格式
输出一个整数,表示给定字符串的最长回文子串的长度。

数据范围
给定字符串的长度不超过 1000。

输入样例:
Is PAT&TAP symmetric?
输出样例:
11
难度:简单
时/空限制:0.4s / 64MB
总通过数:44
总尝试数:114
来源:PAT甲级真题1040
算法标签

样例

blablabla

算法1

(中心扩散(暴力枚举)) $O(n^2)$

由于字符串长度小于1000,因此我们可以用 O(n2)O(n2) 的算法枚举所有可能的情况。
首先枚举回文串的中心 ii,然后分两种情况向两边扩展边界,直到遇到不同字符为止:

回文串长度是奇数,则依次判断 s[i−k]==s[i+k],k=1,2,3,…s[i−k]==s[i+k],k=1,2,3,…
回文串长度是偶数,则依次判断 s[i−k]==s[i+k−1],k=1,2,3,…s[i−k]==s[i+k−1],k=1,2,3,…
如果遇到不同字符,则我们就找到了以 ii 为中心的回文串边界。

时间复杂度分析:一共两重循环,所以时间复杂度是 O(n2)O(n2)。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    getline(cin,s);
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        for(int j=0;i-j>=0&&i+j<s.size();j++)
        {
            if(s[i-j]==s[i+j])
            {
               if(j*2+1>ans)
               {
                   ans=j*2+1;
               }
            }
            else
            break;
        }
        for(int k=i,j=i+1;k>=0&&j<s.size();k--,j++)
        {
            if(s[k]==s[j])
            {
                if(j-k+1>ans)ans=j-k+1;
            }
            else break;
        }
    }
    cout<<ans;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 LeetCode 5. 最长回文子串

h_s
5天前
class Solution {
public:
    string longestPalindrome(string s) {
        int ans=0;
        string res;
        for(int i=0;i<s.size();i++)
        {
            for(int j=0;i-j>=0&&i+j<s.size();j++)
            {
                if(s[i-j]==s[i+j])
                {
                    if(j*2+1>ans)
                    {
                        ans=j*2+1;
                        res=s.substr(i-j,j*2+1);
                    }
                }
                else
                break;
            }
            for(int k=i,j=i+1;k>=0&&j<s.size();k--,j++)
            {
                if(s[k]==s[j])
                {
                    if(j-k+1>ans)
                    {
                        ans=j-k+1;
                        res=s.substr(k,j-k+1);
                    }
                }
                else break;
            }
        }
        return res;

    }
};



h_s
5天前

双指针算法

class Solution {
public:
     unordered_map<char,int>h;
     int ans=0;
    int lengthOfLongestSubstring(string s) {
        for(int i=0,j=0;i<s.size();i++)
        { 
            h[s[i]]++;
            while(h[s[i]]>1)
            {
                h[s[j]]--;
                j++;
            }
            ans=max(ans,i-j+1);
        }
        return ans;
    }
};


活动打卡代码 LeetCode 2. 两数相加

h_s
5天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
          ListNode*res=new ListNode();
           ListNode*ans=res;
          int num=0;
          while(l1||l2)
          {
              int n1=l1?l1->val:0;
              int n2=l2?l2->val:0;
              int sum=n1+n2+num;
              num=sum/10;
              ans->next=new ListNode(sum%10);
              if(l1)l1=l1->next;
              if(l2)l2=l2->next;
              ans=ans->next;
          }
          if(num)ans->next=new ListNode(1);
          return res->next;

    }
};