1
class Solution {
2
public:
3
    int search(vector<int>& a, int t) {
4
        int n=a.size();
5
        set<int> s;
6
        for (auto it:a){
7
            s.insert(it);
8
        }
9
        if (s.find(t)==s.end()){
10
            return -1;
11
        }else{
12
            int l=0,r=n-1;
13
            while (l<=r){
14
                int mid=(l+r)/2;
15
                if (a[mid]==t){
16
                    return mid;
17
                }else if(a[mid]>t){
18
                    r=mid-1;
19
                }else{
20
                    l=mid+1;
21
                }
22
            }
23
        }
24
        return -1;
25
    }
26
};

1
class Solution {
2
public:
3
    int searchInsert(vector<int>& a, int t) {
4
        int n=a.size();
5
        set<int> s;
6
        for (auto it:a){
7
            s.insert(it);
8
        }
9
        if (s.find(t)==s.end()){
10
            if (t<a[0]){
11
                return 0;
12
            }
13
            if (t>a[n-1]){
14
                return n;
15
            }
16
            for (int i=1;i<=n-1;i++){
17
                if (a[i]>t&&a[i-1]<t){
18
                    return i;
19
                }
20
            }
21
        }else{
22
            int l=0,r=n-1;
23
            while (l<=r){
24
                int mid=(l+r)/2;
25
                if (a[mid]==t){
26
                    return mid;
27
                }
28
                if (a[mid]>t){
29
                    r=mid-1;
30
                }
31
                if (a[mid]<t){
32
                    l=mid+1;
33
                }
34
            }
35
        }
36
        return 0;
37
    }
38
};

1
class Solution {
2
public:
3
    vector<int> searchRange(vector<int>& a, int t) {
4
        int n=a.size();
5
        set<int> s;
6
        for (auto it:a){
7
            s.insert(it);
8
        }
9
        if (s.empty()||s.find(t)==s.end()){
10
            return {-1,-1};
11
        }else{
12
            int ansl=0,ansr=0;
13
            int l=0,r=n-1;
14
            while (l<=r){
15
                int mid=(l+r)/2;
16
                if (a[mid]>t){
17
                    r=mid-1;
18
                }else{
19
                    l=mid+1;
20
                    ansr=l;
21
                }
22
            }
23
            l=0,r=n-1;
24
            while (l<=r){
25
                int mid=(l+r)/2;
26
                if (a[mid]>=t){
27
                    r=mid-1;
28
                    ansl=r;
29
                }else{
30
                    l=mid+1;
31
                }
32
            }
33
            return {ansl+1,ansr-1};
34
        }
35
        return {-1,-1};
36
    }
37
};

1
class Solution {
2
public:
3
    int mySqrt(int x) {
4
        int l=1,r=x;
5
        int ans=0;
6
        while (l<=r){
7
            int mid=l+(r-l)/2;
8
            if ((long long)mid*mid<=x){
9
                ans=mid;
10
                l=mid+1;
11
            }else{
12
                r=mid-1;
13
            }
14
        }
15
        return ans;
16
    }
17
};

1
class Solution {
2
public:
3
    bool isPerfectSquare(int x) {
4
        int l=1,r=x;
5
        int ans=0;
6
        while (l<=r){
7
            int mid=l+(r-l)/2;
8
            if ((long long)mid*mid<=x){
9
                ans=mid;
10
                l=mid+1;
11
            }else{
12
                r=mid-1;
13
            }
14
        }
15
        if ((long long)ans*ans==x){
16
            return 1;
17
        }else{
18
            return 0;
19
        }
20
    }
21
};

1
class Solution {
2
public:
3
    int removeElement(vector<int>& a, int v) {
4
        int n=a.size();
5
        int fastidx=0,slowidx=0;
6
        while (fastidx<n&&slowidx<n){
7
            if (a[fastidx]!=v){
8
                a[slowidx++]=a[fastidx];
9
            }
10
            fastidx++;
11
        }
12
        return slowidx;
13
    }
14
};

