Joyce' Blog

数据库中where和having的区别

发表于 2019-04-24 更新于 2019-05-31

where是一个约束声明，在查询结果返回之前起作用，where后面不能使用“聚合函数”，因为where的执行顺序在聚合函数之前；

having是一个过滤声明，分组筛选，在查询结果返回之后起作用，不能对没有查出来的值使用having，having后面可以使用“聚合函数”。

JavaS提供7种变量：undefined（未定义）, null（空）, boolean（布尔型）, string（字符串）, symbol(符号), number（数字）, and object（对象）。Variables（变量）允许计算机以一种动态的形式来存储和操作数据，通过操作指向数据的指针而不是数据本身来避免了内存泄露，以上的七种数据类型都可以存储到一个变量（variable）中。在变量前使用关键字var来创建一个变量。Variable （变量）的名字可以由数字、字母、$ 或者 _组成，但是不能包含空格或者以数字为首。

逆序计数

发表于 2019-04-22 更新于 2020-02-10

分析

穷举（Brute force）: Θ(n2).
分治策略：Θ(nlgn)

划分：把序列一分为二；
分别递归求出左右各自部分的逆序数；
组合: 计数左右部份之间的逆序数, 返回总的逆序数

算法

Merge-and-Count(A,B)

维护一个Current指针指向每个表，初始化指向首元素

维护一个变量Count用于逆序的计数，初始为0

While两个表都不空

令ai与bj是由Current指针指向的元

把这两个表中较小的元素加到输出表中

If bj是较小的元素then

把Count加上在A中右边剩余的元素数

Endif

把较小元素选出的表中的Current指针右移

Endwhile

一旦一个表为空，把另一个表剩余的所有元素加到输出中

返回Count和合并后的表

Sort-and-Count(L)

If这个表中有一个元素，then

没有逆序

Else

把这个表划分成两半，

A包含前个元素

B包含剩下的个元素
(rA,A)=Sort-and-Count(A)

(rB,B)=Sort-and-Count(B)

(r,L)=Merge-and-Count(A,B)

Endif

返回r=rA+rB+r以及排好序的表L

代码

#include<bits/stdc++.h>
using namespace std;
int rev_count = 0;
vector<int> merge_count(vector<int>&A, vector<int>&B)
{
	vector<int> R;
	while (!A.empty() && !B.empty())
	{
		int a = A.front();
		int b = B.front();
		if (b < a)
		{
			R.push_back(b);
			rev_count += A.size();
			B.erase(B.begin());
		}
		else
		{
			R.push_back(a);
			A.erase(A.begin());
		}
	}
	R.insert(R.end(), A.begin(), A.end());
	R.insert(R.end(), B.begin(), B.end());
	return R;
}
vector<int> sort_count(vector<int>&L)
{
	int ls = L.size();
	if ( ls!= 1)
	{
		int x = ls / 2;
		vector<int> A, B;
		int i;
		for (i = 0; i < x; ++i)
			A.push_back(L.at(i));
		for(;i<ls;++i)
			B.push_back(L.at(i));
		A = sort_count(A);
		B = sort_count(B);
		L = merge_count(A, B);
	}
	return L;
}
int main()
{
	vector<int> L;
	int n; int t;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> t;
		L.push_back(t);
	}
	sort_count(L);
	cout << rev_count << "\n";
	for (int i = 0; i < n; i++)
		cout << L.at(i) << " ";
	system("pause");
	return 0;
}

left join & where

发表于 2019-04-17

在做数据库练习题时，遇到了这样的问题：

给出每个专业借阅的“c2”类的图书总数，没有借阅的次数显示为0（majorid，majorname，borrowcount）

数据库内容如下

最开始使用where语句对结果进行筛选，但是显示不了为0的项

参照网上的做法用LEFT JOIN 关键字进行了修改

所以查了一下where和left join的区别：

