感觉智商受到了侮辱… 用hash来做，上来就是map。结果复杂不说，还四处报错。
根据题意，可以确定最大的数组范围。
然后可以直接遍历整个数组来找最大值，同时得到的结果也是从小到大的序号。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10010;
int s[N], n;
int main()
{
cin >> n;
int x;
while(n--)
{
cin >> x;
s[x]++;
}
int res=0;
for(int i=1; i<N; i++)
{
if(s[res]<s[i])
res=i;
}
cout << res << endl;
return 0;
}
DP
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size(); // text是从0开始
vector<vector<int>> f(n+1, vector<int>(m+1)); // 状态我们从1开始
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
// 由于i不存在，j不存在，包含在f[i-1][j]和f[i][j-1]中，但我们求最大值，所以可以忽略，直接求max就行了
f[i][j] = max(f[i-1][j], f[i][j-1]); // i不存在，j存在 。 和 i存在， j不存在的情况
if(text1[i-1] == text2[j-1]){ // 若当前i和j均存在，则在子序列里， 所以就看f[i-1][j-1] 加上本身 1
f[i][j] = max(f[i][j], f[i-1][j-1]+1);
}
}
}
return f[n][m];
}
};
快速幂运算的拓展。
#include<iostream>
using namespace std;
typedef long long ll;
ll calcuate(ll a, ll b, ll p)
{
ll res=0;
while(b)
{
if(b & 1)
res = (res + a) % p;
a = (a*2) % p;
b >>= 1;
}
return res % p;
}
int main()
{
ll a, b, p;
cin >> a >> b >> p;
ll res = calcuate(a, b, p);
cout << res << endl;
return 0;
}
1、取二进制n中的第k位： n >> k & 1
2、二进制转10进制。 原始值左移一位，并加上当前位数。
class Solution {
public:
uint32_t reverseBits(uint32_t n) { // 最高位向左移，最后得到的就是十进制。 即 res << 1. 取n中第k位 即为 n>>k & 1
uint32_t res = 0;
for(int i = 0; i<32; i++) // 翻转后，高位从0开始
res = (res << 1) + (n >> i & 1);
return res;
}
};
CV， ORL
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55; //矩阵边长
int n, m;
int h[N][N]; // 高度
int dist[N][N]; // dijstra 需要一个全局的dist
bool st[N][N]; // 判常数组
struct Node{ // 矩阵中每个点的值
int x, y, d; //坐标 和 值
// 堆里面需要所有元素进行排序
bool operator < (const Node& t) const{
return d > t.d; // 堆默认是大根堆，这题最短路，变成小根堆。所以 >
}
};
int main()
{
int T;
cin >> T; // 测试数据数量
for(int C=1; C<=T; C++) // 每个测试数据
{
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin >> h[i][j]; //每个元素的高度
// 初始化
memset(dist, 0x3f, sizeof dist); // 因为求最短路，所以先初始化为正无穷
memset(st, 0, sizeof st);
priority_queue<Node> heap;
// 把周围一圈的点加入堆里
for(int i=1; i<=n; i++)
{
heap.push({i, 1, h[i][1]}); // 先最左侧，高度为h[i][1]
dist[i][1] = h[i][1];
heap.push({i, m, h[i][m]}); // 最右侧加进来
dist[i][m] = h[i][m];
}
for(int i=2; i<m; i++) // 上下两行加进来
{
heap.push({1, i, h[1][i]});
dist[1][i] = h[1][i];
heap.push({n, i, h[n][i]});
dist[n][i] = h[n][i];
}
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int res = 0; //记录最终的储水量
while(heap.size()) //堆不空
{
auto t = heap.top();
heap.pop();
if(st[t.x][t.y]) continue; // 若该点搜过了就继续
st[t.x][t.y] = true; // 标记为它已经更新过其它点了
res += t.d - h[t.x][t.y]; // 格子的最终高度 - 其初始身的高度 即为 该格子储水量
// 枚举当前点的临边，去更新四条临边
for(int i=0; i<4; i++)
{
int x = t.x + dx[i], y=t.y + dy[i];
if(x >= 1 && x <=n && y>=1 && y<=m)
{
if(dist[x][y] > max(t.d, h[x][y])) // 如果能更新这四条临边
{
dist[x][y] = max(t.d, h[x][y]);
heap.push({x, y, dist[x][y]});
}
}
}
}
printf("Case #%d: %d\n", C, res);
}
return 0;
}
对于每个位置i，去判断它左边的最大值是多少，然后再判断它右边的最大值是多少。 然后取两者最小的一个，即为最终高度。最后该位置i的储水量，即为最终高度 减去 它本身的高度。
所以做法：
1、从左向右遍历，求出每个位置的左边最高高度left[i]. 即left为最高高度， 所以求left[i-1]与当前位置高度height[i]比较即可。
2、同理，从右向左求得每个位置的最高高度right[i]。
3、答案即为 res+= min(left[i], right[i]) - height[i]
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty())
return 0;
int n = height.size();
vector<int> left(n), right(n);
left[0] = height[0];
right[n-1] = height[n-1];
for(int i=1; i<n; i++)
left[i] = max(left[i-1], height[i]);
for(int i=n-2; i>=0; i--)
right[i] = max(right[i+1], height[i]);
int res = 0;
for(int i=0; i<n; i++)
{
res += min(left[i], right[i]) - height[i];
}
return res;
}
};
寒假做过的呀 QAQ ，还是不会，而且忘了做过。。
找非0，首先把0给找完，即对每个因子分解为 2^a、 5^b、 其他部分_1。
对其他部分_1计算非0的数字。
最后k=min(a, b)； 再让其他部分将剩下的2或者5进行累乘，继续算非0数字，即得到正确结果
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int main()
{
cin >> n;
int a=0, b=0, res=1; // res从1开始即阶乘从1开始乘
for(int i=1; i<=n; i++) // 阶乘是从1开始乘的
{
int x = i; // 将每个因子都分解为2^a * 5^b * 其他部分
while(x%2==0) // 因子分解为对应2的个数
{
x/=2;
a++;
}
while(x%5==0) // 2分解完后剩余式子分解为5的个数
{
x/=5;
b++;
}
// 其他部分即为非0部分，需要一直累乘即为阶乘。 且我们需要记录最右侧的非0数字，则%10即可得到非0。
res = (res * x) % 10;
}
// 由于a, b不一定相等，所以最后一定会存在一个多出来的，需要进一步乘，并得到最后一位的数字
int k = min(a, b);
for(int i=0; i<a-k; i++)
res = (res * 2) % 10;
for(int i=0; i<b-k; i++)
res = (res * 5) % 10;
cout << res << endl;
return 0;
}
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
// 由题意可知，右上角的值x为突破口
// 若 x > target，则x所在列均不满足要求，即往前面一列找。
// 若 x < target，则x所在行均不满足要求，即往下面一行找。
// 若 x = target，则返回 true
if(array.empty() || array[0].empty()) return false;
int i = 0, j = array[0].size() - 1;
while(i<array.size() && j>=0)
{
int x = array[i][j];
if(x == target) return true;
else if(x > target) j--;
else i++;
}
return false;
}
};
直接遍历。
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
for(int i=0; i<array.size(); i++)
{
for(int j=0; j<array[i].size(); j++)
{
if(array[i][j] == target)
{
return true;
}
}
}
return false;
}
};
分成两步，先翻转整个的字符串，再单独翻转每个单词。
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end()); // 先翻转整个字符串
for(int i=0; i<s.size(); i++)
{
int j = i+1;
while(j<s.size() && s[j] != ' ') j++; // j为从单词头到单位尾的空格位置
reverse(s.begin() + i, s.begin() + j); // 翻转单个单词。 注意是s.begin() + j
i = j; // 每翻转完后， 换下个单词
}
return s;
}
};
