别再羊了个羊了，大家都在玩刷了个题——LeetCode刷题第3周小结

 前言

        最近羊了个羊火爆全网，我也不知道这游戏为啥这么火啊，感觉就是低化版的消消乐，第一关幼儿园，第二关直接清华北大，游戏道具图案随机出现，能通关几乎只能靠运气加成，和数学逻辑没有太大关系，消耗的是巨大的时间。背后的底层套路是设置噱头吸引巨大流量，接入广告，所以这款微信小游戏背后的运营者简直赢麻了！

        扯远了，扯远了，羊了个羊也就估计火个两三周，但刷了个题还是得坚持玩啊，每日一题就像每日一关，力扣几千关等待各位扣友一起去AC！这是坚持刷题的第三周，期初是和朋友一起互相监督刷题、选题，如今已经成为每日的一种习惯，带着配备无限键盘的平板，再下载力扣APP，上无聊的杂课时能随时随地拿出来AC一道easy题，虽然现在自己的算法水平还是蛮菜的，但“骐骥一跃，不能十步；驽马十驾，功在不舍！”  坚持总归有所收获的！！

文章目录

 1.重塑矩阵

2.最长和谐子序列

3.验证回文串

4.第三大的数

5.加一

6.汇总区间

7.爬楼梯

8.二进制求和

关键字

二维数组一维化、行列号的映射关系、枚举法、滑动窗口、模拟竖式计算、字符串变量StringBuffer、双指针、动态规划初步、滚动数组

---

 

 1.重塑矩阵

难度：★   链接：力扣

 

解题思路:

        本题思路很简单，即将二维数组进行顺序行遍历，将数依次填入r行c列的数组中。若二者个数不相等则肯定无法重塑，直接返回原来数组；否则，进行二维数组的顺序行遍历，此时即将一个二维数组转化成了一个一维数组，下面一步最重要的就是如何确定具体的行列号坐标，通过观察我们发现：一个m行n列的二维数组中的一个数a[ i ][ j ] ，其行号i是由列号j除列数n得到的商所确定的，而列号j是由列号j对列数n取余所得到的, 即:  i=j/n   j=j%n   这个重要的映射关系对本题的填充数字很重要！

解题代码：

class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m=mat.length;
        int n=mat[0].length;
        int plan[][]=new int[r][c];
        //如果原矩阵与新矩阵的元素个数不同，那么肯定无法完成重塑
        if(m*n!=r*c){
            return mat;
        }
        //将二维数组视为经过行遍历而成的一个长度为m*n的一维数组
        for(int i=0;i
            //抓住主要映射关系，行数是由列来确定的
            plan[i/c][i%c]=mat[i/n][i%n];//填充
        }
        return plan;
    }
}

 

---

 

2.最长和谐子序列

难度：★  链接：力扣

 

解题思路:

枚举法，可以枚举数组中的每一个元素，对于当前元素x，它可以和x+1组成一个和谐子序列。所以问题可以转化为：我们在数组中寻找x和x+1的个数，就可以找到以x为最小值的和谐子序列的长度。这一思路是利用枚举法解题的关键所在。同时注意以下几点：

• 实际处理时，我们可以将数组进行升序排序，只需要依次找到两个连续相同元素的子序列。检查这两个序列的元素之差是否为1，为1的话将其长度存在变量res中。比如：排序后的数组元素为1,2,2,2,3,3,3,3,3,4,5,5 此时找到的两个连续相同元素的子序列为：2 2 2 和 3 3 3 3 3 二者元素之差为1 ，符合条件，将其长度8存入res，进行下一轮的遍历，如果遇到更大的则更新
• 利用类似“滑动窗口”的做法，设置两个遍历begin和end ，begin指向第一个连续相同元素的子序列的第一个元素，end指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者之差为1，则当前的和谐子序列长度即为两个子序列的长度之和，等于end-begin+1

 

解题代码：

class Solution {
    public int findLHS(int[] nums) {
        int begin=0;
        int res=0;
        Arrays.sort(nums);
        for(int end=0;end
            while(nums[end]-nums[begin]>1){
                begin++;
            }
            if(nums[end]-nums[begin]==1){
                res=Math.max(res,end-begin+1);
            }
        }
        return res;
    }
}

 

