包含min函数的栈
描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
class Solution {
public:
stack<int> s1; //栈的push和 pop
stack<int> s2; //用于存储最小的min
void push(int value) {
s1.push(value);
if(s2.empty() || s2.top() > value)
s2.push(value);
else
s2.push(s2.top());
}
void pop() {
s1.pop();
s2.pop();
}
int top() {
return s1.top();
}
int min() {
return s2.top();
}
};
数组中出现次数超过一半的数字
描述
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
思路： 哈希表
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
unordered_map<int, int> haxi;
for(int i=0; i< numbers.size(); i++){
haxi[numbers[i]] += 1;
}
for(int i=0; i<numbers.size(); i++)
{
if(haxi[numbers[i]] > numbers.size()/2)
return numbers[i];
}
return -1;
}
};
进制转换
十进制换其他进制
描述
给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。
当 N 大于 10 以后， 应在结果中使用大写字母表示大于 10 的一位，如 ‘A’ 表示此位为 10 ， ‘B’ 表示此位为 11 。
若 M 为负数，应在结果中保留负号。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 进制转换
* @param M int整型 给定整数
* @param N int整型 转换到的进制
* @return string字符串
*/
string s = "0123456789ABCDEF";
string solve(int M, int N) {
// write code here
if(M == 0)
return "0";
string res = "";
bool flag = false; //正负标记
if(M < 0){
flag = true;
M = abs(M);
}
while(M){
res = s[M%N] + res;
M /= N;
}
if(flag)
res = "-" + res;
return res;
}
};
判断一个链表是否为回文结构
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
涉及知识点：
- vector 反转
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
bool isPail(ListNode* head) {
// write code here
vector<int> nums;
while(head != NULL){
nums.push_back(head->val);
head = head->next;
}
vector<int> rev = nums;
reverse(rev.begin(), rev.end());
for(int i=0; i<nums.size(); i++){
if(nums[i] != rev[i])
return false;
}
return true;
}
};
不同路径的数目(一)
描述
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？
备注：m和n小于等于100,并保证计算结果在int范围内
递归、动态规划
class Solution {
public:
/**
*
* @param m int整型
* @param n int整型
* @return int整型
*/
//递归
int uniquePaths1(int m, int n) {
// write code here
if( m ==1 || n ==1)//矩阵只要有一条边为1，路径数就只有一种了
return 1;
return uniquePaths1(m-1, n) + uniquePaths1(m, n-1);//两个分支
}
int uniquePaths(int m, int n) {
// write code here
//dp[i][j]表示大小为i*j的矩阵的路径数量
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));//dp定义，初始化为0
for(int i=1; i <= m; i++){
for(int j=1; j<=n; j++){
//只有1行的时候，只有一种路径
if(i == 1){
dp[i][j] = 1;
continue;
}
//只有1列的时候，只有一种路径
if(j == 1){
dp[i][j] = 1;
continue;
}
//路径数等于左方格子的路径数加上上方格子的路径数
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}