京东移动端笔试（8.12）

1、不动点

数组中元素个数和元素值相等的元素，如[1,2,2]中1、2都是不动点。求不动点数目。

哈希表即可。

2、回文字符串

对一个字符串（全是小写字母）你可以做：

1. 将字符串的首字母移动到该字符串末尾
2. 随意修改一个字母变为任意小写字母

每次操作都可以任选上述两种之一，求将一个字符串变成回文字符串的最小操作数。

假设操作1的次数为i，则字符串变成str[i+1]str[i+2]...str[0]str[1]..str[i]，这时只需统计该字符串中对应不相等的字符数即可知道操作2的数量，操作1和操作2相加即得到操作数。遍历i，去最小值即可。

int foo(string str){
  auto fun = [&](int x){
	int ans = x;
	int i = 0, j = 2*x;
	while (i <= j)
	  ans += str[i++] != str[j--];
	i = 2*x + 1, j = (int)str.size() - 1;
	while (i <= j)
	  ans += str[i++] != str[j--];
	return ans;
  };
  int ans = INT_MAX;
  for (int i = 0; 2*i < str.size(); i++){
	ans = min(ans, fun(i));
  }
  return ans;
}

3、统计正方形数

一个n*m的棋盘，'X'表示有棋子，'.'表示没有棋子，统计四个棋子：(x1,y1),(x2,y2),(x3,y3),(x4,y4)之间围成的形状是正方形的数目。只要有一颗棋子坐标不同，则是不同的组合。

根据数学知识若知道正方形的两个点，则可以确定另外两个点，已知A(x1,y1),B(x2,y2)，不妨正方形由假设AB顺时针旋转得到，则可以知道：

x3 = x1 - (y1 - y2), y3 = y1 + (x1 - x2), x4 = x2 - (y1 - y2), y4 = y2 + (x1 - x2)。

这是即可遍历两个点，利用哈希表去判断另外两个点是否存在，这里会重复计数所以最后结果要除以2。

int main(void){
	int n, m;
  	cin >> n >> m;
  	getchar();
  	char tmp;
  	vector<points<int, int>> points;
  	set<pair<int, int>> st;
  	for (int i = 0; i < n; i++){
	  for (int j = 0; j < m; j++){
		cin >> tmp;
		if (tmp == 'X'){
		  st.insert({i, j});
		  points.emplace_back(i, j);
		}
	  }
	  getchar()
	}
  	int ans = 0;
  	for (int i = 0; i < points.size(); i++){
	  for (int j = i+1; j < points.size(); j++){
		int x1 = points[i].first, x2 = points[j].first;
		int y1 = points[i].second, y2 = points[j].second;
		ans += st.count({x1-(y1-y2), y1+(x1-x2)}) && st.count({x2-(y1-y2), y2+(x1-x2)});
	  }
	}
  	cout << ans/2 << endl;
  	return 0;
}