头像

小猪快跑_9

武汉理工大学


访客:721

离线:4天前



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.size() == 0)
            return vector<int>({-1, -1});
        int l = 0,r = nums.size()-1;
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid]>=target) r= mid;
            else l = mid+1;
        }
        if (nums[l] != target)
            return vector<int>({-1, -1});
        res.push_back(l);
        l = 0,r = nums.size()-1;
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid]<=target)l=mid+1;
            else r = mid;
        }
        if (nums[l] > target)
            res.push_back(l-1);
        else
            res.push_back(l);
        return res;

    }
};



题目描述

实现int sqrt(int x)函数。

计算并返回x的平方根,其中x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

样例

样例一

输入: 4
输出: 2

样例二

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

算法1

(二分) $O(logn)$

二分出最大的 y,满足 y2≤x。
则 y 就是答案。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int mySqrt(int x) {
        long l = 0, h = (long)x + 1;
        while(l < h){
            long m = (l + h) / 2;
            if(m * m > x) h = m; else l = ++m;
        }
        return (int)l - 1;
    }
};



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0,r = nums.size()-1;
        if(r==-1) return 0;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] < target)
                l = mid + 1;
            else
                r = mid;
        }

        if (nums[l] >= target)
            return l;

        return nums.size();
    }
};


活动打卡代码 LeetCode 69. Sqrt(x)

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    int mySqrt(int x) {
        long l = 0, h = (long)x + 1;
        while(l < h){
            long m = (l + h) / 2;
            if(m * m > x) h = m; else l = ++m;
        }
        return (int)l - 1;
    }
};


活动打卡代码 AcWing 282. 石子合并

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 301
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int s[N],f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)cin>>s[i];
    for(int i = 1;i<=n;i++)s[i]+=s[i-1];
    for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;  //区间终点
        f[i][j] = 1e8;
        for (int k = i; k < j; k++) {        //枚举分割点,构造状态转移方程
             f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    }

    cout<<f[1][n]<<endl;
    return 0;
}




//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/*
动态规划 时间复杂度O(n*m)
1.状态表示 f(n,m)表示字符串A中前n个字符,B中前m个字符的所有公共子序列
2.状态计算:分成4个状态,1.A[i],B[j]都不选,这个情况在2,3种情况中被包含,所有不用计算 
        2.A[i]选B[j]不选,f[i][j-1]
        3.A[i]不选B[j]选,f[i-1][j]
        4.都选 f[i-1][j-1]+1 条件:A[i]==B[j]
3.状态转移方程:f[i][j] = max(f[i-1][j],f[i][j-1])   if(A[i]==B[j])  f[i][j] = max(f[i][j],f[i-1][j-1]+1)
*/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 1010
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
char A[N],B[N];
int f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    cin>>A+1>>B+1;
    for(int i = 1;i<=n;i++)
    for(int j = 1;j<=m;j++){
        f[i][j] = max(f[i-1][j],f[i][j-1]);
        if(A[i]==B[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);
    }
    cout<<f[n][m]<<endl;
    return 0;
}




#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 100005
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
vector<int> stk;
int a[N],dp[N];
int main()
{
    int n;
    cin>>n;
    for(int i =1;i<=n;i++)cin>>a[i];
    stk.push_back(a[1]);
    for(int i =1;i<=n;i++){
        if(a[i]>stk.back()){
            stk.push_back(a[i]);
        }
        else{
            *lower_bound(stk.begin(),stk.end(),a[i])=a[i];
        }
    }
    cout<<stk.size()<<endl;
    return 0;
}




//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 1010
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int dp[N],a[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        dp[i] = 1;
        cin>>a[i];
        for(int j = 1;j<=i-1;j++){
            if(a[i]>a[j]){
           dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
    int res = 1;
    for(int i = 1;i<=n;i++)
    res = max(res,dp[i]);
    cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 898. 数字三角形

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 505
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int f[N][N],dp[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i = 0;i<n;i++)
    for(int j = 0;j<=i;j++){
    cin>>f[i][j];
    if(j==0)dp[i][j] = dp[i-1][j]+f[i][j];
    else if(j==i)dp[i][j] = dp[i-1][j-1]+f[i][j];
    else
    dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+f[i][j];
    }
    int res = -INF;
    for(int i=0;i<n;i++ ) res = max(res,dp[n-1][i]);
    cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 9. 分组背包问题

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 2500
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int s[N],w[N][N],v[N][N];
int dp[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++) {
        cin>>s[i];
        for(int j = 0;j<s[i];j++)
        cin>>v[i][j]>>w[i][j];
    }
    for(int i = 1;i<=n;i++)
    for(int j = m;j>=0;j--)
    for(int k = 0;k<s[i];k++)
    if(j>=v[i][k])
    dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k]);
    cout<<dp[m]<<endl;
    return 0;
}