1
class Solution {
2
public:
3
    int removeDuplicates(vector<int>& a) {
4
        unordered_map<int,int> m;
5
        int n=a.size();
6
        for (int i=0;i<n;i++){
7
            m[a[i]]++;
8
        }
9
        int slowidx=0,fastidx=0;
10
        while (slowidx<n&&fastidx<n){
11
            if (m[a[fastidx]]==1){
12
                a[slowidx++]=a[fastidx];
13
            }else if(m[a[fastidx]]>1){
14
                m[a[fastidx]]--;
15
            }
16
            fastidx++;
17
        }
18
        return slowidx;
19
    }
20
};

1
class Solution {
2
public:
3
    void moveZeroes(vector<int>& a) {
4
        int n=a.size();
5
        int slowidx=0,fastidx=0;
6
        while (slowidx<n&&fastidx<n){
7
            if (a[fastidx]!=0){
8
                a[slowidx++]=a[fastidx];
9
            }
10
            fastidx++;
11
        }
12
        while (slowidx<n){
13
            a[slowidx++]=0;
14
        }
15
    }
16
};

1
class Solution {
2
public:
3
    bool backspaceCompare(string S, string T) {
4
        return build(S) == build(T);
5
    }
6

7
    string build(string str) {
8
        string ret;
9
        for (char ch : str) {
10
            if (ch != '#') {
11
                ret.push_back(ch);
12
            } else if (!ret.empty()) {
13
                ret.pop_back();
14
            }
15
        }
16
        return ret;
17
    }
18
};

1
var backspaceCompare = function(S, T) {
2
    let i = S.length - 1,
3
        j = T.length - 1,
4
        skipS = 0,
5
        skipT = 0;
6
    // 大循环
7
    while(i >= 0 || j >= 0){
8
        // S 循环
9
        while(i >= 0){
10
            if(S[i] === '#'){
11
                skipS++;
12
                i--;
13
            }else if(skipS > 0){
14
                skipS--;
15
                i--;
16
            }else break;
17
        }
18
        // T 循环
19
        while(j >= 0){
20
            if(T[j] === '#'){
21
                skipT++;
22
                j--;
23
            }else if(skipT > 0){
24
                skipT--;
25
                j--;
26
            }else break;
27
        }
28
        if(S[i] !== T[j]) return false;
29
        i--;
30
        j--;
31
    }
32
    return true;
33
};

1
class Solution {
2
public:
3
    vector<int> sortedSquares(vector<int>& a) {
4
        int n=a.size();
5
        for (int i=0;i<n;i++){
6
            a[i]=a[i]*a[i];
7
        }
8
        sort(a.begin(),a.end());
9
        return a;
10
    }
11
};

1
class Solution {
2
public:
3
    int minSubArrayLen(int t, vector<int>& a) {
4
        int n=a.size();
5
        int i=0,j=0;
6
        int minn=n;
7
        int sum=a[i];
8
        while (i<n&&j<n){
9
            if (sum<t){
10
                j++;
11
                if (j<n) sum+=a[j];
12
            }else{
13
                minn=min(minn,j-i+1);
14
                sum-=a[i];
15
                i++;
16
            }
17
        }
18
        if (sum<t&&i==0){
19
            return 0;
20
        }else{
21
            return minn;
22
        }
23
    }
24
};

1
class Solution {
2
public:
3
    int totalFruit(vector<int>& f) {
4
        unordered_map<int,int> cnt;
5
        int n=f.size();
6
        int ans=0;
7
        int left=0;
8
        for (int right=0; right<n; right++){
9
            cnt[f[right]]++;
10
            while (cnt.size()>2){
11
                cnt[f[left]]--;
12
                if (cnt[f[left]]==0) cnt.erase(f[left]);
13
                left++;
14
            }
15
            ans=max(ans, right-left+1);
16
        }
17
        return ans;
18
    }
19
};

