Hot100 LeetCode

作者: 奉先 | 来源:发表于2022-01-12 16:47 被阅读0次

1. 爬楼梯

题目地址： https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶； 2. 2 阶。
示例 2：
输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶 ; 2. 1 阶 + 2 阶 ; 3. 2 阶 + 1 阶。

该问题，需要分析规律，可以按照递归方法解决。按照上边示例分析，n = 1 有1种方法；n=2时有2种方法； n=3时有3种方式。下面重点分析有n级台阶时有几种方法，我们现在分析最后一步，有可能上1级，也有可能上2级台阶。把这两种方法的可能性走法相加，就是n级台阶的走法，这里记为 f(n) = f(n-1) + f(n-2) 。这样递归公式就已经出来了。
根据这个递归公式，可以画出递归树：

递归树

从这个递归树，我们就发现了问题，仅以f3为例，在这个递归树中，f3就被计算了3次(方框内)，如果在n较大时，这个程序就会超时。这里使用一个HashMap来保存已经计算过的结果。防止多次重复计算。
下面是我的递归实现：

class Solution {
    private Map<Integer,Integer> map_d = new HashMap() ;
    public int climbStairs(int n) {
        if ( n <= 0 ) return 0 ;
        if ( n == 1 ) return 1 ;
        if ( n == 2 ) return 2 ;
        if(!map_d.containsKey(n)) {
            map_d.put(n,climbStairs( n-1 ) + climbStairs(n-2));
        }
        return map_d.get(n) ;
    }
}

2. 斐波那契数列

题目地址：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100

该题解决方法还是比较简单，只要用2个变量保存每次迭代的前2个值，例如从第2个依次计算到第n个，计算第2个值的时候，用两个变量o和p分别计算第0和第1个值，并往前迭代即可，下边是我的实现代码：

class Solution {
    public int fib(int n) {
        int MOD =  1000000007 ; 
        if (n<=1) return n ;
        int o = 0 ;
        int p = 1 ;
        for(int i=2 ; i<=n ; i++){
            int temp = p ;
            p = (o + p) % MOD ;
            o = temp ;
        }
        return p ; 
    }
}

3. 合并两个有序数组：

题目链接：https://leetcode-cn.com/problems/merge-sorted-array/
合并两个有序数组到一个数组，保证合并后数组有序：
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6]
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。合并结果是 [1] 。

该问题解答方法是个常见的解法。因为原始的2个数组都有序，这里新建一个m+n的数组pd作为新数据存放地址。因为2个数组的长度不一，分别是m和n。
两个数组分别开始一个下标往后迭代，比对时，当第一个数组元素更小时，将该元素放到新数组pd中，当第二个元素更小时，将该元素放到pd中。总有一个时刻，某一个游标迭代到了原数组终点，最后将该数组剩余元素再依次拷贝到pd中即可。下面是我的实现代码。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n==0) return;
        if(m==0){
            for (int i=0 ;i<n ; i++){
                nums1[i] = nums2[i] ;
            }
            return;
        }
        int[] out = new int[m+n] ;
        int i = 0 ;
        int j = 0 ;
        int cnt = 0;
        while( i < m && j < n){
            if (nums1[i] <= nums2[j] ){
                out[cnt] = nums1[i] ;
                i++;
            }
            else {
                out[cnt] = nums2[j] ;
                j++ ;
            }
            cnt++;
        }
        while (i < m)
        {
            out[cnt++] = nums1[i++] ;
        }
        while (j < n){
            out[cnt++] = nums2[j++] ;
        }
        //将迭代后的结果拷贝到nums1数组
        for(int p =0 ;p < m+n ; p++){
            nums1[p] = out[p] ;
        }
        return;
    }
}

4. 两数之和：

这题比较简单，这里略去了。

5. 移动0：

题目地址：https://leetcode-cn.com/problems/move-zeroes/
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

此题目需要使用技巧，双指针挪动。下图列举了分析的过程，下面我尝试写出规律：

双指针思路
1.初始化状态有2个指针，P0和P1都指向下标为0的元素。P1先往后迭代。第一轮迭代的终止条件是P1到了最后一个元素。
2.P1迭代时候有2种情况：（1）如果碰到非0元素，P0指向的元素被P1指向的元素替换，并且P0和P1都向后移动。（2）如果碰到0元素，P1向后移动，P0不移动。
下面给出上边思路的代码：

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length < 2) return;
        //初始化
        int p1 =0 , p0=0 ;
        //第一轮循环
        while(p1<nums.length){
            if(nums[p1] == 0) {
                p1++ ;
            }
            else{
                nums[p0] = nums[p1] ;
                p1 ++ ;
                p0 ++ ;
            }
        }
        //第二轮循环 
        while(p0 < nums.length){
            nums[p0++] = 0 ;
        }
    }
}

