力扣Hot100

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> mp;    
        for(auto i : strs)
        {
            string key = i;
            sort(key.begin(),key.end());
            mp[key].emplace_back(i);
        }
        vector<vector<string>> ans;
        for(auto it = mp.begin(); it != mp.end();it++)
        {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> sets;
        for(auto i : nums) sets.insert(i);

        int ans = 0;
        for(auto i : sets)
        {
            if(!sets.count(i-1))//是连续序列的起点
            {
                int curNum = i;
                int curAns = 1;
                while(sets.count(curNum + 1))//查找后面的元素
                {
                    curNum ++;
                    curAns ++;
                }
                ans = max(ans,curAns);
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;

        //枚举a
        for(int i = 0; i < n; i ++)
        {
            //不是第一个可选元素时才跳过，因为第一个可能构成合法组合
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int k = n - 1;
            int target = -nums[i];
            //枚举b
            for(int j = i + 1; j < n;j++){
                if(j > i + 1 && nums[j] == nums[j-1]) continue;
                while(j < k && nums[j] + nums[k] > target) k--;

                if(j == k) break;//指针相遇，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if(nums[j] + nums[k] == target)
                    ans.push_back({nums[i],nums[j],nums[k]});
            }
        }
        return ans;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n == 0) return 0;

        vector<int> leftMax(n);
        //leftMax[i]表示下标i及其左边的位置中，height的最大高度
        leftMax[0] = height[0];
        for(int i = 1; i < n; i ++) leftMax[i] = max(leftMax[i-1],height[i]);

        vector<int> rightMax(n);
        rightMax[n-1] = height[n-1];
        for(int i = n - 2; i >= 0; i --) rightMax[i] = max(rightMax[i+1],height[i]);

        int ans = 0;
        for(int i = 0; i < n; i ++)
            ans += min(leftMax[i],rightMax[i]) - height[i];

        return ans;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0,right = height.size() - 1;
        int leftMax = 0,rightMax = 0;
        while(left < right){
            //leftMax表示下标left及其左边的位置中，height的最大高度
            leftMax=  max(leftMax,height[left]);
            //rightMax表示下标right及其右边的位置中，height的最大高度
            rightMax = max(rightMax,height[right]);

            if(height[left] < height[right]){
                //leftMax < rightMax 
                ans += leftMax - height[left];
                left++;
            }
            else
            {
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;//哈希集合，记录当前窗口有哪些字符
        int n = s.size();
        //右指针初始为-1
        int rk = -1,ans = 0;
        //枚举左指针的位置
        for(int i = 0; i < n;i++)
        {
            if(i != 0) occ.erase(s[i-1]);
            while(rk + 1 < n && !occ.count(s[rk+1])){
                //不断移动右指针
                occ.insert(s[rk+1]);
                rk++;
            }
            ans = max(ans,rk - i + 1);//每次计算不重复的长度
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen = s.size(),plen = p.size();

        if(slen < plen) return vector<int>();

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);

        //先初始化前plen个字符的频次
        for(int i = 0; i < plen;i++)
        {
          sCount[s[i]-'a']++;
          pCount[p[i]-'a']++;
        }
        //s与p完全相同
        if(sCount == pCount) ans.emplace_back(0);

        for(int i = 0; i < slen - plen;i++)
        {
            sCount[s[i]-'a']--;//移出窗口左端
            sCount[s[i+plen]-'a']++;//窗口右端进入
            if(sCount == pCount) ans.emplace_back(i+1);
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for(int i = 0; i < k;i++)//先处理前k个元素，形成第一个窗口
        {   //把所有比当前元素小（或相等）的尾部下标移除
            while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
        }// 此时队头就是第一个窗口最大值的下标
        vector<int> ans = {nums[q.front()]};
        for(int i = k; i < n;i++)//继续处理后面的元素 i = k ... n-1
        {   //插入新元素之前，清理掉尾部不可能再用的
            while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            //窗口现在是[i-k+1,i],如果队头已经出界就弹掉
            while(q.front() <= i - k) q.pop_front();
            ans.push_back(nums[q.front()]);//队头就是当前窗口最大值
        }
        return ans;        
    }
};

class Solution {
public:
    unordered_map<char,int> ori,cnt;//cnt当前窗口各字符出现次数

    bool check(){//判断当前窗口是否已经覆盖t
        for(const auto &p : ori) 
            if(cnt[p.first] < p.second) return false;
        return true;
    }
    string minWindow(string s, string t) {
        for(const auto &c:t) ori[c]++;//字符串t中每个字符出现次数(目标)

        int l = 0, r = -1;
        int len = INT_MAX,ansL = -1, ansR = -1;//最优的窗口左右边界
        //len记录目前找到的最短合法窗口长度
        while(r < int(s.size())){
            if(ori.find(s[++r]) != ori.end()) cnt[s[r]]++;

            while(check() && l <= r)//如果满足条件，尝试缩短窗口
            {
                if(r - l + 1 < len){
                    len = r - l + 1;
                    ansL = l;
                }
                if(ori.find(s[l]) != ori.end()) cnt[s[l]]--;//如果是目标字符，更新出现次数
                l++;
            } 
        }
        return ansL == -1?string():s.substr(ansL,len);//从ansl起，取长度为len的子串
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> answer(length);

        //answer[i]表示索引左侧所有元素的乘积
        answer[0] = 1;
        for(int i = 1;i < length;i++) answer[i] = nums[i-1] * answer[i-1];

        //R为右侧所有元素的乘积
        int R = 1;
        for(int i = length-1;i >= 0; i --)
        {
            answer[i] = answer[i] * R;
            R *= nums[i];
        }
        return answer;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int &i : nums){
            if(i <= 0) i = n + 1;
        }

        for(int i = 0; i < n;  i++)
        {
            int num = abs(nums[i]);
            if(num <= n)//进行标记
                nums[num-1] = -abs(nums[num-1]);//变成负数
        }
        for(int i = 0;i < n; i ++)
        {
            if(nums[i] > 0) return i + 1;
        }
        return n + 1;//1-n的正数全部出现
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<int> row,col;//行、列
        int m = matrix.size(),n = matrix[0].size();
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j++)
            {
                if(matrix[i][j] == 0)
                {
                    row.emplace(i);
                    col.emplace(j);
                }
            }
        for(int i = 0; i < m; i ++)
        {
            for(int j = 0; j < n; j++)
            {
                if(row.find(i) != row.end()|| col.find(j) != col.end()) matrix[i][j] = 0;
                else {}
                cout << matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

class Solution {
private:
    //右下左上
    static constexpr int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }
        int rows = matrix.size(), columns = matrix[0].size();//行、列
        vector<vector<bool>> visited(rows, vector<bool>(columns));
        int total = rows * columns;
        vector<int> order(total);//答案数组

        int row = 0, column = 0;
        int dirId = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + dir[dirId][0], nextColumn = column + dir[dirId][1];//下一步的坐标
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                dirId = (dirId + 1) % 4;
            }
            row += dir[dirId][0];
            column += dir[dirId][1];
        }
        return order;
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        for(int i = 0; i < n / 2; i ++)
            for(int j = 0; j < (n + 1) / 2;j++)
            {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = tmp;
            }
    }
};

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();
        for(int i = 0; i < length; i ++) last[s[i] - 'a'] = i;//记录每个字母出现的下标

        vector<int> partition;
        int start = 0,end = 0;
        for(int i = 0; i < length;i++){
            end = max(end,last[s[i]-'a']);
            if(i == end){
                partition.push_back(end-start+1);
                start = end + 1;
            }
        }
        return partition;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;
        ListNode *temp = headA;
        while(temp != NULL){
            visited.insert(temp);
            temp = temp->next;
        }
        temp = headB;
        while(temp != NULL){
            if(visited.count(temp)) return temp;
            temp = temp->next;
        }
        return NULL;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;// 反转后链表的头，一开始为空
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;// 1. 保存下一个节点
            cur->next = prev;//2. 进行翻转
            prev = cur;//3. 将头节点前进
            cur = next;//4. 下一个节点
        }
        return prev;
    }
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;

        // 1. 快慢指针找中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 此时 slow 在“前半段的末尾”：
        // n 为偶数：slow 在左中点
        // n 为奇数：slow 在真正中点的位置（下一步反转从 slow->next 开始）

        // 2. 反转后半部分
        ListNode* second = reverseList(slow->next);

        // 3. 比较前半部分和反转后的后半部分
        ListNode* p1 = head;
        ListNode* p2 = second;
        bool res = true;
        while (p2) {
            if (p1->val != p2->val) {
                res = false;
                break;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return res;
    }

    ListNode* reverseList(ListNode* head) {//返回头节点
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while(head != NULL){
            if(seen.count(head)) return true;
            seen.insert(head);
            head = head->next;
        } 
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while(head != NULL)
        {
            if(seen.count(head)) return head;
            seen.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

class Solution {
public:     //output是待排列数组
    void backtrack(vector<vector<int>>& res,vector<int>& output,int first,int len)
    {//len数组长度，first当前填充位置
        if(first == len){
            res.emplace_back(output);
            return;
        }
        for(int i = first;i < len;i++){//按位置考虑
            swap(output[i],output[first]);
            backtrack(res,output,first+1,len);
            swap(output[i],output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        backtrack(res,nums,0,(int)nums.size());
        return res;
    }
};

class Solution {
public:
    vector<vector<string>> res;  // 存所有解
    vector<string> board;        // 当前棋盘
    vector<bool> col, dg, udg;   // 列、主对角线、副对角线
    int n;

    void dfs(int r) {//当前考虑到了第几行
        if (r == n) {
            res.push_back(board); // 保存当前解
            return;
        }
        for (int i = 0; i < n; i++) {//考虑列的填充(r行i列)
            if (!col[i] && !dg[r + i] && !udg[i - r + n]) {//当前位置能填的话
                col[i] = dg[r + i] = udg[i - r + n] = true;
                board[r][i] = 'Q';
                dfs(r + 1);
                board[r][i] = '.';
                col[i] = dg[r + i] = udg[i - r + n] = false;
            }
        }
    }

    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        res.clear();
        board = vector<string>(n, string(n, '.'));
        col.assign(n, false);
        dg.assign(2 * n, false);//对角线
        udg.assign(2 * n, false);
        dfs(0);
        return res;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0,n = nums.size(),end = 0,step = 0;
        for(int i = 0;i < n - 1;i++)
        {
            if(i <= maxPos)
            {   //maxPos是当前能够最远到达的距离
                maxPos = max(maxPos,i + nums[i]);
                if(i == end){//end是当前这一步能够到达的边界
                    end = maxPos;
                    step++;
                }
            }
        }
        return step;
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;

        int size = nums.size();
        if(size == 1) return nums[0];

        vector<int> dp = vector<int> (size,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2; i < size;i++)
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
        return dp[size-1];
        
    }
};