nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

1、NC13 二叉树的最大深度

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
    }
}

实现

递归

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        if(root == null){
            return 0;
        }
        int maxL = 0; //左子树最大深度
        int maxR = 0; //右子树最大深度
        if(root.left != null){
            maxL = maxDepth(root.left);
        }
        if(root.right != null){
            maxR = maxDepth(root.right);
        }
        int max = maxL>maxR ? maxL+1 : maxR+1;
        return max;
    }
}

其他

【数据结构和算法】递归,BFS,DFS等3种实现方式_牛客博客 (nowcoder.net)

2、NC70 单链表的排序

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
    }
}

实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

import java.util.ArrayList;
import java.util.Comparator;
public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        //思路1:单链表构造为二叉树(小于根左子,大于根右子),中序遍历(左根右),迭代
        //思路2:遍历链表,取出数据构成数组/列表,数组/列表排序,重构链表
        if(head == null || head.next == null){
            return head;
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(head.val);
        while(head.next != null){
            list.add(head.next.val);
            head = head.next;
        }
        list.sort(Comparator.naturalOrder()); //自然顺序,即升序排序
        ListNode res = new ListNode(list.get(0));
        ListNode move = res;
        for(int i=1; i<list.size(); i++){
            ListNode temp = new ListNode(list.get(i));
            move.next = temp;
            move = move.next;
        }
        return res;
    }
}

其他1

    //参考1:值排序,不是真正做到链表排序,直接遍历整个链表,用一个数组存储所有的val,然后进行排序,最后将排序完的值赋值给链表
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while(temp != null){
            list.add(temp.val);
            temp = temp.next;
        }
        list.sort( (a,b)->{return a-b;} ); //lambda表达式
        ListNode temp2 = head;
        int i = 0;
        while(temp2 != null){
            temp2.val = list.get(i++);
            temp2 = temp2.next;
        }
        return head;
    }

其他2

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

    //参考2:先利用快慢指针找出链表的中点,然后分为两个链表,一直分,知道无法分为止,然后自底而上排序归并
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //利用快慢指针找到中点
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //分割为两个链表
        ListNode newHead = slow.next;
        slow.next = null;
        //利用递归将两个链表继续分割
        ListNode left = sortInList(head);
        ListNode right = sortInList(newHead);
        ListNode lHead = new ListNode(-1); //
        ListNode res = lHead; //
        //归并排序
        while(left!=null && right!=null){
            if(left.val < right.val){
                lHead.next = left;
                left = left.next;
            }else{
                lHead.next = right;
                right = right.next;
            }
            lHead = lHead.next;
        }
        //判断左右链表是否为空
        lHead.next = left!=null?left:right;
        return res.next;
    }

3、NC62 平衡二叉树

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

 

 nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        
    }
}

参考1

public class Solution {
    
    //参考1:平衡二叉树的左右子树也是平衡二叉树,那么所谓平衡就是左右子树的高度差不超过1
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;
    }
    
    public int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        if(left == -1){
            return -1; //如果发现子树不平衡之后就没有必要进行下面的高度的求解了
        }
        int right = depth(root.right);
        if(right == -1){
            return -1; //如果发现子树不平衡之后就没有必要进行下面的高度的求解了
        }
        if(left-right<-1 || left-right>1){ //Math.abs(left-right) > 1
            return -1;
        }else{
            return 1 + (left>right?left:right); //Math.max(left,right)
        }
    }
    
}

参考2

public class Solution {
    
    //参考2:与参考1解法差不多,本质一样
    //在使用递归求的深度后,其实可以在递归中,直接判断左右子树的差值。这时候就相当于多一个变量。
    boolean isBalanced = true;
    
    public boolean IsBalanced_Solution(TreeNode root) {
        depth(root);
        return isBalanced;
    }
    
    public int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        if(left == -1){
            return -1; //剪枝(不符合条件的,直接一直向上返回,没必要还去计算深度)
        }
        int right = depth(root.right);
        if(right == -1){
            return -1; //剪枝(不符合条件的,直接一直向上返回,没必要还去计算深度)
        }
        if(right-left>1 || left-right>1){ 
            isBalanced = false;
            return -1;
        }else{
            return left>right ? left+1 : right+1; 
        }
    }
    
}

4、NC73 数组中出现次数超过一半的数字

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

 nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        
    }
}

实现

import java.util.HashMap;

public class Solution {
    
    public int MoreThanHalfNum_Solution(int [] array) {
        int length = array.length;
        if(length == 0){
            return -1;
        }
        if(length == 1){
            return array[0];
        }
        
        int half = 0;
        if(length%2 == 0){
            half = length/2;
        }else{
            half = length/2+1;
        }
        
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<length; i++){
            int key = array[i];
            if(!map.containsKey(key)){
                map.put(key, 1);
            }else{
                int value = map.get(key);
                value++;
                if(value >= half){
                    res = key;
                    break;
                }
                map.put(key, value);
            }
            
        }
        
        return res;
    }
    
}

其他1

/*
用一般的排序也可以完成这道题目,但是如果那样完成的话就可能太简单了。
用preValue记录上一次访问的值,count表明当前值出现的次数,
如果下一个值和当前值相同那么count++;如果不同count--,
减到0的时候就要更换新的preValue值了,
因为如果存在超过数组长度一半的值,那么最后preValue一定会是该值。
*/
public class Solution {
    
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int preValue = array[0];
        int count = 1;
        for(int i=1; i<array.length; i++){
            if(array[i] == preValue){
                count++;
            }else{
                count--;
                if(count == 0){
                    preValue = array[i];
                    count = 1;
                }
            }
        }
        int num = 0;//需要判断是否真的是大于1半数,这一步骤是非常有必要的,因为我们的上一次遍历只是保证如果存在超过一半的数就是preValue,但不代表preValue一定会超过一半
        for(int i=0; i<array.length; i++){
            if(array[i] == preValue){
                num++;
            }
        }
        return (num > array.length/2) ? preValue : 0;
    }
    
}

其他2

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

其他3

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

 nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

 其他4

同我的解决思路

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

import java.util.*;

public class Solution {
    
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length == 0){
            return 0;
        }
        
        int len = array.length;
        int threshold = len/2;
        
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++){
            if(!map.keySet().contains(array[i])){
                map.put(array[i],1);
            }else{
                map.put(array[i],map.get(array[i])+1);
            }
        }
        for(Integer key: map.keySet()){
            if(map.get(key) > threshold){
                return key;
            }
        }
        
        return 0;
    }
    
}

5、NC112 进制转换

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

import java.util.*;


public class Solution {
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    public String solve (int M, int N) {
        // write code here
    }
}

参考1

    //算法思路: 除N取余,然后倒序排列,高位补零。
    public String solve (int M, int N) {
        if(M == 0){
            return "0";
        }
        String baseStr = "0123456789ABCDEF";
        StringBuffer sb = new StringBuffer();
        boolean flag = false;
        if(M < 0){
            flag = true;
            M = -M;
        }
        while(M != 0){
            sb.append(baseStr.charAt(M % N));
            M /= N;
        }
        if(flag){
            sb.append("-");
        }
        return sb.reverse().toString();
    }

参考2

参考1的解释

nowcoder-oj【面试高频TOP榜单-简单难度(4)5道】

 

上一篇:6道链表OJ


下一篇:OJ在线编程常见输入输出