面试题09. 用两个栈实现队列
- Used for test inserting images and codes.
class CQueue {
public:
stack Astack, Bstack;
int size = 0;
CQueue() {
}
void appendTail(int value) {
Astack.push(value);
size += 1;
}
int deleteHead() {
if(size == 0)
return -1;
while(!Astack.empty()) {
Bstack.push(Astack.top());
Astack.pop();
}
int ans = Bstack.top();
Bstack.pop();
while(!Bstack.empty()){
Astack.push(Bstack.top());
Bstack.pop();
}
size -= 1;
return ans;
}
}
2020.3.19 每日一题
class Solution {
public:
map counter;
int res = 0;
int longestPalindrome(string s) {
for(int i = 0; i < s.size(); ++i) {
if(counter.find(s.at(i)) == counter.end()) {
counter.insert(map::value_type(s.at(i), 1));
}else {
counter[s.at(i)] += 1;
}
}
for(auto iter = counter.begin(); iter != counter.end(); ++iter){
if(iter->second % 2 == 1)
res += 1;
}
return res == 0 ? s.size(): s.size() - res + 1 ;
}
};
面试题10-I. 斐波那契数列
class Solution {
public:
int res[110];
int mod = 1e9+7;
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
res[1] = 1;
for(int i = 2; i <= n; ++i) {
res[i] = (res[i-1] + res[i-2]) % mod;
}
return res[n];
}
};
面试题16. 数值的整数次方(快速幂)
class Solution {
public:
double ans = 1, exponent = 1;
double myPow(double x, int n) {
exponent = x;
int sgnn = n;
// note: 快速幂可以直接考虑指数为负数的情况,但是为负数时不能用移位运算。
for(; sgnn; sgnn /= 2) {
if(sgnn & 1){
ans = ans * exponent;
}
exponent *= exponent;
}
return n > 0? ans: 1/ ans;
}
};
面试题12. 矩阵中的路径
class Solution {
private:
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};
public:
bool search(pair start, set> &record,vector> board, string word, int row, int col, int depth) {
if(depth == word.size()) return true;
for(int i = 0; i < 4; ++i) {
int new_x = start.first + dir_x[i];
int new_y = start.second + dir_y[i];
if(record.find(make_pair(new_x, new_y)) == record.end() && new_x >= 0 && new_y >= 0 && new_x < row && new_y < col && board.at(new_x).at(new_y) == word.at(depth)) {
record.insert(make_pair(new_x, new_y));
if(search(make_pair(new_x, new_y), record, board, word, row, col, depth+1))
return true;
record.erase(make_pair(new_x, new_y));
}
}
return false;
}
bool exist(vector>& board, string word) {
if(board.size() == 0) return false;
int row = board.size(), col = board.at(0).size();
for(int i = 0; i < row; ++i) {
for(int j = 0; j < col; ++j) {
if(board.at(i).at(j) == word.at(0)) {
set> record;
record.insert(make_pair(i, j));
if(search(make_pair(i, j), record, board, word, row, col, 1))
return true;
}
}
}
return false;
}
};