This is the 10th day of my participation in the genwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

Intersection -of-two-linked-lists

The label

  • The list
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given the head nodes of two singly linked lists, headA and headB, find and return the start node where the two singly linked lists intersect. If two lists do not intersect, null is returned.

The two linked lists intersect at node C1:

The problem data guarantees that there are no rings in the chain.

Note that after the function returns the result, the list must retain its original structure.

Example 1:

Input: listA = [4,1,8,4,5], listB = [5,0,1,8,4,5] output: Intersected at '8' The value of the intersecting nodes is 8 starting from their respective table heads, 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.Copy the code

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], and listB = [3,2,4] output: Intersected at '2' 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.Copy the code

The basic idea

  1. Use PA to point to A and PB to point to B
A linked list (ABCDEFG) headA PA | - > C - A - > B > D - > E - > F - > G - > null | | X - > - > Y Z PB headB B list (XYZEFG) node in ` E ` pointsCopy the code
  1. PA and PB go backwards,
    • PA hypothesisA - > E (point)A distance ofl1Step (4)
    • PB hypothesisX - > E (point)A distance ofl2(step 3)
    • The distance from the intersection to the end is zerol3(step 3)
/ / [A] - > E l1 = 4 step step - > null l3 = 3] [E (A) - - - - > > D > C > B (E) - > - > F (G) - > null ^ | (X) - > - > Y Z / / [X - > E step l2 = 3]Copy the code

In this case, chain A is A -> E -> tail, and then to the head of B -> X -> E, the path is L1 -> L3 -> L2, chain B is X -> E -> NULL -> A -> E, The path is L2 -> l3 -> L1, if there is an intersection, then it will come together.

So the way to do it

  • If PA reaches the end, thenPA = headBContinue to traverse the
  • If PB reaches the end, thenPB = headAContinue to traverse the
  1. If the above two Pointers can come together after traversal, it means that there is an intersection point, and they both go to the end respectivelynullNo intersection is returnednullIn this case, the two Pointers will go to the end, and the paths will be(Long chain + short chain)You walk again, both walk to the other side of the null, then two people walk the pathThe sum of two roads

Writing implement

var getIntersectionNode = function(headA, headB) {
    if(! headA || ! headB) {return null
    }
    let [PA, PB] = [headA, headB]
    // Either there is an intersection or both are null
    while(PA ! == PB) { PA = PA ===null ? headB : PA.next;
        PB = PB === null ? headA : PB.next;
    }
    return PA
};
Copy the code

117. Max. palindromic-substring (max. palindromic)

The label

  • string
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given a string s, find the longest substring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question.Copy the code

Example 2:

Input: s = "CBBD" Output: "bb"Copy the code

Example 3:

Input: s = "a" Output: "a"Copy the code

The basic idea

Walk through each location as a “center” and discuss odd and even

Parity discussion

  • The length of the substring isAn odd number(e.g.,aba, the center isb)
  • The length of the substring isAn even number(e.g.,cbbd, the center isB, b,)

Writing implement

function longestPalindrome(s) {
    let res = ' '

    // Passing in the center (left and right) coordinates, returns the longest palindrome string centered on s[l] and s[r]
    const longestPS = (l, r) = > {
        // The left and right sides should not exceed the boundary
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

    // Walk through each position as a "center" and discuss odd and even
    for (let i = 0; i < s.length; i++) {
        // The longest string in the odd number center, I as the coordinate, technique middle is a coordinate
        let oddStr = longestPS(i, i)
        // The longest string with even center
        let evenStr = longestPS(i, i+1)
        
        // Find the longest palindrome
        if (oddStr.length > evenStr.length) {
            // The odd number is large
            res = res.length > oddStr.length ? res : oddStr
        } else {
            res = res.length > evenStr.length ? res : evenStr
        }
    }
    return res
}

console.log(longestPalindrome('babad')) // aba
console.log(longestPalindrome('cbbd')) // bb
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference