0%

前言

最近有空整理了一下

写这个邀请树纯粹是一时冲动?

也许吧-.-看U2的邀请查询系统感觉挺好玩的

然后又想看Admin这棵树有多大(flag 做完发现浏览器撑不住了

然后发现自己好菜啊(

调查

主要的几个方案:

数据怎么获取:PY啊

前端:Echarts及其相关语言的其他库(pyechart等)、d3js等基于js的一些可视化工具

阅读全文 »

Flood Fill

Desc:

二维格点,用数字代表颜色,选定一个点(sr,sc)进行染色,和该点直接相连的同色点且都会被染成新颜色,求最后的二维矩阵。

很简单不知道为什么我要写一篇blog(表现的自己很努力?

My_Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int oldColor = image[sr][sc];
if (oldColor == newColor) return image;
queue<pair<int, int>> queue;
queue.push(make_pair(sr, sc));
int n = image.size();
int m = image[0].size();
while (!queue.empty()) {
int row = queue.front().first;
int column = queue.front().second;
queue.pop();
if (image[row][column] == oldColor) {
image[row][column] = newColor;
if (row != 0) queue.push(std::make_pair(row-1, column));
if (row != n-1) queue.push(std::make_pair(row+1, column));
if (column != 0) queue.push(std::make_pair(row, column-1));
if (column != m-1) queue.push(std::make_pair(row, column+1));
}
}
return image;
}
};
阅读全文 »

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
};
阅读全文 »

其实没做过LeetCode的 contest

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

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

Score 3:

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

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

My_Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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:

Magical String :一个魔法字符串仅由1和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里

但是这个范围好像给我喂了一口X….

阅读全文 »

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最小的即可

考虑维护一个最多K个元素的单调队列 队首的worker的quality最大 队列中均满足ratio小于当前standard worker

阅读全文 »

不知不觉2018过去了

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

现在还打算继续咕咕

先写2019目标(笑

希望自己考研顺利

PT继续佛系刷

有钱组NAS

换个显示器

其他东西不要坏(瘫

阅读全文 »

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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();
}
};
阅读全文 »

最近的日子过得挺快的。

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

blog也算是小小的安全屋(?

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

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

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

只能说还是犯懒

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

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

考虑把现役期间出的题挂到自己的OJ上

阅读全文 »