Skip to main content

Hot100

4. 寻找两个正序数组的中位数​

时间复杂度 m+n 未按照题目要求

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size()+nums2.size());
        int i = 0 ,j = 0;
        while(i < nums1.size() && j < nums2.size())
        {
            if(nums1[i] < nums2[j]) 
            {
                res[i + j] = nums1[i];
                i++;
            }
            else 
            {
                res[i + j] = nums2[j];
                j++;
            }
        };
        while(i < nums1.size()) res[i + j - 1] = nums1[i++];
        while(j < nums2.size()) res[i + j - 1] = nums2[j++];


        if(res.size() % 2 == 1) return res[res.size() / 2];
        return (double)(res[res.size() / 2 - 1] + res[res.size() / 2]) / 2;
    }
};

22. 括号生成​

class Solution {
    vector<string> res;
    void backtracking(int n , string now,int left ,int right)
    {
        if (now.size() == n*2)
        {
            res.push_back(now);
            return;
        }
        if (left < n) backtracking( n ,  now +'(', left + 1 , right);
        if (right < n && (left > right)) backtracking( n ,  now +')', left  , right+1);
    }

public:
    vector<string> generateParenthesis(int n) {
        backtracking( n ,  "", 0 , 0);
        return res;
    }
};


25. K 个一组翻转链表​

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k == 1) return head;
        vector<ListNode*> res;
        ListNode* t = head;
        while(t)
        {
            res.push_back(t);
            t = t->next;
        }
        for(int i = 0; i < res.size();i += k)
        {
            if(i + k < res.size()) reverse(res.begin() + i,res.begin() + i + k);
            else if(i + k == res.size()) reverse(res.begin() + i,res.end());
        }
        if(res.size() == 1) return head;
        for(int i = 0; i < res.size() - 1;i++)
        {
            res[i]->next =  res[i + 1];
        }
        res.back()->next = nullptr;
        return res[0];
    }
};

32. 最长有效括号（巧妙方法）​

class Solution {
//    /下标计算
public:
    int longestValidParentheses(string s) {
        stack<int>stack1;
        stack1.push(-1); //定义一个栈，里面添加 -1
        int maxs = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') stack1.push(i); //遇到（ 则把该下标加入栈
            else
            {
                if (stack1.size() > 0) stack1.pop(); // 如果栈里面有元素 ， 直接弹出
                if (stack1.size() == 0) stack1.push(i); //如果栈里面无元素 ，则把下标加入
                else
                {
                    int top = stack1.top();
                    maxs = max(maxs,i - top);
                }

            }
        }
        return maxs;
    }
};

33. 搜索旋转排序数组（未完成）​

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0,right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] == nums[left]) left++;
            else if(nums[mid] <= nums[right])
            {
                if(nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
            else
            {
                if(nums[mid] > target && target >= nums[left]) right = mid - 1;
                else left = mid + 1;
            }
            
        }
        return -1;
    }
};

41. 缺失的第一个正数​

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int cur = 0;
        while(cur < nums.size())
        {
            if(nums[cur] <= 0 || nums[cur] >= nums.size() || nums[cur] == cur + 1)cur++;
            else if(nums[cur] == nums[nums[cur] - 1]) nums[cur++] = -1;
            else swap(nums[cur],nums[nums[cur] - 1]);
            //if(nums[cur] == nums[nums[cur] - 1]) nums[cur++] = -1;
        }
        cur = 0;
        while(cur < nums.size())
        {
            if(cur + 1 != nums[cur++]) return cur;
        }
        return nums.size() + 1;
    }
};

75. 颜色分类​

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int zero = 0, two = nums.size() - 1;
        for (int i = 0; i <= two; i++) {
            if (nums[i] == 0) swap(nums[zero++], nums[i]);
            else if (nums[i] == 2) swap(nums[two--], nums[i--]);
        }
    }
};


76. 最小覆盖子串​

