从0开始的Leetcode生活

123456int age = 20;
long long total = 10000000000LL;
double score = 95.5;
bool passed = true;
char letter = 'A';
string name = "Kirawii";

1234567if (x > 0) {
    cout << "positive" << endl;
} else if (x == 0) {
    cout << "zero" << endl;
} else {
    cout << "negative" << endl;
}

123for (int i = 0; i < nums.size(); i++) {
    cout << i << " " << nums[i] << endl;
}

123for (int x : nums) {
    cout << x << endl;
}

123while (left < right) {
    left++;
}

1234567891011vector<int> nums = {1, 2, 3};

nums.push_back(4);  // 添加元素
nums.pop_back();    // 删除最后一个元素

int n = nums.size();

cout << nums[0] << endl;
cout << nums.back() << endl;
nums[0] = 100; //修改元素
swap(nums[0], nums[1]);//交换两个元素

1234567891011class Solution {
public:
    int arraySum(vector<int>& nums) {
        int sum = 0;
        // 在这里遍历 nums
        for(int x : nums){
	        sum+=x;
	      }
        return sum;
    }
};

123456789101112class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        for(int fast = 0;fast < nums.size();fast++){
            if (nums[fast]!=0){
                swap(nums[slow],nums[fast]);
                slow++;
            }
        }
    }
};

12345678910111213class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i =0;i<nums.size();i++){
            for(int j =i+1;j<nums.size();j++){
                if(nums[i]+nums[j] == target){
                    return {i,j};
                }
            }
        }
        return {};
    }
};

1234567891011121314151617181920212223242526int findMax(vector<int>& nums) {
    int max = nums[0];
    for (int i=0;i<nums.size();i++) {//这里可以从1开始，因为0用来初始化了
        if (nums[i]>max) {
            max = nums[i];
        }
    }
    return max;
}
//命名尽量不用max，有库函数也叫max，建议叫maxValue/maximum
int countEven(vector<int>& nums) {
    int sum = 0;
    for (int i = 0;i<nums.size();i++) {
        if (nums[i]%2==0) {
            sum+=1;
        }
    }
    return sum;
}
//可以用只需要元素的循环方式
void swapEnds(vector<int>& nums) {
    int temp = nums[0];
    nums[0]=nums[nums.size()-1];
    nums[nums.size()-1]=temp;
}
//可以加一个判断，nums.empty()，防止空数组越界

123nums.empty()  // 判断是否为空
nums.front()  // 第一个元素
nums.back()   // 最后一个元素

1234567891011121314void reverseArray(vector<int>& nums) {
    if (nums.empty()) {
        return;
    }
    int right = nums.size()-1;
    for (int left = 0;left <nums.size();left++) {
        if (left == right) {
            return;
        }
        swap(nums[left],nums[right]);
        right--;
        }
    }
    //此乃错误答案，只能在奇数数组的情况下运作。偶数不会出现left=right的情况，直接让left在小于right的情况下运作就行。

12345678910void reverseArray(vector<int>& nums) {
    if (nums.empty()) {
        return;
    }
    int right = nums.size()-1;
    for (int left = 0;left <right;left++) {
        swap(nums[left],nums[right]);
        right--;
        }
}

1234567891011unordered_map<int, int> mapping;

mapping[2] = 0;
mapping[7] = 1;

//判断键是否存在
mp.count(key)
mp.find(key)
if (mp.find(10)!=mp.end()){
	cout<<"exist!"<<endl;
}

123456789101112unordered_set<int> seen;

seen.insert(5);

if (seen.count(5)) {
    cout << "存在" << endl;
}
seen.insert(10);  // 添加
seen.erase(10);   // 删除
seen.count(10);   // 判断是否存在
seen.size();      // 元素数量
seen.empty();     // 是否为空

12345678910bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int i:nums) {
        if (seen.count(i)==1) {
            return true;
        }
        seen.insert(i);
    }
    return false;
}

1234567unordered_map<int, int> countFrequency(vector<int>& nums) {
    unorder_map<int,int>frequency;
    for(intx:nums) {
        frequency[x]++;
    }
    return frequecy;
}

1234567891011vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int>indexMap;
    for (int i =0;i<nums.size();i++) {
        int need = target - nums[i];
        if (indexMap.find(need)!=indexMap.end()) {
            return {indexMap[need],i};
        }
        indexMap[nums[i]]=i; //最重要的，先查询再插入，插入的时候，key是数值，value是坐标
    }
    return {};
}