LEFT JOIN 关键字从左表（table1）返回所有的行，即使右表（table2）中没有匹配。如果右表中没有匹配，则结果为 NULL（在某些数据库中，LEFT JOIN 称为 LEFT OUTER JOIN。）

where语句中如果没有匹配的，则返回一个空集，因此借阅人数为0的书籍不会被显示出来

Longest Palindromic Substring

发表于 2019-04-15 更新于 2020-07-09

比较容易理解的方法是以s[i]为中心(i=1,…,n)，分回文序列长度为奇数和偶数的情况，向两边扩张，找到最长的回文序列，这样的时间复杂度为O(n^2)。

还有一种很巧妙的Manacher 算法，可以在O(n)时间求字符串的最长回文子串，大致思路如下：

插入特殊字符，使奇数或偶数长度的字符串，长度都变成了奇数，并且在字符串首位加另外一个特殊字符，就不用处理越界问题，如：”12212321”变成”$#1#2#2#1#2#3#2#1#”;这种做法让我想到“求两个有序数组的中位数”的预处理的思想，同样也是为了统一讨论，将数组元素的下标进行处理，对越界的下标赋了特殊值。

用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度。那么p[i]-1正好是原字符串中以s[i]为中心的回文串的长度。

为了计算p[i]，增加变量id,mx，id是当前已知的右边界最大回文串的中心，mx=id+p[id]，即子串的右边界。id,mx初始值都为0。接下来是算法的关键：

当mx>i，p[i]>=MIN(p[2*id-i],mx-i)；当mx<=i，p[i]=1，然后向两边扩展。

对于mx>i的情况，j=2*id-i是i关于id的对称点，利用前面计算的结果，可以得出对称点的两侧回文串的长度。

代码主要部分：

string longestPalindrome(string s) {
	//预处理
	string a = "$#";
	int len = s.size();
	for (int i = 0; i < len; i++)
		a = a + s[i] + "#";

	int p[2002], mx = 0, id = 0;
	memset(p, 0, 2002);
	for (int i = 1; a[i] != 0; ++i)
	{
		p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
		while (a[i + p[i]] == a[i - p[i]])++p[i];
		if (i + p[i] > mx)
		{
			id = i;
			mx = i + p[i];
		}
	}
	int tmp = 0;
	for (int i = 1; i < 2002; i++)
		tmp = p[tmp] > p[i] ? tmp : i;
	return s.substr((tmp-p[tmp] + 1)/2, p[tmp] - 1);
}

未命名

发表于 2019-04-14 更新于 2019-05-31

title: Ted-Note1
tags: English—

做项目做得有点自闭了，换个学习内容放松一下吧。

推荐这个TED，内容对我很有启发。看待事物时，要学会跳出自我，又不是个小孩了，总是从自己出发看问题的话，算是狭隘还是自私呢？行事之情而忘其身，何暇至于悦生而恶死。其实，把人生当做一场场游戏来看的时候，反而能看得明白和坦然些，乘物以游心，托不得已以养中。下面是应有的正题了：

Key Points

The scout’s job is not to attack or defend. The scout’s job is to understand. The scout is the one going out, mapping the terrain, identifying potential obstacles.侦查员的工作不是攻击或防守，侦查员的工作是认清形势。侦查员是那些走出营地、去测定地形、识别潜在障碍的人。
Some information, some ideas, feel like our allies. We want them to win. We want to defend them. And other information or ideas are the enemy, and we want to shoot them down.有些信息和想法像是我们的盟友，我们希望他们能赢，我们想要保护他们。还有些信息和想法就像是敌人，我们想要打垮它们。
Our judgment is strongly influenced, unconsciusly, by which side we want to win. And this is ubiquitous. This shapes how we think about our health, our relationships, how we decide how to vote, what we consider fair or ethical.我们的判断无意识的受到个人喜好的强烈影响。而且这种现象是普遍存在的。它影响着我们如何看待健康和人际关系，如何决定投谁的票，以及怎样看待公平或道德。（ubiquitous 普遍存在的、似乎无处不在的）
Scouts are grounded, which means their self-worth as a person isn’t tied to how right or wrong they are about any particular topic.侦查兵是以事实为根据的，也就是说，他们的自我价值观不是跟他们在某件事上的对错绑在一起的。
If you want to build a ship, don’t drum up your men to collect wood and give orders and distribute the work. Instead, teach them to yearn for the vast and endless sea.如果你想造一艘船，不要雇人去收集木材，不要发号施令，也不要分配任务，而是要去激发他们对无垠大海的渴望。（这是《小王子》中的一句话，很明智的一种策略，但是这样是不是就能提高成功的可能性呢？我不知道。难怪老师给我们描绘出了项目美好的前景，但是当实际情况不太妙的时候，这种落差感要怎么解决才好呢——走出自身利益看问题，这应该是关键了。同时也体会到周老师说的“自省”，是多么可贵的一种品质和思维）

