Gas Station
Kmeans 算法和EM有点相似，从蛋哥学习的。
一日不学，如隔千秋啊！最近正逢开学，一直都没有看过书。今天想着做几道进制转换的题。算完之后，本想用python检验一下的，没想到竟然忘掉怎么转换的了（话说平时也基本不怎么用到进制转换）。果断翻书去查，哪知翻来翻去，硬是没找到（当初学的时候也是想着暂时用不着，就没怎么看过），最后只好向度娘求救。为了记住这一次的教训，也算是整理一下笔记，特地写此文章作为记录。
十进制转换二进制
bin(10)
‘0b1010’
十进制转换十六进制
hex(10)
‘0xa’
二进制转换十进制
int(‘1010’,2)
10
十六进制转换十进制
int(‘0xa’,16)
10
十六进制转换二进制
bin(0xa)
‘0b1010’
二进制转换十六进制
hex(0b1010)
‘0xa’
python 没有实现链表
http://blog.suchasplus.com/2011/03/why-python-Standard-library-does-not-implement-the-list.html
python即是属于非常简洁完美的语言。没有C++那么多冗余的stack queue啥的
因为数组写成栈非常简单。
python 常用数据结构list, 顺序表
sets hash表
dictionary hashmap
myds=[]//list
myds=sets()//sets, hashset
myds={}//dictionary, hashmap
myds=()//tuple
toposort dfs版from 学神
拓扑其实dfs bfs都可以，但是都是基于临界点并且入度为0的来扩展，
其实本质没区别，之前看的geeksforgeeks那个实在有点蹩脚，直接弃掉了，还用了栈，哎
int deg[maxn], n, t, m, tt=0, x, y;
vector<int> edge[maxn];
void dfs(int i)
{
deg[i]=-1;//visit mark
tt++;
for(auto e: edge[i])
{
if(--deg[e]==0) dfs(e);
}
}
int main()
{
/*
#ifndef ONLINE_JUDGE
freopen ("in.txt" , "r" , stdin);
freopen ("out.txt" , "w" , stdout);
#endif
*/
cin>>t;
for(int ti=1;ti<=t;ti++)
{
cin>>n>>m;
for(int i=1;i<=n;i++) edge[i].clear(), deg[i]=0;
for(int i=0;i<m;i++)
{
cin>>x>>y;
edge[x].push_back(y);
deg[y]++;
}
tt=0;
for(int i=1;i<=n;i++)
{
if(!deg[i]) dfs(i);
}
puts(tt==n ? "Correct": "Wrong");
}
return 0;
}
Java 的数组全都是new的，而且初始为0，C++的局部自动变量的数组都是野值，需要初始化，非常麻烦。
3、continuous是指时间/过程上的“继续”和“承接”，强调中间的“内容或实体”不发生中断或缺失（但是在时间/过程上可以暂时中止/停顿，后续承接着往下发展），是在原有状态下的“继起”和“延续”。如电视连续剧是指在剧情上承接，但可以中途停播然后续播，文章或故事也先写一部分再于后面其它时间续完（这时候最先的文章末尾常有to be continued 或 to be completed字样）。
4、contiguous跟continuous只有g和n一个字母的差别，但它们的区别还是很明显的。contiguous是指地域上的相连、相邻、交界，是“毗邻”的意思，如广东和广西在地域上就是contiguous的，Excel中的单元格之间也是contiguous的。
简单的说，continuous是指时间上的连续，或者过程的连续，
contiguous是指空间的连续
largest rectangle
维护一个单调递增的队列，用栈来存。
左到右是递增，右到左算也是递增的。
代码模板来自谢老师，谢老师分分钟教我单调队列入门~~~
class Solution {
public:
int largestRectangleArea(vector<int>& h) {
int n=h.size();
int l[n], r[n];
stack<int> s1;//mono increase queue
for(int i=0;i<n;)
{
if(s1.empty())
{
l[i]=i;
s1.push(i++);
}
else if(h[s1.top()]<h[i])
{
l[i]=i-s1.top()-1;
s1.push(i++);
}
else s1.pop();
}
stack<int> s2;//mono increase queue
for(int i=n-1;i>=0;)
{
if(s2.empty())
{
r[i]=n-1-i;
s2.push(i--);
}
else if(h[s2.top()]<h[i])
{
r[i]=s2.top()-i-1;
s2.push(i--);
}
else s2.pop();
}
int ans=0;
for(int i=0;i<n;i++)
ans=max(ans, h[i]*(l[i]+r[i]+1));
return ans;
}
} S;
这道题目就是找一个起点，使得每一次累加gas 和 cost 差值之后一直为正。
分析了两个性质之后，就可以解题了。
- 如果sum gas>= sum cost, 那么一定有解.
- 如果从某个起点start,累加到i之后第一次变-， 那么解一定不再[start, i]，因此解可以暂时设定为i+1 (为何呢? 因为第一次变-的话，那么前面每次都累加完都是正，如果解再[start+1,i]的话，例如start+1, 那么从start+1开始累加到i一定是负的，因为会比之前的更小，因为start开始第一次累加一定为正，不然就提前结束了)
因此我们维护几个变量
sum: 表示当前累加的和，如果变-了就清了，修改候选的起始点。
total: 计算总的差值，判断题目是否有解
j: 表示当前候选的答案，起始点
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n=gas.size();
int total=0, sum=0, j=0;
for(int i=0;i<n;i++)
{
sum+=gas[i]-cost[i];
total+=gas[i]-cost[i];
if(sum<0) sum=0, j=i+1;
}
return total < 0 ? -1 : j;
}
};