LeetCode算法

159 阅读 0 评论 105 点赞

我是靠谱客的博主风中芝麻，这篇文章主要介绍LeetCode算法，现在分享给大家，希望可以做个参考。

1、两数之和

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] twoSum(int[] nums,int target){
        //定义数组的长度
        int len = nums.length;
        //定义一个map 存放索引和值 并给他设置初始容量以免扩容带来性能消耗
        Map<Integer,Integer> hashMap = new HashMap<>(len-1);
        //首先存放 数组的第一个索引 和值 并将key作为目标值，value作为索引
        hashMap.put(nums[0],0);
        //遍历数组的长度,并从数组的索引为1(也就是第二个值)的位置开始遍历
        for (int i = 1; i < len; i++) {
            //用目标值减去数组遍历的值 作为目标值的另一个值
            int another = target - nums[i];
            //判断map中是否包含 目标值的另一个值
            if (hashMap.containsKey(another)){
                //如果map中含有目标值的另一个值则返回当前的索引和目标值的索引
                return new int[]{i,hashMap.get(another)};
            }
            //如果map中不包含 目标值的另一个值 则把目标值和相应的索引存放到map
            hashMap.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

代码细节之处：

1.重复使用int len = nums.length; 给声明了一个变量

2.map集合给一个初始化容量并将集合的key作为目标值，value作为索引值

3.遍历数组从数组索引1开始

4.用目标值减去遍历的值作为目标值的另一个值，这样减少了遍历

2、检查回文数

复制代码

public boolean isPalindrome(int x){
        /**
         * 为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 int 数字的一半？
         * 毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同
         */
        /**
         * 首先排除不是回文数的值
         * 当x<0时肯定不是回文数
         * 如果数字的最后一位是 0，为了使该数字为回文，则其第一位数字也应该是 0  只有 0 满足这一属性
         */
        if (x < 0 || ( x % 10 ==0 && x!=0)) return false;
        //定义反转的数值 用于接收反转后的数值
        int revertedNumber = 0;
        //判断x是否大于反转后的值 如何x小于反转后的值 就不进行反转了
        while (x > revertedNumber){
            //反转的值对x进行不断的取余
            revertedNumber = revertedNumber * 10 + x % 10;
            //每取余一次就对x除10
            x /= 10;
        }
        /**
         * 如果x长度为偶数时 反转后的值应该等于x的前半的值 也就是x == revertedNumber
         * 如果x的长度为奇数 那么反转后的值除10 应该等于x的前半部分值
         */
        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber/10;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
  public boolean isPalindrome(int x){
        /**
         * 为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 int 数字的一半？
         * 毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同
         */
        /**
         * 首先排除不是回文数的值
         * 当x<0时肯定不是回文数
         * 如果数字的最后一位是 0，为了使该数字为回文，则其第一位数字也应该是 0  只有 0 满足这一属性
         */
        if (x < 0 || ( x % 10 ==0 && x!=0)) return false;
        //定义反转的数值 用于接收反转后的数值
        int revertedNumber = 0;
        //判断x是否大于反转后的值 如何x小于反转后的值 就不进行反转了
        while (x > revertedNumber){
            //反转的值对x进行不断的取余
            revertedNumber = revertedNumber * 10 + x % 10;
            //每取余一次就对x除10
            x /= 10;
        }
        /**
         * 如果x长度为偶数时 反转后的值应该等于x的前半的值 也就是x == revertedNumber
         * 如果x的长度为奇数 那么反转后的值除10 应该等于x的前半部分值
         */
        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber/10;
    }

算法的理解:

为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 text{int}int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

首先，我们应该处理一些临界情况。所有负数都不可能是回文，例如：-123 不是回文，因为 - 不等于 3。所以我们可以对所有负数返回 false。除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字返回 false。

现在，让我们来考虑如何反转后半部分的数字。

对于数字 1221，如果执行 1221 % 10，我们将得到最后一位数字 1，要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以 10 的余数，122 % 10 = 2，就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。

现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？

由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。

3、转换罗马数字

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  public static Integer numConvert(String s){
        Integer nums = 0; //转换值
        //存放固定的值
        Map<String,Integer> map = new HashMap<>(7);
        map.put("I",1);
        map.put("V",5);
        map.put("X",10);
        map.put("L",50);
        map.put("C",100);
        map.put("D",500);
        map.put("M",1000);
        int n = s.length();//字符串的长度
        for (int i = 0; i < n; i++) {
            Integer value = map.get(String.valueOf(s.charAt(i))); //按顺序取出值
            //如果 当前值小于下一个值 则减去当前值 否则加上当前值 n-1 的作用就是当遍历到字符串最后一个的时候要加上最后 一个字符串的值
            if (i < n-1 && value < map.get(String.valueOf(s.charAt(i+1)))){
                nums -= value;
            }else {
                nums += value;
            }
        }
        return nums;
    }