class Solution {
public:
    string minWindow(string s, string t) {
        //设置哈希表用来存放窗口值以及进行比较的值
        unordered_map<char, int> need, win;
        //将我们所需要的值加入到哈希表（需要进行比较的值）
        for (auto &i : t) ++need[i];
        int left = 0, right = 0, count = 0, len = INT_MAX, start = 0;
        while (right < s.size()) {
            //如果我们此时字符串中的元素在我们的需要窗口中的话
            //我们就需要扩充窗口
            if (need.find(s[right]) != need.end()) {
                //此时进行扩充窗口
                ++win[s[right]];
                //运用count来进行确保我们此时的窗口值完全覆盖了我们需要的子串
                if (win[s[right]] == need[s[right]]) {
                    ++count;
                }
            }

        //如果此时的窗口值完全覆盖了我们需要的子串，就要进行缩小窗口的操作
        while (count == need.size()) {
            //这里是进行更新我们的最小子串
            if (len > right - left + 1) {
                start = left;
                len = right - left + 1;
            }
            //这里开始对窗口进行处理
            //如果此时的窗口左侧的值在我们的哈希表中的话
            //就要进行判断是否要对count进行处理
            if (need.find(s[left]) != need.end()) {
                //如果此时的窗口左侧的值在哈希表中且数量和哈希表中的数量一致
                //就对count计数位进行减一操作
                if (need[s[left]] == win[s[left]]) {
                    --count;
                }
                //将窗口左侧的值进行减一，缩小窗口
                --win[s[left]];
            }
            left++;
        }
        ++right;
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

85. 最大矩形​

每一行加起来和84题一样

class Solution {

    int largestRectangleArea(vector<int> heights) {
        stack<int> stack;
        int res = 0;
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        stack.push(0);
        for (int i = 0; i < heights.size(); ++i) {
            if (heights[i] == heights[stack.top()]) stack.pop();
            while (!stack.empty() && heights[stack.top()] > heights[i])
            {
                int mid = stack.top();
                stack.pop();
                if (stack.size()!=0)
                {
                    int h = heights[mid];
                    int w = i - stack.top() - 1;
                    res  = max(res,h * w);
                }
            }
            stack.push(i);
        }
        return res;
    }
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int row = matrix.size() , col = matrix[0].size();
        int res = 0;
        vector<int> hight(col);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '1') hight[j] += 1;
                else hight[j] = 0;
            }
            res = max(res,largestRectangleArea(hight));
        }
        return res;
    }
};

114. 二叉树展开为链表​

class Solution {
    vector<int> res;
    TreeNode* pre = NULL;
    void  pres(TreeNode* root)
    {
        if (!root) return;
        if(pre) 
        {
            pre->right = root;
            pre->left = NULL;
        }
        pre = root;
        TreeNode* ttright = root->right;
        pres(root->left);
        pres(ttright);
    }
public:
    void flatten(TreeNode* root) {
        pres(root);
    }
};

118. 杨辉三角​

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        int count = 1;
        res.push_back({1});
        while(count < numRows)
        {
            vector<int> temp(count + 1,1);
            for(int i = 1 ; i < count;i++)
            {
                temp[i] = res[count - 1][i - 1] + res[count - 1][i];
            }
            count++;
            res.push_back(temp);
        }
        return res;
    }
};

124. 二叉树中的最大路径和​

class Solution {
    int mas = -1000000;
    vector<int> find(TreeNode* root)
    {
        if (!root) return {-1000000,-1000000};

        vector<int>left = find(root->left);
        vector<int>right  = find(root->right);
        mas = max(mas,root->val+right[0]+left[0]);

        return {max(root->val, max(root->val+left[0], root->val+right[0])),
                max(left[0],max(left[1],max(right[0],right[1])))};
    }
public:
    int maxPathSum(TreeNode* root) {
        vector<int>res = find( root);
        return max(res[0],
                   max(res[1],max(res[0], max(res[1],mas))));
    }
};

152. 乘积最大子数组​

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int mins = 1 , maxs = 1, ans = INT_MIN;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < 0) swap(maxs,mins);
            mins = min(nums[i], nums[i] * mins);
            maxs = max(nums[i], nums[i] * maxs);
            ans = max(maxs,ans);
        }
        return ans;
        }
};

155. 最小栈​

class MinStack {
public:
    stack<int> data;
    stack<int> minstack;
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        data.push(x);
        if(minstack.empty() || x <= minstack.top()){
            minstack.push(x);
        }
    }
    
    void pop() {
        if(data.top() == minstack.top()){
            minstack.pop();
        }
        data.pop();
    }
    
    int top() {
        return data.top();
    }
    
    int getMin() {
        return minstack.top();
    }
};

207. 课程表​

