头像

废wù




离线:3天前



废wù
3天前

正则表达式

import re
...
        return max(min(int(*re.findall('^[\+\-]?\d+', str.lstrip())), 2**31 - 1), -2**31)



废wù
5天前
#include<bits/stdc++.h>
using namespace std;

int main(){
    int pricesSize,fee;
    cin >> pricesSize >> fee;
    int prices[pricesSize];
    for(int i = 0;i < pricesSize;i ++)
        cin >> prices[i];

    int hode = INT_MIN + fee,cash = 0,i = 0,bh_hode = hode;

    for(i = 0;i < pricesSize;i++){
        hode = max(hode,cash - prices[i]);
        cash = max(bh_hode + prices[i] - fee,cash);
        bh_hode = hode;
    }
    cout << cash;
    return 0;
}



废wù
7天前

三维DP,本质和股票123没区别;

第i天交易次数0不持有股票的情况只能来自第i-1天交易次数0不持有股票
第i天交易j次不持有股票的状态可以来自第i-1天交易j次不持有股票或者第i-1天交易j-1次持有股票
第i天交易j次持有股票的状态可以来自第i-1天交易j次持有股票或者第i-1天交易j次不持有股票

#include<bits/stdc++.h>
using namespace std;

int m_maxProfit(vector<int>& prices, int pricesSize){
    int hode = INT_MIN,cash = 0,i = 0,bh_hode = INT_MIN;
    for(i = 0;i < pricesSize;i++){
        hode = max(hode,cash - prices[i]);
        cash = max(bh_hode + prices[i],cash);
        bh_hode = hode;
    }
    return cash;
}


int maxProfit(int k, vector<int>& prices) {
    int i = 0,j = 0,n = prices.size();
    if(n < 2)return 0;
    if(k >= n/2) return m_maxProfit(prices,n);//超过了就是没限制
    vector<vector<int>> cash(n, vector<int>(k + 1,0));
    vector<vector<int>> hode(n, vector<int>(k + 1,INT_MIN));
    for(j = k;j > 0;j--){
        cash[i][j] = max(hode[0][j] + prices[i],cash[0][j]);
        hode[i][j] = max(hode[0][j],cash[i][j - 1] - prices[i]);
    }
    for(i = 1;i < n;i++){
        for(j = k;j > 0;j--){
           cash[i][j] = max(hode[i-1][j] + prices[i],cash[i - 1][j]);
           hode[i][j] = max(hode[i-1][j],cash[i - 1][j - 1] - prices[i]);
        }
    }
    return cash[n - 1][k];
}

int main(){
    int n,k,p;
    cin >> n >> k;
    vector<int>arr(n);
    for(int i = 0;i < n;i ++){
        cin >> p;
        arr[i] = p;
    }
    cout << maxProfit(k,arr);
    return 0;
}



废wù
9天前

#include<bits/stdc++.h>
using namespace std;

int maxProfit(vector<int>& prices) {
    int i = 0,j = 0,n = prices.size(),k = 2;
    if(n < 2)
        return 0;
    vector<vector<int>> cash(n, vector<int>(k + 1,0));
    vector<vector<int>> hode(n, vector<int>(k + 1,INT_MIN));
    for(j = k;j > 0;j--){
        cash[i][j] = max(hode[0][j] + prices[i],cash[0][j]);
        hode[i][j] = max(hode[0][j],cash[i][j - 1] - prices[i]);
    }
    for(i = 1;i < n;i++){
        for(j = k;j > 0;j--){
           cash[i][j] = max(hode[i-1][j] + prices[i],cash[i - 1][j]);
           hode[i][j] = max(hode[i-1][j],cash[i - 1][j - 1] - prices[i]);
        }
    }
    return cash[n - 1][k];
}

int main(){
    int n,p;
    cin >> n;
    vector<int>prices(n);
    for(int i = 0;i < n;i ++){
        cin >> p;
        prices[i] = p;
    }
    cout << maxProfit(prices);
    return 0;
}




废wù
9天前

无脑DP

#include<bits/stdc++.h>
using namespace std;

int maxProfit(int* prices, int pricesSize){
    if(pricesSize <= 1) return 0;
    int i = 0,* _prices,sum = 0;
    _prices = (int *)malloc(sizeof(int) * pricesSize);
    _prices[0] = 0;
    for(i = 1;i < pricesSize;i++){
        _prices[i] = prices[i] - prices[i - 1];
        if (_prices[i] > 0) sum += _prices[i]; 
    }
    return sum;
}

