牛客网算法——名企高频面试题143题（5）

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 划分链表
 * @Description TODO
 * @Date 2020/12/12 15:33
 * @Created by xjl
 */
public class 划分链表 {
    public class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode h1 = new ListNode(0);
        ListNode h2 = new ListNode(0);
        ListNode n1 = h1;
        ListNode n2 = h2;
        ListNode pre = head;

        while (pre != null) {
            if (pre.val < x) {
                n1.next = pre;
                n1 = pre;
            } else {
                n2.next = pre;
                n2 = pre;
            }
            pre = pre.next;
        }
        n2.next = null;
        n1.next = h2.next;
        return h1.next;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(4);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(2);
        ListNode s5 = new ListNode(5);
        ListNode s6 = new ListNode(2);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;
        s5.next = s6;

        ListNode res = partition(s1, 3);
        while (res != null) {
            System.out.print(res.val+" ");
            res = res.next;
        }

    }
}

package 复现代码;

import org.junit.Test;

/**
 * @Classname 分割链表
 * @Description TODO
 * @Date 2020/12/12 16:24
 * @Created by xjl
 */
public class 分割链表 {
    public class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode per(ListNode head, int x) {
        //检查安全
        if (head == null) return null;
        ListNode dumpy1 = new ListNode(0);
        ListNode dumpy2 = new ListNode(0);

        ListNode samll = dumpy1;
        ListNode large = dumpy2;
        ListNode pre = head;
        
        while (pre!=null){
            if (pre.val>=x){
                large.next=pre;
                large=large.next;
            }else {
                samll.next=pre;
                samll=samll.next;
            }
            pre=pre.next;
        }
        large.next=null;
        samll.next=dumpy2.next;
        return dumpy1.next;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(4);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(2);
        ListNode s5 = new ListNode(5);
        ListNode s6 = new ListNode(2);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;
        s5.next = s6;

        ListNode res = per(s1, 3);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }
}

题目描述

给定一个非负整数N，返回N!结果的末尾为0的数量

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 阶乘问题
 * @Description TODO
 * @Date 2020/12/12 16:39
 * @Created by xjl
 */
public class 阶乘问题 {
    /**
     * @description TODO  阶乘结果的0和乘数的2和5有关，而2的个数远多于5，所以只要数5。而5，25，125的倍数是自相似的，所以可以用递归。时间复杂度O(logN)。
     * @param: n
     * @date: 2020/12/12 16:41
     * @return: long
     * @author: xjl
     */
    public long thenumberof0(long n) {
        long res = 0;
        while(n>0){
            n /= 5;
            res += n;
        }
        return res;
    }

    /**
     * @description TODO 数组中的1的个数
     * @param: n
     * @date: 2020/12/12 16:44
     * @return: long
     * @author: xjl
     */
    public long thenumberof1(int n) {
        int res = n;
        int count = 0;
        while (res != 0) {
            count++;
            res = res & (res - 1);
        }
        return count;
    }

    @Test
    public void test(){
        long l = thenumberof0(5);
        System.out.println(l);
    }
}

题目描述

给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。

设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。

package 名企高频面试题143;

/**
 * @Classname 是否包含子树
 * @Description TODO
 * @Date 2020/12/12 16:51
 * @Created by xjl
 */
public class 是否包含子树 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * @description TODO 给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
     * @param: root1
     * @param: root2
     * @date: 2020/12/12 16:53
     * @return: boolean
     * @author: xjl
     */
    public boolean isContains(TreeNode root1, TreeNode root2) {
        if (root2 == null) return true;   // t 为 null 一定都是 true
        if (root1 == null) return false;
        return isContains(root1.left, root2) || isContains(root1.right, root2) || isSameTree(root1,root2);
    }

    public boolean isSameTree(TreeNode s, TreeNode t){
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}

题目描述

给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 转化为的Nj进制数字
 * @Description TODO
 * @Date 2020/12/12 17:59
 * @Created by xjl
 */
public class 转化为的N进制数字 {

    public String solve(int M, int N) {
        if (M == 0) return "0";
        String s = "0123456789ABCDEF";
        String res = "";
        boolean f = false;
        if (M < 0) {
            f = true;
            M = -M;
        }
        while (M != 0) {
            res += s.charAt(M % N);
            M /= N;
        }
        if (f) res += "-";
        StringBuffer sb = new StringBuffer(res);
        return sb.reverse().toString();
    }

    @Test
    public void test() {
        String solve = solve(7, 2);
        System.out.println(solve);
    }
}