最近沉迷扫雷，无法自拔。恍然一看这周还没刷题，心都碎了。今天开始要赶进度了，开始刷题。
01矩阵
题目：给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。
示例 1：
输入：
[[0,0,0],
[0,1,0],
[0,0,0]]
输出：
[[0,0,0],
[0,1,0],
[0,0,0]]
示例 2：
输入：
[[0,0,0],
[0,1,0],
[1,1,1]]
输出：
[[0,0,0],
[0,1,0],
[1,2,1]]
提示：
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
思路:这个题的思路还是很清晰的，我觉得就是一层一层的过。直到所有的元素都填满。因为没有任何时间空间要求，我先去用暴力法试试超不超时。
有点小神奇，居然ac了并且性能超过百分之九十九，哈哈。先贴代码：
class Solution {
public int[][] updateMatrix(int[][] matrix) {
int n = 0; //记录一共多少要该的数字
for(int i = 0;i<matrix.length;i++) {
for(int j = 0;j<matrix[0].length;j++) {
if(matrix[i][j]==1) {
n++;
matrix[i][j] = -1;
}
}
}
int temp = 0;
while(n>0) {//说明还有要该的数字，所以继续循环
for(int i = 0;i<matrix.length;i++) {
for(int j = 0;j<matrix[0].length;j++) {
//这个元素开始四外扩散.因为从小的开始扩散，所以先赋值的肯定是最小的
if(matrix[i][j]==temp) {
if(i>0 && matrix[i-1][j] == -1) {
matrix[i-1][j] = temp+1;
n--;
}
if(i<matrix.length-1 && matrix[i+1][j] == -1) {
matrix[i+1][j] = temp+1;
n--;
}
if(j>0 && matrix[i][j-1] == -1) {
matrix[i][j-1] = temp+1;
n--;
}
if(j<matrix[0].length-1 && matrix[i][j+1] == -1) {
matrix[i][j+1] = temp+1;
n--;
}
}
}
}
//第一遍填充0周围的，第二次填充1周围的。。。依次类推，直到都填完
temp++;
}
return matrix;
}
}
这个题就像我之前说的思路差不多，一层一层的往外填充，最终没有可填充元素就说明都填完路径了，跳出循环return就好了。其实这个题挺有意思，哪怕思路清晰代码也比较麻烦。我挺喜欢这种的，不是一眼就能看出答案，但是又不是死活想不出来。哈哈。下一题了。
朋友圈
题目：班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1：
输入：
[[1,1,0],
[1,1,0],
[0,0,1]]
输出：2
解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回 2 。
示例 2：
输入：
[[1,1,0],
[1,1,1],
[0,1,1]]
输出：1
解释：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1 。
提示：
1 <= N <= 200
M[i][i] == 1
M[i][j] == M[j][i]
思路：找个语文好的翻译这么难么？这个题我反复读了几遍才懂。总而言之这个题叫深搜还是光搜啥的来这，反正是有思路，而且本质上就数组长度个人，应该不难，我去试试。
这个性能我绝望了，自我感觉良好，现实给我一巴掌。先贴代码：
class Solution {
public int findCircleNum(int[][] M) {
int n = 0;
for(int i = 0;i<M.length;i++) {
if(M[i][i] == 1) {//说明这个人没被纳入圈子，可以单独开圈
n++;
M[i][i] = -1;
//把和这个能一个圈的都纳入
dfs(M, i);
}
}
return n;
}
public void dfs(int[][] M,int i) {
//如果跟这个有关系说明是一个圈子
for(int k = 0;k<M.length;k++) {
if(M[i][k] == 1) {
M[i][k] = -1;
M[k][k] = -1;
//M[i][k] = 1 说明i和k有关系，k进入i的圈子.同时k圈子里的也都进入
dfs(M, k);
}
}
}
}
这个其实就是每个同学只能有一个圈子，所以有圈子的不用管了。所有没圈子的判断一遍就好了。感觉性能不应该这样啊，我去看看性能排行第一的代码吧。
看了半天解析没太懂，据说这个是查并集的题，我反正贴上题解下一题了：
class Solution {
// DFS
// public int findCircleNum(int[][] M) {
// if (M == null || M.length == 0) {
// return 0;
// }
// int count = 0;
// boolean[] visited = new boolean[M.length];
// for (int i = 0; i < M.length; i++) {
// if (!visited[i]) {
// dfs(M, visited, i);
// ++ count;
// }
// }
// return count;
// }
// public void dfs(int[][] M, boolean[] visited, int i) {
// for (int j = 0; j < M.length; j++) {
// if (M[i][j] == 1 && !visited[j]) {
// visited[j] = true;
// dfs(M, visited, j);
// }
// }
// }
// BFS second
// public int findCircleNum(int[][] M) {
// if (M == null || M.length == 0) {
// return 0;
// }
// int length = M.length;
// int count = 0;
// boolean[] visited = new boolean[length];
// for (int i = 0; i < length; i++) {
// if (!visited[i]) {
// bfs(M, visited, i);
// count++;
// }
// }
// return count;
// }
// public void bfs(int[][] M, boolean[] visited, int i) {
// for (int j = 0; j < M.length; j++) {
// if (!visited[j] && M[i][j] == 1) {
// visited[j] = true;
// bfs(M, visited, j);
// }
// }
// }
// 并查集 错误
// public int findCircleNum(int[][] M) {
// if (M == null || M.length == 0) {
// return 0;
// }
// int[] parent = new int[M.length];
// for (int i = 0; i < M.length; i++) {
// parent[i] = i;
// }
// for (int i = 0; i < M.length; i++) {
// for (int j = i + 1; j < M.length; j++) {
// if (M[i][j] == 1) {
// parent = union(M, parent, i, j);
// }
// }
// }
// Set<Integer> set = new HashSet();
// for (int p : parent) {
// set.add(p);
// }
// return set.size();
// }
// public int[] union(int[][] M, int[] parent, int i, int j) {
// int pi = parent(M, parent, i);
// int pj = parent(M, parent, j);
// parent[pj] = pi;
// return parent;
// }
// public int parent(int[][] M, int[] parent, int i) {
// int result = i;
// while (parent[result] != result) {
// parent[result] = parent[parent[result]];
// result = parent[result];
// }
// while (parent[i] != i) {
// int temp = i;
// i = parent[i];
// parent[temp] = result;
// }
// return result;
// }
// 并查集
// public int findCircleNum(int[][] M) {
// if (M == null || M.length == 0) {
// return 0;
// }
// int n = M.length;
// Union union = new Union(n);
// for (int i = 0; i < n; i++) {
// for (int j = i + 1; j < n; j++) {
// if (M[i][j] == 1) {
// union.union(M, i, j);
// }
// }
// }
// return union.getCount();
// }
// class Union {
// private int count;
// private int[] parent;
// public Union(int n) {
// count = n;
// parent = new int[n];
// for (int i = 0; i < n; i++) {
// parent[i] = i;
// }
// }
// public void union(int[][] M, int i, int j) {
// int pi = find(M, i);
// int pj = find(M, j);
// if (pi == pj) {
// return;
// }
// parent[pj] = pi;
// count --;
// }
// public int find(int[][] M, int i) {
// int result = i;
// while (parent[result] != result) {
// parent[result] = parent[parent[result]];
// result = parent[result];
// }
// return result;
// }
// public int getCount() {
// return count;
// }
// }
// 并查集 second
// public int findCircleNum(int[][] M) {
// if (M == null || M.length == 0) {
// return 0;
// }
// int n = M.length;
// Union u = new Union(n);
// for (int i = 0; i < n; i++) {
// for (int j = i + 1; j < n; j++) {
// if (M[i][j] == 1) {
// u.union(M, i, j);
// }
// }
// }
// return u.count();
// }
// class Union {
// private int count;
// private int[] p;
// public Union(int n) {
// this.count = n;
// p = new int[n];
// for (int i = 0; i < n; i++) {
// p[i] = i;
// }
// }
// public void union(int[][] M, int i, int j) {
// int pi = this.parent(i);
// int pj = this.parent(j);
// if (pi == pj) {
// return;
// }
// p[pj] = pi;
// count --;
// }
// public int parent(int i) {
// while(p[i] != i) {
// i = p[p[i]];
// }
// return i;
// }
// public int count() {
// return count;
// }
// }
public int findCircleNum(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int n = M.length;
Union u = new Union(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (M[i][j] == 1) {
u.union(i, j);
}
}
}
return u.count();
}
class Union {
private int n;
private int count;
private int[] p;
public Union(int n) {
this.n = n;
this.count = n;
p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = i;
}
}
public void union(int i, int j) {
int pi = findParent(i);
int pj = findParent(j);
if (pi != pj) {
count--;
p[pj] = pi;
}
}
public int findParent(int i) {
while(p[i] != i) {
i = p[p[i]];
}
return i;
}
public int count() {
return count;
}
}
}
（ps：吐槽一下写上面代码的大佬，确实厉害，好几个版本。）下一题了。
最优除法
题目：给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
示例：
输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释:
1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。
其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
说明:
输入数组的长度在 [1, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。
思路：这个题怎么说呢，本来看了名字我都不想做了，以为又是位操作的那种呢，不过审完题觉得是我想错了。其实这个题的思路我觉得应该挺清晰的。每个数字都是正整数。而除法来讲，被除数.除数，商的关系。我感觉这个题是dp啊，不知道感觉对不对。尤其是最多只有10个数。。是不是说明这个暴力法会超时？我一一去试试。
我可能是个憨憨，在那寻思半天，真正的要做了的时候才发现个问题。这个题就三者。第一是被除数，第二个除数。第三个是商。想要商最大就是被除数最大，除数最小就行了。因为都是正整数。所以肯定是越除越小。直接第一个数除后面所有相除的结果，这个题简单到离谱。。直接贴代码：
class Solution {
public String optimalDivision(int[] nums) {
StringBuffer sb = new StringBuffer();
sb.append(nums[0]);
int len = nums.length;
if(len == 1) return sb.toString();
if(len == 2) return sb.append("/"+nums[1]).toString();
sb.append("/(");
for(int i = 1;i<len-1;i++) sb.append(nums[i]+"/");
return sb.append(nums[len-1]+")").toString();
}
}
我这个其实是好几次改版的结果了，感觉这个题就是一个性能比拼，我去看看性能第一的代码怎么处理的吧：
class Solution { // 1000/((100/10)/2) 这样就是最大的
public String optimalDivision(int[] nums) {
StringBuilder sb = new StringBuilder();
sb.append(nums[0]);
if (nums.length == 1) return sb.toString();
sb.append('/');
if (nums.length == 2) {
sb.append(nums[1]);
return sb.toString();
}
sb.append('(');
for (int i = 1; i < nums.length; i++) {
sb.append(nums[i]);
sb.append('/');
}
sb.deleteCharAt(sb.length() - 1);
sb.append(')');
return sb.toString();
}
}
纯粹的代码性能优化，不多说了，下一题。
砖墙
题目：你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
题目截图
思路：这个题挺有意思。其实思路是有的，比如说二维数组。但是那样明显性能有问题。所以我现在的想法是怎么不用二维数组实现这个计算。初步的想法很多。不管是map还是set其实都可以实现一个记录。每一个墙缝都记录。这样这一层不在墙缝的就要穿。实现一个记录。但是最多的话1w1w的计算量是少不了了。哪怕剪枝也不见得能ac，我先去试试吧。*
完美的超时了，所以这个果然不行。我再去看看。反着思路能不能好一点。一定是从一个墙缝开始算的。有了墙缝才可能会少于给定长度。
我也不知道今天是什么邪，做出来每一个性能好的，我直接贴代码：
class Solution {
public int leastBricks(List<List<Integer>> wall) {
//list下标代表层数，值代表这层的墙缝
List<Set<Integer>> list = new ArrayList<Set<Integer>>();
int wide = 0;
for(int i = 0;i<wall.size();i++) {
Set<Integer> set = new HashSet<Integer>();
int sum = 0;
for(int j =0;j<wall.get(i).size();j++) {
sum = sum +wall.get(i).get(j);
set.add(sum);
}
list.add(set);
wide = sum;
}
int min = list.size();
int max = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(Set<Integer> set:list) {
for(Integer i:set) {
if(i == wide) continue;
if(map.get(i)!=null) {
map.put(i,map.get(i)+1);
}else {
map.put(i, 1);
}
max = Math.max(max,map.get(i));
}
}
return min-max;
}
}
思路还是挺清楚的，第一步获取所有的墙缝。第二步最大值是所有层数（一个缝没有）。第三步减去缝最多的那一层的缝。反正整体思路就这样，ac了，优化点感觉不少。我直接去看性能排行第一的代码吧，懒得自己优化了：
class Solution {
public int leastBricks(List<List<Integer>> wall) {
int n=wall.size();
if(n==0||n==1&&wall.get(0).size()>1) return 0;
//统计有效节点数目（没有去重）
int count=0;
for(int i=0;i<n;i++){
count+=wall.get(i).size()-1;
}
if(count==0) return n;
//计算节点位置,入栈
int[] points=new int[count];
int p=-1;
for(List<Integer> list:wall){
int listSize=list.size();
if(listSize==1) continue;
points[++p]=list.get(0);
for(int i=1;i<listSize-1;i++){
points[++p]=list.get(i);
points[p]+=points[p-1];
}
}
//排序
Arrays.sort(points);
//统计相同节点最大数目
int max=-1;
int bucket=points[0]; int num=0;
for(int e:points){
if(e==bucket) num++;
else{
max=Math.max(max,num);
bucket=e;
num=1;
}
}
max=Math.max(max,num);
return n-max;
}
}
这个怎么说呢，感觉思路是差不多的，找到墙缝最多的那一层。不过实现起来比我的要优雅一些。各种数组操作比我set各种map判断应该是好的。算是学到了一些细节处理的东西。下一题吧。
下一个更大元素3
题目：给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。
示例 1:
输入: 12
输出: 21
示例 2:
输入: 21
输出: -1
思路：这个题怎么说呢，我觉得还好吧。挺好理解的，应该也挺好做的。首先比这个大，而且位数相同。就是这个几个数字的重排序。如何只大一点？我感觉是首先列出所有的数字。从后往前遍历。遇到小于后面的元素则替换成稍微大一点的那个。然后后面的正序填充。反正是有思路但是说不出来，我去直接试试代码。
第一版本的代码ac了，我先贴代码：
class Solution {
public int nextGreaterElement(int n) {
if(n<10) return -1;
char[] num = String.valueOf(n).toCharArray();
List<Character> list = new ArrayList<Character>();
list.add(num[num.length-1]);
for(int i = num.length-2;i>=0;i--) {
if(num[i]<num[i+1]) {
//肯定是有降序才能值更大。
Collections.sort(list);
for(int j = 0;j<list.size();j++) {
if(list.get(j)>num[i]) {
char temp = num[i];
num[i] = list.get(j);
list.remove(j);
list.add(j, temp);
for(int k = 0;k<list.size();k++) {
num[++i] = list.get(k);
}
Long res = Long.valueOf(new String(num));
return res>Integer.MAX_VALUE?-1:Integer.valueOf(new String(num));
}
}
}else {
list.add(num[i]);
}
}
return -1;
}
}
其实这个题不算难，我上面的代码就是找到第一个较小值，换成较大的，然後后面从小到大依次排列。执行时间是1ms，我觉得可能是细节处理上有一些问题。我去试试。算了，我直接附上性能排行第一的代码:
class Solution {
public int nextGreaterElement(int n) {
char[] arr = String.valueOf(n).toCharArray();
int i = arr.length - 2 ;
while(i >= 0 && arr[i] >= arr[i+1]){
i -- ;
}
if(i < 0) return -1 ;
int j = arr.length -1 ;
while(j > i && arr[i] >= arr[j]){
j -- ;
}
swap(arr, i , j);
reverse(arr,i+1);
try{
return Integer.parseInt(new String(arr));
}catch(Exception e){
return -1 ;
}
}
public void swap(char[] arr , int i , int j){
char a = arr[i];
arr[i] = arr[j];
arr[j] = a;
}
public void reverse(char[] arr , int i){
int r = arr.length -1;
while(i < r){
swap(arr,i++,r--);
}
}
}
其实代码不难，思路也不是理解不了，就是一开始没想到而已。这个题我都不知道说什么好了，所以直接过吧。下一题。
和为k的子数组
题目：给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
思路：感觉是滑窗吧。毕竟要连续的子数组。双指针一个在前一个在后。和小于k后面的指针往后走。和大于k前面的指针往后走。反正思路还算清晰。但是这个题有个很大的问题，那就是这个元素可能是负的。这就让滑窗变得复杂了。我再想想。
算了，暂时没有什么好思路，我先暴力破解一下试试：
暴力法一次ac了。。虽然是低空掠过。。我附上代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
for(int i = 0;i<nums.length;i++){
int sum = nums[i];
if(sum == k) res++;
for(int j = i+1;j<nums.length;j++) {
sum += nums[j];
if(sum == k) res++;
}
}
return res;
}
}
我去看看性能排行第一的代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int[] preSum = new int[nums.length];
preSum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
preSum[i] = preSum[i - 1] + nums[i];
}
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int ans = 0;
for (int i = 0; i < nums.length; i++) {
Integer cnt = null;
if ((cnt = map.get(preSum[i] - k)) != null) {
ans += cnt;
}
if ((cnt = map.get(preSum[i])) != null) {
map.put(preSum[i], cnt + 1);
} else {
map.put(preSum[i], 1);
}
}
return ans;
}
}
！！！！这个思路我居然没想到！这几天没怎么做题感觉脑子都生锈了。这种方式我以前用过。如果一系列操作以后和操作之前的差值是k。说明这写数字可以凑成k。很简单的一个思路但是我偏偏没想到，太生气了。只要懂了就能明白的思路，我就不多说了，这个题就这样了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利！
网友评论