YeZi

Maximum Length of Repeated Subarray

发表于 2019-05-01 阅读次数： Valine：
本文字数： 489 阅读时长 ≈ 1 分钟

Maximum Length of Repeated Subarray

Desc: 给出两个字符串求两串最大公共子串的长度

DP：

dp[i][j]代表了以a[i]和b[i]为起点的的字符串的最大公共子串的长度

那么dp[i][j] = a[i] == b[j] ? 1 + dp[i + 1][j + 1] : 0

考虑利用“滚动数组优化”可以降低一维

My_Code:

class Solution {
public:
    int findLength(vector<int>& a, vector<int>& b) {
        int m = a.size(), n = b.size();
        if (!m || !n) return 0;
        vector<int> dp(n + 1);
        int res = 0;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                res = max(res, dp[j] = a[i] == b[j] ? 1 + dp[j + 1] : 0);
            }
        }
        return res;
    }
};

阅读全文 »

WeeklyContest14

发表于 2019-04-28 阅读次数： Valine：
本文字数： 3.2k 阅读时长 ≈ 6 分钟

其实没做过LeetCode的 contest

url: https://leetcode.com/contest/leetcode-weekly-contest-14

今天头疼就virtual一场结果脸比较好抽到的题很简单….

Score 3:

Number Complement : 简单的把一个数二进制下0换成1 1换成0

xjb写由于人比较蠢不会用位运算就全算出来了

My_Code:

class Solution {
public:
    int findComplement(int num) {
        vector<int>q;
        while(num){
            q.push_back(num%2);
            num/=2;
        }
        int ss=q.size();
        for(int i=ss-1;i>=0;i--){
            if(q[i]==1) q[i]=0;
            else q[i]=1;
        }
        int ans=0;
        for(int i=ss-1;i>=0;i--){
            ans*=2;
            ans+=q[i];
        }
        return ans;
    }
};

Score 6:

阅读全文 »

Bitwise ORs of Subarrays

发表于 2019-04-19 阅读次数： Valine：
本文字数： 1.2k 阅读时长 ≈ 2 分钟

LeetCode 898. Bitwise ORs of Subarrays

Desc:

有一个非负整数数组a，对所有整数对(i,j)求 a[i]|a[i+1]|a[i+2]…a[j] 的值（|为按位或），求共有多少个不相等的值
$$
1\le a.length() \le 5000
$$

$$
0 \le a[i] \le 10^9
$$

My_Ans:

n^2裸题冲冲冲

设b(i,j)=a[i]|a[i+1]….|a[j] 用一个set now保存b(0,i),b(1,i),b(2,i)

然后每次处理到a[i+1]的时候把now里的所有项和a[i+1] 按位或一下

然后把a[i+1]添加到now里

阅读全文 »

LeetCode.857.Minimum.Cost.to.Hire.K.Workers

发表于 2019-04-18 阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 3 分钟

LeetCode 857. Minimum Cost to Hire K Workers

Desc：

N个worker，每个worker有quality和wage，你需要雇佣K个worker，这K个worker之间的real wage比例和quality比例相同，且real wage不小于wage。
$$
1 \le K ,N \le 10000

1\le quality,wage\le10000
$$
答案允许有10^-5的误差

My_Ans:

冷静分析，首先 worker之间严格按照比例发real wage 且
$$
real wage[i]\ge wage[i]
$$
定义
$$
ratio[i]=wage[i]/quality[i]
$$
假设已经选出了K个worker，那么这个standard worker就需要设置为ratio最大的那个worker

否则会有worker的real wage<wage。

因此对于每个standard worker 我们需要找出k-1个ratio小于它的worker，而且K个worker的
$$
totalwage = ratio* \sum_{n=1}^K{quality}
$$
按照ratio对worker从小到大排序，枚举第i个worker作为standard worker

所以第0~第i-1个worker均为满足ratio满足要求的，然后需要找出K-1个quality最小的即可

阅读全文 »

2018总结

发表于 2019-01-03 阅读次数： Valine：
本文字数： 81 阅读时长 ≈ 1 分钟

不知不觉2018过去了

本来打算12.31写的然而咕咕了

现在还打算继续咕咕

先写2019目标（笑

希望自己考研顺利

PT继续佛系刷

有钱组NAS

换个显示器

其他东西不要坏（瘫

阅读全文 »

Min_stack

发表于 2018-12-22 阅读次数： Valine：
本文字数： 577 阅读时长 ≈ 1 分钟

还是比较简单的，但是这个跟我在宁夏坑队友的一个题一模一样，权当纪念吧

题目：实现一个数据结构，这个数据结构需要实现栈的插入，栈的弹出，返回栈顶元素，返回栈内最小值四种操作。

My Ans：用vector保存从栈底到栈顶的前缀Min，可以知道每次插入的时候需要在Vector中插入Min(input,Vector.back())；

跑的不是很快…28ms beat 50.39%而已

class MinStack {
public:
    /** initialize your data structure here. */
    vector<int>m;
    stack<int>st;
    MinStack() {
        m.clear();
    }
    void push(int x) {
        st.push(x);
        if(m.empty()) m.push_back(x);
        else m.push_back(min(m.back(),x));
    }
    void pop() {
        m.pop_back();
        st.pop();
    }
    int top() {
        return st.top();
    }
    int getMin() {
        return m.back();
    }
};

阅读全文 »

摸鱼记录

发表于 2018-12-22 阅读次数： Valine：
本文字数： 248 阅读时长 ≈ 1 分钟

最近的日子过得挺快的。

感觉有丶弱智，搭了OJ不知道用来干嘛

blog也算是小小的安全屋（？

R6打的比较多其他游戏也都歇了准备开始数1 英1的复习

课程方面刚结束了数据结构最后考试有一题不太会其他都还行

JAVA就不提了..学院自己开的水课，基本也就学了SWING的一些基本框架应用进程算是半懂不懂的情况

只能说还是犯懒

LeetCode 算是半摸鱼状态吧，到现在也就刷了一百个

明年得报个PAT，也算是留条后路

阅读全文 »

CompareVersionNumbers

发表于 2018-11-25 阅读次数： Valine：
本文字数： 752 阅读时长 ≈ 1 分钟

大模拟吧…细节蛮多的(这个题我发现全是踩所以写一篇…)

我是将字符串分割读入vector中然后去掉vector中的末尾0

按照比较字典序大小的方法逐个比较vector中的元素

class Solution {
public:
    vector<int> div(string s){
        int ss=s.size();
        vector<int>ans;
        for(int i=0;i<ss;){
            if(isdigit(s[i])){
                int cnt=0;
                while(isdigit(s[i])){
                    cnt=cnt*10+s[i]-'0';
                    i++;
                }
                if(cnt!=0)ans.push_back(cnt);
            }
            else i++;
        }
        return ans;
    }
    int compareVersion(string version1, string version2) {
        vector<int>v1=div(version1);
        vector<int>v2=div(version2);
        for(int i=0;i<min(v1.size(),v2.size());i++){
            if(v1[i]>v2[i]) return 1;
            else if(v1[i]<v2[i]) return -1;
        }
        if(v1.size()>v2.size()) return 1;
        else if(v2.size()>v1.size()) return -1;
        return 0;
    }
};