6. 存在重复元素

题目链接：
给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:
输入: [1,2,3,1]
输出: true

这题非常简单，唯一需要注意的是时间复杂度。如果嵌套两层for循环会导致超时不符合要求。这里使用了Set来额外做比对，降低时间复杂度，代码如下：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> mySet = new HashSet() ;
        for (int i =0 ; i < nums.length ; i++){
            if (mySet.contains(nums[i])){
                return true ;
            }
            else {
                mySet.add(nums[i]);
            }         
        }
        return false ;
    }
}

7. 接雨水

题目地址： https://leetcode-cn.com/problems/trapping-rain-water/
描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

示例1

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

这道题目是一个非常经典的题，开始没有想到思路，看过题解后。找到了思路，本题其实在找一些“凹地”。不难理解，头和尾两个节点不可能围住水（如果节点数小于3也不可能围住水）。从第2个到倒数第2个节点，需要考虑，每个节点往左找到最大的数A，往右找到最大的节点B，找A和B中最小的那个（木桶原理：能接多少水，关键看最短的那个板子）。然后，计算这个值与本来节点值的差，作为该节点所能接住的水。这样从第2个到倒数第二个循环一遍就得到了结果。为了帮助理解，我画了下边的图：

解题思路

有了这个思路，代码就很好写了：

class Solution {
    public int trap(int[] height) {
        //变量记录装水量
        int vSum = 0 ;
        if (height.length < 3) return 0 ;

        //储存数组每个元素左边和右边的最大值,从第2个到倒数第2个记录每个元素的最大左右边界值
        int[][] boundary = new int [height.length][2] ;

        //从第一个元素迭代到倒数第2个元素，存储每个元素最大的左右值
        for(int i=1 ; i<height.length-1; i++){
            int leftMax = 0 , rightMax = 0 ;
            for(int j=0 ; j<=i ; j++){
                leftMax = Integer.max(leftMax,height[j]) ;
            }
            for(int k=i ; k< height.length ;k ++){
                rightMax = Integer.max(rightMax,height[k]);
            }
            boundary[i][0] = leftMax ;
            boundary[i][1] = rightMax ;
        }

        for(int i=1 ; i<height.length-1 ; i++){
            //木桶原理，考察左右最大中，最小的一个跟本元素的大小之差
            vSum += Integer.min( boundary[i][0] - height[i], boundary[i][1] - height[i] ) ;
        }
        return  vSum ;
    }
}

收获：
这道题中用了2维数组，我对2维数组的使用并不是很熟练，查了Baidu 。本题中从i=1迭代到i=height.length-2 ，每次迭代记录2个值，左边最大和右边最大。二维数组定义方法是：int[][] boundary = new int [height.length][2] ; 第2列的2，表示n个元素，每行是一个2个元素的数组。

8.最长公共前缀

该题目是字符串标签下的一道热题，题号14（简单）
题目地址：https://leetcode-cn.com/problems/longest-common-prefix/
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

该题目比较简单，我自己独立做出来了，但是代码量还是不短，不过执行效率非常高。思路就是逐个比对，拿出所有字符串先比较第一个字符，再比较第2个字符，以此类推。期间发现不一致的情况，直接结束后续流程并返回结果。下面是我的代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length ==0) return "" ;
        int ans_len = 0 ;    //记录公共前缀的长度。
        //找到字符串数据中最短的一个字符，防止后边迭代越界
        int minStrLen = Integer.MAX_VALUE;
        for(int i=0 ; i< strs.length ; i++){
            minStrLen = Integer.min(minStrLen,strs[i].length()) ;
        }
        //存储公共前缀的字符
        char[] ans = new char[minStrLen] ;
        while(minStrLen > ans_len){
            char baseChar = strs[0].charAt(ans_len) ;
            int flag = 1 ;
            for(int i=0 ; i< strs.length ;i++){
                if(strs[i].charAt(ans_len) != baseChar){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                ans[ans_len++] = baseChar;
            }
            else{
                break;
            }
        }
        char[] ansOutput = new char[ans_len];
        for(int j=0 ;j < ans_len ;j++){
            ansOutput[j] = ans[j] ;
        }
        return String.valueOf(ansOutput);
    }
}

收获：
这里练习了java中字符数组和String的转化，最开始尝试了Arrays.toString()但是这种返回了"[f,l]" 不符合结果。这里需要使用String.valueOf(char[] c)这种形式。

9.罗马数字转整数

题目链接： https://leetcode-cn.com/problems/roman-to-integer/
题目标签：哈希表
题目描述比较复杂，直接截图吧：

