RSS
SITEMAP
Articles
-
二分法使用无符号位右移运算求解上中位数
获取中间值的方式一般是 int mid = left + (right-left)/2; 如果要求偶数时中位数取后一位时，需要将（right-left+1） 效率更高如下： int mid = left + ((right-left)>>1); 1.有符号右移 >> 有符号右移：右移之后，左边补上符号为，正数补0，负数补1. 2.无符号位右移 >>> 无符号右移： 右移之后， 无论该数是正数还是负数， 右移之后左边都是补上0。 3.左移 << 左移不区分有符号和无符号， 都是左移之后右边补上0， 最左边的符号位也直接移走。 4.计算除法时（2的n次方）可以使用有符号的右移 20 的二进制位 10100 有符号位右移2位后为 101 十进制解释表示为 20⁄4=5（取整） 20 的二进制位 10100 左移2位后 1010000 十进制结果为81 5.判奇数偶数的方法 (num & 1) == 0表示为偶数 (num & 1) == 1表示为奇数 这里注意一个遇到的坑 使用 int mid = left + ((right-left)>>1); 时切记+号后面是加一个整体，因此需要将((right-left)>>1)括起来。 6. -
二叉树的镜像问题
题目描述如下图所示： 解题思路：利用栈的先进后出特性去做；也可以利用队列去做，只要保证right先进队列就行 import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public void Mirror(TreeNode root) { if(root==null)return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.isEmpty()){ TreeNode tn = stack.pop(); if(tn.left != null||tn.right != null){ TreeNode temp = tn.left; tn.left = tn.right; tn.right = temp; } if(tn. -
扑克牌问题
题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。 输入：[0,3,2,6,4] 输出：true 解题思路： 我们分两种情况考虑， 一. 如果vector中不包含0的情况： 那么如何判断呢？因为需要是顺子，所以首先不能有重复值， 如果没有重复值，那么形如[1 2 3 4 5] [5 6 7 8 9]， 会发现最大值与最小值的差值应该小于5. 二. 如果数组中包含0： 发现除去0后的值，判断方法和1中是一样的。 所以根据如上两个条件，算法过程如下： 1. 初始化一个set，最大值max_ = 0, 最小值min_ = 14 2. 遍历数组， 对于大于0的整数，没有在set中出现，则加入到set中，同时更新max, min 3. 如果出现在了set中，直接返回false 4. 数组遍历完，最后再判断一下最大值与最小值的差值是否小于5 方法1 使用set集合，利用set集合不可重复特性解决问题 public boolean isContinuous(int [] numbers) { if(numbers==null || numbers.length==0) return false; Set<Integer> set = new HashSet<>(); int max = 0,min = 14; for(int num:numbers){ if(num>0){ if(set. -
旋转数组的问题
1.数组一次旋转的问题 题目描述： 1.1 题目分析 处于递增：low上移 处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值） 其余情况：low++缩小范围 1.2 根据算法分析，编写程序实现如下 public int minNumberInRotateArray(int [] array) { int left = 0,right = array.length-1,mid; while(left<right){ mid = left + ((right-left)>>1); if(array[mid]>array[right]){ left = mid+1; }else{ right = mid; } } return array[right]; } 2. 数组变换找目标值的问题 题目描述：给出一个转动过的有序数组，你事先不知道该数组转动了多少 (例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2). 在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。 假设数组中不存在重复项。 -
在无序数组中找出最小的正整数
/** * return the min number * @param arr int整型一维数组 the array * @return int整型 */ public int minNumberdisappered (int[] arr) { // write code here Arrays.sort(arr); int min = 1; for(int i = 0;i<arr.length;i++){ if(arr[i]==min) min++; } return min; }