1
class Solution {
2
public:
3
    string minWindow(string s, string t) {
4
        int n1 = s.size();
5
        int n2 = t.size();
6
        if (n1 < n2) return "";
7

8
        unordered_map<char,int> h1;
9
        for (auto c : t) h1[c]++;
10

11
        unordered_map<char,int> h2;
12
        int left = 0;
13
        int match = 0;
14
        int minlen = INT_MAX;
15
        int start = 0;
16

17
        for (int right = 0; right < n1; right++) {
18
            char c = s[right];
19
            if (h1.count(c)) {
20
                h2[c]++;
21
                if (h2[c] == h1[c]) match++;
22
            }
23

24
            while (match == (int)h1.size()) {
25
                if (right - left + 1 < minlen) {
26
                    minlen = right - left + 1;
27
                    start = left;
28
                }
29
                char d = s[left];
30
                if (h1.count(d)) {
31
                    h2[d]--;
32
                    if (h2[d] < h1[d]) match--;
33
                }
34
                left++;
35
            }
36
        }
37
        return minlen == INT_MAX ? "" : s.substr(start, minlen);
38
    }
39
};

1
class Solution {
2
public:
3
    vector<vector<int>> generateMatrix(int n) {
4
        int top=0,bottom=n-1,left=0,right=n-1;
5
        int cur=1;
6
        vector<vector<int>> m(n,vector<int>(n));
7
        while (top<=bottom&&left<=right){
8
            for (int i=left;i<=right;i++){
9
                m[top][i]=cur;
10
                cur++;
11
            }
12
            top++;
13
            for (int i=top;i<=bottom;i++){
14
                m[i][right]=cur;
15
                cur++;
16
            }
17
            right--;
18
            if (top<=bottom){
19
                for (int i=right;i>=left;i--){
20
                    m[bottom][i]=cur;
21
                    cur++;
22
                }
23
                bottom--;
24
            }
25
            if (left<=right){
26
                for (int i=bottom;i>=top;i--){
27
                    m[i][left]=cur;
28
                    cur++;
29
                }
30
                left++;
31
            }
32
        }
33
        return m;
34
    }
35
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* removeElements(ListNode* head, int val) {
14
        while (head!=NULL&&head->val==val){
15
            ListNode *temp=head;
16
            head=head->next;
17
            delete temp;
18
        }
19

20
        ListNode* cur=head;
21
        while (cur!=NULL&&cur->next!=NULL){
22
            if (cur->next->val==val){
23
                ListNode *temp=cur->next;
24
                cur->next=cur->next->next;
25
                delete temp;
26
            }else{
27
                cur=cur->next;
28
            }
29
        }
30
        return head;
31
    }
32
};