int main(){
    int pricesSize;
    cin >> pricesSize;
    int prices[pricesSize];
    for(int i = 0;i < pricesSize;i++)
        cin >> prices[i];
    cout << maxProfit(prices,pricesSize);
}



废wù
10天前

DP

#include<bits/stdc++.h>
using namespace std;

int maxProfit(int* prices, int pricesSize){
    if(pricesSize <= 1) return 0;
    int i = 0,* _prices,max;
    _prices = (int *)malloc(sizeof(int) * pricesSize);
    _prices[0] = 0;
    if(prices[1] - prices[0] > 0) max = _prices[1];else max = 0;
    for(i = 1;i<pricesSize;i++){
        _prices[i] = prices[i] - prices[i-1];
        if(_prices[i - 1] > 0)_prices[i] += _prices[i - 1];
        if(_prices[i] > max)max = _prices[i];
    }

    free(_prices);
    return max;
}

int main(void){
    int pricesSize;
    cin >> pricesSize;
    int prices[pricesSize];
    for(int i = 0;i < pricesSize;i ++)
        cin >> prices[i];
    cout << maxProfit(prices,pricesSize);
}



废wù
12天前

树状数组

class Solution {
public:
    int lowbit(int x) {return x&(-x);}
    void update(int i,vector<int>& c)
    {
        while(i <= c.size())
        {
            c[i]+=1;
            i+=lowbit(i);
        }
    }
    int getsum(int i,vector<int>& c)
    {
        int res=0;
        while(i)
        {
            res+=c[i];
            i-=lowbit(i);
        }
        return res;
    }
    int inversePairs(vector<int>& nums) {
        int n=nums.size();
        vector<int> vt;
        vector<int> c(n+20);
        for(auto i:nums) vt.push_back(i);
        sort(vt.begin(),vt.end());
        vt.erase(unique(vt.begin(),vt.end()),vt.end());
        unordered_map<int,int> mp;
        int cont=1;
        for(auto i:vt) mp[i]=cont++;
        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            update(mp[nums[i]],c);
            ans+=(i+1)-getsum(mp[nums[i]],c);
        }
        return ans;
    }
};



废wù
13天前

阿哲.....

return nums.empty() ? -1 : *min_element(nums.begin(),nums.end());



废wù
15天前

···cpp
class Solution {
public:
int findNumberAppearingOnce(vector[HTML_REMOVED]& nums) {
unordered_map[HTML_REMOVED] t;
for(int i: nums) t[i]++;
for(int i: nums)
if(t[i]== 1) return i;
return 0;
}
};
···




废wù
16天前

递归求解

n = 3421

3421 = 1000 * [1*] + 3 * [0 - 999] + 1 * [0 - 421]

999 = 100 * [1*] + 9 * [0 - 99] + 1 * [0 - 99]

99 = 10 * [1*] + 9 * [0 - 9] + 1 * [0 - 9]

421 = 100 * [1*] + 4 * [0 - 99] + 1 * [0 - 21]

21 = 10 * [1*] + 2 * [0 - 9] + 1 * [0 - 1]

3421 = 1000 * [1*] + 3 * [0 - 999] + 1 * [0 - 421] 代表 3421 中 1 的个数 为

1000 个 1_ _ _

3 个 [0 ~ 999] 中的 1 的个数

余数部分 的 [0~421] 中的 1 的个数

class Solution {
public:
    unordered_map<int , int > rec;
    int numberOf1Between1AndN_Solution(int n) {
        if (n < 1) return 0;
        else if (n <= 9) return 1;

        if (rec.count(n)) return rec[n];
        // 9981
        string ns = to_string(n);
        int f = ns[0] - '0';
        int a = pow(10, ns.size() - 1); // 1000
        int r = n % a ;// 981
        int res = 0;
        if (f > 1){
            // printf("%d = %d * [1*] + %d * [0 - %d]  +  1 * [0 - %d]\n",n, a, (f), a - 1, r);
            res += a + (f) * numberOf1Between1AndN_Solution(a - 1) + numberOf1Between1AndN_Solution(r);
        }
        else if (f == 1){
            // printf("%d = %d * [1*] + 1 * [0 - %d] + 1 * [0 - %d] \n", n, r + 1,  a - 1,  r);
            res += (r + 1) + numberOf1Between1AndN_Solution(a - 1)  + numberOf1Between1AndN_Solution(r);
        }
        rec[n] = res;
        return res;
    }
};