题目
我的实现思路中，用HashMap来保存不能字符（一位：I ，二位：XV等）所表示的数字。然后从第一个字符开始往后不断匹配，直至得到最终结果。下面是我的实现代码：

class Solution {
    public int romanToInt(String s) {
        if (s == "") return 0 ;
        Map<String,Integer> mapRoma = new HashMap<>() ;
        mapRoma.put("I",1) ;
        mapRoma.put("V",5) ;
        mapRoma.put("X",10) ;
        mapRoma.put("L",50) ;
        mapRoma.put("C",100) ;
        mapRoma.put("D",500) ;
        mapRoma.put("M",1000) ;
        mapRoma.put("IV",4) ;
        mapRoma.put("IX",9) ;
        mapRoma.put("XL",40) ;
        mapRoma.put("XC",90) ;
        mapRoma.put("CD",400) ;
        mapRoma.put("CM",900) ;

        int strLength = s.length();
        //滑动游标从0开始
        int startCursor = 0, ans = 0 ;
        while (strLength > startCursor){
            if((startCursor + 1) < strLength){
                String df = s.substring(startCursor,startCursor+2) ;
                if(mapRoma.containsKey(df)){
                    ans += mapRoma.get(df) ;
                    startCursor += 2 ;
                }
                else {
                    ans += mapRoma.get(s.substring(startCursor, startCursor+1));
                    startCursor += 1;
                }
            }
            else {
                    ans += mapRoma.get(s.substring(startCursor, startCursor+1));
                    startCursor += 1;
                }
        }
        return ans ;
    }
}

反思：
1.这里熟悉了String.substring()函数的使用，两个标记的截串规则是左闭右开的。例如 "google".substring(0,2) 得到的事"go" 。
2.我的解法有点代码冗余，看题解里，把 IX这种拆解成 -1 + 10 ，判断条件是较小的数在较大的数左边。就是I在X左边这样拆解后，代码就比较简单了。

10.链表反转：

链表反转是经常碰到的题目，leetcode中找到了2道反转链表的题目，题号92和206 ，题目标签都是链表常考题 。
https://leetcode-cn.com/problems/reverse-linked-list/
https://leetcode-cn.com/problems/reverse-linked-list-ii/
反转链表的题目描述非常简单，下边一个图就能读懂：

反转链表
该题目实现起来还是比较复杂的，虽然代码量不多，但是理解起来着实费劲痛苦。我采用了比较好理解的“双指针”方法，定义一个current 一个prev，不断往后挪指针，来完成链表反转。下面是我的代码可以参考：

class Solution {
    public ListNode reverseList(ListNode head) {
        //迭代指针
        ListNode current = head;
        ListNode prev = null ;
        while(current != null){
            //修改指针指向
            ListNode behind = current.next ;   //先保存下下一个节点，为了后边挪动指针
            current.next = prev;

            //挪动当前指针向后
            prev = current ;
            current = behind ;
        }
        return prev ;
    }
}

反转链表II相比上边的反转链表复杂了一些，复杂的点主要在于，反转的子链表的头，需要连接到之前断开的左边链表，反转的子链表的尾需要连接到断开的右边链表（当然还要考虑，只有2个节点的边界情况）。
更复杂的链表反转题目（反转链表II），我的方案代码：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left == right || head == null || head.next == null ) return head ;
        ListNode current = head ;
        ListNode prev = null ;

        //记录头尾节点
        ListNode leftHeadOri = null,rightHeadOri = null,leftHead = null,rightHead = null;
        int cursor = 1 ;

        while(current != null){
            ListNode behind = current.next ;
            if (cursor <= left )
            //直接前移current和prev
            {
                if(cursor == left) {
                    leftHeadOri = prev ;
                    leftHead = current;
                }
                prev = current ;
                current = behind ;
            }
            else if(cursor > left && cursor <= right){
                if(cursor == right) {
                    rightHeadOri = behind ;
                    rightHead = current ;
                }
                current.next = prev ;
                prev = current;
                current = behind ;
            }
            else {
                prev = current ;
                current = behind ;
            }
            cursor++;
        }
        //边界问题处理：
        if(leftHeadOri!=null) {leftHeadOri.next = rightHead ;} else {head = rightHead ;}
        if(leftHead!=null) leftHead.next = rightHeadOri ;
        return head ;
    }
}

Hot100 LeetCode

1. 爬楼梯

2. 斐波那契数列

3. 合并两个有序数组：

4. 两数之和：

5. 移动0：

6. 存在重复元素

7. 接雨水

8.最长公共前缀

9.罗马数字转整数

10.链表反转：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读