//拓扑排序
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //定义邻接矩阵 1- >0
        vector<vector<int>> dmatrix(numCourses,vector<int>(numCourses,0));
        //定义节点入度
        vector<int> ind(numCourses,0);
        for (int i = 0; i < prerequisites.size(); ++i) {
            dmatrix[prerequisites[i][1]][prerequisites[i][0]] = 1;
            ind[prerequisites[i][0]]++;
        }

        queue<int> que;
        for (int i = 0; i < ind.size(); ++i) {
            if (ind[i] == 0) que.push(i);
        }

        while (!que.empty())
        {
            int top = que.front();
            que.pop();
            for (int i = 0; i < dmatrix.size(); ++i) {
                if (dmatrix[top][i] == 1)
                {
                    ind[i]--;
                    if (ind[i] == 0) que.push(i);
                }
            }
        }
        for (int i = 0; i < ind.size(); ++i) {
            if (ind[i]) return false;
        }
        return true;
    }
};

208. 实现 Trie (前缀树)​

class Trie {
    class dicttree
    {
    public:
        char val;
        bool isWord;
        vector<dicttree*> trees;
        dicttree()
        {
            val = 0;
            isWord = false;
            trees.resize(26);
            for (int i = 0; i < 26; ++i) {
                trees[i] = nullptr;
            }
        }
    };
    dicttree *root;
public:
    Trie() {
        root = new dicttree();
    }

    void insert(string word) {
        dicttree * cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->trees[word[i] - 'a'] == NULL)
            {
                cur->trees[word[i] - 'a'] = new dicttree();
                cur->trees[word[i] - 'a']->val = word[i];

            }
            cur = cur->trees[word[i] - 'a'];
        }
        cur->isWord = true;
    }

    bool search(string word) {
        dicttree * cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->trees[word[i] - 'a'] == NULL) return false;
            cur = cur->trees[word[i] - 'a'];
        }
        if(cur->isWord == false) return false;
        return true;
    }

    bool startsWith(string prefix) {
        dicttree * cur = root;
        for (int i = 0; i < prefix.size(); ++i) {
            if (cur->trees[prefix[i] - 'a'] == nullptr ) return false;
            cur = cur->trees[prefix[i] - 'a'];
        }
        return true;
    }
};

215. 数组中的第K个最大元素​

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>> que;
        for (int i = 0; i < nums.size(); ++i) {
            que.push(nums[i]);
            if (que.size() > nums.size()) que.pop();
        }
        while(--k) que.pop();
        return que.top();
    }
};

238. 除自身以外数组的乘积​

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        if (nums.size() == 1) return nums;
        vector<int> left(nums.begin(),nums.end());
        vector<int> right(nums.begin(),nums.end());

        //左边 + 右边
        left[0] = nums[0] , right[nums.size() - 1] = nums.back();
        for (int i = 1 ,j = nums.size() - 2; i < nums.size() && j >= 0; ++i ,j--) {
            left[i] = left[i] * left[i - 1];
            right[j] = right[j] * right[j + 1];
        }
        //两边乘积
        nums[0] = right[1];
        nums[nums.size() - 1] = left[nums.size() - 2];
        for (int i = 1; i < nums.size() - 1; ++i) {
            nums[i] = left[i- 1] * right[i+1];
        }
        return nums;
    }
};

297. 二叉树的序列化与反序列化（未完成-困难）​

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL)
            return "#_";
        string res = to_string(root->val) + "_";
        res += serialize(root->left);
        res += serialize(root->right);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        std::stringstream ss(data);
        std::string item;
        queue<string> q;
        while (std::getline(ss, item, '_'))
            {
                q.push(item);
                cout << item << " ";
            }
        return helper(q);
    }
    TreeNode* helper(queue<string>& q)
    {
        string val = q.front();
        q.pop();
        if (val == "#")
            return NULL;
        TreeNode* head = new TreeNode(stoi(val));
        head->left = helper(q);
        head->right = helper(q);
        return head;
    }
};

394. 字符串解码​

class Solution {
public:
    string decodeString(string s) {
        int start = 0 , right = 0;
        stack<int> nums;
        string chars;
        while (right < s.size())
        {
            if (s[right] >= '0' && s[right] <= '9')
            {
                start = right++;
                while (right < s.size() && s[right] >= '0' && s[right] <= '9') right++;
                nums.push(stoi(s.substr(start,right-start)));
                right--;
            } else if(s[right] == ']')
            {
                int st = chars.size() - 1;
                while (st >= 0 && chars[st] != '[') st--;
                cout << st << endl;
                chars.erase(chars.begin() + st);
                string temp(chars.begin()+st,chars.end());
                int n = nums.top();
                nums.pop();
                while (--n) chars+=temp;
            } else chars.push_back(s[right]);
            right++;
        }
        return chars;

    }
};

