点击刷新
2018-2-25
面试题7：重建二叉树
根据前序遍历和中序遍历重建二叉树。
思路：根据前序遍历第一个作为根节点，在中序遍历中划分为左子树和右子树。递归处理。
边界判断需要小心。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 12 if (pre == null || in == null || pre.length != in.length) { 13 return null; 14 } 15 TreeNode res = reConstr(pre, 0, pre.length - 1, in, 0, in.length - 1); 16 return res; 17 } 18 private TreeNode reConstr(int[] pre,int startPre, int endPre, int[] in, int startIn,int endIn) { 19 if ((startPre > endPre) || (startIn > endIn)) { 20 return null; 21 } 22 int node = pre[startPre]; 23 int pos = startIn; 24 for (int i = startIn; i <= endIn; i++) { 25 if (in[i] == node) { 26 pos = i; 27 break; 28 } 29 } 30 TreeNode res = new TreeNode(pre[startPre]); 31 int countLeft = pos - startIn; 32 res.left = reConstr(pre, startPre + 1, startPre + countLeft,in, startIn, pos - 1); 33 res.right = reConstr(pre,startPre + countLeft + 1, endPre,in,pos + 1, endIn); 34 return res; 35 } 36 }
面试题8：二叉树的下一个节点
给定二叉树和其中一个节点，找出中序遍历的下一个节点。（有指向父节点的指针）
思路：思路要清晰
中序遍历：左-中-右
①判空
②如果该节点存在右子树，则返回右子树
③不存在右子树，则往上找，直到找到一个点，是其父节点的左节点，返回该父节点。
④找到根节点都不存在这样的父节点，则说明该点是最后一个点，返回空。
1 /* 2 public class TreeLinkNode { 3 int val; 4 TreeLinkNode left = null; 5 TreeLinkNode right = null; 6 TreeLinkNode next = null; 7 8 TreeLinkNode(int val) { 9 this.val = val; 10 } 11 } 12 */ 13 public class Solution { 14 public TreeLinkNode GetNext(TreeLinkNode pNode) 15 { 16 if (pNode == null) { 17 return null; 18 } 19 if (pNode.right != null) { 20 TreeLinkNode temp = pNode.right; 21 while (temp != null && temp.left != null) { 22 temp = temp.left; 23 } 24 return temp; 25 } 26 if (pNode.next != null && pNode.next.left == pNode) { 27 return pNode.next; 28 } 29 while (pNode.next != null && pNode.next.right == pNode) { 30 pNode = pNode.next; 31 } 32 if (pNode.next == null) { 33 return null; 34 } 35 return pNode.next; 36 37 } 38 }
我的写法，太复杂，而且会出现空指针异常，因为比如 if (pNode.next != null && pNode.next.left == pNode)
需要先判断pNode.next是否为空，才能判断pNode.next.left
答案写法：
1 链接：https://www.nowcoder.net/questionTerminal/9023a0c988684a53960365b889ceaf5e 2 来源：牛客网 3 4 public class Solution { 5 TreeLinkNode GetNext(TreeLinkNode node) 6 { 7 if(node==null) return null; 8 if(node.right!=null){ //如果有右子树，则找右子树的最左节点 9 node = node.right; 10 while(node.left!=null) node = node.left; 11 return node; 12 } 13 while(node.next!=null){ //没右子树，则找第一个当前节点是父节点左孩子的节点 14 if(node.next.left==node) return node.next; 15 node = node.next; 16 } 17 return null; //退到了根节点仍没找到，则返回null 18 } 19 }
面试题9：用两个栈实现队列
思路：不需要每次都倒腾过去。
push进stack1，pop可以pop到stack2中，从stack2取。
但是只要stack2不空，就可以一直从stack2取，push进去放入stack1。
2018-2-6
面试题10：斐波那契数列
①递归做法：n的指数上升。
②动态规划：T: O(n) S:O(1)
f[0] = 0 f[1] = 1 f[n] = f[n-1]+f[n-2]
1 public class Solution { 2 public int Fibonacci(int n) { 3 if (n <= 1) { 4 return n; 5 } 6 int[] f = new int[n]; 7 f[0] = 0; 8 f[1] = 1; 9 for (int i = 2; i < n; i++) { 10 f[i] = f[i - 1] + f[i - 2]; 11 } 12 return f[n - 1] + f[n - 2]; 13 } 14 }
虽然是用动态规划做，但是不需要新建那么大的数组空间int[] f = new int[n];仅需要fn-2 fn-1两个变量即可。
1 public class Solution { 2 public int Fibonacci(int n) { 3 if (n < 2) { 4 return n; 5 } 6 int fnMinus1 = 1; 7 int fnMinus2 = 0; 8 int fn = 1; 9 for (int i = 2; i <= n; i++) { 10 fn = fnMinus1 + fnMinus2; 11 fnMinus2 = fnMinus1; //先改fnMinus2！ 12 fnMinus1 = fn; 13 } 14 return fn; 15 } 16 }
③数学公式 T：O(logn)
2018-2-8
面试题11：旋转数组的最小数字
面试题12：矩阵中的路径
答案的dfs做法
1 public class Solution { 2 public boolean hasPath(char[] matrix, int rows, int cols, char[] str) 3 { 4 if(matrix == null || matrix.length < rows * cols || str.length > matrix.length) { 5 return false; 6 } 7 boolean visited[] = new boolean[rows * cols]; 8 //初始化 9 for (int i = 0; i < rows * cols; i++) { 10 visited[i] = false; 11 } 12 for (int i = 0; i < rows; i++) { 13 for (int j = 0; j < cols; j++) { 14 if (hasPoint(matrix, visited, rows, cols, i, j, str, 0)){ 15 return true; 16 } 17 } 18 } 19 return false; 20 } 21 private boolean hasPoint(char[] matrix, boolean[] visited, int rows, int cols, int r, int c, char[] str, int index) { 22 23 if ((r >= 0 )&& (c >= 0) &&( r < rows) && (c < cols) && 24 (visited[r * cols + c] == false) && 25 (matrix[r * cols + c] == str[index])) { 26 if (index == (str.length - 1)) { 27 return true; 28 } 29 visited[r * cols + c] = true; 30 31 boolean hasPath = false; 32 index++; 33 hasPath = hasPoint(matrix, visited, rows, cols, r + 1, c, str, index) || 34 hasPoint(matrix, visited, rows, cols, r - 1, c, str, index) || 35 hasPoint(matrix, visited, rows, cols, r, c + 1, str, index) || 36 hasPoint(matrix, visited, rows, cols, r, c - 1, str, index); 37 if (hasPath) { 38 return true; 39 } else { 40 visited[r * cols + c] = false; 41 } 42 } 43 return false; 44 } 45 46 47 }
面试题13：机器人的运动范围
我的bfs做法
1 import java.util.*; 2 public class Solution { 3 class Point{ 4 int x; 5 int y; 6 public Point(int a, int b) { 7 x = a; 8 y = b; 9 } 10 } 11 public int movingCount(int threshold, int rows, int cols) 12 { 13 int count = 0; 14 if (rows <= 0 || cols <= 0) { 15 return 0; 16 } 17 boolean visited[][] = new boolean[rows][cols];//!!!忘记，默认初始false 18 int[] deltaX ={0, 0, 1, -1}; 19 int[] deltaY ={1, -1, 0, 0}; 20 Queue<Point> queue = new LinkedList<>(); 21 Point p = new Point(0, 0); 22 if (threshold >= 0) { 23 queue.add(p); 24 visited[0][0] = true;//!!!忘记，时刻记着queue.add和visited一起做出改动 25 } 26 27 28 while (!queue.isEmpty()) { 29 Point temp = queue.poll();//not pop 30 count++; 31 for (int i = 0; i < 4; i++) { 32 Point nextPoint = new Point(temp.x + deltaX[i], temp.y + deltaY[i]); 33 if (isValid(nextPoint, rows, cols, threshold, visited)) { 34 queue.add(nextPoint); 35 visited[nextPoint.x][nextPoint.y] = true; 36 37 } 38 } 39 } 40 return count; 41 42 43 } 44 private boolean isValid(Point point, int rows, int cols, int threshold, boolean[][] visited) { 45 if (point.x >= 0 && point.x < rows 46 && point.y >=0 && point.y < cols 47 && (visited[point.x][point.y] == false) 48 && (countSum(point) <= threshold)) { 49 return true; 50 }else { 51 return false; 52 } 53 } 54 private int countSum(Point p) { 55 int count = 0; 56 int x = p.x; 57 int y = p.y; 58 while (x != 0) { 59 count += x % 10; 60 x = x / 10; 61 } 62 while (y != 0) { 63 count += y % 10; 64 y = y / 10; 65 } 66 return count; 67 } 68 }
回溯法（答案dfs）
1 public class Solution { 2 public int movingCount(int threshold, int rows, int cols) 3 { 4 if (threshold < 0 || rows < 0 || cols < 0) { 5 return 0; 6 } 7 boolean[][] visited = new boolean[rows][cols]; 8 return dfs(threshold, rows, cols, 0, 0, visited); 9 10 } 11 private int dfs(int threshold, int rows, int cols, int r, int c, boolean[][] visited) { 12 int sum = 0; 13 if (r >= 0 && c >= 0 && r < rows && c < cols && visited[r][c] == false && (count(r) + count(c)) <= threshold) { 14 visited[r][c] = true; 15 sum = dfs(threshold, rows, cols, r + 1, c, visited) + 16 dfs(threshold, rows, cols, r - 1, c, visited) + 17 dfs(threshold, rows, cols, r , c + 1, visited) + 18 dfs(threshold, rows, cols, r , c - 1, visited) + 1; 19 } 20 return sum; 21 } 22 private int count(int x) { 23 int c = 0; 24 while (x != 0) { 25 c += x % 10; 26 x = x / 10; 27 } 28 return c; 29 } 30 }
面试题15：二进制中1的个数
1 public class Solution { 2 public int NumberOf1(int n) { 3 int count = 0; 4 while (n != 0) { 5 count++; 6 n = (n - 1) & n; 7 } 8 return count; 9 } 10 }
面试题16：数值的整数次方->时间复杂度O(logn)
思路：
①判断边界，判断底数base是否为0，double类型不可直接==.
当底数为0且指数<0时 会出现对0求倒数的情况，需进行错误处理，设置一个全局变量 0的0次幂和0的负次幂在数学是都是没有定义的
②幂正负分情况
③快速幂
an = an/2 * an/2 n是偶数
an = an/2 * an/2 * a n是奇数
④exponent >>1 除2写法
⑤判断奇偶：(exponent &0x1 == 1)
1 public class Solution { 2 public double Power(double base, int exponent) { 3 if (equal(base, 0.0)&&exponent < 0) { 4 return 0.0;//无意义，可讨论 5 } 6 if (exponent == 0) { 7 return 1; 8 } 9 int n = Math.abs(exponent); 10 double res = Power(base, n >> 1); 11 if ((n & 0x1) == 1) { 12 if (exponent > 0) { 13 return res * res * base; 14 } else { 15 return 1 / (res * res * base); 16 } 17 } else { 18 if (exponent > 0) { 19 return res * res; 20 } else { 21 return 1 / (res * res); 22 } 23 } 24 25 } 26 private boolean equal(double a, double b) { 27 if (Math.abs(a - b) < 0.001) { 28 return true; 29 } 30 return false; 31 } 32 }
稍显复杂
1 public class Solution { 2 public double Power(double base, int exponent) { 3 if (equal(base, 0.0)&&exponent < 0) { 4 return 0.0;//无意义，可讨论 5 } 6 if (exponent < 0) { 7 exponent = exponent * (-1); 8 return 1 / help(base, exponent); 9 } 10 return help(base, exponent); 11 } 12 private double help(double base, int exponent) { 13 if (exponent == 1) { 14 return base; 15 } 16 if (exponent == 0) { 17 return 1; 18 } 19 double res = help(base, exponent >> 1); 20 res = res * res; 21 if ((exponent & 0x1) == 1) { 22 return res * base; 23 } else { 24 return res; 25 } 26 } 27 private boolean equal(double a, double b) { 28 if (Math.abs(a - b) < 0.001) { 29 return true; 30 } 31 return false; 32 } 33 }
分出来写比较好
double浮点数判断相等
①
final double epsilon = 0.001; if(Math.abs(double_x - 0) < epsilon) { return true; }
②
if(Double.doubleToLongBits(double_x) == Double.doubleToLongBits(double_y))
面试题18：删除链表的节点
1 /* 2 public class ListNode { 3 int val; 4 ListNode next = null; 5 6 ListNode(int val) { 7 this.val = val; 8 } 9 } 10 */ 11 public class Solution { 12 public ListNode deleteDuplication(ListNode pHead) 13 { 14 if (pHead == null) { 15 return null; 16 } 17 ListNode dummy = new ListNode(0); 18 dummy.next = pHead; 19 ListNode pre = dummy; 20 ListNode cur = pHead; 21 ListNode next = cur.next; 22 while (next != null) { 23 while (next!= null && next.val == cur.val) { 24 cur = next; 25 next = next.next; 26 pre.next = cur; 27 } 28 if (next != null) { 29 pre = cur; 30 cur = next; 31 next = next.next; 32 } else { 33 return dummy.next; 34 } 35 36 } 37 return dummy.next; 38 39 } 40 }
错误的解法，懒得看了。重写
面试题21：调整数组顺序使奇数位于偶数前面
1 public class Solution { 2 public void reOrderArray(int [] array) { 3 if (array == null || array.length == 0) { 4 return; 5 } 6 int left = 0; 7 int right = 0; 8 while (left < array.length) { 9 if (array[left] % 2 == 0) { 10 right = left + 1; 11 while (right < array.length && array[right] % 2 == 0) { 12 right++; 13 } 14 int temp = array[left]; 15 array[left] = array[right]; 16 array[right] = temp; 17 left = right; 18 } else { 19 left++; 20 } 21 } 22 } 23 }
错误写法。
面试题19：正则表达式匹配
1 public class Solution { 2 public boolean match(char[] str, char[] pattern) 3 { 4 if(str == null && pattern == null) { 5 return true; 6 } 7 if (str.length == 0 && pattern.length == 0) { 8 return true; 9 } 10 if (pattern.length == 2 && pattern[0] == '.' && pattern[1] == '*') { 11 return true; 12 } 13 if (str.length == 0 && pattern.length == 2 && pattern[1] == '*') { 14 return true; 15 } 16 if (str == null || pattern == null || str.length == 0 || pattern.length == 0) { 17 return false; 18 } 19 20 int i = 0; 21 int j = 0; 22 while (i < str.length && j < pattern.length) { 23 if (pattern[j] == '.' || (str[i] == pattern[j])) { 24 i++; 25 j++; 26 } else if(str[i] != pattern[j] && (j + 1) < pattern.length && pattern[j + 1] == '*') { 27 //i++; 不用 分析清楚 28 j = j + 2; 29 } else if (pattern[j] == '*' && str[i] == pattern[j - 1]) { 30 i++; 31 } else if (pattern[j] == '*' && (j + 1) < pattern.length && str[i] == pattern[j + 1]) { 32 j++; 33 } 34 // bbbba .*a*b ‘.*’是个大麻烦 35 else if (str[i] != pattern[j] && pattern[j] == '.' && pattern[j + 1] == '*') { 36 37 } else { 38 return false; 39 } 40 } 41 if (i == str.length) { 42 if (j == pattern.length || (j < pattern.length && pattern[j] == '*') || (j == (pattern.length - 2) && pattern[j + 1] == '*')) { 43 return true; 44 } 45 46 } 47 return false; 48 } 49 }
乱写的一堆。
2018-2-14
面试题19：表示数值的字符串
面试题20：正则表达式
面试题27：对称的二叉树
1 /* 2 public class TreeNode { 3 int val = 0; 4 TreeNode left = null; 5 TreeNode right = null; 6 7 public TreeNode(int val) { 8 this.val = val; 9 10 } 11 12 } 13 */ 14 public class Solution { 15 boolean isSymmetrical(TreeNode pRoot) 16 { 17 if (pRoot == null) { 18 return true; 19 } 20 return isSym(pRoot.left, pRoot.right); 21 } 22 private boolean isSym(TreeNode left, TreeNode right) { 23 if (left == null && right == null) { 24 return true; 25 } 26 if (left == null) { 27 return false; 28 } 29 if (right == null) { 30 return false; 31 } 32 if (left.val == right.val) { 33 return isSym(left.left, right.right) && isSym(left.right, right.left); 34 } 35 return false; 36 } 37 }
还是有点糊里糊涂。
面试题30：包含main函数的栈
1 import java.util.Stack; 2 3 public class Solution { 4 5 Stack<Integer> stack = new Stack<>(); 6 Stack<Integer> minStack = new Stack<>(); 7 public void push(int node) { 8 if (stack.isEmpty()) { 9 stack.push(node); 10 minStack.push(node); 11 } else { 12 stack.push(node); 13 if (node < minStack.peek()) { 14 minStack.push(node); 15 } else { 16 minStack.push(minStack.peek()); 17 } 18 } 19 } 20 21 public void pop() { 22 stack.pop(); 23 minStack.pop(); 24 } 25 26 public int top() { 27 return stack.peek(); 28 } 29 30 public int min() { 31 return minStack.peek(); 32 } 33 }
不用每个都加一次
1 import java.util.Stack; 2 3 public class Solution { 4 5 Stack<Integer> stack = new Stack<>(); 6 Stack<Integer> minStack = new Stack<>(); 7 public void push(int node) { 8 if (stack.isEmpty()) { 9 stack.push(node); 10 minStack.push(node); 11 } else { 12 stack.push(node); 13 if (node < minStack.peek()) { 14 minStack.push(node); 15 } 16 } 17 } 18 19 public void pop() { 20 int node = stack.pop(); 21 if (node <= minStack.peek()) { 22 if (stack.peek() > minStack.peek()) { 23 minStack.pop(); 24 } 25 } 26 } 27 28 public int top() { 29 return stack.peek(); 30 } 31 32 public int min() { 33 return minStack.peek(); 34 } 35 }
面试题34：二叉树中和为某一值的路径
1 import java.util.ArrayList; 2 /** 3 public class TreeNode { 4 int val = 0; 5 TreeNode left = null; 6 TreeNode right = null; 7 8 public TreeNode(int val) { 9 this.val = val; 10 11 } 12 13 } 14 */ 15 public class Solution { 16 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { 17 ArrayList<ArrayList<Integer>> paths = new ArrayList<>(); 18 if (root == null) { 19 return paths; 20 } 21 22 ArrayList<Integer> path = new ArrayList<>(); 23 help(root, target, paths, path); 24 return paths; 25 } 26 private void help(TreeNode root, int target, ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path) { 27 //这样写有问题，叶子的 左null 右null会放入两次 28 //测试用例:{10,5,12,4,7},22 29 //对应输出应该为:[[10,5,7],[10,12]] 30 //你的输出为:[[10,5,7],[10,5,7],[10,12],[10,12]] 31 //if (target == 0 && root == null) { //从根到叶不能断 32 // paths.add(new ArrayList<Integer>(path)); 33 // return; 34 //} 35 if (target < 0 || root == null) { 36 return; 37 } 38 if (target == root.val && root.left == null && root.right == null) { 39 path.add(root.val); 40 paths.add(new ArrayList<Integer>(path)); 41 path.remove(path.size() - 1); 42 return; 43 } 44 path.add(root.val); 45 help(root.left, target - root.val, paths, path); 46 help(root.right, target - root.val, paths, path); 47 path.remove(path.size() - 1); 48 } 49 }
面试题35：复杂链表的复制
1 /* 2 public class RandomListNode { 3 int label; 4 RandomListNode next = null; 5 RandomListNode random = null; 6 7 RandomListNode(int label) { 8 this.label = label; 9 } 10 } 11 */ 12 public class Solution { 13 public RandomListNode Clone(RandomListNode pHead) 14 { 15 if (pHead == null) { 16 return null; 17 } 18 RandomListNode cur = pHead; 19 while (cur != null) { 20 RandomListNode temp = new RandomListNode(cur.label); 21 temp.next = cur.next; 22 cur.next = temp; 23 cur = temp.next; 24 } 25 cur = pHead; 26 while (cur != null) { 27 if (cur.random != null) { 28 cur.next.random = cur.random.next; 29 } 30 cur = cur.next.next; 31 } 32 RandomListNode copyHead = pHead.next; 33 cur = pHead; 34 RandomListNode copyCur = copyHead; 35 while (copyCur.next != null) { //这个判断条件就这么简单，要好好想想 36 cur.next = cur.next.next; 37 copyCur.next = copyCur.next.next; 38 cur = cur.next; 39 copyCur = copyCur.next; 40 } 41 cur.next = null; //最后一个的判断要注意 42 return copyHead; 43 } 44 }
1->1'->2->2'->null
因为cur = 1, copyCur = 1',
cur = cur.next.next; cur.next一定存在
但是copyCur.next可能为null，所以while条件是copyCur.next != null
出来时cur=2， copycur = 2',所以要把cur.next = null
面试题37：序列化二叉树
1 /* 2 public class TreeNode { 3 int val = 0; 4 TreeNode left = null; 5 TreeNode right = null; 6 7 public TreeNode(int val) { 8 this.val = val; 9 10 } 11 12 } 13 */ 14 import java.util.*; 15 public class Solution { 16 String Serialize(TreeNode root) { 17 if (root == null) { 18 return "{}"; 19 } 20 Queue<TreeNode> queue = new LinkedList<>(); 21 queue.add(root); 22 StringBuffer sb = new StringBuffer(); 23 sb.append("{"); 24 while (!queue.isEmpty()) { 25 TreeNode temp = queue.poll(); 26 if (temp != null) { 27 sb.append(temp.val); 28 sb.append(","); 29 queue.add(temp.left); 30 queue.add(temp.right); 31 } else { 32 sb.append("#,"); 33 } 34 } 35 sb.deleteCharAt(sb.length() - 1); 36 sb.append("}"); 37 return sb.toString(); 38 } 39 TreeNode Deserialize(String str) { 40 if (str == null || str.length() == 0 || str.equals("{}")) { 41 return null; 42 } 43 str = str.substring(1, str.length() - 1); 44 String[] array = str.split(","); 45 TreeNode root = new TreeNode(Integer.parseInt(array[0])); 46 Queue<TreeNode> queue = new LinkedList<>(); 47 queue.add(root); 48 int i = 1; 49 while (!queue.isEmpty()) { 50 TreeNode temp = queue.poll(); 51 if ("#".equals(array[i])) { 52 temp.left = null; 53 } else { 54 TreeNode leftNode = new TreeNode(Integer.parseInt(array[i])); 55 temp.left = leftNode; 56 queue.add(leftNode); 57 } 58 i++; 59 if ("#".equals(array[i])) { 60 temp.right = null; 61 } else { 62 TreeNode rightNode = new TreeNode(Integer.parseInt(array[i])); 63 temp.right = rightNode; 64 queue.add(rightNode); 65 } 66 i++; 67 } 68 return root; 69 } 70 }
str = str.substring(1, str.length() - 1);
String：[] array = str.split(",");
连续子数组的最大和
1 public class Solution { 2 public int FindGreatestSumOfSubArray(int[] array) { 3 if (array == null || array.length == 0) { 4 return 0; 5 } 6 int max = Integer.MIN_VALUE; 7 int sum = 0; 8 for (int i = 0; i < array.length; i++) { 9 if (sum < 0) { 10 sum = 0; 11 } 12 sum = sum + array[i]; 13 if (sum > max) { 14 max = sum; 15 } 16 } 17 return max; 18 } 19 }
数组中出现次数超过一半的数字
1 import java.util.*; 2 public class Solution { 3 public int MoreThanHalfNum_Solution(int [] array) { 4 if (array == null || array.length == 0) { 5 return 0; 6 } 7 if (array.length == 1) { 8 return array[0]; 9 } 10 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 11 int length = array.length / 2; 12 for (int i = 0; i < array.length; i++) { 13 if (map.containsKey(array[i])) { 14 15 map.put(array[i], map.get(array[i]) + 1); 16 if (map.get(array[i]) > length) { 17 return array[i]; 18 } 19 } else { 20 map.put(array[i], 1); 21 } 22 } 23 return 0; 24 } 25 }
最小的k个数
1 import java.util.*; 2 public class Solution { 3 public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { 4 ArrayList<Integer> res = new ArrayList<>(); 5 if (input == null || input.length < k) { 6 return res; 7 } 8 PriorityQueue<Integer> minPq = new PriorityQueue<>(); 9 for (int i = 0; i < input.length; i++) { 10 minPq.offer(input[i]); 11 } 12 for (int i = 0; i < k; i++){ 13 res.add(minPq.poll()); 14 } 15 return res; 16 } 17 }
答案
1 public class Solution { 2 public int MoreThanHalfNum_Solution(int [] array) { 3 if (array == null || array.length == 0) { 4 return 0; 5 } 6 int res = array[0]; 7 int count = 1; 8 for (int i = 1; i < array.length; i++) { 9 if (array[i] != array[i - 1]) { 10 count--; 11 } else { 12 count++; 13 } 14 if (count == 0) { 15 count = 1; 16 res = array[i]; 17 } 18 } 19 //check 20 int doubleCount = 0; 21 for (int i = 0; i < array.length; i++) { 22 if (array[i] == res) { 23 doubleCount++; 24 } 25 } 26 if (doubleCount > array.length / 2) { 27 return res; 28 } 29 return 0; 30 } 31 }
