剑指offer026输入两棵二叉树A,B,判断B是不是A的子结构

Posted on 2020-02-02 In 剑指offer Valine:

Problem:

输入两棵二叉树A,B,判断B是不是A的子结构

Intuition:

树和链表都是典型的递归结构，遇到题目优先尝试从递归的角度来考虑。这个题目我们要找树A与B是否存在子结构的关系，那么这个过程可以分为两步。第一步，在树A中找到和树B的根节点一样的节点R;第二步，判断树A中以R为根节点的子树是不是包含和树B一样的结构。

Solution:

public class CodingInterview_026 {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null)
            return false;
        return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
        if (root2 == null)
            return true;
        if (root1 == null)
            return false;
        if (root1.val != root2.val)
            return false;
        return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
    }
}

剑指offer025合并两个排序的链表

Posted on 2020-02-02 In 剑指offer Valine:

Problem:

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

Solution:

public class CodingInterview_025 {
    public class ListNode
    {
        int val;
        ListNode next;

        public ListNode(int x){
            val=x;
        }
    }
    //递归是一种比较直接的思路，难度也比较低，在面试的紧张环境下链表类问题优先考虑用递归来解决
    public ListNode MergeWithRecursion(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

    public ListNode Merge(ListNode list1, ListNode list2) {
        //这种方法叫做头插法，如果我们要生成一个链表，那么我们先可以创建一个空的链表头，然后往那个链表头后面添元素，最后返回链表头的下一个元素就是新的链表，同时链表头也就完成了它工具人的使命
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null)
            cur.next = list1;
        if (list2 != null)
            cur.next = list2;
        return head.next;
    }
}

剑指offer024反转链表

Posted on 2020-02-02 In 剑指offer Valine:

Problem:

输入一个链表，反转链表后，输出新链表的表头。

Intuition:

我们要用递归的思路完成这个问题，那么第一个节点原来应该指向的是第二个节点，现在指向的是null.对于第n个节点来说，原来指向的应该是第n+1个节点，现在应该指向的是第n-1个节点.那么这个递归关系如何进行构建？实际上问题就变成了我知道如何变换一个长度为n-1的反向链表（利用递归的特性），如何在它前面加一个节点然后拼起来的问题。想象一下从n-1个节点到n个节点的拼装的过程，问题就明确了。

Solution:

public class CodingInterview_024 {
    public class ListNode
    {
        int val;
        ListNode next;

        public ListNode(int x){
            val=x;
        }
    }

    public ListNode ReverseListWithRecursion(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode next = head.next;
        head.next = null;
        ListNode newHead = ReverseListWithRecursion(next);
        next.next = head;
        return newHead;
    }



    public ListNode ReverseListWithLoop(ListNode head) {

        if(head==null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
        ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

剑指offer023链表中环的入口节点

Posted on 2020-02-02 In 剑指offer Valine:

Problem:

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

Intuition:

设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。以下是两个结论证明：
两个结论：
1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。
证明结论2：
设：
链表头到环入口长度为–a
环入口到相遇点长度为–b
相遇点到环入口长度为–c

则：相遇时
快指针路程=a+(b+c)k+b ，k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。
慢指针路程=a+(b+c)l+b ,k-l>=1
快指针走的路程是慢指针的两倍，所以：
a+(b+c)k=2[a+(b+c)l+b]
化简可得：
a=(k-l)(b+c)+c 这个式子的意思是：链表头到环入口的距离=相遇点到环入口的距离+（k-l）圈环长度。其中k>=1,所以k-l>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

Solution:

public class CodingInterview_023 {
    public class ListNode
    {
        int val;
        ListNode next;

        public ListNode(int x){
            val=x;
        }
    }
    ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead == null || pHead.next == null)
            return null;
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        while(p2 != null && p2.next != null ){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){
                p2 = pHead;
                while(p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next;
                }
                if(p1 == p2)
                    return p1;
            }
        }
        return null;
    }
}

剑指offer022链表中倒数第K个节点

Posted on 2020-01-31 In 剑指offer Valine:

Problem:

输入一个链表，输出该链表中倒数第k个结点。

Intuition:

设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。

Solution:

public class CodingInterview_022 {

    public class ListNode
    {
        int val;
        ListNode next;

        public ListNode(int x){
            val=x;
        }

    }
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null)
            return null;
        ListNode P1 = head;
        while (P1 != null && k-- > 0)
            P1 = P1.next;
        if (k > 0)
            return null;
        ListNode P2 = head;
        while (P1 != null) {
            P1 = P1.next;
            P2 = P2.next;
        }
        return P2;
    }
}

剑指offer021调整数组顺序使奇数位于偶数前面

Posted on 2020-01-31 In 剑指offer Valine:

Problem:

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

Intuition:

这个题目比较容易，我们只需要知道整个数组中奇数有多少个，然后分开分别进行存放就可以了。

Solution:

public class CodingInterview_021 {
    public void reOrderArray(int[] nums) {
        // 奇数个数
        int oddCnt = 0;
        for (int x : nums)
            if (!isEven(x))
                oddCnt++;
        int[] copy = nums.clone();
        int i = 0, j = oddCnt;
        for (int num : copy) {
            if (num % 2 == 1)
                nums[i++] = num;
            else
                nums[j++] = num;
        }
    }

    private boolean isEven(int x) {
        return x % 2 == 0;
    }
}

剑指offer020表示数值的字符串

Posted on 2020-01-31 In 剑指offer Valine:

Problem:

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

Intuition:

