155. 最小栈
题目地址:155. 最小栈 - 力扣(LeetCode)
题解思路:两个栈,一个存数据,另一个存最小值
时间复杂度:O(1)
空间复杂度:O(n)
代码:
class MinStack {
public:stack<int>stk;stack<int>min_stk;MinStack() {// 两个栈,一个栈存最小值min_stk.push(INT_MAX);}void push(int val) {stk.push(val);min_stk.push(min(min_stk.top(), val));}void pop() {stk.pop();min_stk.pop();}int top() {return stk.top();}int getMin() {return min_stk.top();}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/
461. 汉明距离
题目地址:461. 汉明距离 - 力扣(LeetCode)
题解思路:模拟题
时间复杂度:O(log(2^31))
空间复杂度:O(1)
代码:
class Solution {
public:int hammingDistance(int x, int y) {// z = x ^ y,检查z的每一位,如果是1就++int ret = 0, z = x ^ y;while(z){ret += z & 1;z >>= 1;}return ret;}
};
448. 找到所有数组中消失的数字
题目地址:448. 找到所有数组中消失的数字 - 力扣(LeetCode)
题解思路:常见模拟
时间复杂度:O(n)
空间复杂度:O(1)
代码:
class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {// 遍历nums,如4,就在下标为4的位置取负数// 第二次遍历nums,如果值为正数,则加入retint size = nums.size();vector<int>ret;for(auto& i : nums){int id = abs(i);nums[id - 1] = -abs(nums[id - 1]);}for(int i = 0; i < size; i++){//cout << nums[i] << ' ';if(nums[i] > 0){ret.push_back(i + 1);}}return ret;}
};