所以问题归结于，我们更想要的是什么呢？是捍卫自己的信仰，还是尽可能清晰地看见这个世界？

随想

庄子所说的“散木”，不汲汲于为世所用，生命得以保存，是一种人生智慧，范蠡功成身退、刘邦和朱元璋杀功臣，正反例皆有。但不是我想要的人生——立德，立言，立功。

C++ list,vector,deque,set,map

发表于 2019-04-13

list

列表，封装了链表，不支持[]运算符。常用函数：

.front(),.back(),.pop_back(),.pop_front(),.insert(),.size(),.empty(),.push_back(),.push_front()

vector

向量，封装了数组，支持[]运算符。常用函数：

push_back(),pop_back(),front(),size(),clear(),empty(),operator[]

deque

双端队列，合并了list和vector

如果需要高效的随即存取，而不在乎插入和删除的效率，使用vector
如果需要大量的插入和删除，而不关心随即存取，使用list
如果需要随即存取，而且关心两端数据的插入和删除，使用deque

set

集合，基于红黑树，只含有key，内部自动有序且不包含重复数据。常用函数：

inser(),find(),erase(),size(),clear()

map

基于红黑树，key-value形式

最小生成树（Kruskal算法）

发表于 2019-04-13 更新于 2019-06-02

####题目描述

输出无向连通图最小生成树权重之和。

####输入

第一行是2个整数,分别表示顶点个数n和边数m。接下来的m行中,每一行第一个整数表示边的开始顶点，第二个表示边的结束顶点，第三个表示这条边的权重。
(测试数据中保证图是连通图；
没有自环；
两个顶点之间只有一条边；
0<权重<100(可以相等)；n<=50; m<=1000；)

####输出

输出无向连通图最小生成树权重之和。

####样例输入

####样例输出

思路

利用优先队列存储边的信息，并且每次选出最短的边，注意需要重载<，定义优先级：

1	bool operator < (const edge &e) const {return dist > e.dist;}

Component数组维护每个点所在的集合信息，Comonent[i]=s表示顶点i在集合s中。Union函数判断两个点是否在同一集合中，若是，则合并失败返回false；若否，遍历Component数组，将两个顶点所在的集合改为同一个集合，返回true，这个过程复杂度为O(n)，应该可以再降吧，我没多想……然后就在主函数中遍历所有的边，把符合条件的边的长度累加就行啦。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct edge
{
	int start,end,dist;
	edge(int s = 0, int e = 0, int d = 0){
		start = s; end = e; dist = d;}
	bool operator < (const edge &e) const {
		return dist > e.dist;}//用于实现优先级的比较函数，默认是functional中的less<T>	
};
int main()
{	
	int n, m;//顶点个数n和边数m
	cin >> n >> m;
	int** a = new int*[n];
	bool* label = new bool[n];
	priority_queue<edge> q;
	for (int i = 0; i < n; i++)
	{
		label[i] = 0;
		a[i] = new int[n];
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			a[i][j] = 100;
	label[0] = true;
	int x, y, d;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y >> d;
		a[x - 1][y - 1] = d;
		a[y - 1][x - 1] = d;
		if (x == 1 || y == 1)
		{
			int k = x > y ? x : y;
			q.push(edge(0, k - 1, d));//以0为起点
		}
	}
	int res = 0; edge e;
	int v = 0;//加入的顶点数
	while (!q.empty()&&v<n-1)
	{	
		e = q.top();
		q.pop();
		if (label[e.end])continue;
		res += e.dist;
		label[e.end] = true;
		++v;
		for (int i = 0; i < n; i++){
			if (a[e.end][i] < 100&&!label[i])
				q.push(edge(e.end, i, a[e.end][i]));
		}
	}
	cout << res << endl;
	return 0;
}