1234567891011bool isAnagram(string s, string t) {
    unordered_map<char,int>times;
    unordered_map<char,int>times2;
    for (char x:s) {
        times[x]++;
    }
    for (char x:t) {
        times2[x]++;
    }
    return times==times2;
}

1234567891011121314151617class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> groups;
        for (string s:strs){
            string key = s;
            sort(key.begin(),key.end());
            groups[key].push_back(s);
        }
        vector<vector<string>> result;
        for (auto& pair:groups){
            result.push_back(pair.second);
        }
        return result;

    }
};

1234遍历哈希表时：for (auto& pair : groups)
每个pair都包含
pair.first   // key
pair.second  // value

12345678910stack<int> st;

st.push(10);
st.push(20);
st.push(30);

int x = st.top();//获取栈顶数值
st.pop();//弹出
st.empty(); // 是否为空
st.size();  // 元素数量

1234567891011121314151617181920212223242526class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(char c:s){
            if(c=='(' || c == '{' || c == '['){
                st.push(c);
            }else{
                if(st.empty()){
                    return false;
                }
                if((c == ')' && st.top()=='(')||(c == ']' && st.top()=='[')||(c == '}' && st.top()=='{')){
                    st.pop();
                    continue;
                }else{
                    return false;
                }
            }
    }
    if (st.empty()){
        return true;
    }else{
        return false;
    }
    }
};

12345678910queue<int> q;

q.push(10);
q.push(20);
q.push(30);
q.front(); //访问队首
q.back(); //访问队尾
q.pop(); //删除队首
q.empty();
q.size();

123456struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

1ListNode* head; //可以理解为head保存某个链表节点的位置

123if (!head) {
    return;
}

123456ListNode* cur = head;

while (cur != nullptr) {
    cout << cur->val << endl;
    cur = cur->next;
}

123456789int getLength(ListNode* head) {
    ListNode* cur = head;
    int sum = 0;
    while(cur!= nullptr){
        sum++;
        cur=cur->next;
    }
    return sum;
}

1234567891011121314class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur!=nullptr){
            ListNode* nextNode = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nextNode;
        }
        return prev;
    }
};

123456789101112131415class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!=nullptr && fast->next != nullptr){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
};

123456789101112131415161718192021222324左右相向：数组反转，有序数组查找，最多水的容器，三数之和
int left = 0;
int right = nums.size() - 1;

while (left < right) {
    // 根据条件移动 left 或 right
}
快慢指针：移动0，删除重复元素，原地修改数组
int slow = 0;

for (int fast = 0; fast < nums.size(); fast++) {
    // 根据 fast 的内容更新 slow
}
滑动窗口：连续子数组，连续子字符串，最长最短满足某种条件的区间。
int left = 0;

for (int right = 0; right < nums.size(); right++) {
    // 加入 nums[right]

    while (窗口不合法) {
        // 移除 nums[left]
        left++;
    }
}

12345678910111213141516171819202122class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size()-1;
        int answer = 0;
        int area = min(height[left],height[right])*(right-left);
        int temp = 0;
        while(left<right){
            if (height[left]<height[right]){
                left++;
            }else{
                right--;
            }
            temp = min(height[left],height[right])*(right-left);
            if(temp>area){
                area = temp;
            }
        }
        return area;
    }
};

12345678910111213141516171819202122232425262728293031323334class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        for(int i = 0;i <nums.size();i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.size()-1;
            while(left<right){
                if (nums[left]+nums[right]>-nums[i]){
                    right--;
                }else if(nums[left]+nums[right]<-nums[i]){
                    left++;
                }else{
                    result.push_back({nums[i],nums[left],nums[right]});

                    while(left < right && nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left < right && nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
            }
           
        }
    }
        return result;    
}
};

123456789101112131415161718class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> window;
        int left = 0;
        int answer = 0;
        for (int right =0;right<s.size();right++){
            while(window.count(s[right])){
                window.erase(s[left]);
                left++;
            }
            window.insert(s[right]);
            int length = right - left +1;
            answer = max(answer,length);
        }
        return answer;
        }
};

123456789101112131415161718class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> prefixCount;
        prefixCount[0]=1;
        int prefix = 0;
        int answer = 0;
        for (int x:nums){
            prefix += x;
            int need = prefix -k;
            if(prefixCount.count(need)){
                answer+=prefixCount[need];
            }
            prefixCount[prefix]++;
        }
        return answer;
    }
};

1prefix

1previousPrefix

1prefix - previousPrefix = k

1previousPrefix = prefix - k

