classSolution{ publicintfindRepeatNumber(int[] nums){ Arrays.sort(nums); for (int i = 1;i < nums.length; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } } return0; } }
Set去重
可以将该数组丢到Set集合里去重,若是添加失败就代表该数字重复,直接返回就好了。
1 2 3 4 5 6 7 8 9 10 11
classSolution{ publicintfindRepeatNumber(int[] nums){ Set<Integer> set = new HashSet<>(); for (int i : nums) { if (!set.add(i)) { return i; } } return0; } }
哈希表
跟Set差不多,添加到哈希表之前,先判断一下是否有该键,然后要是有就直接返回。
1 2 3 4 5 6 7 8 9 10 11 12
classSolution{ publicintfindRepeatNumber(int[] nums){ HashMap<Integer,Integer> map = new HashMap<>(); for (int i : nums) { if (map.containsKey(i)) { return i; } map.put(i,i); } return0; } }
classSolution{ publicintduplicateInArray(int[] nums){ int l = 1; int r = nums.length - 1; while (l < r) { int mid = l + r >> 1; // 记录小于中间值的数的个数 int count = 0; for(int i : nums) { if(l <= i && i <= mid) count++; } // 个数大于坑数就进入左区间,直到找到重复的数字 if(count > mid - l + 1) r = mid; else l = mid + 1; } return l; } }
4.二维数组中的查找
数组遍历
直接将这个二维数组遍历,暴力破解。
1 2 3 4 5 6 7 8 9 10
classSolution{ publicbooleanfindNumberIn2DArray(int[][] matrix, int target){ for (int[] i : matrix) { for (int j : i) { if (j == target) returntrue; } } returnfalse; } }
publicCQueue(){ stack1 = new Stack<>(); stack2 = new Stack<>(); } publicvoidappendTail(int value){ stack1.push(value); } publicintdeleteHead(){ if (!stack2.isEmpty()) return stack2.pop(); if (stack1.isEmpty()) return -1; while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.pop(); } }
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */
classSolution{ publicintfib(int n){ if (n == 0 || n == 1) return n; int a = 0; int b = 1; for (int i = 2; i <= n; i++) { int temp = b; b = a + b; a = temp; if (b >= 1000000007) b -= 1000000007; } return b; } }
青蛙跳台阶
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution{ publicintnumWays(int n){ if (n <= 1) return1; if (n == 2) return2; int a = 1; int b = 1; for (int i = 2;i <= n;i++) { int c = (a + b) % 1000000007; a = b; b = c; } return b; } }
classSolution{ publicintminArray(int[] numbers){ for (int i = 0;i < numbers.length - 1; i++) { if (numbers[i] > numbers[i + 1]) return numbers[i + 1]; } return numbers[0]; } }
二分查找
二分查找最主要的就是划分区间,需要先分析一下怎样确定好区间。
中间的数大于最右边的数,代表期间不会单调递增,直接进入右边的区间
中间的数小于最右边的数,代表期间是单调递增的,直接进入左边的区间
要是中间的数与最右边的数相等,那就缩进一下区间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution{ publicintminArray(int[] numbers){ int l = 0; int r = numbers.length - 1; while (l < r) { int mid = l + r >> 1; if (numbers[mid] > numbers[r]) { l = mid + 1; } elseif (numbers[mid] < numbers[r]) { r = mid; } else { r -= 1; } } return numbers[l]; } }
classSolution{ publicintmovingCount(int m, int n, int k){ if (m == 0 || n == 0) return0; boolean[][] isVisited = newboolean[m][n]; return dfs(0,0,k,isVisited); }
publicintdfs(int i,int j,int k,boolean[][] isVisited){ if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || !isAllowed(i,j,k)) return0; isVisited[i][j] = true; // 上下左右 return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1; } // 判断是否合法 publicbooleanisAllowed(int m, int n, int k){ int sum = 0; while (m != 0) { sum += m % 10; m = m / 10; } while (n != 0) { sum += n % 10; n = n / 10; } if (sum <= k) returntrue; elsereturnfalse; } }
看看别人的发现判断是否合法不用这么麻烦,还可以优化一下,所以变成下面这样。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution{ publicintmovingCount(int m, int n, int k){ if (m == 0 || n == 0) return0; boolean[][] isVisited = newboolean[m][n]; return dfs(0,0,k,isVisited); }
classSolution{ publicintmovingCount(int m, int n, int k){ if (m == 0 || n == 0) return0; boolean[][] isVisited = newboolean[m][n]; return dfs(0,0,k,isVisited); }
classSolution{ publicintcuttingRope(int n){ if (n == 1 || n == 2) return1; if (n == 3) return2; int res = 1; while (n > 4) { res *= 3; n -= 3; } return res * n; } }
14.2 剪绳子2
这题将数据量变大了很多,使用动态规划就会很麻烦,所以用刚刚的贪婪算法,修改一下。
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution{ publicintcuttingRope(int n){ if (n == 1 || n == 2) return1; if (n == 3) return2; long res = 1; while (n > 4) { res *= 3; res %= 1000000007; n -= 3; } return (int)(res * n % 1000000007); } }
publicint[] quickSort(int[] arr, int left, int right, int k) { int i = left, j = right, x = arr[left]; while (i < j) { while (i < j && arr[j] >= x) j--; while (i < j && arr[i] <= x) i++; if (i < j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } arr[left] = arr[i]; arr[i] = x; if (i > k) return quickSort(arr, left, i - 1, k); if (i < k) return quickSort(arr, i + 1, right, k); return Arrays.copyOf(arr, k); } }
classSolution{ public String minNumber(int[] nums){ if (nums.length == 1) return String.valueOf(nums[0]); sort(nums, 0, nums.length - 1); StringBuilder res = new StringBuilder(); for (int num : nums) { res.append(num); } return res.toString(); }
// 快排 publicvoidsort(int[] nums, int l , int r){ if (l >= r) return; int x = nums[l], i = l - 1, j = r + 1; while (i < j) { do i++; while (check(x,nums[i])); do j--; while (check(nums[j],x)); if (i < j) swap(nums, i, j); } sort(nums, l, j); sort(nums, j + 1, r); } // 判断i是否大于j(自定义的大于) publicbooleancheck(int i, int j){ StringBuilder a = new StringBuilder(); StringBuilder b = new StringBuilder(); a.append(i).append(j); b.append(j).append(i); return a.toString().compareTo(b.toString()) > 0; }
publicvoidswap(int[] nums, int i, int j){ int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }
}
Java还有更简单的排序方法。
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution{ public String minNumber(int[] nums){ if (nums.length == 1) return String.valueOf(nums[0]); List<String> list = new ArrayList<>(); for (int num : nums) { list.add(String.valueOf(num)); } // 这个排序虽然简单,但是效率好像没有快排高 list.sort((o1,o2) -> (o1 + o2).compareTo(o2 + o1)); return String.join("",list); }
}
46.把数字翻译成字符串
递归
1 2 3 4 5 6 7 8 9 10 11
classSolution{ publicinttranslateNum(int num){ if (num <= 9) return1; int ba = num % 100; if (ba <= 9 || ba >= 26) { return translateNum(num / 10); } else { return translateNum(num / 10) + translateNum(num / 100); } } }
classSolution{ publicintlengthOfLongestSubstring(String s){ int len = s.length(); if (len <= 1) return len; int l = 0, max = 0; Map<Character,Integer> map = new HashMap<>(); for (int i = 0; i < len; i++) { // 如果已经存在重复的字符,就更新窗口的左边界让字符串不重复 if (map.containsKey(s.charAt(i))) { // 重新定义窗口左边界 l = Math.max(l, map.get(s.charAt(i)) + 1); } // 更新(添加)map里字符的坐标 map.put(s.charAt(i),i); // 计算最大值 max = Math.max(max, i - l + 1); } return max; } }
49. 丑数
使用动态规划,主要是凑成最小的丑数,然后一个个凑到第N个,就是用2,3,5的公倍数从小凑到N。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution{ publicintnthUglyNumber(int n){ int[] dp = newint[n]; dp[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; i++) { int min = Math.min(Math.min(dp[p2] * 2,dp[p3] * 3),dp[p5] * 5); if (min % 2 == 0) p2++; if (min % 3 == 0) p3++; if (min % 5 == 0) p5++; dp[i] = min; } return dp[n - 1]; } }
classSolution{ publiccharfirstUniqChar(String s){ Map<Character,Integer> map = new HashMap<>(); for (char c : s.toCharArray()) { map.put(c,map.getOrDefault(c,0) + 1); } for (char c : s.toCharArray()) { if (map.get(c) == 1) return c; } return' '; } }
51.数组中的逆序对
暴力破解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution{ publicintreversePairs(int[] nums){ int[] sum = newint[nums.length]; for (int i = 0; i < sum.length; i++) { for (int j = i + 1; j < sum.length; j++) { if (nums[i] > nums[j]) sum[i]++; } } int res = 0; for (int s : sum) { res += s; } return res; } }
classSolution{ publicintsearch(int[] nums, int target){ int l = 0, r = nums.length; int res = 0; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } while (l < nums.length && nums[l++] == target) { res++; } return res; } }
53.20~n-1中缺少的数字
暴力破解
数组本身是递增的,直接递增,就能直接查找到缺少的数字。
1 2 3 4 5 6 7 8 9 10
classSolution{ publicintmissingNumber(int[] nums){ int res = 0; for (int num : nums) { if (num != res) return res; res++; } return res; } }
求和
求和然后逐个减去数组中的数字,这样就能找出缺少的数字了。
1 2 3 4 5 6 7 8 9 10 11 12
classSolution{ publicintmissingNumber(int[] nums){ int res = 0; for (int i = 0; i <= nums.length; i++) { res += i; } for (int num : nums) { res -= num; } return res; } }
二分查找
数组有序,那就是二分查找。
最主要的问题是查找什么。
若是每个数字都不缺少,那n这个数字应该会在数组的n的下标的位置。
要是有个数字缺少了,数组就会乱序,所以我们只要找到第一个乱序的数字,即为答案。
1 2 3 4 5 6 7 8 9 10 11
classSolution{ publicintmissingNumber(int[] nums){ int l = 0, r = nums.length; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] == mid) l = mid + 1; else r = mid; } return l; } }
56.1 数组中数字出现的次数
位运算
首先看到这题就想到之前写的找出唯一一个不是两个数的数字,使用异或很快就解决了问题。
不过这里的数组有两个这样的数,所以就无法直接异或得到答案,需要进行一些处理。
58.2 左旋转字符串
切片
直接截出这两段字符串然后换位置就可以了。
1 2 3 4 5
classSolution{ public String reverseLeftWords(String s, int n){ return s.substring(n) + s.substring(0,n); } }
顺序处理
遍历字符串一个个加入到结果字符中也是可以的。
1 2 3 4 5 6 7 8 9
classSolution{ public String reverseLeftWords(String s, int n){ StringBuilder res = new StringBuilder(); char[] arr = s.toCharArray(); for (int i = n; i < arr.length; i++) res.append(arr[i]); for (int i = 0; i < n; i++) res.append(arr[i]); return res.toString(); } }
classSolution{ publicdouble[] dicesProbability(int n) { double[][] dp = newdouble[n + 1][6 * n + 1]; // 初始化一颗筛子的情况 for (int i = 1; i <= 6; i++) dp[1][i] = (double) 1 / 6; for (int i = 2; i <= n; i++) { // i颗筛子的最大点数 int max = 6 * i; // 遍历i颗筛子的所有点数求出概率 for (int j = i; j <= max; j++) { for (int k = 1; k <= 6; k++) { if (j - k <= 0) { continue; } dp[i][j] += dp[i - 1][j - k] * dp[1][k]; } } } // 存储答案 double[] res = newdouble[5 * n + 1]; int value = n; for (int i = 0; i < res.length; i++) { res[i] = dp[n][value++]; } return res;
} }
61. 扑克牌的顺子
首先确定答案的约束。
抽到的五张牌是不是连续的。
抽到的五张牌是不重复的。
大小王可以换为任意一张牌,可以存在重复的0
这里可以找出一定的规律,抽到的五张牌中最大的减去最小的小于5就可以说明这五张牌是重复的了。
Set去重
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution{ publicbooleanisStraight(int[] nums){ Set<Integer> res = new HashSet<>(); int max = -1, min = 14; for (int i : nums) { if (i == 0) continue; max = Math.max(max,i); min = Math.min(min,i); // 如果有重复的就返回false if (!res.add(i)) returnfalse; } return max - min < 5; } }
classSolution{ publicintlastRemaining(int n, int m){ if (n == 1) return1; List<Integer> list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(i); } int k = 0; while (n > 1) { k = (k + m - 1) % n; list.remove(k); n--; } return list.get(0); } }
约瑟夫环公式
这题就算典序的约瑟夫环的问题。
约瑟夫环有一个递推公式。
F(n,m) = (f(n - 1,m) + m) % n
F(n,m)表示的是n个人报数,报到m的人会被杀掉,最终胜利者的编号,也就是这题的答案。
1 2 3 4 5 6 7 8 9 10
classSolution{ publicintlastRemaining(int n, int m){ int res = 0; // f(2,m)是最初的状态,需要加到F(n,m)才是最终答案 for (int i = 2; i <= n; i++) { res = (res + m) % i; } return res; } }
63. 股票的最大利润
这题是经典的动态规划题,不过这一题只交易一次。所以只需要找到一个最小的数买进,最大的数卖出就行了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution{ publicintmaxProfit(int[] prices){ if (prices.length <= 1) return0; int res = 0, min = prices[0]; for (int i = 1; i < prices.length; i++) { // 找到一个更小的数就替换 if (prices[i] <= min) { min = prices[i]; } else { res = Math.max(res,prices[i] - min); } } return res; } }
classSolution{ publicintadd(int a, int b){ // 直到进位数为0,就停止循环 while(b != 0) { int c = (a & b) << 1; a ^= b; b = c; } return a; } }
66. 构建乘积数组
这题主要是除了当前元素其他元素都相乘,其实就算数左边的元素的乘积与右边元素的乘积的乘积。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution{ publicint[] constructArr(int[] a) { if (a.length <= 1) return a; int[] res = newint[a.length]; int left = 1; int right = 1; for(int i = 0; i < a.length; i++) { res[i] = left; left *= a[i]; } for(int i = a.length - 1; i > -1; i--) { res[i] *= right; right *= a[i]; } return res; } }
68.1 二叉搜索树的最近公共祖先
这题主要总结节点的情况,该题的节点应该是分为三种的。
p和q都在左子树
p和q都在右子树
p和q一个在左子树,一个在右子树(这种情况的节点就算二叉树的最近公共祖先)
了解了状态这题应该就不难了。
1 2 3 4 5 6 7 8 9 10
classSolution{ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){ if (root == null) returnnull; if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q); if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q); return root; } }
68.2 二叉树的最近公共祖先
这题的分析跟上面的情况一样,只是判断子树的情况不太一样。
1 2 3 4 5 6 7 8 9 10 11
classSolution{ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){ if (root == p || root == q || root == null) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if (left == null) return right; if (right == null) return left; if (left != null && right != null) return root; returnnull; } }