Sword finger offer (2nd Edition)

• The finger of the sword Offer 52. The first common node of two linked lists

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        Set<ListNode> set = new HashSet<>();
        ListNode temp = headA;
        while(temp!=null){
    
            set.add(temp);
            temp=temp.next;
        }
        temp = headB;
        while(temp!=null){
    
            if(!set.add(temp)){
    
                return temp;
            }
            temp=temp.next;
        }
        return null;
    }
}

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        if (headA == null || headB == null) {
    
            return null;
        }
        ListNode A = headA;
        ListNode B = headB;
        while (A != B) {
    
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return B;
    }
}

• The finger of the sword Offer 24. Reverse a linked list

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode cur = head;
        ListNode p = null,pre =null;
        while(cur!=null){
    
            p = cur;
            cur = cur.next;
            p.next =pre;
            pre = p;
        }
        return p;
    }
}

• The finger of the sword Offer 09. Queues are implemented with two stacks

class CQueue {
    
private Stack<Integer> inStack ;
private Stack<Integer> outStack;

    public CQueue() {
    
        inStack = new Stack<>();
        outStack= new Stack<>();
    }

    public void appendTail(int value) {
    
        inStack.add(value);
    }

    public int deleteHead() {
    
        if(outStack.isEmpty()){
    
            if(inStack.isEmpty()){
    
                return -1;
            }
            while(!inStack.isEmpty()){
    
                outStack.add(inStack.pop());
            }
        }
        return outStack.pop();
    }
}

• The finger of the sword Offer 11. Minimum number of rotation array

class Solution {
    
    public int minnArray(int[] numbers) {
    
        Arrays.sort(numbers);
        return numbers[0];
    }
}

class Solution {
    
    public int minArray(int[] numbers) {
    
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
    
            int mid = low + (high - low) / 2;
            if (numbers[mid] < numbers[high]) {
    
                high = mid;
            } else if (numbers[mid] > numbers[high]) {
    
                low = mid + 1;
            } else {
    
                high -= 1;
            }
        }
        return numbers[low];
    }
}

• The finger of the sword Offer 06. Print linked list from end to end

class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        Stack<Integer> stack = new Stack<>();
        ListNode p = head;
        int size =0;
        while(p!=null){
    
            stack.push(p.val);
            p=p.next;
            size ++;
        }
        int [] ans = new int[size];
        int o = 0;
        while(!stack.isEmpty()){
    
            ans[o++]=stack.pop();
        }
        return ans;
    }
}

class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        ListNode cur = head;
        ListNode p = null;
        ListNode pre = null;
        int size = 0;
        while(cur !=null){
    
            p = cur ;
            cur = cur.next;
            p.next = pre;
            pre= p;
            size ++;
        }
        int [] ans = new int [size];
        for(int i =0;i< size;i++){
    
            ans[i] = p.val;
            p = p.next;
        }
        return ans;
    }
}

The finger of the sword Offer 10- I. Fibonacci sequence

class Solution {
    
    public int fib(int n) {
    
        final int MOD = 1000000007;
        if(n<2){
    
            return n;
        }
        int p = 0, q = 0, r =1;
        for(int i = 2; i<= n;++i){
    
            p = q ;
            q = r ;
            r = (p+q)%MOD;
        }
        return r;
    }
}

• The finger of the sword Offer 10- II. The problem of frog jumping on the steps

class Solution {
    
    public int numWays(int n) {
    
        
        final int MOD = 1000000007;
        int p = 0, q = 1,r=1;
        for(int i = 2;i <= n ; i++){
    
            p = q;
            q = r;
            r = (p+q)%MOD;
        }
        return r;
    }
}

• The finger of the sword Offer 17. Print from 1 To the biggest n digit

class Solution {
    
    public int[] printNumbers(int n) {
    
        int num = 9;
        for(int i = 1;i<n;i++){
    
            num = num*10+9;
        }
        int print[] = new int[num];
        for(int i = 0 ;i < num ;i++){
    
            print[i] = i+1;
        }
        return print;
    }
}