leetcode-4

  1. 有效的括号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

bool isValid(string s) {
    int n=s.length();
    if(n%2==1){
        return false;
    }

    unordered_map<char,char> pairs={
        {')','('},
        {']','['},
        {'}','{'}
    };
    stack<char> stk;
    for(char ch:s){
        if(pairs.count(ch)){
            if(stk.empty()||stk.top()!=pairs[ch]){
                return false;
            }
            stk.pop();
        }
        else{
            stk.push(ch);
        }
    }

    return stk.empty();
}
  1. 两数相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head=nullptr;
    ListNode *tail=nullptr;
    int carry =0;
    while(l1||l2)
    {
        int n1= l1? l1->val:0;
        int n2 =l2? l2->val:0;
        int sum = n1+n2+carry;
        if(!head){
            tail = new ListNode(sum%10);
            head=tail;
        }else{
            tail->next = new ListNode(sum % 10);
            tail=tail->next;
        }
        carry=sum/10;
        if(l1){
            l1=l1->next;
        }
        if(l2){
            l2 =l2->next;
        }
    }
    if(carry>0){
        tail->next = new ListNode(carry);
    }
    return head;
}
  1. 搜索插入位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int searchInsert(vector<int>& nums, int target) {
    int n =nums.size();
    int left =0;
    int right = n-1;
    int ans =n;
    while(left<=right){
        int mid =((right-left)>>1)+left;
        if(target<=nums[mid]){
            ans=mid;
            right=mid-1;
        }
        else {
            left=mid+1;
        }
    }
    return ans;
}
  1. 二进制求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

string addBinary(string a, string b) {
    string ans;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());

    int n =max(a.size(),b.size());
    int carry =0;
    for (size_t i = 0; i < n; ++i) {
        if(i<a.size()){
            carry+=(a.at(i)=='1')?1:0;
        }
        if(i<b.size()){
            carry+=(b.at(i)=='1')?1:0;
        }
        ans.push_back((carry % 2) ? '1' : '0');
        carry /= 2;
    }
    if(carry){
        ans.push_back('1');
    }
    reverse(ans.begin(),ans.end());
    return ans;
}
  1. 环形链表

hash表遍历，set可以去除重复的性质

1
2
3
4
5
6
7
8
9
10
11
12

bool hasCycle(ListNode *head) {
    unordered_set<ListNode*> seen;
    while(head!=nullptr){
        if(seen.count(head)){
            return true;
        }
        seen.insert(head);
        head=head->next;
    }
    return false;
}

最优：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bool hasCycle(ListNode *head) {
    if(head==nullptr||head->next==nullptr){
        return false;
    }
    ListNode *slow = head;
    ListNode *fast = head->next;
    while(slow!=fast){
        if(fast ==nullptr||fast->next ==nullptr){
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

通过两个指针，一个快一个慢来实现