阅读 68

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

1、NC13 二叉树的最大深度

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
    }
}

实现

递归

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;
    }
}

其他

2、NC70 单链表的排序

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 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){
            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 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

    //参考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 平衡二叉树

 

  

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 数组中出现次数超过一半的数字

  

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 map = new HashMap<>();
        
        for(int i=0; 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){
            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){
            if(array[i] == preValue){
                num++;
            }
        }
        return (num > array.length/2) ? preValue : 0;
    }
    
}

其他2

其他3

 

 其他4

同我的解决思路

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 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 进制转换

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的解释

 

原文：https://www.cnblogs.com/yppah/p/15311977.html
文章分类
代码人生
文章标签
nowcoder
oj
高频
top
榜单
难度
版权声明：本站是系统测试站点，无实际运营。本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 XXXXXXo@163.com 举报，一经查实，本站将立刻删除。
相关推荐