牛客 HJ30 字符串合并处理
- 注意此题取了最低一位
tmp & 1之后要将这个类型立即转换为int类型，否则无法计算移位或者乘法
using namespace std;
int main() {
string a, b;
cin>>a>>b;
string s = a+b;
string even, odd;
for(int i = 0; i<s.size(); ++i)
{
if(i%2 == 0)
{
even+=s[i];
}
else
{
odd+=s[i];
}
}
sort(even.begin(), even.end());
sort(odd.begin(), odd.end());
vector<char> num2char = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
string ans;
for(int i = 0; i<s.size(); ++i)
{
if(i%2 == 0)ans+=even[i/2];
else ans+=odd[i/2];
}
for(int i = 0; i<ans.size(); ++i)
{
if('0'<= ans[i] && ans[i] <='9')
{
unsigned int tmp = ans[i]-'0';
int a = int(tmp&1)*8;
unsigned int converted = int(tmp&1)*8+int((tmp/2)&1)*4+int((tmp/4)&1)*2+int((tmp/8)&1);
ans[i] = num2char[converted];
}
else if('a'<= ans[i] && ans[i] <='f')
{
unsigned int tmp = ans[i]-'a'+10;
int a = int((tmp/2)&1)*8;
unsigned int converted = int(tmp&1)*8+int((tmp/2)&1)*4+int((tmp/4)&1)*2+int((tmp/8)&1);
ans[i] = num2char[converted];
}
else if('A'<= ans[i] && ans[i] <='F')
{
unsigned int tmp = ans[i]-'A'+10;
unsigned int converted = int(tmp&1)*8+int((tmp/2)&1)*4+int((tmp/4)&1)*2+int((tmp/8)&1);
ans[i] = num2char[converted];
}
}
cout<<ans;
}leetcode 318. 最大单词长度乘积
- 此题主要是将26个字母映射为26个位，用位运算的形式寻找是否存在重复字母
class Solution {
public:
int maxProduct(vector<string>& words)
{
vector<int> flags(words.size(), 0);
for(int i = 0; i<words.size(); i++)
{
for(auto j = words[i].begin(); j!=words[i].end(); j++)
{
flags[i] |= 1<<int(*j-'a');
}
}
int maxVal = 0;
for(int i = 0; i<words.size()-1; i++)
{
for(int j = i+1; j<words.size(); j++)
{
if((flags[i]&flags[j]) == 0)
maxVal = max(maxVal, int(words[i].size()*words[j].size()));
}
}
return maxVal;
}
};
leetcode 11.接最多水的容器
- 双指针法，左边一个右边一个，先左边在最左边，右边在最右边
- 然后两个指针靠近，选择下一个高度较高的往里挪
- 每一步的时候都计算承载量，取每一步的最大值
class Solution {
public:
int maxArea(vector<int>& height) {
int maxVal = 0;
int left = 0, right = height.size()-1;
int tempVal = min(height[left], height[right])*(right-left);
while(left!=right)
{
tempVal = min(height[left], height[right])*(right-left);
maxVal = maxVal>tempVal?maxVal: tempVal;
if(height[left]<=height[right])left++;
else right--;
}
return maxVal;
}
};
leetcode 42.接雨水
遍历求双侧的最大值
- 这种方式先从左往右遍历一次，再从右往左遍历一次，存储下每个位置左侧和右侧比自己大的元素的位置，然后横向计算矩形的面积。
class Solution {
public:
int trap(vector<int>& height) {
int leftMax = 0, templ = 0, rightMax = 0, tempr = 0;
vector<int> leftMap(height.size(), 0), rightMap(height.size(), 0);
for(int i = 0; i<height.size(); i++)
{
leftMax = max(leftMax, height[i]);
rightMax = max(rightMax, height[height.size()-i-1]);
leftMap[i] = leftMax;
rightMap[height.size()-1-i] = rightMax;
}
int sumW = 0;
for(int i = 1; i<height.size()-1; i++)
{
sumW+=max(0, min(leftMap[i-1], rightMap[i+1]) - height[i]);
}
return sumW;
}
};
单调栈
- 使用单调栈找每个位置右侧比自己大的第一个值（因为左侧比自己大的第一个值是自己下面的一个值）
- 找到之后，意味着这个位置必然出现了凹陷部位（因为左侧和右侧都存在一个元素比自己大）
- 然后找这个凹陷部位左侧的墙在哪里，实际上就是栈中顶上元素的下一个元素，找到之后将这个元素与此时要插入栈的元素取最小值，与当前栈顶元素做差得到高度，同时计算出当前元素和左侧的墙之间（不包括墙）的宽度，二者相乘得到水的面积
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
while (!st.empty() && height[i] > height[st.top()]) {
int mid = st.top();
st.pop();
if (!st.empty()) {
int h = min(height[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1;
sum += h * w;
}
}
st.push(i);
}
return sum;
}
};
Leetcode 84. 柱状图中最大的矩形
- 这题的解决思路与上一题几乎相同
- 用的栈是一个递增栈
- 用来找比当前元素小的第一个元素
- 然后找比这个元素小的左侧第一个（也就是栈中它下面那个）
- 以上条件的隐含意思是在当前元素和比当前元素小的左侧第一个元素之间的所有元素的最小值（之一）就是栈顶元素，因此用栈顶元素的高度乘这个宽度即可得到面积，实际上栈顶元素是最小元素
- 然后用宽度和栈顶元素的高度算面积
// 版本一
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
// 第一个元素已经入栈，从下标1开始
for (int i = 1; i < heights.size(); i++) {
if (heights[i] > heights[st.top()]) { // 情况一
st.push(i);
} else if (heights[i] == heights[st.top()]) { // 情况二
st.pop(); // 这个可以加，可以不加，效果一样，思路不同
st.push(i);
} else { // 情况三
while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是while
int mid = st.top();
st.pop();
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = max(result, w * h);
}
}
st.push(i);
}
}
return result;
}
};
leetcode 239.滑动窗口最大值
- 用优先级队列解决即可
- 先把窗口内部的所有元素压入队列，然后每次前进窗口的时候将队列所有已经在窗口外（窗口结束坐标之前）的元素弹出，然后队列中队头的元素就是此时最大的值
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int, int>> q;
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first};
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};使用单调队列的方式
pop(value)：如果窗口移除的元素value等于单调队列的出口（队头）元素，那么队列弹出元素，否则不用任何操作push(value)：如果push的元素value大于入口（队尾）元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止- 滑动窗口每往前一步就弹出不在窗口内的元素
- 再加入最后面的元素
- 把此时队尾头元素加入答案序列中
class Solution {
private:
class MyQueue { //单调队列（从大到小）
public:
deque<int> que; // 使用deque来实现单调队列
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
que.push(nums[i]);
}
result.push_back(que.front()); // result 记录前k的元素的最大值
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};
leetcode 48. 旋转图像
- 使用临时变量储存，将矩阵旋转中的四个位置变量依次交换
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j];
// 存一个变量然后旋转
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
};