当前位置：首页 > news >正文

C/C++每日一练(20230310)

news 2025/9/13 4:21:50

1. 用栈实现队列 ★★

2. 单词搜索 II ★★★

3. 直线上最多的点数 ★★★

1. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释： 
MyQueue myQueue = new MyQueue(); 
myQueue.push(1); // queue is: [1] 
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) 
myQueue.peek(); // return 1 
myQueue.pop(); // return 1, queue is [2] 
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

代码：

#include <bits/stdc++.h>
using namespace std;class MyQueue
{
public:/** Initialize your data structure here. */stack<int> a, b;MyQueue(){}/** Push element x to the back of queue. */void push(int x){while (!b.empty()){a.push(b.top());b.pop();}b.push(x);while (!a.empty()){b.push(a.top());a.pop();}}/** Removes the element from in front of queue and returns that element. */int pop(){int res = b.top();b.pop();return res;}/** Get the front element. */int peek(){return b.top();}/** Returns whether the queue is empty. */bool empty(){return b.empty();}
};int main()
{MyQueue myQueue = MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) cout << myQueue.peek() << endl; // return 1 cout << myQueue.pop() << endl; // return 1, queue is [2] myQueue.empty(); // return falsereturn 0;
}

输出：

1
1

2. 单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:struct Node{bool isflag = false;Node *next[27] = {};};set<string> res;vector<string> ans;Node *root;vector<int> dirx{0, 0, 1, -1};vector<int> diry{1, -1, 0, 0};bool flag;void createtree(vector<string> &words){root = new Node();for (auto w : words){Node *p = root;for (int i = 0; i < w.length(); i++){if (p->next[w[i] - 'a'] == NULL){p->next[w[i] - 'a'] = new Node();}p = p->next[w[i] - 'a'];}p->isflag = true;}}void backtrack(vector<vector<char>> &board, vector<vector<bool>> visited, int row, int col, Node *roott, string cur){cur += board[row][col];roott = roott->next[board[row][col] - 'a'];if (!roott)return;if (roott->isflag == true){res.insert(cur);flag = true;}visited[row][col] = true;for (int i = 0; i < 4; i++){int nx = row + dirx[i];int ny = col + diry[i];if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size())continue;if (visited[nx][ny] == false){backtrack(board, visited, nx, ny, roott, cur);}}}vector<string> findWords(vector<vector<char>> &board, vector<string> &words){if (board.size() == 0 || words.size() == 0)return ans;createtree(words);for (int i = 0; i < board.size(); i++){for (int j = 0; j < board[i].size(); j++){Node *p = root;flag = false;if (p->next[board[i][j] - 'a']){vector<vector<bool>> visited{board.size(), vector<bool>(board[0].size(), false)};backtrack(board, visited, i, j, p, "");}}}set<string>::iterator it;for (it = res.begin(); it != res.end(); it++)ans.push_back(*it);return ans;}
};int main()
{Solution s;vector<vector<char>> board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};vector<string> words = {"oath","pea","eat","rain"};for (auto str: s.findWords(board, words))cout << str << " ";cout << endl;return 0;
}

输出：

eat oath

3. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

1 <= points.length <= 300
points[i].length == 2
-10^4 <= xi, yi <= 10^4
points 中的所有点 互不相同

代码：

#include <bits/stdc++.h>
using namespace std;
struct Point
{int x;int y;Point() : x(0), y(0) {}Point(int a, int b) : x(a), y(b) {}
};
class Solution
{
public:int maxPoints(vector<Point> &points){int ans = 0;for (int i = 0; i < points.size(); ++i){map<pair<int, int>, int> m;int p = 1;for (int j = i + 1; j < points.size(); ++j){if (points[i].x == points[j].x && (points[i].y == points[j].y)){++p;continue;}int dx = points[j].x - points[i].x;int dy = points[j].y - points[i].y;int d = gcd(dx, dy);++m[{dx / d, dy / d}];}ans = max(ans, p);for (auto it = m.begin(); it != m.end(); ++it){ans = max(ans, it->second + p);}}return ans;}int gcd(int a, int b){return (b == 0) ? a : gcd(b, a % b);}
};int main()
{Solution s;vector<Point> points = {{1,1},{2,2},{3,3}};cout << s.maxPoints(points) << endl;points = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};cout << s.maxPoints(points) << endl;return 0;
}

输出：

3
4