---

 

3.验证回文串

难度：★ 链接：力扣

 

解题思路:

方法一：筛选+判断，即：先将字符串中的字母与数字字符取出存入字符串变量StringBuffer中，最后将其进行翻转与原来进行字符串比较，相同则是回文串返回true ,否则不是回文串，返回false

解题代码:

class Solution {
    public boolean isPalindrome(String s) {
       int n=s.length();
       //设置字符串变量arr来存储字符串中的字母与数字字符
       StringBuffer arr=new StringBuffer();
       for(int i=0;i
           //调用API判断是否是字母或者数字字符
           char ch=s.charAt(i);
           if(Character.isLetterOrDigit(ch)){
               arr.append(Character.toLowerCase(ch));
           }
       }
       //将取出的字母数字字符串进行翻转后与原来进行字符串的比较
       //相同则是回文串返回true 否则返回false 
       StringBuffer res=new StringBuffer(arr).reverse();
       return res.toString().equals(arr.toString());
      
    }
}

 

方法二：双指针法，设置两个指针left与right分别从已经取出字母数字字符的字符串的首尾同时向中间移动，步长相同，每移动一次判断各自对应的字符是否相等，不相等直接返回false ,否则继续移动，如果该字符串是回文串，则左右指针left与right终会相遇，返回true

解题代码：

class Solution {
    public boolean isPalindrome(String s) {
       int n=s.length();
       //设置字符串变量arr来存储字符串中的字母与数字字符
       StringBuffer arr=new StringBuffer();
       for(int i=0;i
           //调用API判断是否是字母或者数字字符
           char ch=s.charAt(i);
           if(Character.isLetterOrDigit(ch)){
               arr.append(Character.toLowerCase(ch));
           }
       }
       //双指针逐个字符进行判断
       String s2=arr.toString();
       int left=0,right=s2.length()-1;
       while(left
           char ch1=s2.charAt(left);
           char ch2=s2.charAt(right);
           if(ch1!=ch2){
               return false;
           }else{
               left++;
               right--;
           }
       }
       return true;
    }
}

 

---

 

4.第三大的数

难度：★  链接：力扣

 

解题思路：

先将数组降序排列，然后从中找出第三个不重复的元素返回即可，我们用变量count来记录元素的种类，当达到3时返回此时的元素即为数组中第三大的元素 ；如果遍历结束仍未返回，则说明数组中元素不存在第三大的数字，返回最大的数nums[0]（已经降序排列）

解题代码：

class Solution {
    public int thirdMax(int[] nums) {
        //先降序排序，然后再从前往后遍历计数不重复元素
        //选择排序
        int n=nums.length;
        for(int i=0;i1;i++){
            int max=i;                                            
            for(int j=i+1;j
                if(nums[j]>nums[max]){
                    max=j;
                }
            }
            if(max!=i){
                int temp=nums[i];
                nums[i]=nums[max];
                nums[max]=temp;
            }
        }
        int count=1;
        for(int i=1;i
            if(nums[i]!=nums[i-1]&&++count==3){
                return nums[i];
            }
            
        }
        return nums[0];
    }
}

 

---

 

5.加一

难度：★  链接：力扣

 

 

解题思路：

一个数字加一，只需考虑末尾是否为9，即是否需要进位的情况；如果末尾为9则进一后原位置数值为0.如果末尾不是9则直接普通加一返回数组即可。注意这里所说的“末尾”是动态变化的，简单来说就是从后往前遍历数组，判断该位置的数字是否为9 ，最后别忽略了全部进位的情况，则要额外开辟一个空间给最高位即进位的1来使用。

解题代码：

class Solution {
    public int[] plusOne(int[] digits) {
        //题目本质就是在结尾加一，，分末尾数字是否为9进行判断
        int n=digits.length;
        for(int i=n-1;i>=0;i--){
            if(digits[i]==9){
                digits[i]=0;//满十进位后原位置的值就变为0
            }else{
                //末尾不是9的情况直接加一返回数组即可
                digits[i]+=1;
                return digits;
            }
        }
        //如果上面循环后还未返回，说明上面末尾为9后一次进位，之后前面的数依次全部进位了
        //所以需要额外开辟一个空间给最高位进位1使用
        digits=new int [n+1];
        digits[0]=1;
        return digits;
    }
}

 

