JAVA刷力扣《算法面试题汇总》

一.开始之前 

1.找出只出现一次的数字，其余均为两次

异或运算(^)就行了。

2.多数元素（次数多于n/2的元素，假设数组中一定存在）

（1）排序法：中间位置

先排序Array.sort(nums)，然后取nums[nums.length/2]

class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } }

（2）摩尔投票法

多数元素比其他所有元素加起来都多，所以投票法mode可以抓到多数元素。

a、假如mode直接抓到了多数元素，则一个多数元素消掉一个非多数元素，最后留下的肯定是多数元素。

b、假如没有抓到多数元素，也不会使多数元素减少，只会使非多数元素减少，最后留下的还是多数元素。

class Solution { public int majorityElement(int[] nums) { //1.初始化 int mode=0; int vote=0; //2.遍历 for(int num:nums){ //更新mode if(vote==0){ mode=num; } //更新vote if(num==mode){ vote++; }else{vote--;} } return mode; } }

3.有序矩阵找元素

熟悉以下java关于矩阵的声明于遍历（矩阵也是二维数组）

class Solution { public boolean searchMatrix(int[][] matrix, int target) { //搞定特殊用例：空矩阵 if (matrix.length == 0 || matrix[0].length == 0) { return false; } //右上角开始，小了行数++，大了列数-- int row = 0; int col = matrix[0].length - 1; while (row < matrix.length && col >= 0) { if ( matrix[row][col]<target) { row++; } else if (matrix[row][col]>target) { col--; } else { return true; } } return false; } }

4.合并有序数组：把nums2合并到nums1中，升序。(不能开新的数组)

python中可以直接对数组pop、append，把数组当作栈或队列用，java不行。

java的栈、数组、列表不是同一个东西，数组不能直接pop、append。

class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { //先归并大的，这样一遍扫面即可。 for(int k = m+n-1,i = m-1,j = n-1;k >= 0;k--) { if(i < 0) { nums1[k] = nums2[j--]; continue; } if(j < 0) { nums1[k] = nums1[i--]; continue; } if(nums1[i] >= nums2[j]) nums1[k] = nums1[i--]; else nums1[k] = nums2[j--]; } } }

5.丢鸡蛋（困难）

最坏情况下的移动次数。

动态规划

class Solution { public int superEggDrop(int K, int N) { if (N == 1) { return 1; } int[][] f = new int[N + 1][K + 1]; for (int i = 1; i <= K; ++i) { f[1][i] = 1; } int ans = -1; for (int i = 2; i <= N; ++i) { for (int j = 1; j <= K; ++j) { f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j]; } if (f[i][K] >= N) { ans = i; break; } } return ans; } }

二.字符串

1.验证回文串

移动双指针，遇到不同的返回false；一直相同，直到i、j相遇则返回true。

class Solution { public boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while(i < j){ //i，j位置不是字符则直接移动 while(i < j && !Character.isLetterOrDigit(s.charAt(i))) i++; while(i < j && !Character.isLetterOrDigit(s.charAt(j))) j--; if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false; i++; j--; } return true; } }

2.分割回文串

把一个字符串全部拆分为‘回文串’，每一种拆法为一个List。

然后把所有拆法都放进一个大的List中，形成二维List输出。

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; public class Solution { public List<List<String>> partition(String s) { int len = s.length(); List<List<String>> res = new ArrayList<>(); if (len == 0) { return res; } // Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new ArrayDeque<Integer>(); // 注意：只使用 stack 相关的接口 Deque<String> stack = new ArrayDeque<>(); backtracking(s, 0, len, stack, res); return res; } /** * @param s * @param start 起始字符的索引 * @param len 字符串 s 的长度，可以设置为全局变量 * @param path 记录从根结点到叶子结点的路径 * @param res 记录所有的结果 */ private void backtracking(String s, int start, int len, Deque<String> path, List<List<String>> res) { if (start == len) { res.add(new ArrayList<>(path)); return; } for (int i = start; i < len; i++) { // 因为截取字符串是消耗性能的，因此，采用传子串索引的方式判断一个子串是否是回文子串 // 不是的话，剪枝 if (!checkPalindrome(s, start, i)) { continue; } path.addLast(s.substring(start, i + 1)); backtracking(s, i + 1, len, path, res); path.removeLast(); } } /** * 这一步的时间复杂度是 O(N)，因此，可以采用动态规划先把回文子串的结果记录在一个表格里 * * @param str * @param left 子串的左边界，可以取到 * @param right 子串的右边界，可以取到 * @return */ private boolean checkPalindrome(String str, int left, int right) { // 严格小于即可 while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; } }

三.数组

 

四.堆、栈、序列

 

五.链表

 

六.哈希与映射

 

七.树

 

八.排序与检索

 

九.动态规划

 

十.图论

 

十一.数学&位运算

 

十二.模拟面试