额，昨天的三十九莫名其妙被锁了，也发邮件申请解锁了。本来当时有点 生气，但是后来一想反正我自己能看见，也就罢了，今天顺序40.ps：元旦快乐！
较大分组的位置
题目：在一个由小写字母构成的字符串 S 中，包含由一些连续的相同字符所构成的分组。例如，在字符串 S = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。最终结果按照字典顺序输出。
示例 1:
输入: "abbxxxxzzy"
输出: [[3,6]]
解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。
示例 2:
输入: "abc"
输出: []
解释: "a","b" 和 "c" 均不是符合要求的较大分组。
示例 3:
输入: "abcdddeeeeaabbbcd"
输出: [[3,5],[6,9],[12,14]]
说明: 1 <= S.length <= 1000
思路：目前我的思路就是遍历一边。用计数器和一个起始常量来存数组。我先去实现了。
好了，两次做出来。一开始有个细节错了！这里大于等于3就可以。一开始我计数器大于三才可以。后来测试案例没通过找到这个问题了。其实只要计数器大于2就行（或者大于等于3）。直接贴代码:
class Solution {
public List<List<Integer>> largeGroupPositions(String S) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int start = 0;
int count = 1;
char[] c = S.toCharArray();
for(int i = 0;i<c.length-1;i++){
if(c[i]==c[i+1]){
count++;
}else{
if(count>2){
List<Integer> list = new ArrayList<Integer>();
list.add(start);
list.add(i);
res.add(list);
}
start = i+1;
count = 1;
}
}
if(count>2){
List<Integer> list = new ArrayList<Integer>();
list.add(start);
list.add(c.length-1);
res.add(list);
}
return res;
}
}
性能只超过百分之八十八的人，我也很懵逼我这个性能为啥不好啊。直接看性能第一的代码了：
哦，看完了，我这个是从0开始，判断到倒数第二个。人家是从1开始判断到最后一个。虽然不知道性能为啥有差但是既然那么写性能好也就贴上吧。
class Solution {
public List<List<Integer>> largeGroupPositions(String S) {
List<List<Integer>> ans = new ArrayList<>();
char[] str = S.toCharArray();
int pre = 0;
for(int i = 1;i <= str.length;i++){
if(i == str.length || str[i] != str[pre]){
if(i - pre >= 3){
List<Integer> list = new ArrayList<>();
list.add(pre);
list.add(i - 1);
ans.add(list);
}
pre = i;
}
}
return ans;
}
}
反转图像
题目：给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
示例 1:
输入: [[1,1,0],[1,0,1],[0,0,0]]
输出: [[1,0,0],[0,1,0],[1,1,1]]
解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
示例 2:
输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
说明:
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
思路：图片平滑器，翻转像素啥的，都是这种二维数组的题。其实难是不难，就是处理墨迹。这道题也是。其实也不难，就是两步：1，元素倒叙。2.1变0，0变1。只不过放到二维数组中应该很墨迹。我去暴力实现了。
如我所说。暴力实现。性能超过百分百。所以这道题直接贴代码过:
class Solution {
public int[][] flipAndInvertImage(int[][] A) {
for(int i = 0;i<A.length;i++){
A[i]=reverse(A[i]);
}
return A;
}
public int[] reverse(int[] s){
int l = 0;
int r = s.length-1;
while(r>l){
int temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
for(int i = 0;i<s.length;i++){
s[i] =(s[i] == 0?1:0);
}
return s;
}
}
矩形重叠
题目：矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。给出两个矩形，判断它们是否重叠并返回结果。
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true
示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false
说明：
两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
矩形中的所有坐标都处于 -10^9 和 10^9 之间。
思路：这道题怎么说呢。感觉很简单。但是一时间又不是直接能做出来的。难受。我理理思路！绝对是有一种判断方法的。首先不重叠就是两个三角形绝对没有边交叉（挨着的不算）。然后给定的点已经确定是左下，右上了。同时能求出四个点了。只需要判断其中一个矩形四个点在另一个矩形上面/下面/左边/右边就行了。不然就是有重叠的。我照着这个思路去试试。
首先思路没错！！！其次这个题目有点反常规思路啊！！怎么测试怎么不对，后来仔细读了题目，不重叠false，重叠是true。我一直理解反了。。。
直接贴代码吧：
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
//rec1[0]是矩形1 的下边横坐标。rec1[1]是矩形1左边纵坐标
//rec1[2]是矩形1 的上边横坐标 rec1[3]是矩形1右边纵坐标
//同理 rec2也是这样。
//在上面的上面就是不重叠。下面的下面不重叠，左边左边不重叠，右边左边不重叠
if (rec1[0] >= rec2[2]
|| rec2[0] >= rec1[2]
|| rec1[1] >= rec2[3]
|| rec2[1] >= rec1[3]) {
return false;
}
return true;
}
}
这个题就是比较抽象，我用画图一直来回来去画然后去想象。但是其实理解了以后很简单的，除了不重叠的剩下都是重叠。下一题。
矩阵中的幻方
题目：3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
示例：
输入: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
输出: 1
解释:
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276
而这一个不是：
384
519
762
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
提示:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15
思路：这道题很有意思啊。名字起的就有意思。还幻方，我还幻奇幻天幻读呢~~哈哈，说正经的。这道题除了暴力法我也没啥思路。就是从左上开始三个三个判断呗？我去尽量实现下。
说真的，这个题简直有毒！我做出来了，暴力法，各种暴力！然后性能超过百分百？？考点是什么？？？？直接贴代码：
class Solution {
public int numMagicSquaresInside(int[][] grid) {
int res = 0;
int len = grid.length;
int subLen = grid[0].length;
if(len<3||subLen<3) return 0;
for(int i = 0;i<len-2;i++){
for(int j = 0;j<subLen-2;j++){
if(grid[i][j]==5) continue;
int n = grid[i][j]+grid[i][j+1]+grid[i][j+2];
if(n!=15) continue;
if(grid[i][j]>9 || grid[i][j+1]>9 ||grid[i][j+2]>9) continue;
if(grid[i+1][j]>9||grid[i+1][j+1]>9||grid[i+1][j+2]>9) continue;
if(grid[i+2][j]>9||grid[i+2][j+1]>9||grid[i+2][j+2]>9) continue;
if(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2]!=n) continue;
if(grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2]!=n) continue;
if(grid[i][j]+grid[i+1][j]+grid[i+2][j]!=n) continue;
if(grid[i][j+1]+grid[i+1][j+1]+grid[i+2][j+1]!=n) continue;
if(grid[i][j+2]+grid[i+1][j+2]+grid[i+2][j+2]!=n) continue;
if(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]!=n) continue;
if(grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]!=n) continue;
res++;
}
}
return res;
}
}
这一串if 我自己写的自己都恶心。。。我再去看看大神代码？有没有简单点的方式：
也没啥好法，都是生加。。。这个题就这么过了吧。
比较含退格的字符串
题目：给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
示例 1：
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。
示例 3：
输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。
思路：这个题又是一个送分题。不就是有#删除前面的字符（如果前面有字符的话），然后判断两个字符串是不是相等么？我先去实现了。
唔，怎么说呢，实现是实现了。就是性能不好。我是用最直接的方式实现的：
class Solution {
public boolean backspaceCompare(String S, String T) {
return getStr(S).equals(getStr(T));
}
public String getStr(String s){
char [] sc = s.toCharArray();
for(int i = 0;i<sc.length;i++){
if(sc[i]=='#'){
sc[i] = ' ';
int n = i;
while(n>1 && sc[n-1]==' '){
n--;
}
if(n>0) sc[n-1] = ' ';
}
}
return new String(sc).replace(" ","");
}
}
我去想想有什么好的实现方式。有一个新想法:用stringbuffer处理试试，刚刚看了源码，是有删除指定下标的方法的。
我去实现啦：
很好，优化完立刻超过百分之九十九的人了。贴代码:
class Solution {
public boolean backspaceCompare(String S, String T) {
return getStr(S).equals(getStr(T));
}
public String getStr(String s){
char [] sc = s.toCharArray();
StringBuffer sb = new StringBuffer();
for(int i = 0;i<sc.length;i++){
if(sc[i]!='#'){
sb.append(sc[i]);
}else{
if(sb.length()-1>=0){
sb.deleteCharAt(sb.length()-1);
}
}
}
return sb.toString();
}
}
这道题就这么过了，最后一题：
到最近的人的最大距离
题目：在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。至少有一个空座位，且至少有一人坐在座位上。亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。返回他到离他最近的人的最大距离。
示例 1：
输入：[1,0,0,0,1,0,1]
输出：2
解释：
如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
因此，他到离他最近的人的最大距离是 2 。
示例 2：
输入：[1,0,0,0]
输出：3
解释：
如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
这是可能的最大距离，所以答案是 3 。
提示：
1 <= seats.length <= 20000
seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。
思路：又是似曾相似的一道题！类似的做过好多，现在看啥都隐隐见过，，哈哈，直接说这道题:抛去首位。找出中间0的最大连续数除2（首位如果是0开始结束则全算）。然后计算最大值就行了。我去做做，感觉这个题应该不难。我甚至想到一个用字符串处理的偷懒方法，哈哈
emmm...我残存的良知让我没有偷懒，没直接用字符串处理。因为比较简单所以直接贴代码：
class Solution {
public int maxDistToClosest(int[] seats) {
int[] arr = new int[seats.length];
//新数组下标
int index = 0;
//最大连续0数
int max = 0;
//计数
int c = 0 ;
for(int i=0;i<seats.length;i++){
if(seats[i]==0){
c++;
}else{
if(c!=0){
max = max>c?max:c;
arr[index]=c;
c = 0;
index++;
}
}
}
if(c!=0){
max = max>c?max:c;
arr[index]=c;
index++;
}
if(max%2==0){
max = max/2;
}else{
max = max/2+1;
}
if(seats[0]==0) max = Math.max(max,arr[0]);
if(seats[seats.length-1]==0) max = Math.max(max,arr[index-1]);
return max;
}
}
其实这个题还是很麻烦的。麻烦就麻烦在开始结尾是0.还有0的奇数偶数问题，虽然都是一行代码的事，但是多了也就变成上面的那么多行了。字符串处理能略简单一些。但是性能肯定好不了，而且我上面的代码性能已经超过百分之九十九的人了，所以这道题就这么过吧。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注~~另外今天元旦，祝大家2020新的一年心想事成万事如意！有诗有远方，有钱有梦想！多吃不胖，积极向上！
