&：按位与。
|：按位或。
~：按位非。
^：按位异或。
<<：左位移运算符。
>>：右位移运算符。
>>>：无符号右移运算符。
1. 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
int a = n&1;
count = a==1 ? count+1 : count;
n = n >> 1;
}
return count;
}
没有通过测试
因为先要和1进行与&运算，求出最后一位
再向右移位一次
答案：
public int NumberOf1(int n) {
int count = 0;
while(n!=0)
{
n = n&(n-1);
count++;
}
return count;
}
解释：
一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
二叉树
public int kthSmallest(TreeNode root, int k) {
List<Integer> list = new ArrayList<Integer>();
if(root.left == null && root.right == null) {
return root.val;
}
list.add(root.val);
bianli(root,list);
Collections.sort(list);
return list.get(k-1);
}
private void bianli(TreeNode root,List<Integer> list) {
if(root.left != null) {
list.add(root.left.val);
bianli(root.left,list);
}
if(root.right != null) {
list.add(root.right.val);
bianli(root.right,list);
}
return;
}
正确解答为中序遍历，这样可以省略排序环节
2.1 从上往下打印二叉树
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null) {
return list;
}
if(root.left==null && root.right==null) {
list.add(root.val);
return list;
}
queue.add(root);
while(!queue.isEmpty()) {
TreeNode st = queue.poll();
list.add(st.val);
if(st.left != null) {
queue.add(st.left);
}
if(st.right != null) {
queue.add(st.right);
}
}
return list;
}
2.2 二叉树打印成多行
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot == null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode last = pRoot;
TreeNode nlast =null;
queue.offer(pRoot);
ArrayList<Integer> tmp = new ArrayList<>();
while (!queue.isEmpty()) {
pRoot = queue.poll();
tmp.add(pRoot.val);//出队列，就把他左右孩子入队列，
//此时，下一层的最右要跟着更新
if (pRoot.left!=null) {
queue.offer(pRoot.left);
nlast = pRoot.left;
}
if (pRoot.right!=null) {
queue.offer(pRoot.right);
nlast = pRoot.right;
}
//如果到了本层的最右，就把这一层结果放入。注意最后一层时，isempty不成立，
//最后一层的结果要单独放入。
if (pRoot == last && !queue.isEmpty()) {
res.add(new ArrayList<>(tmp));
last = nlast;
tmp.clear();
}
}
res.add(new ArrayList<>(tmp));
return res;
}
2.3 按之字形顺序打印二叉树
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot == null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode last = pRoot;
TreeNode nlast =null;
queue.offer(pRoot);
ArrayList<Integer> tmp = new ArrayList<>();
int flag = 0;
while (!queue.isEmpty()) {
if(flag == 1) {
pRoot = queue.poll();
tmp.add(pRoot.val);//出队列，就把他左右孩子入队列，
//此时，下一层的最右要跟着更新
if (pRoot.left!=null) {
queue.offer(pRoot.left);
nlast = pRoot.left;
}
if (pRoot.right!=null) {
queue.offer(pRoot.right);
nlast = pRoot.right;
}
//如果到了本层的最右，就把这一层结果放入。注意最后一层时，isempty不成立，
//最后一层的结果要单独放入。
if (pRoot == last && !queue.isEmpty()) {
Collections.reverse(tmp);
res.add(new ArrayList<>(tmp));
last = nlast;
tmp.clear();
flag = flag == 1 ? 0 : 1;
}
}
else {
pRoot = queue.poll();
tmp.add(pRoot.val);//出队列，就把他左右孩子入队列，
//此时，下一层的最右要跟着更新
if (pRoot.left!=null) {
queue.offer(pRoot.left);
nlast = pRoot.left;
}
if (pRoot.right!=null) {
queue.offer(pRoot.right);
nlast = pRoot.right;
}
//如果到了本层的最右，就把这一层结果放入。注意最后一层时，isempty不成立，
//最后一层的结果要单独放入。
if (pRoot == last && !queue.isEmpty()) {
res.add(new ArrayList<>(tmp));
last = nlast;
tmp.clear();
flag = flag == 1 ? 0 : 1;
}
}
}
if(flag == 0) {
res.add(new ArrayList<>(tmp));
}else {
Collections.reverse(tmp);
res.add(new ArrayList<>(tmp));
}
return res;
}
和上一个题一样的解法，加了一个flag标记为看是否需要反转list
- 数据流中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
import java.util.PriorityQueue;
public class MedianFinder {
/**
* 当前大顶堆和小顶堆的元素个数之和
*/
private int count;
private PriorityQueue<Integer> maxheap;
private PriorityQueue<Integer> minheap;
/**
* initialize your data structure here.
*/
public MedianFinder() {
count = 0;
maxheap = new PriorityQueue<>((x, y) -> y - x);
minheap = new PriorityQueue<>();
}
public void addNum(int num) {
count += 1;
maxheap.offer(num);
minheap.add(maxheap.poll());
// 如果两个堆合起来的元素个数是奇数，小顶堆要拿出堆顶元素给大顶堆
if ((count & 1) != 0) {
maxheap.add(minheap.poll());
}
}
public double findMedian() {
if ((count & 1) == 0) {
// 如果两个堆合起来的元素个数是偶数，数据流的中位数就是各自堆顶元素的平均值
return (double) (maxheap.peek() + minheap.peek()) / 2;
} else {
// 如果两个堆合起来的元素个数是奇数，数据流的中位数大顶堆的堆顶元素
return (double) maxheap.peek();
}
}
}
PriorityQueue是一个基于优先级堆的无界队列。它的元素是按照自然顺序排序的。在创建元素的时候，我们给它一个一个负责排序的比较器。PriorityQueue不允许null值，因为
它们没有自然排序，或者说没有任何相关联的比较器。最后PriorityQueue不是线程安全的，出对和入队的时间复杂度都是O(log(n))
Java 比较器Comparator和Comparable的使用和区别
- 二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
private ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> path = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) {
return res;
}
findPath(root,target);
return res;
}
private void findPath(TreeNode root, int target) {
path.add(root.val);
if(root.val == target && root.left == null && root.right == null) {
res.add(new ArrayList<Integer>(path));
}
if(root.left != null) {
findPath(root.left,target-root.val);
}
if(root.right != null) {
findPath(root.right,target-root.val);
}
path.remove(path.size()-1);
return;
}
尤其注意 new 一个新的 ArrayList 路径，不然最后啥也不剩
- 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre == null || in == null) {
return null;
}
if(pre.length == 0 || in.length == 0) {
return null;
}
if(pre.length != in.length) {
return null;
}
TreeNode root = new TreeNode(pre[0]);//前序遍历第一个值为根节点
for(int i=0;i<in.length;i++) {
if(pre[0] == in[i]) {
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),
Arrays.copyOfRange(in, i+1, in.length));
}
}
return root;
}
二叉树遍历
B
A C
前序遍历：BAC
中序遍历：ABC
后序遍历：ACB
- 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
//先从根开始再把左作为根，再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
//从根可以认为是一颗树，从左子树开始又可以认为是另外一颗树，从右子树开始又是另外一棵树。
//本函数就是判断这一整颗树包不包含树2，如果从根开始的不包含，就从左子树作为根节点开始判断，
//再不包含从右子树作为根节点开始判断。
//是整体算法递归流程控制。
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean res = false;
if (root1 != null && root2 != null) {
if(root1.val == root2.val){
res = doesTree1haveTree2(root1,root2);
}
if(!res)
{
res = HasSubtree(root1.left, root2);
}
if(!res)
{
res = HasSubtree(root1.right, root2);
}
}
return res;
}
//本函数，判断从当前的节点 ，开始两个树能不能对应上，是具体的比对过程
public boolean doesTree1haveTree2(TreeNode root1,TreeNode root2) {
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root1.val != root2.val){
return false;
}
//如果根节点可以对应上，那么就去分别比对左子树和右子树是否对应上
return doesTree1haveTree2(root1.left, root2.left) && doesTree1haveTree2(root1.right, root2.right);
}
- 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
public class Solution {
/**
* 算法步骤
* 1.节点为空直接返回
* 2.如果这个节点的左右子树不为空，就交换。
* 3.递归对这个节点的左子树进行求镜像。对这个节点的右子树求镜像。
* @param root
*/
public void Mirror(TreeNode root){
if (root == null) {
return;
}
if(root.left != null || root.right != null) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}
- 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出Yes,否则输出No。
假设输入的数组的任意两个数字都互不相同。
public class Solution {
/**二叉搜索树的性质：
* 所有左子树的节点小于根节点，所有右子树的节点值大于根节点的值。
* 算法步骤：
* 1.后序遍历的最后一个值为root，在前面的数组中找到第一个大于root值的位置。
* 2.这个位置的前面是root的左子树，右边是右子树。然后左右子树分别进行这个递归操作。
* 3.其中，如果右边子树中有比root值小的直接返回false
* @param sequence
* @return
*/
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0)
return false;
return IsBST(sequence, 0, sequence.length -1);
}
public boolean IsBST(int [] sequence, int start, int end) {
if(start >= end) //注意这个条件的添加// 如果对应要处理的数据只有一个或者已经没
//有数据要处理（start>end）就返回true
return true;
int index = start;
for (; index < end; index++) {//寻找大于root的第一个节点，然后再分左右两部分
if(sequence[index] > sequence[end])
break;
}
for (int i = index; i < end; i++) {//若右子树有小于根节点的值，直接返回false
if (sequence[i] < sequence[end]) {
return false;
}
}
return IsBST(sequence, start, index-1) && IsBST(sequence, index, end-1);
}
}
- 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
TreeNode head = null;
TreeNode resultHead = null; //保存生成链表的头结点，便于程序返回
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return resultHead;
}
public void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree == null)
return;
ConvertSub(pRootOfTree.left);
if(head == null){
head = pRootOfTree;
resultHead = pRootOfTree;
}
else {
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
ConvertSub(pRootOfTree.right);
}
- 二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
public int TreeDepth(TreeNode root) {
if(root == null) {
return 0;
}
int count = 1;
List<Integer> list = new ArrayList<>();
MaxDepth(root.left,count,list);
MaxDepth(root.right,count,list);
Collections.sort(list);
return list.get(list.size()-1);
}
private void MaxDepth(TreeNode root, int count, List<Integer> list) {
// TODO 自动生成的方法存根
if(root == null) {
list.add(count);
return;
}
count++;
MaxDepth(root.left,count,list);
MaxDepth(root.right,count,list);
}
极致递归
public int TreeDepth(TreeNode root) {
if(root == null)
return 0;
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return left > right? left +1:right+1;
}
- 平衡二叉树\
输入一棵二叉树，判断该二叉树是否是平衡二叉树
描述：如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
利用上面自己的方法得到的list，然后最大减最小，最后得到的结果不对，因为最小和最大是在同一侧
利用上面的极致的递归
boolean isBalance = true;
public boolean IsBalanced_Solution(TreeNode root) {
lengthOfTree(root);
return isBalance;
}
private int lengthOfTree(TreeNode root) {
if (root == null)
return 0;
int left = lengthOfTree(root.left);
int right = lengthOfTree(root.right);
if (Math.abs(left - right) > 1)
isBalance = false;
return Math.max(left, right) + 1;
}
因为是每一个节点都判断最大深度，当我们来到根节点的左右节点对比时，如果出现差值大于1，一下子就发现了
- 二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null)
return null;
// 如果有右子树，则找右子树的最左节点
if (pNode.right != null) {
pNode = pNode.right;
// 如果此时pNode没有左子树，那么它就是下一个结点 ，就是最左边的了
//如果有左子树，那就在左子树找最左边的
while(pNode.left != null)
pNode = pNode.left;
return pNode;
}
//// 非跟结点，并且没有右子树
while(pNode.next != null) {
// 找到一个结点是该其父亲的左孩子 ,找到就是返回父节点作为后记
if (pNode.next.left == pNode)
return pNode.next;
//找不到这个左孩子的，就继续往上，next其实是parent
pNode = pNode.next;
}
return null;
}
看不懂题。。。
- 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
boolean isSymmetrical(TreeNode pRoot)
{
if (pRoot == null)
return true;
return isCommon(pRoot.left,pRoot.right);
}
public boolean isCommon(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null && rightNode == null)
return true;
if (leftNode != null && rightNode != null) {
return leftNode.val == rightNode.val &&
isCommon(leftNode.left, rightNode.right) &&
isCommon(leftNode.right, rightNode.left);
}
return false;
}
这最后的return有点doug lea的reentrantlock的感觉了
- 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
网友评论