组合总和3
题目：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
思路：这个题我见过呀，我记得之前是回溯实现的。不过这个题我觉得好像稍微简单一些，毕竟只能1-9.然后还不许重复。其实我总觉得这个题不会太难。我都不打算用回溯了，直接拆数不知道行不行，我去试试吧。
好的吧，写着写着还是变成了回溯。。我直接贴代码：
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new ArrayList<List<Integer>>();
dfs(new ArrayList<Integer>(),k,n,1);
return res;
}
public void dfs(List<Integer> list,int k,int n,int start){
//正好k个数和是n
if(k==0 && n==0) {
res.add(list);
return;
}
if(k<=0 && n<=0) return;
for(int i = start;i<=9;i++){
//剩下的和比能选的数字都小，直接pass
if(n<i) break;
list.add(i);
dfs(new ArrayList<Integer>(list),k-1,n-i,i+1);
list.remove(list.size()-1);
}
}
}
真的是做着做着还是觉得回溯最不用动脑，甚至不考虑性能的话剪枝都不用，全便利呗。。。不然还得一点点想。。哈哈，我反正就这样了，看看性能排行第一的代码吧：
额，也是回溯，然后我这里是减法，人家是加法而已，我直接贴代码：
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
back(n,k,0,1,0,new ArrayList<>(),res);
return res;
}
//pos为组合长度
public void back(int n,int k,int pos,int start,int tmp,List<Integer> list,List<List<Integer>> res)
{
if(pos > k || tmp >n)
return;
if(pos == k && tmp == n)
{
res.add(new ArrayList<>(list));
return;
}
for(int i = start;i<=9;i++)
{
list.add(i);
back(n, k, pos+1, i+1, tmp+i, list, res);
list.remove(list.size()-1);
}
}
}
这道题其实比较简单，所以就这样了，下一题。
三维形体的表面积（简单）
题目：在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。请你返回最终形体的表面积。
示例 1：
输入：[[2]]
输出：10
示例 2：
输入：[[1,2],[3,4]]
输出：34
示例 3：
输入：[[1,0],[0,2]]
输出：16
示例 4：
输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32
示例 5：
输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46
提示：
1 <= N <= 50
0 <= grid[i][j] <= 50
思路：这道题我刷过，甚至以前记录过，不过我是现在才知道leetcode每天有一道题给积分了，今天就是这道题，上次还是三个月前做的，所以又刷了一边，很简单，主要是思路，我直接贴代码
class Solution {
public int surfaceArea(int[][] grid) {
int sum = 0;
int s = 0;
//有相邻的 减去两个面。先横数，然后竖数，最后摞着数
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
sum += grid[i][j];//一共方形个数
if(grid[i][j]>1)s += (grid[i][j]-1)*2;//多一个少两个面。
if(j != grid[0].length-1)s += Math.min(grid[i][j],grid[i][j+1])*2;//横着少的面数
if(i != grid.length-1)s += Math.min(grid[i][j],grid[i+1][j])*2;//竖着少的面数
}
}
return sum*6 - s;
}
}
这个只要反着想就很好做，有挨着的少两个面。然后我就不多说了，代码比较简洁。直接下一题了（这道不算今天刷的，还有两题）
存在重复元素
题目：给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false
思路：这个题乍一看很简单啊，仔细一看都是最大为而不是为。所以就从一个直接判断变成了范围判断。哎，不考虑时间的话，就是双层循环呗。外层左起始点，内层到k之前的范围。不过我觉得应该有什么简单的算法吧？不管了，先实现再说。
很好，很完美的超时了。果然一点懒不能偷，我还是好好想想怎么做吧。
额， 这个题我没做出来，所以面向邪恶势力低头了~~~接下来我贴代码:
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k==10000) return false;
for(int i = 0;i<nums.length-1;i++){
for(int j = 1; j<=k && (i+j)<nums.length;j++){
Long r = Long.valueOf(nums[i])-nums[i+j];
if(Math.abs(r)<=t) return true;
}
}
return false;
}
}
这个题有点羞愧，真的是感觉有简单算法，但是自己没想出来，然后看了评论都是面向测试案例编程（这个等于10000直接返回false是测试案例中的一个回超时的案例）
刚刚看了题解，这个题是我知识上的盲区。这个应该是滑窗解决。这个问题好解决。但是因为是范围的，所以单纯的双指针滑窗不行，还需要一些数据结构，这里treeMap和treeSet都可以的。。但是我两个都不会~~哈哈，决定明天去好好补补这方面的知识。不过这里我还是贴出来方法共同学习下吧：
这个方法的前提是对 TreeSet 这个数据结构要了解。其中有一个方法 public E ceiling(E e) ，返回 treeSet 中大于等于 e 的元素中最小的元素，如果没有大于等于 e 的元素就返回 null。
还有一个对应的方法，public E floor(E e)，返回 treeSet 中小于等于 e 的元素中最大的元素，如果没有小于等于 e 的元素就返回 null。
并且两个方法的时间复杂度都是 O(log(n))。
此时我们去寻找窗口中是否存在 x - t ~ x + t 的元素。
如果我们调用 ceilling(x - t) 返回了 c，c 是窗口内大于等于 x - t 中最小的数。
只要 c 不大于 x + t, 那么 c 一定是我们要找的了。否则的话，窗口就继续右移。
代码的话，由于溢出的问题，运算的时候我们直接用 long 强转。
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> set = new TreeSet<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > k) {
set.remove((long)nums[i - k - 1]);
}
Long low = set.ceiling((long) nums[i] - t);
//是否找到了符合条件的数
if (low != null && low <= (long)nums[i] + t) {
return true;
}
set.add((long) nums[i]);
}
return false;
}
这个题就到这里，最后一题。
最大正方形
题目：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
思路：这个题我感觉应该可以用双层遍历来解决吧。最笨的办法，每一个1作为一个起始点，取横竖都是1的正方形面积。然后从头遍历到尾，只要是1就作为左上角判断下能组成正方形面积最大多少，最后取最大值。只不过话说回来，这么做无用功也是很多的。而且写起来肯定很墨迹，我还是想想能怎么优雅的处理吧。
其实这个规律画个图比较好找点，如图，当前是0不用管，所以就这样。如果当前是1则最小是1了。如果当前是1怎么判断最大是多少呢？如图我是把当前点作为图形的左上来判断，那么只要知道它的下面，右边，右下分别是多少就行了，但凡这三个位置有1个是0，说明没办法凑成正方形1，所以当前值也只能是1.如果三个位置都是1的话，起码说明下，右，右下都是1，凑成了边长2的正方形。换言之数字不同，但是我们要取的应该是三个值中最小的边，然后边长+1。最终取结果最大的那个，如图中最大的就是黄的，边长是3，面积就是9.
图解
然后我逻辑已经理清楚了，我去写代码了。
class Solution {
public int maximalSquare(char[][] matrix) {
// base condition
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;
int height = matrix.length;
int width = matrix[0].length;
int maxSide = 0;
// 相当于已经预处理新增第一行、第一列均为0
int[][] dp = new int[height + 1][width + 1];
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
if (matrix[row][col] == '1') {
dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1;
maxSide = Math.max(maxSide, dp[row + 1][col + 1]);
}
}
}
return maxSide * maxSide;
}
}
对，这个叫做动态规划（用数组记录中间过程的递归）,其实这个挺典型的，但是我一开始没反应过来。直到自己理出逻辑来才发现这个是动态规划的变种。反正就这样了，虽然性能不咋地但是起码做出来了。
接下来我去看看性能排行第一的代码;
class Solution {
char[][] matrix;
int rows;
int columns;
int maxSide;//记录最大正方形边长
public int maximalSquare(char[][] matrix) {
if (matrix == null) return 0;
this.matrix = matrix;
rows = matrix.length;
if (rows == 0) return 0;
columns = matrix[0].length;
maxSide=0;
for(int i=0;i<rows;i++){
getCases(i);
}
return maxSide*maxSide;
}
private void getCases(int row){
if(rows-row<=maxSide) return;
char[] mix=matrix[row].clone();
for(int i=row+1;i<=row+maxSide;i++){
char[] assist=matrix[i];
for(int j=0;j<columns;j++){
mix[j]&=assist[j];
}
}
if(!existSquare(mix,maxSide+1)) return;
int add=1;
for(int i=row+maxSide+1;i<rows;i++){
char[] assist=matrix[i];
for(int j=0;j<columns;j++){
mix[j]&=assist[j];
}
if(!existSquare(mix,i-row+1)) break;
add++;
}
maxSide+=add;
}
private boolean existSquare(char[] mix,int height){
int i=0;
while (i<columns){//每一趟检测以位置i为开始的连续1的长度
if(mix[i]=='0'){
i++;
}else {
int num=1;
while (i+1<columns&&mix[i+1]=='1'){
i++;
num++;
}
if(num>=height) return true;
i++;
}
}
return false;
}
}
额，要不咋说人家性能好呢~~洋洋洒洒恨不得自己写个工具包了，反正我还是选择我自己是性能不是那么好的代码了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！最近工作比较忙，天天加班到九十点钟，所以每天三道题都有点刷不完了，本来还预计的专门整理一下排序算法的~哎，这个债啊，真的是越来越多。有空一定要静下心来整理整理东西。也希望大家不忘初心！
网友评论