<twoyao>

August 09, 2014

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                  ↘
                    c1 → c2 → c3
                  ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. Credits: Special thanks to @stellari for adding this problem and creating all test cases.

Analysis & Solution:

First check intersection by each list’s tail. If they have intersection, they must share same tail. Then make a loop by point c3.next to a1(or c3.next to b1 equally).

After we build the loop, if we start two pointer an b1, one move 1 step and another move 2 steps in each iteration, they will meet in the loop finally. First one has moved a+b steps, second has moved a+b+c+b, so we have2(a+b)=a+b+c+b which infers a=c. This means that if we have a pointer started at b1 and another pointer started at the meet node, after walk a/c step, they will meet at the intersection node.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// Space O(1), Complexity O(M+N)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) return NULL;

        ListNode*p1 = headA, *p2 = headB;
        while (p1->next != NULL) p1 = p1->next;
        while (p2->next != NULL) p2 = p2->next;
        if (p1 != p2) {
            return NULL;
        }
        p2->next = headA;
        ListNode*q1=headB, *q2=headB, *q3=headB;
        do {
            q1 = q1->next->next;
            q2 = q2->next; 
        } while (q1 != q2);
            
        while (q3 != q2) {
            q3 = q3->next;
            q2 = q2->next;
        }
        
        p2->next = NULL;
        return q3;
    }
};

854. K-Similar Strings

Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.

Given two anagrams A and B, return the smallest K for which A and B are K-similar.

Example 1:

Input: A = “ab”, B = “ba” Output: 1

Example 2:

Input: A = “abc”, B = “bca” Output: 2

Example 3:

Input: A = “abac”, B = “baca” Output: 2

Example 4:

Input: A = “aabc”, B = “abca” Output: 2

Note:

  1. 1 <= A.length == B.length <= 20
  2. A and B contain only lowercase letters from the set {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}

Solution

Brute-force and DFS .

import (
    "fmt"
)

func similar(a, b []byte, l int) int {
    if l == 0 {
        return 0
    }
    
    if a[l] == b[l] {
        return similar(a,b,l-1)
    }
    
    min := 9999999
    for i:=l; i>=0; i-- {
        if b[i] == a[l] {
            b[i],b[l] = b[l],b[i]
            k := similar(a,b,l-1) + 1
            if k < min {
                min = k
            }
            b[i],b[l] = b[l],b[i]
            if a[i] == b[l] {
                break
            }
        }
    } 
    return min
}

func kSimilarity(A string, B string) int {
    return similar([]byte(A), []byte(B), len(A)-1) 
}

[852. Peak Index in a Mountain Array]

(https://leetcode.com/problems/peak-index-in-a-mountain-array/description/)

Let’s call an array A a mountain if the following properties hold:

  • A.length >= 3
  • There exists some 0 < i < A.length - 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1  

Note:

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A is a mountain, as defined above.

Solution

Binary search.

func peakIndexInMountainArray(A []int) int {
    l, r := 0, len(A) - 1
    for ;l < r; {
        m := (l + r) / 2
        if A[m-1] < A[m] && A[m] > A[m+1] {
            return m
        }
        if A[m-1] < A[m] && A[m] < A[m+1] {
            l = m+1
        }
        if A[m-1] > A[m] && A[m] > A[m+1] {
            r = m-1
        }
    }
    return l
}

853. Car Fleet

N cars are going to the same destination along a one lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored - they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

  1. 0 <= N <= 10 ^ 4
  2. 0 < target <= 10 ^ 6
  3. 0 < speed[i] <= 10 ^ 6
  4. 0 <= position[i] < target
  5. All initial positions are different.

Solution

import (
    "sort"
)

type PS struct {
    position int
    speed int    
}

func carFleet(target int, position []int, speed []int) int {
    if len(position) == 0 {
        return 0
    }
    
    var ps []PS
    for i := 0; i < len(position); i++ {
        ps = append(ps, PS{position[i], speed[i]})
    }
    
    // sort by position desc
    sort.Slice(ps, func(i, j int) bool {
        return ps[i].position > ps[j].position
    })
    
    lastFleet := &ps[0]
    fleetCount := 1
    for i := 1; i < len(ps); i++ {
        if (target - lastFleet.position) * ps[i].speed >= (target - ps[i].position) * lastFleet.speed {
            continue
        } else {
            fleetCount++
            lastFleet = &ps[i]
        }        
    }
    
    return fleetCount    
}