欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  科技

荐 LeetCode-Easy-1-5

程序员文章站 2022-03-05 09:37:17
文章目录题目1 两数之和思路与代码方法一：暴力法方法二：两遍哈希表方法三：一遍哈希表题目7 整数反转题解代码实现题目9 回文数解题思路：代码：题目13 罗马数字转整数题解：代码题目14最长公共前缀思路代码题目1 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。示例:给定 nums = [2, 7, 11, 1...

文章目录

题目1 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路与代码

方法一：暴力法

暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：

  • 时间复杂度：O(n^2)
    对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。

  • 空间复杂度：O(1)。

方法二：两遍哈希表

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i] 本身！

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：

  • 时间复杂度：O(n)，
    我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。

  • 空间复杂度：O(n)，
    所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

方法三：一遍哈希表

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：

  • 时间复杂度：O(n)，
    我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

  • 空间复杂度：O(n)，
    所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

题目7 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

题解

首先我们想一下，怎么去反转一个整数？
用栈？
或者把整数变成字符串，再去反转这个字符串？
这两种方式是可以，但并不好。实际上我们只要能拿到这个整数的末尾数字就可以了。
以12345为例，先拿到5，再拿到4，之后是3，2，1，我们按这样的顺序就可以反向拼接处一个数字了，也就能达到反转的效果。
怎么拿末尾数字呢？好办，用取模运算就可以了
荐 LeetCode-Easy-1-5
1、将12345 % 10得到5，之后将12345 / 10
2、将1234 % 10得到4，再将1234 / 10
3、将123 % 10得到3，再将123 / 10
4、将12 % 10得到2，再将12 / 10
5、将1 % 10得到1，再将1 / 10

这么看起来，一个循环就搞定了，循环的判断条件是x>0
但这样不对，因为忽略了负数
循环的判断条件应该是while(x!=0)，无论正数还是负数，按照上面不断的/10这样的操作，最后都会变成0，所以判断终止条件就是!=0
有了取模和除法操作，对于像12300这样的数字，也可以完美的解决掉了。

看起来这道题就这么解决了，但请注意，题目上还有这么一句

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。

也就是说我们不能用long存储最终结果，而且有些数字可能是合法范围内的数字，但是反转过来就超过范围了。
假设有1147483649这个数字，它是小于最大的32位整数2147483647的，但是将这个数字反转过来后就变成了9463847411，这就比最大的32位整数还要大了，这样的数字是没法存到int里面的，所以肯定要返回0(溢出了)。
甚至，我们还需要提前判断
荐 LeetCode-Easy-1-5
上图中，绿色的是最大32位整数
第二排数字中，橘黄色的是5，它是大于上面同位置的4，这就意味着5后跟任何数字，都会比最大32为整数都大。
所以，我们到【最大数的1/10】时，就要开始判断了
如果某个数字大于 2147483647那后面就不用再判断了，肯定溢出了。
如果某个数字等于 2147483647呢，这对应到上图中第三、第四、第五排的数字，需要要跟最大数的末尾数字比较，如果这个数字比7还大，说明溢出了。

对于负数也是一样的
荐 LeetCode-Easy-1-5
上图中绿色部分是最小的32位整数，同样是在【最小数的 1/10】时开始判断
如果某个数字小于 -2147483648说明溢出了
如果某个数字等于 -2147483648，还需要跟最小数的末尾比较，即看它是否小于8

java.lang.Integer.MAX_VALUE：2147483647

java.lang.Integer.MIN_VALUE：-2147483648

代码实现

class Solution {
    public int reverse(int x) {
        // 使用long接收处理值，因为有可能大于int的最大值
        long res = 0L;
        while(x!=0) {
            // 每次取末尾数字
            int tmp = x%10;
            // 判断是否 大于 最大32位整数
            if (res > java.lang.Integer.MAX_VALUE || (res == java.lang.Integer.MAX_VALUE && tmp>7)) {
                return 0;
            }
            // 判断是否 小于 最小32位整数
            if (res < java.lang.Integer.MIN_VALUE || (res == java.lang.Integer.MIN_VALUE && tmp<-8)) {
                return 0;
            }
            // 接收值 末尾数字拼接数据
            res = res * 10 + tmp;
            // 
            x /= 10;
        }
        return (int) res;
    }
}

题目9 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:
输入: 121
输出: true

示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶: 你能不将整数转为字符串来解决这个问题吗？