---

 

6.汇总区间

难度：★  链接：力扣

 

解题思路：

 蛮力法，依次遍历找出连续区间，然后将此区间的左右端点加入字符串变量，然后将其加入动态数组中。注意点就是要判断该区间内连续元素的个数，如果只有一个，则不用输出区间直接输出单个值即可，否则要按照题目要求的格式 a->b的格式将其加入动态数组。

解题代码：

class Solution {
    public List summaryRanges(int[] nums) {
        Listlist=new ArrayList<>();
        int n=nums.length;
        int i=0;
        while(i
            //遍历的起始位置，未来可能是区间的左端点位置
            int low=i++;//必须先加一，否则第一次遍历时会越界
            //判断相邻元素，即区间内的连续的值
            while(i1]==1){
                i++;
            }
            //循环结束，此时i的位置即为不连续的第一个值
            int high=i-1;//连续区间的最后一个值的位置为i-1，即连续区间的右端点
            StringBuffer s=new StringBuffer(Integer.toString(nums[low]));
            //如果a!=b 则low与high不会相等，将箭头符号与右区间端点加入字符串变量中
            if(low
                s.append("->");
                s.append(Integer.toString(nums[high]));
            }
            //如果a==b 则low 与 high会相等此时区间里就是一个单个值
            list.add(s.toString());
          
        }
         return list;
    }
}

 

---

 

7.爬楼梯

难度：★  链接：力扣

 

解题思路：

 动态规划法：我们用f(x)代表爬到第x级台阶的方案数，因为一次只能爬1级或者2级，所以最后一步可能是爬1级到达x级，或者爬2级到达x级，所以爬到x级的方案数是爬到x-1级台阶和爬到x-2级台阶的方案数之和，所以我们可以列出如下的式子：f(x) = f(x-1) + f(x-2) 。这就是动态规划的状态转移方程，即f(x)只能是由f(x-1)和f(x-2)转移过来 。

解题代码：

class Solution {
    public int climbStairs(int n) {
       int dp[]=new int[n+1];
       dp[0]=1;
       dp[1]=1;
       for(int i=2;i<=n;i++){
           dp[i]=dp[i-1]+dp[i-2];
       }
       return dp[n];
    }
}
 

注意到这里的时间复杂度与空间复杂度都为O(n)，但是这里我们可以发现f(x)之和f(x-1)和f(x-2)有关，所以我们可以利用“滚动数组的思想”，把其空间复杂度优化为O(1)，代码如下：

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

滚动数组的思想是个基本思想，可以结合下面动图来理解

另外贴一位扣友的总结，非常到位的总结

 

---

 

8.二进制求和

难度：★   链接：力扣

 

解题思路：

本题类似于十进制加法，模拟其竖式计算，只不过进制不同，这是二进制加法，需要逢二进一，注意进位的值最后为1的情况

解题代码：

class Solution {
    public String addBinary(String a, String b) {
        //类似于模拟十进制的竖式计算，只不过这里是逢二进一
        StringBuffer res=new StringBuffer();
        int carry=0;//储存进位
        int m=a.length(),n=b.length();
        int i=m-1,j=n-1;
        while(i>=0||j>=0||carry!=0){
            //通过字符的ASCII码值与字符0相减得到整型值进行计算
            int x=i>=0?a.charAt(i)-'0':0;
            int y=j>=0?b.charAt(j)-'0':0;
            int sum=x+y+carry;
            res.append(sum%2);
            carry=sum/2;
            i--;
            j--;
        }
        //因为计算顺序与最终的二进制顺序相反，所以需要将计算结果翻转
        res.reverse();
        return res.toString();
    }
}

 

 

本专栏目前适合算法初学者学习，刷题范围主要是力扣的简单题偶尔夹杂中等题，语言主要使用Java，如果是水平很高的大佬可以略读本文，如果是还处在算法刷题初级阶段的朋友，可以点赞关注一下，我会一直更新下去的。