1
class MyLinkedList {
2
public:
3
    // 定义链表节点结构体
4
    struct LinkedNode {
5
        int val;
6
        LinkedNode* next;
7
        LinkedNode(int val):val(val), next(nullptr){}
8
    };
9

10
    // 初始化链表
11
    MyLinkedList() {
12
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
13
        _size = 0;
14
    }
15

16
    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
17
    int get(int index) {
18
        if (index > (_size - 1) || index < 0) {
19
            return -1;
20
        }
21
        LinkedNode* cur = _dummyHead->next;
22
        while(index--){ // 如果--index 就会陷入死循环
23
            cur = cur->next;
24
        }
25
        return cur->val;
26
    }
27

28
    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
29
    void addAtHead(int val) {
30
        LinkedNode* newNode = new LinkedNode(val);
31
        newNode->next = _dummyHead->next;
32
        _dummyHead->next = newNode;
33
        _size++;
34
    }
35

36
    // 在链表最后面添加一个节点
37
    void addAtTail(int val) {
38
        LinkedNode* newNode = new LinkedNode(val);
39
        LinkedNode* cur = _dummyHead;
40
        while(cur->next != nullptr){
41
            cur = cur->next;
42
        }
43
        cur->next = newNode;
44
        _size++;
45
    }
46

47
    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
48
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
49
    // 如果index大于链表的长度，则返回空
50
    // 如果index小于0，则在头部插入节点
51
    void addAtIndex(int index, int val) {
52

53
        if(index > _size) return;
54
        if(index < 0) index = 0;
55
        LinkedNode* newNode = new LinkedNode(val);
56
        LinkedNode* cur = _dummyHead;
57
        while(index--) {
58
            cur = cur->next;
59
        }
60
        newNode->next = cur->next;
61
        cur->next = newNode;
62
        _size++;
63
    }
64

65
    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
66
    void deleteAtIndex(int index) {
67
        if (index >= _size || index < 0) {
68
            return;
69
        }
70
        LinkedNode* cur = _dummyHead;
71
        while(index--) {
72
            cur = cur ->next;
73
        }
74
        LinkedNode* tmp = cur->next;
75
        cur->next = cur->next->next;
76
        delete tmp;
77
        //delete命令指示释放了tmp指针原本所指的那部分内存，
78
        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
79
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
80
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
81
        tmp=nullptr;
82
        _size--;
83
    }
84

85
    // 打印链表
86
    void printLinkedList() {
87
        LinkedNode* cur = _dummyHead;
88
        while (cur->next != nullptr) {
89
            cout << cur->next->val << " ";
90
            cur = cur->next;
91
        }
92
        cout << endl;
93
    }
94
private:
95
    int _size;
96
    LinkedNode* _dummyHead;
97
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* reverseList(ListNode* head) {
14
        ListNode *temp;
15
        ListNode *cur=head;
16
        ListNode *pre=NULL;
17
        while (cur!=NULL){
18
            temp=cur->next;
19
            cur->next=pre;
20
            pre=cur;
21
            cur=temp;
22
        }
23
        return pre;
24
    }
25
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* swapPairs(ListNode* head) {
14
        ListNode *dummyhead=new ListNode(0);
15
        dummyhead->next=head;
16
        ListNode *cur=dummyhead;
17
        while (cur->next!=NULL&&cur->next->next!=NULL){
18
            ListNode *temp1=cur->next;
19
            ListNode *temp2=cur->next->next->next;
20
            cur->next=cur->next->next;
21
            cur->next->next=temp1;
22
            cur->next->next->next=temp2;
23
            cur=cur->next->next;
24
        }
25
        return dummyhead->next;
26
    }
27
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* removeNthFromEnd(ListNode* head, int n) {
14
        ListNode *dummy=new ListNode(0);
15
        dummy->next=head;
16
        ListNode *fast=dummy;
17
        ListNode *slow=dummy;
18
        while (n--&&fast!=NULL){
19
            fast=fast->next;
20
        }
21
        fast=fast->next;
22
        while (fast!=NULL){
23
            fast=fast->next;
24
            slow=slow->next;
25
        }
26
        slow->next=slow->next->next;
27
        return dummy->next;
28
    }
29
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
12
        ListNode *cur1=headA;
13
        ListNode *cur2=headB;
14
        int lenA=0,lenB=0;
15
        while (cur1!=NULL){
16
            lenA++;
17
            cur1=cur1->next;
18
        }
19
        while (cur2!=NULL){
20
            lenB++;
21
            cur2=cur2->next;
22
        }
23
        cur1=headA;
24
        cur2=headB;
25
        if (lenB>lenA){
26
            swap(lenA,lenB);
27
            swap(cur1,cur2);
28
        }
29
        int gap=lenA-lenB;
30
        while (gap--){
31
            cur1=cur1->next;
32
        }
33
        while (cur1!=NULL){
34
            if (cur1==cur2){
35
                return cur1;
36
            }
37
            cur1=cur1->next;
38
            cur2=cur2->next;
39
        }
40
        return NULL;
41
    }
42
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode *detectCycle(ListNode *head) {
12
        unordered_map<ListNode*,int> v;
13
        while (head!=NULL){
14
            if (v.count(head)){
15
                return head;
16
            }
17
            v[head]++;
18
            head=head->next;
19
        }
20
        return NULL;
21
    }
22
};

1
class Solution {
2
public:
3
    bool isAnagram(string s, string t) {
4
        if (s.size()!=t.size()){
5
            return 0;
6
        }
7
        unordered_map<char,int> sh;
8
        unordered_map<char,int> th;
9
        for (auto c:s){
10
            sh[c]++;
11
        }
12
        for (auto c:t){
13
            th[c]++;
14
        }
15
        for (auto c:s){
16
            if (t.find(c)==string::npos){
17
                return 0;
18
            }else{
19
                if (th[c]!=sh[c]){
20
                    return 0;
21
                }
22
            }
23
        }
24
        return 1;
25
    }
26
};

