重复的子字符串
题目：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
思路：审完题就不断的循环+循环在脑子里转。说一下大概的想法，只要可以由子串组成，只有两种情况：1，偶数个串，那么肯定字符串可以一分为二，前后相等。 2，奇数个串，除了第一个串以后还是一分为二前后相等。我去看看这种想法的实现难度。
嗯，首先可喜可贺，第一想法是可实现性是对的，按照这个思路是可以完成这个题目的！
但是！！！性能低到离谱！
我是真的觉得中午思路没有晚上好，心累。
class Solution {
public boolean repeatedSubstringPattern(String s) {
if(s.substring(0,s.length()/2).equals(s.substring(s.length()/2))) return true;
//不是二分，最少也得三个重复子字符串，所以直接遍历前三分之一就可以了。子字符串一定在这里面
for(int i = 1;i<=s.length()/3;i++){
StringBuffer sl = new StringBuffer(s.substring(0,i));
StringBuffer sr = new StringBuffer(s.substring(s.length()-i));
if(sl.toString().equals(sr.toString()) && s.length()%i==0){
int d = s.length()/i;
while(d>1){
sl.append(sr.toString());
d--;
}
if(sl.toString().equals(s)){
return true;
}
}
}
return false;
}
}
第一版本的代码就是这样，不优雅也不直观，但是能通过我就满意了。思路先判断是不是偶数个组成，这样true直接返回，不然就是某一段字符串不断追加，最后能成为整个字符串，说明true，不然就是false。
卧槽！看了题解心碎成渣，我感觉我从1一直加到了一万的委屈！！
这个题的逻辑：
String ss = s+s;
然后掐头去尾。
如果这个ss中还包含s，说明是子串组成的。
其实这个说起来很简单，理解起来还是有点抽象，我反正用了几组字符串实际测了几次才明白的，毕竟我是个傻子，哎。
class Solution {
public boolean repeatedSubstringPattern(String s) {
String ss =s+s;
ss = ss.substring(1,ss.length()-1);
if(ss.indexOf(s)!=-1){
return true;
}
return false;
}
}
！！！最让我安慰的是，性能排行第一的，用的是和我差不多的方法！！但是也有一些小区别，我这里不断创建StringBuffer是无用的消耗，人家处理的更加优雅和干练，直接附上代码：
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
for(int i=len/2;i>0;i--){
if(len%i != 0)
continue;
boolean flag = true;
for(int j=len/i;j>1;j--){
if(!s.substring(0,i).equals(s.substring((j-1)*i,j*i))){
flag = false;
break;
}
}
if(flag) return flag;
}
return false;
}
}
汉明距离
题目：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。
题目
思路：这道题，我看来看去，所谓是汉明距离是不是就是x异或y之后数字的二进制的1的个数？不知道是不是我理解错了，我先去按照这个想法用测试案例试试。顺便附上二进制运算符的意思，感觉用了很多次，在调用之前还要想想，有点烦躁
二进制运算符
这道题，一次过了！激动，这两天还以为自己变傻了，这么一看还是题目难度的问题，刚刚的思路完全没问题，异或，然后数1:
class Solution {
public int hammingDistance(int x, int y) {
int z = x^y;
int res = 0;
while(z>0){
if(z%2!=0){
res++;
}
z = z/2;
}
return res;
}
}
性能凑合，时间和内存消耗都七十多。我去瞅一眼性能超过百分百的代码：
有点无奈，百分百的代码是引用现成api的，然后我又去看了下这个api的源码，这么说吧，除了没看懂的剩下都看懂了。
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
api的实现
不纠结于这个位移了，下一题。
岛屿的周长
题目：给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
题目截图
思路：额，这个题其实蛮有意思的。我仔细看了会儿图，大概思路就是每一个这是一个数组型数组，每一个1判断上下左右0的个数，一个0可以加1（上下是上一个数组元素的同下标元素和下一个数组元素的同下标元素。左右就是同一个数组元素的左右元素。）这里的特别点就是边边的自动为0，比如第一个元素的左边自动是0，第一行元素的上面也自动是0、最后一个元素的右边，最后一个数组元素的下边 都是自动为0的.大概思路就是这样，接下来要代码实现了。
这么复杂的题，一次过了，给自己点赞，晚上给自己加餐，哈哈~~
说一下思路：换了个想法，按照上面说的做有点麻烦，换的思路是如果都不接壤，有几块陆地，就4块数的周长。但是接壤，两个边接一起，一下子少两个边。所以我们可以理解为：4块数 - 接壤2，剩下的周长就是岛的周长。
所以双循环遍历不变，遍历的目的：1，判断岛的块数。2，判断一行中岛接壤的块数（就是这一块和下一块都是1说明接壤了）。3，判断一列汇总岛接壤的块数。
最后块数4-接壤数*2.完美通过。
class Solution {
public int islandPerimeter(int[][] grid) {
int res = 0;
int in = 0;
for(int i = 0;i<grid.length;i++){
int [] arr = grid[i];
for(int j = 0;j<arr.length;j++){
//总岛块数
if(arr[j]==1){
res++;
}
//一行的接壤块数
if(j!=arr.length-1 && arr[j]==1 && arr[j+1]==1){
in++;
}
//一列的接壤块数
if(i!=grid.length-1 && grid[i][j]==1 && grid[i+1][j]==1){
in++;
}
}
}
return res*4-in*2;
}
}
这个性能超过八十多的人，相当自豪，接下来去看超过百分百的代码：
emmm~~一样一样的思路，就是人家的代码优雅点。我为了看着方便，用了一个arr表示每一层，人家没用而已。
class Solution {
public int islandPerimeter(int[][] grid) {
int c = 0;
int adj = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
c += 4;
if (j < grid[0].length - 1 && grid[i][j+1] == 1) adj++;
if (i < grid.length - 1 && grid[i+1][j] == 1) adj++;
}
}
}
return c - 2 * adj;
}
}
下一题。
供暖器
题目：冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。说明:
给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
思路：刚刚寻思贼多都寻思歪了，所以现在开始理思路：其实就是找到每个房子距离最近的取暖器，然后取最大的一个返回。拨开迷雾见太阳了啊。然后是代码实现
脑壳痛，一个惨痛的教训：不要用现实的逻辑来判断代码。啥JB数据都能出现。比如房子不一定连续的，可以跳着来，1房子后面直接跟5。比如唯一的供暖器离房子贼鸡儿远。再比如房子能倒着来，不是越来越远，是看心情放的。
嗯，在参考了大神的代码下终于完成了！对，我凭自己的能力完全做不出来了，心态太炸了。
说一下思路：思路没问题，然后代码也ok，但是运行总是得不到想要的结果，我到现在也很诧异啊。
首先两个数组排序，然后遍历房子，每一个房子取最近的暖气，然后一个变量专门存储最远距离（这里每出现一个距离都要比较，保证变量存的是最远的）。因为两边都排序了，所以可以判断左边距离和右边距离，如果右边比左边进，则整个暖气的指针往右挪一下（因为事先排好序的，所以可以保证以后所有的房子不可能出现前面的暖气是距离最近的暖气。）
一直到这里我思路都是对的，而且自测也通过，但是提交出现问题了。问题就是每一个数字都对应，几千个数字的时候，我这个跑起来就出问题了！
后来看了大神的代码，百分之九十九的相似，就是判断的时候略有不同，我判断的是当后一个指针距离大于当前指针距离，指针往后移。
然后大佬的思路是后一个指针距离大于等与当前指针距离就往后移。
虽然理论上可以明白，如果两边距离相等也可以继续往后比较了，但是我还是没明白之前出那个错是因为点啥。至今也不知道，我就好奇这个13703是哪里来的？想的都魔怔了。。
测试案例的数据！
数字的补数
题目：给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
注意:
给定的整数保证在32位带符号整数的范围内。
你可以假定二进制数不包含前导零位。
示例 1:
输入: 5
输出: 2
解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。
示例 2:
输入: 1
输出: 0
解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。
思路：这道题怎么说呢，一个数和32个1异或，是1就变0，是0变成1、然后输出这个数，有毛病么？我去试试吧
嗯，有点毛病，这里不能用32个1异或。因为人家说了不含前零导位。所以这个判断多少个1反而是重点，但是做起来也很简单，直接上代码:
class Solution {
public int findComplement(int num) {
int temp = num;
int i = 0;
while(temp > 0){
temp = temp>>1;
i = (i<<1)+1;
}
return num^i;
}
}
密钥格式化
题目:给定一个密钥字符串S，只包含字母，数字以及 '-'（破折号）。N 个 '-' 将字符串分成了 N+1 组。给定一个数字 K，重新格式化字符串，除了第一个分组以外，每个分组要包含 K 个字符，第一个分组至少要包含 1 个字符。两个分组之间用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。
示例 1：
输入：S = "5F3Z-2e-9-w", K = 4
输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；
注意，两个额外的破折号需要删掉。
示例 2：
输入：S = "2-5g-3-J", K = 2
输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。
提示:
S 的长度不超过 12,000，K 为正整数
S 只包含字母数字（a-z，A-Z，0-9）以及破折号'-'
S 非空
思路：这道题，是不是又有什么隐含的要求？应该能调用全部大写的api吧?应该能调用去掉所有'-'的api吧？那还有什么难度了？考的是什么？难不成是从后往前加‘-’是考点?我去写写代码，看看有没有坑。
嗯，确定了没有坑，但是各种api调用性能一般，直接上代码：
class Solution {
public String licenseKeyFormatting(String S, int K) {
S = S.replace("-","");
S =S.toUpperCase();
if(S.length()==0) return "";
StringBuffer sb = new StringBuffer();
int s = S.length()%K;
int n = S.length()/K;
if(s!=0) sb.append(S.substring(0,s)+"-");
while(n>0){
sb.append(S.substring(s,s+K)+"-");
s = s+K;
}
return sb.toString().substring(0,sb.toString().length()-1);
}
}
其实性能也不能说那么差吧，超过百分之六十多的人，但是没达到我的心里预期。我这里用的stringbuffer累加的，我不知道是我整个思路都不对还是说只是我的写法有问题，再想想思路。
看了性能比较好的前几位，怎么说呢，用的char数组，自己一步步加，不用replace。不用substring也不用sb，纯属组操作，真的是底层数据结构，不佩服不行，但是我自己做有点受不了。贴上大神代码:
class Solution {
public String licenseKeyFormatting(String S, int K) {
int count = 0;
char[] chars = S.toCharArray();
for (char ch : chars) {
if (ch == '-') {
count++;
}
}
int len = chars.length - count;
if (len == 0) {
return "";
}
int num = len % K == 0 ? len / K - 1 : len / K;
len += num;
char[] str = new char[len];
count = 0;
int pos = len - 1;
for (int i = chars.length - 1; i >= 0; i--) {
if (chars[i] == '-') {
continue;
}
if (count % K == 0 && count != 0) {
str[pos--] = '-';
}
if (chars[i] >= 'a' && chars[i] <= 'z') {
chars[i] -= 32;
}
str[pos--] = chars[i];
count++;
}
return new String(str);
}
}
最大连续1的个数给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。
思路：一看题就知道又是一道送分题，但是这个时候拼的就是性能了（还好没要求什么时间复杂度，空间复杂度的）。个人暂时思路：定义两个常量，一个是当前最大的连续数，一个是当前累加数。还有一个骚操作:数组转字符串，然后用0分割成String数组，比较最长的元素就是最大的个数。接下来一个个代码实现：
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0;
int temp = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i]==0){
max = max>temp?max:temp;
temp = 0;
}else{
temp++;
}
}
max = max>temp?max:temp;
return max;
}
}
第一个想法性能超过百分百用户，完美成功！接下来第二个：
额，第二个有点小问题。。。就是这个我之前用过直接将char数组转成字符串。我以为int也可以，事实证明不行，所以要想换成字符串还得遍历，简直是脱了裤子放屁，所以第二个思路折腰了，这道题过！
构造矩形
题目：作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
- 你设计的矩形页面必须等于给定的目标面积。
- 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
- 长度 L 和宽度 W 之间的差距应当尽可能小。
你需要按顺序输出你设计的页面的长度 L 和宽度 W。
示例：
输入: 4
输出: [2, 2]
解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。
说明:
给定的面积不大于 10,000,000 且为正整数。
你设计的页面的长度和宽度必须都是正整数。
思路:虽然一堆槽要吐，但是还是好好说题目：长宽尽量相似，所以从平方根开始试：面积除平方根往上加的正整数，知道整除为止，该正整数是长，商是宽。思路应该是没问题的，我去实践测试一下
很好，思路又没问题，性能又差的一批！
class Solution {
public int[] constructRectangle(int area) {
int i = (int)Math.sqrt(area);
while(area%i!=0){
i--;
}
int [] res = new int[2];
res[0] = area/i;
res[1] = i;
return res;
}
}
想来想去可能影响性能的也就是第1行代码了。所以这里不应该直接使用Marh.sqrt（）？哎，我再想想。
说真的，我觉得这个力扣针对我啊，差不多的代码，我排名靠后，人家排名第一??why??大神也是这个思路，只不过人家直接在结果中new int[]，剩下几乎没区别：
class Solution {
public int[] constructRectangle(int area) {
int sqrt = (int) Math.sqrt(area);
while (area % sqrt != 0) {
sqrt--;
}
return new int[]{area / sqrt, sqrt};
}
}
今天的笔记就写到这里，如果稍微帮到你了记得点个喜欢点个关注，每天进步一点点~~~也祝大家工作顺顺利利！
网友评论