408算法题leetcode--第38天

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;}
};