163. Unique Binary Search Trees、47. Majority Element II

描述

• Given n, how many structurally unique BSTs (binary search trees) that store values 1…n?
• 给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一

解决

• 对于从1~n中的一个值k，将其作为root
• 由于二叉搜索树的特性：大于k的在右边，小于k的在左边
• 因此实际情况是可以计算得到：Dj[k-1]*Dj[n-k]

public class Solution {
    /*** @param n: An integer* @return: An integer*/public int numTrees(int n) {// write your code hereif (n == 0)return 1;int[] Dj = new int[n+1];int ans = 0;Dj[0] = 1;for (int i = 1; i <= n ;i ++ ){Dj[i] = 0;for (int j = 1; j <= i; j ++){Dj[i] += Dj[i-j]*Dj[j-1];}} return Dj[n];}
}

• 同一个数组中不可能出现3个主元素
• 用HashMap记录下出现的个数
• 然后对所有记录进行逐步遍历

public class Solution {/** @param nums: a list of integers* @return: The majority number that occurs more than 1/3*/public int majorityNumber(List<Integer> nums) {// write your code hereMap<Integer,Integer> Helper = new HashMap<Integer,Integer>();for (int i = 0;i < nums.size();i++){if (Helper.get(nums.get(i)) == null){Helper.put(nums.get(i),1);} else {Helper.put(nums.get(i),Helper.get(nums.get(i)) + 1);}}for (Map.Entry<Integer, Integer> entry : Helper.entrySet()) {if (entry.getValue() > nums.size() / 3 )return entry.getKey();}return -1;}
}

这是适用于的，但是空间复杂度不符合要求

• 使用两个数字用于记录出现频率最多的两个
• 遍历一次数组，找到实际出现频数进行比较即可

public class Solution {/** @param nums: a list of integers* @return: The majority number that occurs more than 1/3*/public int majorityNumber(List<Integer> nums) {// write your code here// Map<Integer,Integer> Helper = new HashMap<Integer,Integer>();// for (int i = 0;i < nums.size();i++){
    // if (Helper.get(nums.get(i)) == null){
    // Helper.put(nums.get(i),1);// } else {
    // Helper.put(nums.get(i),Helper.get(nums.get(i)) + 1);// }// }// for (Map.Entry<Integer, Integer> entry : Helper.entrySet()) {
    // if (entry.getValue() > nums.size() / 3 )// return entry.getKey();// }// return -1;if(nums.size()==1) {return nums.get(0);}int m1 = nums.get(0);int m2 = 0;int c1 = 1;int c2 = 0;for(int i=1; i<nums.size(); i++) {int x = nums.get(i);if(x==m1) ++c1;else if(x==m2) ++c2;else if(c1==0) {m1 = x;c1 = 1;} else if(c2==0) {m2 = x;c2 = 1;} else {--c1; --c2;}}c1 = 0; c2 = 0;for(int i=0; i<nums.size(); i++) {if(m1 == nums.get(i)) ++c1;else if(m2 == nums.get(i)) ++c2;}if(c1>nums.size()/3) return m1;if(c2>nums.size()/3) return m2;return -1;}
}