package com.dengzm.lib;
/**
* @Description 054 二叉搜索树的第k大节点
*
* Created by deng on 2019/10/29.
*/
public class Jianzhi054 {
private static int index = 0;
public static void main(String[] args) {
BinaryTreeNode node2 = new BinaryTreeNode(2);
BinaryTreeNode node3 = new BinaryTreeNode(3);
BinaryTreeNode node4 = new BinaryTreeNode(4);
BinaryTreeNode node5 = new BinaryTreeNode(5);
BinaryTreeNode node6 = new BinaryTreeNode(6);
BinaryTreeNode node7 = new BinaryTreeNode(7);
BinaryTreeNode node8 = new BinaryTreeNode(8);
node5.setNodes(node3, node7);
node3.setNodes(node2, node4);
node7.setNodes(node6, node8);
System.out.println("The 6th Big Number is " + getKthNumberInBinaryTree(node5, 6).value);
}
/**
* 对二叉树进行中序遍历，得到的即为升序，即可得到第K大的数字
*
* @param root root
* @return Kth num
*/
private static BinaryTreeNode getKthNumberInBinaryTree(BinaryTreeNode root, int k) {
if (root == null || k < 1) {
return null;
}
index = 0;
return getKthNumCore(root, k);
}
private static BinaryTreeNode getKthNumCore(BinaryTreeNode root, int k) {
if (root == null) {
return null;
}
BinaryTreeNode temp = null;
// 如果有左子数，先遍历
if (root.left != null) {
temp = getKthNumCore(root.left, k);
}
// temp为null，代表此时遍历左子树后，未获得第K大的节点
// 此时，第一步，计算当前节点自身添加后是否满足
// 第二步，在自身不满足的情况下，遍历右子树
if (temp == null) {
index ++;
if (index == k) {
return root;
}
if (root.right != null) {
temp = getKthNumCore(root.right, k);
}
}
return temp;
}
static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
BinaryTreeNode(int value) {
this.value = value;
}
void setNodes(BinaryTreeNode left, BinaryTreeNode right) {
this.left = left;
this.right = right;
}
}
}
package com.dengzm.lib;
/**
* @Description 055 二叉树的深度
* 题目一：二叉树的深度
* 题目二：平衡二叉树 判断一棵树是否为平衡二叉树
*
* Created by deng on 2019/10/29.
*/
public class Jianzhi055 {
private static final int ERROR = -1;
public static void main(String[] args) {
BinaryTreeNode node2 = new BinaryTreeNode(2);
BinaryTreeNode node3 = new BinaryTreeNode(3);
BinaryTreeNode node4 = new BinaryTreeNode(4);
BinaryTreeNode node5 = new BinaryTreeNode(5);
BinaryTreeNode node6 = new BinaryTreeNode(6);
BinaryTreeNode node7 = new BinaryTreeNode(7);
BinaryTreeNode node8 = new BinaryTreeNode(8);
// BinaryTreeNode node9 = new BinaryTreeNode(9);
// BinaryTreeNode node10 = new BinaryTreeNode(10);
// BinaryTreeNode node11 = new BinaryTreeNode(11);
node5.setNodes(node3, node7);
node3.setNodes(node2, node4);
node7.setNodes(node6, node8);
// node8.setNodes(node9, node10);
// node10.setNodes(null, node11);
System.out.println("The depth of tree is " + getDepthOfBinaryTree(node5));
System.out.println("This tree is balanced ? Answer is " + isTreeBalanced(node5));
}
/**
* 题目一：二叉树的深度
* 简单的递归，较高的子数的深度+1
*
* @param root root node
* @return depth of tree
*/
private static int getDepthOfBinaryTree(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int left = getDepthOfBinaryTree(root.left);
int right = getDepthOfBinaryTree(root.right);
return left > right ? left + 1 : right + 1;
}
/**
* 题目二：平衡二叉树
* 与深度遍历类似，在遍历子树和返回深度时，增加了是否为平衡树的判断，并将-1作为不平衡的常量值
*
*
* @param root root
* @return is tree balanced
*/
private static boolean isTreeBalanced(BinaryTreeNode root) {
return getDepth(root) != ERROR;
}
private static int getDepth(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int left = getDepth(root.left);
if (left == ERROR) {
return ERROR;
}
int right = getDepth(root.right);
if (right == ERROR) {
return ERROR;
}
return Math.abs(left - right) > 1 ? ERROR : Math.max(left, right) + 1;
}
}
package com.dengzm.lib;
/**
* @Description 056 数组中数字出现的次数
* 题目一：数组中只出现一次的两个数字
* 一个整型数组里除了两个数字之外，其他数字都出现了两次，找出这两个数字，要求时间复杂度O(n),空间复杂度O(1)
* 题目二：数组中唯一只出现一次的数字
* 在一个数组中除一个数字只出现一次之外，其他数字都出现了三次，请找出那个只出现一次的数字
*
* Created by deng on 2019/10/31.
*/
public class Jianzhi056 {
public static void main(String[] args) {
int[] data1 = new int[] {1,1,2,2,3,4,4,5,6,6,7,7};
int[] data2 = new int[] {1,2};
int[] data3 = new int[] {1,2,3,3};
findNumsAppearOnce(data1);
findNumsAppearOnce(data2);
findNumsAppearOnce(data3);
int[] data4 = new int[] {1,1,1,2,2,2,3,4,4,4,5,5,5};
int[] data5 = new int[] {1,1,1,2};
int[] data6 = new int[] {1,2,1,1,2,3,2,4,5,4,5,4,5};
System.out.println("single num is " + findNumberAppearOnce(data4));
System.out.println("single num is " + findNumberAppearOnce(data5));
System.out.println("single num is " + findNumberAppearOnce(data6));
}
/**
* 题目一 思路
* 相同数字进行异或为0，将所有数字进行异或，得到的即为两个不同的数字的异或
* 不同的数字的异或，二进制中一定会有一位为1，找到第一个为1的位，通过该位将数组分堆异或，即可得到两个数字
*
* @param data data
*/
private static void findNumsAppearOnce(int[] data) {
if (data == null || data.length < 2) {
System.out.println("data is invalid");
return;
}
int result = 0;
for (int i : data) {
result ^= i;
}
int indexBitOfOne = findFirstBitIs1(result);
if (indexBitOfOne == -1) {
System.out.println("sth is wrong with 'data'");
return;
}
int num1 = 0;
int num2 = 0;
for (int i : data) {
if (isBit1(i, indexBitOfOne)) {
num1 ^= i;
} else {
num2 ^= i;
}
}
System.out.println("The numbers are " + num1 + " and " + num2);
}
/**
* 找到num二进制中第一个为1的位
*
* @param num num
* @return first 1 in bits
*/
private static int findFirstBitIs1(int num) {
if (num == 0) {
return -1;
}
int indexBit = 0;
while ((num & 1) == 0) {
num = num >> 1;
++ indexBit;
}
return indexBit;
}
private static boolean isBit1(int num, int indexBit) {
return ((num >> indexBit) & 1) == 1;
}
/**
* 题目二 思路
* 使用一个大小为32int数组，的将所有数字的各个位都加在一起，%3，得到的即为单独的数字的各个位
*
* @param data data
* @return num appeared once
*/
private static int findNumberAppearOnce(int[] data) {
if (data == null || data.length == 0) {
throw new RuntimeException("data is invalid");
}
// 数字的最高位，保存在数组的第一位
int[] bits = new int[32];
for (int i = 0; i < 32; i ++) {
bits[i] = 0;
}
for (int i : data) {
int bitMask = 1;
// 将各个位，放进数组
for (int j = 31; j >= 0; j --) {
int bit = bitMask & i;
if (bit != 0) {
bits[j] += 1;
}
bitMask = bitMask << 1;
}
}
// 计算数字
int result = 0;
for (int i = 0; i < 32; i ++) {
result = result << 1;
result += bits[i] % 3;
}
return result;
}
}
