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;
}
}
其他
【数据结构和算法】递归，BFS，DFS等3种实现方式_牛客博客 (nowcoder.net)
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<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
//参考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<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
其他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<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 进制转换
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的解释