import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int value){
this.val = value;
}
}
class ListNode
{
int val;
ListNode next;
public ListNode(int value){
this.val = value;
}
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
public class HelloWorld
{
public static String serilize(TreeNode root){
String res = "";
if(root == null) return res += "#!";
return res += root.val + "!" + serilize(root.left) + serilize(root.right);
}
// 1!2!3!#!#!4!#!#!5!6!#!#!7!#!#!
public static TreeNode deSerilize(String str){
if(str == null || str.length() < 1) return null;
String[] Strings = str.split("!");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i < Strings.length; i++){
queue.offer(Strings[i]);
}
return deSerilizeHelper(queue);
}
public static TreeNode deSerilizeHelper(Queue<String> queue){
String value = queue.poll();
if(value.equals("#")){
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(value));
root.left = deSerilizeHelper(queue);
root.right = deSerilizeHelper(queue);
return root;
}
public static ArrayList<ArrayList<Integer>> level(TreeNode root){
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
ArrayList<Integer> resTemp = new ArrayList<Integer>();
for(int i =0; i < size; i++){
TreeNode temp = queue.poll();
resTemp.add(temp.val);
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
res.add(resTemp);
}
return res;
}
public static void preOrder(TreeNode root){
if (root == null) return ;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
System.out.println(temp.val);
if (temp.left != null){
stack.push(temp.left);
}
if(temp.right != null){
stack.push(temp.right);
}
}
}
public static void inOrder(TreeNode root){
if (root == null) return ;
Stack<TreeNode> stack = new Stack<>();
while(!stack.isEmpty() || root != null){
if(root != null) {
stack.push(root);
root = root.left;
}else{
TreeNode temp = stack.pop();
System.out.println(temp.val);
root = temp.right;
}
}
}
public static void postOrder(TreeNode root){
if (root == null) return ;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> stackres = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
stackres.push(temp.val);
if (temp.left != null){
stack.push(temp.left);
}
if(temp.right != null){
stack.push(temp.right);
}
}
while(!stackres.isEmpty()){
System.out.println(stackres.pop());
}
}
public static ListNode reserveListNode(ListNode head){
if(head == null) return head;
ListNode pre = null;
ListNode next = null;
ListNode cur = head;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public static void printList(ListNode head){
if(head == null) return;
ListNode dunny = new ListNode(0);
dunny.next = head;
while(dunny.next != null){
System.out.println(dunny.next.val);
dunny = dunny.next;
}
}
public static int binarySearch(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(arr[mid] == target) return mid;
else if (arr[mid] > target){
right = mid - 1;
}else {
left = mid + 1;
}
}
return -1;
}
public static int binarySearchLeftIndex(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
int res = -1;
while(left <= right){
int mid = left + (right - left)/2;
if(arr[mid] == target) res = mid;
if (arr[mid] >= target){
right = mid - 1;
}else {
left = mid + 1;
}
}
return res;
}
public static int binarySearchRighrIndex(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
int res = -1;
while(left <= right){
int mid = left + (right - left)/2;
if(arr[mid] == target) res = mid;
// arr[mid] == target 与下面的 arr[mid] <= target 情况是独立的,
// 不是放在一个if else 里面,因为这里随时要更新res
if (arr[mid] <= target){
left = mid + 1;
}else {
right = mid - 1;
}
}
return res;
}
// 旋转的数组中是没有重复的数字的
public static int binarySearchInRotateArray(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(arr[mid] == target) return mid;
if(arr[mid] >= arr[left]){
// 因为上面已经判断了 arr[mid] == target 的这种情况,所以这里不需要再加上等于号了
if(target < arr[mid] && arr[left] <= target){
right = mid - 1;
}else{
left = mid + 1;
}
} else {
if(target > arr[mid] && arr[right] >= target){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}
// 旋转的数组中是有重复的数字的
public static int binarySearchInRotateArrayHasSameNum(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){
// 注意这里的 left 不能大于right 一直left++会存在越界的情况
// while里不可以让left等于right,因为如果等于的话 left会left++,这样的话就会超过了right,然而right就是数组的最右边界。
while(left < right && arr[left] == arr[right]) left++;
int mid = left + (right - left) / 2;
if(arr[mid] == target) return mid;
if(arr[mid] >= arr[left]){
// 因为上面已经判断了 arr[mid] == target 的这种情况,所以这里不需要再加上等于号了
if(target < arr[mid] && arr[left] <= target){
right = mid - 1;
}else{
left = mid + 1;
}
} else {
if(target > arr[mid] && arr[right] >= target){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}
public static ListNode deleteNode(ListNode head, int target){
//首先找到的是第一个不等于target值的节点 作为头结点
if(head == null) return head;
while(head != null ){
if(head.val != target){
break;
}
head = head.next;
}
//pre是作为待删除节点的前一个节点
ListNode pre = head;
ListNode cur = head;
while(cur != null){
if(cur.val == target){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return head;
}
static class myComparator implements Comparator<String>{
@Override
public int compare(String str1, String str2){
return (str1+str2).compareTo(str2+str1);
}
}
public static String minNumber(int[] num){
String resString = "";
int res = 0;
if (num == null || num.length < 1) return resString;
String [] strings = new String[num.length];
for(int i = 0; i < num.length; i++){
strings[i] = num[i]+"";
}
Arrays.sort(strings,new myComparator());
for(int i = 0; i < strings.length; i++){
resString += strings[i];
}
// res = Integer.parseInt(resString);
return resString;
}
//the first number not repeat char
public static char firstNotRepeatChar(String str){
char[] chars = str.toCharArray();
HashMap<Character,Integer> hashMap = new HashMap<>();
for(int i = 0; i < chars.length; i++){
if(!hashMap.containsKey(chars[i])){
hashMap.put(chars[i],1);
}else{
hashMap.put(chars[i],hashMap.get(chars[i])+1);
}
}
for(int i = 0; i < chars.length; i++){
if(hashMap.get(chars[i]) == 1) return chars[i];
}
return ' ';
}
//the number appearing only once
public static int numAppearingOnce(int[]arr){
if(arr == null || arr.length < 1) return 0;
int a = 0;
int b = 0;
for(int i = 0; i < arr.length; i++){
a = a ^ arr[i] & ~ b;
b = b ^ arr[i] & ~ a;
}
return a;
}
public static ListNode meetingNode(ListNode head){
// note that there must be a circle
if(head == null) return head;
ListNode fast = head;
ListNode slow = head;
while(fast != slow){
fast = fast.next.next;
slow = slow.next;
}
System.out.println(slow.val);
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
System.out.println(slow.val);
return fast;
}
public static String systemReadLine(){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
return str;
}
public static int widthOfBinaryTree(TreeNode root){
if(root == null) return 0;
LinkedList <Integer> lefts = new LinkedList<Integer>();
return widtOfBinaryTreeHelper(root, 1, 0, lefts);
}
public static int widtOfBinaryTreeHelper(TreeNode root, int id, int level, LinkedList<Integer> lefts){
if(root == null) return 0;
if(level == lefts.size()){
lefts.add(id);
}
return Math.max(id - lefts.get(level) + 1,
Math.max(widtOfBinaryTreeHelper(root.left, id * 2, level + 1, lefts),
widtOfBinaryTreeHelper(root.right, id * 2 + 1, level + 1, lefts)));
}
public static boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
if(root.left == null || root.right == null)
return root.val == sum;
else return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new LinkedList<>();
List<Integer> temp = new LinkedList<>();
if(root == null) return res;
pathSumHelper(root, sum, res, temp);
return res;
}
public static void pathSumHelper(TreeNode root, int sum, List<List<Integer>> res,
List<Integer> temp){
if(root == null) return;
temp.add(root.val);
if(root.left == null && root.right == null&&root.val == sum){
res.add(new LinkedList<>(temp));
}
pathSumHelper(root.left, sum - root.val, res, temp);
pathSumHelper(root.right, sum - root.val, res, temp);
temp.remove(temp.size() - 1);
}
// 不一定必须是从根节点到叶子节点
public int pathSum3(TreeNode root, int sum) {
if(root == null) return 0;
return pathSum3Helper(root, sum) + pathSum3(root.left, sum) + pathSum3(root.right, sum);
}
public int pathSum3Helper(TreeNode root, int sum ){
if(root == null) return 0;
int res = 0;
if(root.val == sum){
res++;
}
return res + pathSum3Helper(root.left, sum - root.val) + pathSum3Helper(root.right, sum - root.val);
}
// print all the path
public static List<List<Integer>> binaryTreePaths(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
List<Integer> resTemp = new ArrayList<>();
binaryTreePathHelper(root,resTemp,res);
return res;
}
public static void binaryTreePathHelper(TreeNode root,List<Integer> resTemp , List<List<Integer>> res){
if (root == null) return;
resTemp.add(root.val);
if (root.left == null && root.right== null){
res.add(new LinkedList<>(resTemp));
}
binaryTreePathHelper(root.left,resTemp,res);
binaryTreePathHelper(root.right,resTemp,res);
resTemp.remove(resTemp.size()-1);
}
//////////////////////////////////////////////////////////////////////////////////
public static boolean isValidArea(char[][] board, int x,int y){
if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;
return true;
}
public static boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0) return false;
if(word == null || word.length() == 0) return false;
boolean[][] visit = new boolean[board.length][board[0].length];
int[][] step = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(search(board, word, step, i, j, 0, visit) == true)
return true;
}
}
return false;
}
public static boolean search(char[][] board, String word,int[][] step, int x, int y, int index, boolean[][] visit){
if(index == word.length() - 1) return word.charAt(index) == board[x][y];
if(board[x][y] == word.charAt(index)){
visit[x][y] = true;
for(int i = 0; i < 4; i++){
int newx = x + step[i][0];
int newy = y + step[i][1];
if(isValidArea(board, newx, newy) && visit[newx][newy] == false){
if(search(board, word, step, newx, newy, index + 1, visit) == true) return true;
}
}
visit[x][y] = false;
}
return false;
}
/***
添加两个数据项:
以该节点为结尾的个数,可以达到查询是否存在某个字符串的功能
插入节点时,记录节点划过的次数,可以达到查询有多少个以某个字符串作为前缀的功
***/
public static TrieNode buildTrieTree(String[] words){
TrieNode root = new TrieNode();
for( String word : words){
TrieNode p = root;
for(char c : word.toCharArray()){
int i = c - 'a';
// 如果没有的节点 需要建立出来
if(p.next[i] == null) {
p.next[i] = new TrieNode();
}
p = p.next[i];
}
p.word = word;
}
return root;
}
// pre and inorder rebuilt the tree
public static TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null) return null;
HashMap<Integer,Integer> hashMap = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
hashMap.put(inorder[i],i);
}
return buildTreeHelper(preorder, 0, preorder.length -1, 0, inorder.length -1,hashMap);
}
// 0 1 2 3 4 5 6 7 8
// 1 2 4 5 8 9 3 6 7
// 4 2 8 5 9 1 6 3 7
public static TreeNode buildTreeHelper(int[] preorder,int pi, int pj, int oi,int oj,
HashMap<Integer,Integer> hashMap){
if(pi > pj) return null;
int index = hashMap.get(preorder[pi]);
TreeNode root = new TreeNode(preorder[pi]);
root.left = buildTreeHelper(preorder,pi + 1, pi + index - oi, oi, index - 1, hashMap);
root.right = buildTreeHelper(preorder,pi + index - oi + 1, pj, index + 1, oj, hashMap);
return root;
}
// find the largerst product of the subArray
public static int maxProduct(int[] nums) {
// surpose nums is not null and has number
int max = nums[0];
int min = nums[0];
int res = nums[0];
for(int i = 1; i < nums.length; i++){
int temp = max;
//attention:这里的max必须记录下来
//下含有nums[i]本身为最大值的一种情况,因此这里求的子数组并非是从下标0开始的
max = Math.max( Math.max(nums[i] * max, nums[i] * min),nums[i]);
min = Math.min( Math.min(nums[i] * min, nums[i] * temp),nums[i]);
if(res < max) res = max;
}
return res;
}
// 子数组的最大的累加和
// Max{arr[i],dp[i - 1] + arr[i]}
// dp[i] 表示以i为结尾的最大的子数组
public static int maxSum(int[] arr){
if(arr == null || arr.length < 1) return 0;
int[] dp = new int[arr.length];
int res = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++){
dp[i] = Math.max(arr[i],(i - 1 >= 0)?dp[i - 1] + arr[i]:Integer.MIN_VALUE);
res = Math.max(res, dp[i]);
}
return res;
}
public static int maxSum2(int[] arr){
if(arr == null || arr.length < 1) return 0;
int cur = arr[0];
int res = arr[0];
for (int i = 1; i < arr.length; i++){
cur = Math.max(arr[i],cur + arr[i]);
res = Math.max(res, cur);
}
return res;
}
// 这种的思路与上面的思路有所不同,
// cur从0 ... arr.length -1
// 每次cur 与当前的值相加,如果cur累加为负数就设为0
// res 记录max的最大值即可
public static int maxSum3(int[] arr){
if(arr == null || arr.length < 1) return 0;
int cur = 0;
int res = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++){
cur = cur + arr[i];
res = Math.max(res, cur);
cur = cur > 0 ? cur : 0;
}
return res;
}
/**
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
*/
public int maxSubArray(int[] nums) {
int curSum = nums[0];
int resSum = nums[0];
for (int i = 1;i<nums.length;i++){
curSum = Math.max(curSum+nums[i],nums[i]);
resSum = Math.max(curSum,resSum);
}
return resSum;
}
public int maxProfit(int[] prices) {
if (prices ==null||prices.length==0) return 0;
int[] diff = new int[prices.length];
diff[0] = 0;
for (int i = 1 ; i< prices.length ;i++){
diff[i] = prices[i]-prices[i-1];
}
return maxSubArray(diff);
}
// 双指针 当arr[left] > arr[right]时候 把left更新为right
// 因为如果arr[left] > arr[right] ,说明以right为开头可以获得更大的差值
public static int maxProfit2(int [] arr){
if(arr == null || arr.length < 1) return 0;
int left = 0;
int right = 1;
int res = 0;
while(right < arr.length){
if(arr[left] > arr[right]){
left = right;
right++;
continue;
}
res = Math.max(res, arr[right] - arr[left]);
right++;
}
return res;
}
/*
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
*/
//计算所有的prices[i]<prices[i+1]的差值之和。
public int maxProfit3(int[] prices) {
int maxProfit =0;
if(prices.length<1) return maxProfit;
for(int i=0;i<prices.length-1;i++){
if(prices[i]<prices[i+1]){
maxProfit+=prices[i+1]-prices[i];
}
}
return maxProfit;
}
// 创建一个优先队列,堆,按照数组中的两个元素之和为递增的顺序
public static PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] + o1[1] - o2[0] - o2[1];
}
});
// LIS Longest Increasing Subsequence
public static int LIS(int [] nums){
if(nums == null || nums.length < 1) return 0;
int [] arr = new int[nums.length];
for(int i = 0; i < nums.length; i++){
arr[i] = 1;
}
for(int i = 1; i < nums.length; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
arr[i] = Math.max(arr[i], arr[j] + 1);
}
}
}
int res = 1;
for(int i =0; i < nums.length; i++){
res = Math.max(res,arr[i]);
System.out.println(res);
}
System.out.println();
return res;
}
public static void testComInt(int[] arr1, int [] arr2){
if(arr1 == null || arr2 ==null) return;
//PriorityQueue<int[]> queue = new PriorityQueue<int[]>();
for(int i = 0; i < arr1.length; i++){
for(int j = 0; j < arr2.length; j++){
priorityQueue.offer(new int[]{arr1[i], arr2[j]});
}
}
while(!priorityQueue.isEmpty()){
int [] temp = priorityQueue.poll();
System.out.print(temp[0]+ " ");
System.out.println(temp[1]);
}
}
public static int maxSubArrLength(int[] arr ,int aim){
if(arr == null || arr.length < 1) return 0;
HashMap<Integer> hashMap = new HashMap<>();
// 注意这里必须要加上<0,-1>
hashMap.put(0,-1);
int sum = 0;
for(int i = 0; i < arr.length; i++){
sum += arr[i];
if(hashMap.containsKey(sum - aim)){
// i - hashMap.get(sum - aim) + 1 这里不需要加1
res = Math.max(max, i - hashMap.get(sum - aim) + 1);
}
// 为什么不是直接put()呢?
// 因为要求最长的子数组,那么i的值越小越好,因此不要覆盖原来的值
// 这里的hashMap.push操作必须放在后面,例如如果对于arr[] = {1},求 aim = 0;
// <0, -1> <1, 1> 那么sum - aim = 0 是包函在hashMap中的,但是实际上,arr里面并没有0的存在
if(!hashMap.containsKey(sum)){
hashMap.put(sum, i);
}
}
return res;
}
public static void main(String[] args)
{
// 1
// 2 5
// 3 4 6 7
// 1!2!3!#!#!4!#!#!5!6!#!#!7!#!#!
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
/* String str = serilize(root);
System.out.println(str);
TreeNode temp = deSerilize(str);
str = serilize(root);
System.out.println(str);
*/
// System.out.println(level(root));
// preOrder(root);
// postOrder(root);
//1 - 2 - 3 - 4 - 5 - 6 - 7
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);
head.next.next.next.next.next.next = new ListNode(7);
head.next.next.next.next.next.next = head.next;
//head = reserveListNode(head);
//printList(head);
//int[] arr = {3,6,6,3,3,4,111,5,6,4,4,5,5};
//System.out.println(binarySearch(arr,5));
//System.out.println(binarySearchInRotateArray(arr,7));
//head = deleteNode(head,3);
//printList(head);
//String str = "101213142";
//System.out.println( firstNotRepeatChar(str) );
//printList(head);
//System.out.println(meetingNode(head).val);
/// System.out.println(systemReadLine());
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。