437. 路径总和 III​

class Solution {
public:
    int count = 0;
    int pathSum(TreeNode* root, int sum) {
        dfs(root,  sum, true);
        dfs(root,  sum, false);
        return count;
    }
    void dfs(TreeNode* root, long long sum,bool baohan) {
        if (!root) return;
        if (baohan)
        {
            if (sum == (long long)root->val) count++;
            dfs(root->left, sum - root->val,baohan);
            dfs(root->right, sum - root->val,baohan);
        } else
        {
            dfs(root->left, sum ,baohan);
            dfs(root->left, sum ,1- baohan);
            dfs(root->right, sum ,baohan);
            dfs(root->right, sum ,1-baohan);
        }
    }
};

//解法2 -- 双递归
class Solution {
public:
    int count = 0;
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        dfs(root, sum) ;
        pathSum(root->left, sum) ;
        pathSum(root->right, sum);
        return count;
    }
    void dfs(TreeNode* root, long long sum) {
        if (!root) return;
        if (sum - root->val == 0) count++;
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
    }
};

581. 最短无序连续子数组​

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int>cur(nums.begin(),nums.end());
        std::sort(cur.begin(), cur.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == cur[i]) cur[i] = 1;
            else cur[i] = 0;
            //cout << cur[i] << endl;
        }
        //找出左边0 与右边0的位置
        int posleft = -1,poseright = -1;
        for (int i = 0; i < cur.size(); ++i) {
            if (cur[i] == 0)
            {
                posleft = i;
                break;
            }
        }
        for (int i = cur.size() - 1; i >= 0 ; --i) {
            if (cur[i] == 0)
            {
                poseright = i;
                break;
            }
        }
        if (posleft == -1) return 0;
        return  poseright - posleft + 1;
    }
};

621. 任务调度器​

class Solution {
public:
    char getValue(unordered_map<char,int> &counttask,unordered_map<char,int> &used_recently,const int &n,int ii)
    {
        char res = '0';
        int maxs = 0;
        pair<char , int> par;
        for (auto x:counttask)
        {
            if(used_recently.find(x.first) == used_recently.end() || ii - used_recently[x.first] > n)
            {
                if (maxs < counttask[x.first])
                {
                    maxs = counttask[x.first];
                    par = x;
                    res = x.first;
                }
            }
        }
        if (res == '0') return res;
        used_recently[par.first] = ii;
        counttask[par.first]--;
        res = par.first;
        if (counttask[par.first] == 0) counttask.erase(par.first);
        return res;
    }

public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char,int> counttask;
        unordered_map<char,int> used_recently;
        for (char &x : tasks) counttask[x]++;
        vector<char> res;
        int i = 0;
        while (!counttask.empty())
        {
            char temp = getValue(counttask,used_recently,n,i);
            res.push_back(temp);
            i++;
        }
        return res.size();
    }
};

994. 腐烂的橘子​

class Solution {
    
public:
    int orangesRotting(vector<vector<int>>& grid) {
        vector<vector<int>> pre = grid;
        function<int(int,int)> infection = [&](int i,int j){
            if(i < 0 || i >= pre.size() || j < 0 || j >= pre[0].size()) return 0;
            if(grid[i][j] == 1)
            {
                pre[i][j] = 2;
                return 1;
            }
            return 0;
        };
        function<int(int,int)> del = [&](int i,int j){
            int count = 0;
            count +=infection(i+1,j);
            count +=infection(i-1,j);
            count +=infection(i,j+1);
            count +=infection(i,j-1);
            return count;
        };
        function<bool()> find = [&](){
            for(int i = 0; i < grid.size(); i++)
            {
                for(int j = 0; j < grid[0].size(); j++)
                {
                    if(grid[i][j] == 1) return true;
                }
            }
            return false;
        };

        int res = 0;
        while(true)
        {
            int counts = 0;
            for(int i = 0; i < grid.size(); i++)
            {
                for(int j = 0; j < grid[0].size(); j++)
                {
                    if(grid[i][j] == 2) counts += del(i,j);
                }
            }
            if(counts == 0)
            {
                bool if_t = find();
                if( if_t) return -1;
                else if(!if_t) return res;
            }
            grid = pre;
            res++;
        }
        return -1;

    }
};