1unordered_map<int,int>prefixCount;

1230 → 1
1 → 2
3 → 1

123456789101112class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int current = nums[0];
        int answer = nums[0];
        for(int i = 0;i<nums.size();i++){
            current = max(current+nums[i],nums[i]);
            answer = max(answer,current);
        }
        return answer;
    }
};

1234567891011121314151617class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> answer(nums.size(),1);
        int leftProduct = 1;
        for(int i = 0;i<nums.size();i++){
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }
        int rightProduct = 1;
        for(int i = nums.size()-1;i>=0;i--){
            answer[i]*=rightProduct;
            rightProduct *= nums[i];
        }
        return answer;
    }
};

12345for (int i = 0; i < matrix.size(); i++) {
    for (int j = 0; j < matrix[0].size(); j++) {
        cout << matrix[i][j] << endl;
    }
}

12345678910111213141516171819202122class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> zeroRows;
        unordered_set<int> zeroCols;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(matrix[i][j]==0){
                    zeroCols.insert(j);
                    zeroRows.insert(i);
                }
            }
        }
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(zeroCols.count(j) || zeroRows.count(i)){
                    matrix[i][j]=0;
                }
            }
        }
    }
};

123456789101112131415161718192021222324252627282930313233class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int top = 0;
        int bottom = matrix.size()-1;
        int left = 0;
        int right = matrix[0].size()-1;
        vector<int> result;
        while(top<=bottom && left<=right){
            for(int i = left;i<=right;i++){
                result.push_back(matrix[top][i]);
            }
            top++;
            for(int j = top;j<=bottom;j++){
                result.push_back(matrix[j][right]);
            }
            right--;
            if(top<=bottom){
                for(int k = right;k>=left;k--){
                    result.push_back(matrix[bottom][k]);
                }
                bottom--;
            }
            if(left<=right){
                for(int l = bottom;l>=top;l--){
                    result.push_back(matrix[l][left]);
                }
                left++;
            }
        }
        return result;
    }
};

12345678910111213class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        for(int i = 0;i<matrix.size();i++){
            for(int j = i+1;j<matrix[0].size();j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        for(int i = 0;i<matrix.size();i++){
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

12ListNode dummy(0);
dummy.next = head;

1234567891011121314151617181920212223class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(list1 != nullptr && list2 != nullptr){
            if(list1->val < list2->val){
                tail->next = list1;
                list1 = list1->next;
            }else{
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if(list1){
            tail->next = list1;
        }else{
            tail->next = list2;
        }
        return dummy.next;
    }
};

123456789101112131415161718class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;
        for(int i = 0;i<=n;i++){
            fast = fast->next;
        }
        while(fast!=nullptr){
            fast= fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy.next;
    }
};

123456789101112class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pA = headA;
        ListNode* pB = headB;
        while(pA != pB){
            pA = (pA == nullptr) ? headB:pA->next;
            pB = (pB == nullptr)? headA:pB->next;
        }
        return pA;
    }
};

12345678struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x)
        : val(x), left(nullptr), right(nullptr) {}
};

123if (root == nullptr) {
    return ...;
}

1cur =cur->next;

1root->left;root->right;

123456789返回类型dfs(TreeNode*root) {
if (root==nullptr) {
	return 空节点对应的结果;
    }

    左子树结果 =dfs(root->left);
    右子树结果 =dfs(root->right);
    return 根据当前节点和左右结果计算答案;
}

1234567891011class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        int leftD = maxDepth(root->left);
        int rightD = maxDepth(root->right);
        return max(leftD,rightD)+1;
    }
};

123456789101112class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return nullptr;
        }
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

1当前节点 → 左子树 → 右子树

123456789void preorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    cout << root->val;
    preorder(root->left);
    preorder(root->right);
}

1左子树 → 当前节点 → 右子树

123456789void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    inorder(root->left);
    cout << root->val;
    inorder(root->right);
}

1左子树 → 右子树 → 当前节点

123456789void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    postorder(root->left);
    postorder(root->right);
    cout << root->val;
}

12345678910111213141516171819202122232425262728class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> result;
        if (root == nullptr){
            return result;
        }
        while(!q.empty()){
            int levelSize = q.size();
            vector<int> level;
            for(int i =0;i<levelSize;i++){
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node -> val);
                if(node->left != nullptr){
                    q.push(node->left);
                }
                if(node->right != nullptr){
                    q.push(node->right);
                }
            }
            result.push_back(level);
        }
        return result;
    }
};