【第一题】数组中数字出现的次数II
分析：
方法一：集合；
方法二：哈希表；
//哈希好慢
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
for(int key:map.keySet()){
if(map.get(key) == 1){return key;}
}
return -1;
}
}
【第二题】最小的K个数
分析：
方法一：排序；输出前k个元素。
方法二：大根堆；用前k个元素组成一个大根堆，然后每进来一个元素就和堆根进行比较，如果大则抛之，如果小则加入堆，把堆根元素（堆中最大值）弹出堆。
方法三：分治；将所有元素分为k部分，每部分选出一个最小的。
方法四：二叉搜索树。
方法五：先找到第k小的数，然后遍历一遍数组，将所有比k小的数加入结果集。
方法六：快速选择。利用快排的partition思想，进行不完全的快速排序，只需要直到最小的k个数是哪些即可。
//大根堆
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] vec = new int[k];
if(k == 0){return vec;}
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
public int compare(Integer num1,Integer num2){
return num2 - num1;
}
});
for(int i = 0;i < k;++i){
queue.offer(arr[i]);
}
for(int i = k;i < arr.length;i++){
if(queue.peek() > arr[i]){
queue.poll();
queue.offer(arr[i]);
}
}
for(int i = 0;i < k;++i){
vec[i] = queue.poll();
}
return vec;
}
}
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0) {
return new int[0];
} else if (arr.length <= k) {
return arr;
}
// 原地不断划分数组
partitionArray(arr, 0, arr.length - 1, k);
// 数组的前 k 个数此时就是最小的 k 个数，将其存入结果
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
void partitionArray(int[] arr, int lo, int hi, int k) {
// 做一次 partition 操作
int m = partition(arr, lo, hi);
// 此时数组前 m 个数，就是最小的 m 个数
if (k == m) {
// 正好找到最小的 k(m) 个数
return;
} else if (k < m) {
// 最小的 k 个数一定在前 m 个数中，递归划分
partitionArray(arr, lo, m-1, k);
} else {
// 在右侧数组中寻找最小的 k-m 个数
partitionArray(arr, m+1, hi, k);
}
}
// partition 函数和快速排序中相同，具体可参考快速排序相关的资料
// 代码参考 Sedgewick 的《算法4》
int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
int v = a[lo];
while (true) {
while (a[++i] < v) {
if (i == hi) {
break;
}
}
while (a[--j] > v) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, lo, j);
// a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
作者：nettee
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
【第三题】扑克牌中的顺子
分析：首先，有重复的牌就不能作为顺子；第二，一个0只能填一个“坑”（根据0的个数、下标与元素之差，两者之间的关系来判断坑）
//执行用时：1 ms, 在所有 Java 提交中击败了91.86% 的用户
//内存消耗：36.1 MB, 在所有 Java 提交中击败了10.17% 的用户
class Solution {
public boolean isStraight(int[] nums) {
if(nums.length <= 1){return true;}
Arrays.sort(nums);
//gap为下标与数组之差
//count为0的个数
int gap = 0,i = 0,count = 0;
while(nums[i]==0){
i++;
count++;
}
gap = nums[i] - i;
//System.out.println(count + " " + i +" "+gap);
int j = 0;
for(j = i;j < nums.length-1;j++){
//判断重复元素
if(nums[j] == nums[j+1]){return false;}
if(nums[j] - j - gap <= count){
continue;
}else{
return false;
}
}
//判断最后一个位置是否满足条件
return nums[j]-j-gap <= count?true:false;
}
}
【第五题】数组中数字出现的次数
分析：空间复杂度为O(1)——立即推 位运算！
参考链接：接地气讲解（分组位运算）「还不懂就来P城砍我」
//执行用时：8 ms, 在所有 Java 提交中击败了18.05% 的用户
//内存消耗：40.1 MB, 在所有 Java 提交中击败了63.30% 的用户
//双指针
class Solution {
public int[] singleNumbers(int[] nums) {
if(nums.length == 2){
if(nums[0]!=nums[1]){
return nums;
}
}
Arrays.sort(nums);
int[] arr = new int[2];
//双指针比较
int i = 0,j = 1;
int k = 0;
while(i < nums.length && j < nums.length){
if(nums[i] ==nums[j]){
i+=2;
j+=2;
}else{
if(k <=1){
arr[k++] = nums[i];
}else{break;}
i++;
j++;
}
}
if(k <= 1){
arr[k] = nums[i];
}
return arr;
}
}
class Solution {
public int[] singleNumbers(int[] nums) {
int sum = 0;
//最后得到的是这两个不同的数的异或结果
for(int num:nums){
sum ^= num;
}
int flag = sum & (-sum);
int res = 0;
//分成两个组进行异或
for(int val:nums){
if((flag & val) !=0){
res ^= val;
}
}
return new int[]{res,sum ^ res};
}
}
public int[] singleNumbers(int[] nums) {
//xor用来计算nums的异或和
int xor = 0;
// 计算异或和 并存到xor
// e.g. [2,4,2,3,3,6] 异或和：(2^2)^(3^3)^(4^6)=2=010
for(int num : nums) xor ^= num;
//设置mask为1，则二进制为0001
// mask是一个二进制数，且其中只有一位是1，其他位全是0，比如000010，
// 表示我们用倒数第二位作为分组标准，倒数第二位是0的数字分到一组，倒数第二位是1的分到另一组
int mask = 1;
// & operator只有1&1时等于1 其余等于0
// 用上面的e.g. 4和6的二进制是不同的 我们从右到左找到第一个不同的位就可以分组 4=0100 6=0110
// 根据e.g. 010 & 001 = 000 = 0则 mask=010
// 010 & 010 != 0 所以mask=010
// 之后就可以用mask来将数组里的两个数分区分开
while((xor & mask)==0){
mask <<= 1;
}
//两个只出现一次的数字
int a=0, b=0;
for(int num : nums){
//根据&是否为0区分将两个数字分区，并分别求异或和
if((num & mask)==0) a ^= num;
else{
b ^= num;
}
}
return new int[]{a,b};
}
【第六题】从上到下打印二叉树
分析：直接利用队列层序遍历。
class Solution {
public int[] levelOrder(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){return list.stream().mapToInt(Integer::intValue).toArray();}
//if(root == null){return list.toArray(new Integer[0]);}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
int count = q.size();
for(int i = 0;i < count;i++){
TreeNode node = q.poll();
//arr[j++] = node.val;
list.add(node.val);
if(node.left!=null){
q.add(node.left);
}
if(node.right !=null){
q.add(node.right);
}
}
}
//将Integer类型list复制为int数组 使用了java8的stram新特性
return list.stream().mapToInt(Integer::intValue).toArray();
//return list.toArray(new Integer[list.size()]);
}
}
【第七题】重建二叉树
分析：根据前序中序遍历还原二叉树。
1、根据前序遍历找到父节点；
2、根据父节点在中序遍历中确定左右子树的顺序；
class Solution{
public TreeNode buildTree(int[] preorder,int[] inorder){
int n = preorder.length;
if(n == 0){return null;}
int rootVal = preorder[0];
int index = 0;
for(int i = 0;i < n;i++){
if(inorder[i] == rootVal){
index = i;
break;
}
}
TreeNode node = new TreeNode(rootVal);
root.left = buildTree(Arrays.copyRange(preorder,1,index+1),Arrays.copyRange(inorder,0,Index));
root.right = buildTree(Arrays.copyRange(preorder,index+1,n),Arrays.copyRange(inorder,index+1,n));
return root;
}
}
【第八题】丑数（动态规划挖坑）
【第九题】二叉树中和为某一值的路径
分析：深度优先.
class Solution{
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root,int sum){
recur(root,sum);
return res;
}
void recur(TreeNode root,int tar){
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null){
res.add(new LinkedList(path));
}
recur(root.left,tar);
recur(root.right,tar);
path.removeLast();
}
}
class Solution {
List<List<Integer>> res=new ArrayList<>();
List<Integer> temp=new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root==null){
return res;
}
dfs(root,sum);
return res;
}
public void dfs(TreeNode root,int sum){
sum-=root.val;
if(sum==0&&root.left==null&&root.right==null){
temp.add(root.val);
res.add(new ArrayList<>(temp));
temp.remove(temp.size()-1);
return;
}
temp.add(root.val);
if(root.left!=null){
dfs(root.left,sum);
}
if(root.right!=null){
dfs(root.right,sum);
}
temp.remove(temp.size()-1);
}
}
19216801
【第十题】汉诺塔问题
分析：假如是一步，则直接从A移动到C；假如是两个以上的盘子，则先（A,B），再（A,C），再（B，C）。
class Solution{
public void hanota(List<Integer> A,List<Integer> B,List<Integer> C){
int n = A.size();
move(n,A,B,C);
}
public void move(int n,List<Integer> A,List<Integer> B,List<Integer> C){
if(n == 1){
C.add(A.size()-1);
A.remove(A.size()-1);
}
move(n-1,A,C,B);
C.add(A.size()-1);
A.remove(A.size()-1);
move(n-1,B,A,C);
}
}
【第十一题】字符串压缩
分析：
方法一：一个for循环
class Solution {
public String compressString(String S) {
if(S.length() <= 2){return S;}
StringBuilder sb = new StringBuilder();
int count = 1;
int i = 0;
for(i = 0;i < S.length()-1;i++){
if(S.charAt(i) == S.charAt(i+1)){
count++;
}else{
sb.append(S.charAt(i));
sb.append(count+"");
count = 1;
}
}
sb.append(S.charAt(i));
sb.append(count);
String S1 = sb.toString();
return S1.length() >= S.length()?S:S1;
}
}
方法二：快慢指针
class Solution {
// 快慢指针
public String compressString(String S) {
if(S.length() == 0) return S;
char[] chars = S.toCharArray();
StringBuilder sb = new StringBuilder();
int slow = 0, fast = 0;
while(fast <= chars.length){
if(fast == chars.length){
sb.append(chars[slow]).append(fast-slow);
}else if(chars[fast] != chars[slow]){
sb.append(chars[slow]).append(fast-slow);
slow = fast;
}
fast++;
}
return sb.length() < chars.length ? sb.toString() : S;
}
}
【第十二题】交换数字
分析：
class Solution {
public int[] swapNumbers(int[] numbers) {
numbers[0] = numbers[0] ^ numbers[1];
numbers[1] = numbers[0] ^ numbers[1];
numbers[0] = numbers[0] ^ numbers[1];
return numbers;
}
}
//但是有溢出风险
class Solution{
public int[] swapNumbers(int[] numbers){
numbers[0] = numbers[0] + numbers[1];
numbers[1] = numbers[0] - numbers[1];
numbers[0] = numbers[0] - numbers[1];
return numbers;
}
}
【第十三题】幂集
分析：涉及到穷举和剪枝——立即推，回溯。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<Integer> list = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
backTrace(nums,0,list,res);
return res;
}
private void backTrace(int[] nums,int cur,List<Integer> list,List<List<Integer>> res){
/**回溯模板：
1、递归出口
2、for循环
2.1 将元素加入列表
2.2 向下递归
2.3 向上回溯
**/
res.add(new ArrayList<>(list));
for(int i = cur;i < nums.length;i++){
list.add(nums[i]);
backTrace(nums,i+1,list,res);
list.remove(list.size()-1);
}
}
}
【第十四题】检查子树
分析：
class Solution {
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
if(t1 == null){return false;}
//假如两棵树的根节点相同，那么就继续向下递归比较
if(t1.val == t2.val){
if(digui(t1,t2)){
return true;
}
}
//假如根节点不同，那么就在t1的左右子树递归匹配
return checkSubTree(t1.left,t2) || checkSubTree(t1.right,t2);
}
public boolean digui(TreeNode t1,TreeNode t2){
if(t1 == null && t2 == null){return true;}
if(t1 == null || t2 == null || t1.val!=t2.val){return false;}
return digui(t1.left,t2.left) && digui(t1.right,t2.right);
}
}
【第十五题】阶乘尾数
分析：因为末尾的0是由是否是10的倍数决定，而是否是10——>是否有2*5——>多少个5（因为偶数的个数肯定比5多，因此只需要计算5的个数即可）。
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while(n >= 5){
n /= 5;
count+=n;
}
return count;
}
}