首先我们来看一下题干里面的数字有哪些特点，不难发现所有的数字都可以大体写成整数+符号（小数点或者E,e）+整数的形式（如果第一个符号是小数点还可能出现第二个符号是e,但是总体来说不会出现比这种情况更复杂的情况了）。实现的时候我们要注意两个点。1.最好用一个全局变量index来存当前扫描到的下标，否则不断对下标进行传参或者进行数组的拷贝很麻烦也很容易出错。2.在进行其他判断之前都要判断数组是否越界，养成良好的习惯。

Solution:

public class CodingInterview_020 {
    public static void main(String[] args) {
        CodingInterview_020 main=new CodingInterview_020();
        //"+100", "5e2", "-123", "3.1416", ".0e2", "1E-1", "+31.4e-1", ".12", "12"
        String s="+31.4e-1";
        System.out.println(main.isNumeric(s.toCharArray()));
    }



    //index作为一个全局下标记录当前字符串被扫描到的位置,如果不用全局变量的话一直记录将下标进行传参或者复制数组内容的话会非常不方便
    private int index = 0;

    public boolean isNumeric(char[] str) {
        if (str.length < 1)
            return false;
        //下面这一行代码执行完后，如果这个str表示的是一个数的话，那么index此时指向的就是小数点或者字母e疑惑直接指向字符串的结尾。
        //这一题肯定不能用递归来写，这样5.4.3就会被判定为整数。
        boolean flag = scanInteger(str);

        if (index < str.length && str[index] == '.') {
            index++;
            flag = scanUnsignedInteger(str) && flag;
        }
        //数字里面也可以出现先出现小数点再出现e

        if (index < str.length && (str[index] == 'E' || str[index] == 'e')) {
            index++;
            flag = flag && scanInteger(str);
        }

        return flag && index == str.length;

    }

    private boolean scanInteger(char[] str) {
        //这个函数包括下面的函数都要小心index<str.length的边界情况
        if (index < str.length && (str[index] == '+' || str[index] == '-') )
            index++;
        return scanUnsignedInteger(str);

    }

    private boolean scanUnsignedInteger(char[] str) {
        int start = index;
        while (index < str.length && str[index] >= '0' && str[index] <= '9')
            index++;
        //这一步要额外注意一下，不然5.这样的测试用例就不会通过。
        return start < index; //是否存在整数
    }


}

剑指offer019.2 删除链表中重复的结点

Posted on 2020-01-27 In 剑指offer Valine:

Problem:

删除链表中重复的结点

Solution:

public class CodingInterview_019 {
    public class ListNode
    {
        int val;
        ListNode next;

        public ListNode(int x){
            val=x;
        }

    }

    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null)
            return pHead;
        ListNode next = pHead.next;
        if (pHead.val == next.val) {
            while (next != null && pHead.val == next.val)
                next = next.next;
            return deleteDuplication(next);
        } else {
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        }
    }
}

剑指offer019在 O(1) 时间内删除链表节点

Posted on 2020-01-27 In 剑指offer Valine:

Problem:

在 O(1) 时间内删除链表节点

Intuition:

① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。

② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。

综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)。

Solution:

public class CodingInterview_018 {

    public class ListNode
    {
        int val;
        ListNode next;

        public ListNode(int x){
            val=x;
        }

    }

    public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
        if (head == null || tobeDelete == null)
            return null;
        if (tobeDelete.next != null) {
            // 要删除的节点不是尾节点，直接让当前节点的内容变得跟下一个节点完全一样（不仅是节点的值，还有节点指向的下一个节点），这样就等价于删除了当前节点
            ListNode next = tobeDelete.next;
            tobeDelete.val = next.val;
            tobeDelete.next = next.next;
        } else {
            if (head == tobeDelete)
                // 只有一个节点
                head = null;
            else {
                ListNode cur = head;
                while (cur.next != tobeDelete)
                    cur = cur.next;
                cur.next = null;
            }
        }
        return head;
    }
}

剑指offer018打印从 1 到最大的 n 位数

Posted on 2020-01-27 In 剑指offer Valine:

Problem:

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。

Intuition:

由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 StringBuffer进行存储。既然是用StringBuffer来存，那么我们就要完成两个功能，第一个功能是如何对使用char数组存储的数字进行递增，第二个功能是如何将该数字打印出来（这个部分的核心代码主要是去掉符号扩展自动补上的0）.

Solution:

public class CodingInterview_017 {

    public static void main(String[] args) {

        Print1ToMaxOfNDigits(4);
    }

    public static void Print1ToMaxOfNDigits(int n){
        StringBuffer stringBuffer=new StringBuffer();
        for(int i=0;i<n;i++){
            stringBuffer.append('0');
        }
        while(!Increment(stringBuffer)){
            PrintNumber(stringBuffer);
        }

    }
    //自加
    public static boolean Increment(StringBuffer s) {
        //因为是要在原来数字的基础上递增1，所以默认加1，这个1就放在个位的carry上
        int carry=1;//carry表示进位
        for(int i=s.length()-1;i>=0;i--){
            int digit=s.charAt(i)-'0';
            digit=digit+carry;
            if(digit>=10){
                digit-=10;
                carry=1;
            }else{
                carry=0;
            }
            s.setCharAt(i,(char)(digit+'0'));
        }
        if(carry==1){
            return true;
        }else{
            return false;
        }
    }

    //打印数字
    public static void PrintNumber(StringBuffer s){
        int startPos=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='0'){
                startPos++;
            }else{
                break;
            }
        }
        for(int i=startPos;i<s.length();i++){
            System.out.print(s.charAt(i));
        }
        System.out.println();
    }

}