LeetCode select good questions (3)

Selected in, I am sure I will do after the second brush.

The article directories

• • 1. Set the matrix to zero
  • • Ideas:
    • Code implementation:
  • 2, letter allotopic word grouping
  • • Ideas:
    • Code implementation:
  • 3. The oldest string without repeating characters
  • • Ideas:
    • Code implementation:
  • Add the two numbers
  • • Code implementation:
  • 5. Odd-even linked lists
  • • Train of thought
    • Code implementation:
  • 6. Intersecting linked lists
  • • Ideas:
    • Code implementation:

1. Set the matrix to zero

Given an m x n matrix, if one element is 0, set all elements in its row and column to 0. Please use the in place algorithm.

Example 1:

Input: [[1.1.1],
  [1.0.1],
  [1.1.1]]Copy the code

Output: [[1.0.1],
  [0.0.0],
  [1.0.1]]Copy the code

Example 2:

Input: [[0.1.2.0],
  [3.4.5.2],
  [1.3.1.5]]Copy the code

Output: [[0.0.0.0],
  [0.4.5.0],
  [0.3.1.0]]Copy the code

Advanced:

An immediate solution is to use O(MN) extra space, but this is not a good solution. A simple improvement would be to use O(m + N) extra space, but this is still not the best solution. Can you think of a solution for constant space?Copy the code

Ideas:

Code implementation:

class Solution {
void setZeroes(vector<vector<int>>& matrix) {
    int R = matrix.length;
    int C = matrix[0].length;

    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        if (matrix[r][c] == 0) {
          // We modify the corresponding rows and column elements in place.
          // Note, we only change the non zeroes to MODIFIED
          for (int k = 0; k < C; k++) {
            if(matrix[r][k] ! =0) { matrix[r][k] = INT_MIN; }}for (int k = 0; k < R; k++) {
            if(matrix[k][c] ! =0) {
              matrix[k][c] = INT_MIN;
            }
          }
        }
      }
    }
    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        // Make a second pass and change all INT_MIN elements to 0 """
        if (matrix[r][c] == INT_MIN) {
          matrix[r][c] = 0;
        }
      }
    }
  }
}
Copy the code

2, letter allotopic word grouping

Input:"eat"."tea"."tan"."ate"."nat"."bat"]
Copy the code

Output: [["ate"."eat"."tea"],
  ["nat"."tan"],
  ["bat"]]Copy the code

Ideas:

The string is sorted and used as the key value of the map. The original string is filled into the map as a real value, and then the map is traversed to retrieve the value. Map
,vector>

Code implementation:

vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        vector<vector<string>> res;
        map<string,vector<string>> vec;
        if(strs.empty()) return res;
        for(int i=0; i<strs.size(a); i++) { string temp=strs[i];sort(temp.begin(),temp.end());
            vec[temp].push_back(strs[i]);
        }
        map<string,vector<string>>::iterator it;
        for(auto it=vec.begin(a); it! =vec.end(a); it++) { res.push_back(it->second);
        }
        return res;
    }
Copy the code

3. The oldest string without repeating characters

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input:"abcabcbb"
Copy the code

Output:3Because the oldest string without repeating characters is"abc", so its length is3.Copy the code

Example 2:

Input:"bbbbb"
Copy the code

Output:1Because the oldest string without repeating characters is"b", so its length is1.Copy the code

Example 3:

Input:"pwwkew"
Copy the code

Output:3Because the oldest string without repeating characters is"wke", so its length is3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Ideas:

Code implementation:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() = =0) return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(a); i++){while (lookup.find(s[i]) ! = lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    }
        returnmaxStr; }};Copy the code

Add the two numbers

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) output:7 -> 0 -> 8The reason:342 + 465 = 807
Copy the code

Code implementation:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummyHead = new ListNode(0);
        ListNode *p = l1, *q = l2, *curr = dummyHead;
        int carry = 0;
        while(p ! =NULL|| q ! =NULL) {
            intx = (p ! =NULL)? p->val :0;
            inty = (q ! =NULL)? q->val :0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            if(p ! =NULL) p = p->next;
            if(q ! =NULL) q = q->next;
        }
        if (carry > 0) {
            curr->next = new ListNode(carry);
        }
        return dummyHead->next;
    }
Copy the code

What if lists were stored sequentially? My idea: Reverse in place.

5. Odd-even linked lists

Input:1->2->3->4->5->NULLOutput:1->3->5->2->4->NULL
Copy the code

Input:2->1->3->5->6->4->7->NULLOutput:2->3->6->7->1->5->4->NULL
Copy the code

Train of thought

Fast and slow hands, point to point exchange, no pressure. Oh, no, not swap. I fell for the swap algorithm. The fast pointer nodes should be moved directly to the front.

Code implementation:

ListNode* oddEvenList(ListNode* head) {
    if (head == NULL)
        return head;
        
    ListNode* fast = head;  / / fast
    ListNode* slow = head;  / / slow
    ListNode* temp = head;  / / temporary

    int flag = 1;
    while (1) {
        for (int i = flag; i > 0&& fast->next ! =NULL; i--) {
            fast = fast->next;
        }
        if(fast->next ! =NULL) {
            temp = fast->next;
            fast->next = temp->next;
            temp->next = slow->next;
            slow->next = temp;
            fast = temp;
            slow = temp;
            flag++;
        }
        else {
            break; }}return head;
}
Copy the code

6. Intersecting linked lists

Write a program to find the start node where two singly linked lists intersect.

Here are two linked lists:



The intersection begins at node C1.

Example 1:

Enter: intersectVal =8, listA = [4.1.8.4.5], listB = [5.0.1.8.4.5], skipA = 2, skipB = 3Output: Reference of the node with value =8
Copy the code

Input interpretation: The value of the intersection node is 8 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [4,1,8,4,5] and linked list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersecting node; In B, there are three nodes before the intersection node.

Example 2:

Enter: intersectVal =2, listA = [0.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: Reference of the node with value =2
Copy the code

Input explanation: The value of the intersection node is 2 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [0,9,1,2,4] and linked list B is [3,2,4]. In A, there are three nodes before the intersecting node; In B, there is 1 node before the intersecting node.

Example 3:

Enter: intersectVal =0, listA = [2.6.4], listB = [1.5], skipA = 3, skipB = 2Output: nullCopy the code

Input explanation: from the respective table headers, linked list A is [2,6,4] and linked list B is [1,5]. Because the two linked lists do not intersect, intersectVal must be 0, and skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.

Note:

If two lists do not intersect, null is returned. After the result is returned, both lists must retain their original structure. It can be assumed that there are no loops in the entire list structure. The program meets the O(n) time complexity as far as possible and uses only O(1) memory.Copy the code

Ideas:

Code implementation:

 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a = headA, *b = headB;
        while(a ! = b) { a = a? a->next : headB;// When NULL, set the value to the starting point of another list
            b = b? b->next : headA; 
        }
        return a;
    }
Copy the code