解题思路：

对于数字的末位，直接取余就可以了，对于数字的首位，我们可以这么算。
首先用一个变量记录数字的最高位，
比如 12321，可以标记 help 为 10000，
第一个末位为 1，第一个首位为 12321/10000=1，
接下来我们需要计算 232 是否为回文，怎么计算呢？
我们需要去掉首位和末位。
可以采用 x % help / 10 的方式
12321%10000==2321 可以将最高位去掉，然后 2321/10==232 可以将最低为去掉。
最后不要忘记将 help/100。

代码：

 public boolean isPalindrome(int x) {
        // 负数一定不是回文数
        if (x < 0) {
            return false;
        }
        int help = 1;
        int tmp = x;
        // 获取最大位
        while (tmp >= 10) {
            help *= 10;
            tmp /= 10;
        }
        // 遍历判断
        while (x != 0) {
            // 末尾与首位判断， (x%10)：最末尾  (x/help)：首位
            if (x % 10 != x / help) {
                return false;
            }
            // 采用 `x % help / 10` 的方式,可以将最高位去掉，然后可以将最低为去掉
            x = x % help / 10;
            help /= 100;
        }
        // 0 是回文数
        return true;
    }

题目13 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + I
I 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5
减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:
输入: “III”
输出: 3

示例 2:
输入: “IV”
输出: 4

示例 3:
输入: “IX”
输出: 9

示例 4:
输入: “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:
输入: “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

题解：

按照题目的描述，可以总结如下规则：

  1. 罗马数字由 I,V,X,L,C,D,M 构成；
  2. 当小值在大值的左边，则减小值，如 IV=5-1=4；
  3. 当小值在大值的右边，则加小值，如 VI=5+1=6；
  4. 由上可知，右值永远为正，因此最后一位必然为正。

一言蔽之，把一个小值放在大值的左边，就是做减法，否则为加法。
荐 LeetCode-Easy-1-5
在代码实现上，可以往后看多一位，对比当前位与后一位的大小关系，从而确定当前位是加还是减法。当没有下一位时，做加法即可。

也可保留当前位的值，当遍历到下一位的时，对比保留值与遍历位的大小关系，再确定保留值为加还是减。最后一位做加法即可。

代码

import java.util.*;

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        // 首位
        int preNum = getValue(s.charAt(0));
        for(int i = 1;i < s.length(); i ++) {
            // 第二位开始
            int num = getValue(s.charAt(i));
            // 前位与其后位置判断 
            if(preNum < num) {
                // 当小值在大值的左边，则减小值，如 `IV=5-1=4`
                sum -= preNum;
            } else {
                // 当小值在大值的右边，则加小值，如 `VI=5+1=6`；
                sum += preNum;
            }
            // 向前进一位
            preNum = num;
        }
        // 加上首位
        sum += preNum;
        // 返回值
        return sum;
    }
    
    /**
     * 罗马数字转换值
     */
    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
}

题目14 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: [“flower”,“flow”,“flight”]
输出: “fl”

示例 2:
输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。

说明: 所有输入只包含小写字母 a-z 。

思路

  • 标签：链表
  • 当字符串数组长度为 0 时则公共前缀为空，直接返回
  • 令最长公共前缀 ans 的值为第一个字符串，进行初始化
  • 遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
  • 如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
  • 时间复杂度：O(s)，s 为所有字符串的长度之和

代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 为空直接返回
        if(strs.length == 0) 
            return "";
        // 以第一个字符串初始化
        String ans = strs[0];
        // 用剩余的字符串依次与第一个字符串比较
        for(int i =1;i<strs.length;i++) {
            int j=0;
            // 遍历第一个字符串与第[i]个字符串中较小字符串的长度
            for(;j<ans.length() && j < strs[i].length();j++) {
                // 依次判断字符是否在判断字符串中的指定位置
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;// 判断不相同就中断判断
            }
            // 获取最新的最长公共前缀
            ans = ans.substring(0, j);
            // 如果为空说明 不存在公共前缀，返回""
            if(ans.equals(""))
                return ans;
        }
        // 返回结果值
        return ans;
    }
}

本文地址：https://blog.csdn.net/baidu_25310663/article/details/107346561

上一篇： 【win10WLAN不显示问题】关于WIN10系统右下角网络中只有飞行模式没有WLAN和移动热点的解决办法

下一篇： 荐 数据结构和算法5-非线性-树

推荐阅读