1
class Solution {
2
public:
3
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
4
        unordered_map<int,int> h;
5
        set<int> exist;
6
        vector<int> ans;
7
        for (auto it:nums1){
8
            h[it]++;
9
        }
10
        for (auto it:nums2){
11
            if (h.count(it)&&exist.find(it)==exist.end()){
12
                ans.push_back(it);
13
                exist.insert(it);
14
            }
15
        }
16
        return ans;
17
    }
18
};

1
int turnnum(int n){
2
    int res=0;
3
    while (n>0){
4
        int t=n%10;
5
        res+=t*t;
6
        n/=10;
7
    }
8
    return res;
9
}
10

11
class Solution {
12
public:
13
    bool isHappy(int n) {
14
        unordered_map<int,int> h;
15
        h.emplace(n,1);
16
        while (1){
17
            if (n==1){
18
                return 1;
19
            }
20
            n=turnnum(n);
21
            if (h.count(n)){
22
                return 0;
23
            }
24
            h[n]++;
25
        }
26
        return 0;
27
    }
28
};

1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int t) {
4
        unordered_map<int,int> h;
5
        int n=nums.size();
6
        for (int i=0;i<n;i++){
7
            auto ans=h.find(t-nums[i]);
8
            if (ans!=h.end()){
9
                return {ans->second,i};
10
            }
11
            h[nums[i]]=i;
12
        }
13
        return {};
14
    }
15
};

1
class Solution {
2
public:
3
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
4
        unordered_map<int,int> h;
5
        for (auto a:nums1){
6
            for (auto b:nums2){
7
                h[a+b]++;
8
            }
9
        }
10
        int sum=0;
11
        for (auto c:nums3){
12
            for (auto d:nums4){
13
                auto ans=h.find(0-(c+d));
14
                if (ans!=h.end()){
15
                    sum+=h[0-(c+d)];
16
                }
17
            }
18
        }
19
        return sum;
20
    }
21
};

1
class Solution {
2
public:
3
    vector<vector<int>> threeSum(vector<int>& nums) {
4
        vector<vector<int>> ans;
5
        int n=nums.size();
6
        sort(nums.begin(),nums.end());
7
        int l,r;
8
        for (int i=0;i<n;i++){
9
            if (nums[i]>0){
10
                return ans;
11
            }
12
            if (i>0&&nums[i]==nums[i-1]){
13
                continue;
14
            }
15
            l=i+1,r=n-1;
16
            while (l<r){
17
                if (nums[i]+nums[l]+nums[r]>0){
18
                    r--;
19
                }
20
                else if(nums[i]+nums[l]+nums[r]<0){
21
                    l++;
22
                }else{
23
                    ans.push_back({nums[i],nums[l],nums[r]});
24
                    while (l<r&&nums[l]==nums[l+1]) l++;
25
                    while (l<r&&nums[r]==nums[r-1]) r--;
26
                    l++;
27
                    r--;
28
                }
29
            }
30
        }
31
        return ans;
32
    }
33
};

1
class Solution {
2
public:
3
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
4
        int n = nums.size();
5
        vector<vector<int>> ans;
6
        sort(nums.begin(), nums.end());
7

8
        for (int i = 0; i < n; i++) {
9
            if (i > 0 && nums[i] == nums[i - 1]) continue;
10
            for (int j = i + 1; j < n; j++) {
11
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
12

13
                int l = j + 1, r = n - 1;
14
                while (l < r) {
15
                    long long sum = (long long)nums[i] + nums[j] + nums[l] + nums[r];
16
                    if (sum > target) r--;
17
                    else if (sum < target) l++;
18
                    else {
19
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
20
                        while (l < r && nums[l] == nums[l + 1]) l++;
21
                        while (l < r && nums[r] == nums[r - 1]) r--;
22
                        l++;
23
                        r--;
24
                    }
25
                }
26
            }
27
        }
28
        return ans;
29
    }
30
};