36题解–两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思路解析
这里我们需要明白如果两个链表有公共的节点，那么这两个链表应该是这样的
我这里选择的先将两个链表的元素分别存入两个list之中，之后再比较记录下公共节点在list1中的位置，之后再将list1剩下的节点串起来返回即可。
源代码
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ import java.util.ArrayList; import java.util.List; public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { int flag=-1; if(pHead1==null||pHead2==null) return null; List<ListNode>list1=new ArrayList<ListNode>(); List<Integer>list2=new ArrayList<Integer>(); ListNode node1=pHead1; while(node1!=null) { list1.add(new ListNode(node1.val)); if(node1.next!=null) node1=node1.next; else break; } while(pHead2!=null) { list2.add(pHead2.val); if(pHead2.next!=null) pHead2=pHead2.next; else break; } //这里要注意break只能跳出一层循环也就是一层for，while循环，所以这里我进行了标注，否则无法跳出这个双层循环 a:for(int i=0;i<list1.size();i++) { for(int j=0;j<list2.size();j++) { if(list1.get(i).val==list2.get(j)) { flag=i; break a; } } } if(flag>-1) { //将标记点之后的节点都串起来 for(int i=flag;i<list1.size()-1;i++) list1.get(i).next=list1.get(i+1); return list1.get(flag); } else return null; } }
37题解–数字在升序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
思路解析
暴力即可，但是又不用一直暴力，因为此题是有序的数组，所以我们匹配到第一个符合的数开始计数，当数据不同时即跳出循环。
源代码
public class Solution { public int GetNumberOfK(int [] array , int k) { int count=0; for(int i=0;i<array.length;i++) { if(array[i]==k) count++; //注意count>0，如果不写，可能跑第一个元素就直接跳出循环了 //count>0是为了保证在查找到该数的情况下已经没有所以才跳出循环 if(array[i]!=k&&count>0) break; } return count; } }
38题解–二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路解析
这里我用的是两个队列来实现求深度的操作的通过下面的图来模拟给大家看一遍。
相信有这张图大家就好理解了。
源代码
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.LinkedList; import java.util.Queue; public class Solution { int count=0; public int TreeDepth(TreeNode root) { int count=0; Queue<TreeNode> queue1=new LinkedList<TreeNode>(); Queue<TreeNode> queue2=new LinkedList<TreeNode>(); if(root==null) return 0; queue2.add(root); while(!queue2.isEmpty()) { count++; for(TreeNode node:queue2) queue1.add(node); queue2.clear(); //通过queue1将节点的左孩子与右孩子节点再次压入queue2中 for(TreeNode node:queue1) { //这句判断是避免孩子节点为空，而报空指针异常 if(node.left!=null) queue2.add(node.left); if(node.right!=null) queue2.add(node.right); } queue1.clear(); } return count; } }
39题解–平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
思路解析
首先我们需要理解什么是平衡树
平衡树就是指任意节点的左子树与右子树的高度的差值要小于等于1，看到这里，想必大家也能看出来，这一题我们需要用到上面的方法，我们可以递归检查每一个节点，计算出以该节点的左孩子为根节点的二叉树的高度以及以该节点的右孩子为根节点的二叉树的高度，然后比较他们的差值即可判断是否为平衡树。
源代码
import java.util.LinkedList; import java.util.Queue; public class Solution { public int TreeDepth(TreeNode root) { int count=0; Queue<TreeNode> queue1=new LinkedList<TreeNode>(); Queue<TreeNode> queue2=new LinkedList<TreeNode>(); if(root==null) return 0; queue2.add(root); while(!queue2.isEmpty()) { count++; for(TreeNode node:queue2) queue1.add(node); queue2.clear(); for(TreeNode node:queue1) { if(node.left!=null) queue2.add(node.left); if(node.right!=null) queue2.add(node.right); } queue1.clear(); } return count; } public boolean IsBalanced_Solution(TreeNode root) { if(root==null) return true; //判断是否为平衡树 int cha=Math.abs(TreeDepth(root.left)-TreeDepth(root.right)); if(cha>1) return false; //递归检查左孩子节点 if(root.left!=null) IsBalanced_Solution(root.left); //递归检查右孩子节点 if(root.right!=null) IsBalanced_Solution(root.right); return true; } }
40题解–数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路解析
这题的原理和第34题类似，就不过多说了，主要是对象的部分属性发生了改变，不在包括数组下标这个属性。
源代码
//num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class Solution { public class Node { int val; int count; Node(int val) { this.val =val; this.count=1; } } public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { List<Node>list=new ArrayList<Node>(); Set<Integer>set=new HashSet<Integer>(); List<Integer>list1=new ArrayList<Integer>(); for(int i=0;i<array.length;i++) { if(!set.contains(array[i])) { set.add(array[i]); Node node=new Node(array[i]); list.add(node); } else { for(int j=0;j<list.size();j++) { if(list.get(j).val==array[i]) list.get(j).count++; } } } for(int i=0;i<list.size();i++) { if(list.get(i).count==1) list1.add(i); } num1[0]=list.get(list1.get(0)).val; num2[0]=list.get(list1.get(1)).val; } }