C++_tips

发表于 2019-04-13 更新于 2020-02-10

<bits/stdc++.h> in C++

引入一堆的头文件会显得冗杂，有时会出现CE。<bits/stdc++.h>包含了目前c++所包含的所有头文件，只要用了这个头文件就不用再写其他头文件。但这个头文件属于gcc 的内部实现，不是标准库头文件，可能导致不可移植的问题。

Disadvantages of bits/stdc++

bits/stdc++.h is not a standard header file of GNU C++ library. So, if you try to compile your code with some compiler other than GCC it might fail; e.g. MSVC do not have this header.
Using it would include a lot of unnecessary stuff and increases compilation time.
This header file is not part of the C++ standard and is therefore, non-portable, and should be avoided.
Moreover, even if there were some catch-all header in the standard, you would want to avoid it in lieu of specific headers, since the compiler has to actually read in and parse every included header (including recursively included headers) every single time that translation unit is compiled.

Advantages of bits/stdc++

In contests, using this file is a good idea, when you want to reduce the time wasted in doing chores; especially when your rank is time sensitive.
This also reduces all the chores of writing all the necessary header files.
You don’t have to remember all the STL of GNU C++ for every function you use.

So, the user can either use it and save the time of writing every include or save the compilation time by not using it and writing necessary header files.

OJ中的常用术语

简写	全拼	中文
OJ	Online Judge	在线判题系统
AC	Accepted	通过
WA	Wrong Answer	答案错误
TLE	Time Limit Exceed	超时
OLE	Output Limit Exceed	超出输出限制
MLE	Memory Limit Exceed	超内存
RE	Runtime Error	运行时错误
PE	Presentation Error	格式错误
CE	Compile Error	无法编译

std::ios::sync_with_stdio(false)

（如果用了using namespace std;就可以去掉前面的std::）

这句话在IO之前将stdio解除绑定，这样做了之后要注意不要同时混用cin/cout和scanf，sscanf, getchar, fgets/printf之类。

在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。

#include<iostream>
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    //IO
}

取消同步的目的，是为了让cin不超时，另外cout的时候尽量少用endl，换用”\n”，也是防止超时的方法。若用scanf，printf就不用考虑这种因为缓冲的超时了。

每一次都不得不感慨——他的代码像是一件艺术品！

HTML-tips

发表于 2019-04-11 更新于 2019-04-16

Style覆盖优先级：

!important属性 > in-line style > id > class(后覆盖前)

CSS 中，可以使用 6 位十六进制数字表示颜色，每 2 位分别表示红色 (R)、绿色 (G) 和蓝色 (B) 成分。例如，#000000是黑色，也可以表示为 rgb(0, 0, 0)

script元素：

元素选择器：$("button")、class选择器：$(".btn")、id选择器：$("#target1")

<script>
  $(document).ready(function() {
	$("button").addClass("animated");
    $(".btn").addClass("shake");
    $("#target1").addClass("btn-primary");
  });    
</script>

继承:

h3继承div，div继承body

.parent() .children()

jQuery 用CSS选择器来选取元素，target:nth-child(n) CSS选择器允许你按照索引顺序(从1开始)选择目标元素的所有子元素。