LeetCode1

发表于 2020-09-30 更新于 2024-01-18 阅读次数：本文字数： 1.3k 阅读时长 ≈ 5 分钟

这两天在LeetCode这个平台上刷算法题，想着也快毕业了，不想读研，那就要为找工作多费心力了。之后我会经常在这看题的，也会发一些好的题目算法，做个记录。

这次相对都是简单一些的。

7.整数反转

题目地址

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

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

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

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

注意:

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

begin

是不是感觉很简单，没错是相对简单的题，解这个题应该都可以的，但解题前是否分析了该怎么做才能做到最优，时间空间达到平衡。

这个题关键是就是用好“%”、“/”和循环，然后判断溢出即可，最简单的开始练手嘛！

一种java题解

class Solution {
    public int reverse(int x) {
        int rev=0;
        while(x!=0){
            int pop=x%10;
            x/=10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8))return 0;
            rev=rev*10+pop;
        }
        return rev;
    }
}

详细题解

热身好就下一个

9.回文数

题目地址

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

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

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

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

进阶:

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

begin

很多人可能对进阶的字符串回文的会更了解，low、high首尾判断。这个题是整数的回文，最好自己先是尝试一下，不知道有没有人这样想，分三种情况考虑，负数false，0true，正数在做类似于字符串那样处理，不怕你们嘲笑，我当时就这么想的，实现之后，虽然通过但时间消耗太大了，需要改进，看了题解，不禁感慨：我怎么想不到！！！

题解思路：负数和以0结尾的数false，重点来了，下一步将这个数反转一半，如：12321和123321分别反转为123和123，接着与剩下的比较，匹配则true。

一种java题解

class Solution {
public:
    bool isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

详细题解

是不是觉得，就这，那就来一道复杂一点的吧！

2. 两数相加

题目地址

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例： >输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
>输出：7 -> 0 -> 8
>原因：342 + 465 = 807

begin

这个，还行吧，包含链表知识，可以费点心思了吧！

选这个题是有目的的，因为这个题和解太有趣了，也可能就我笨想不到吧！

提示一下下面直接放题解了——从低位依次向上加，存入链表即可。

一种java题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l=new ListNode(0);
        ListNode p1=l1,p2=l2,p=l;
        int carry=0;
        while(p1!=null||p2!=null){
            int x=(p1!=null)? p1.val:0;
            int y=(p2!=null)? p2.val:0;
            int sum=carry+x+y;
            carry=sum/10;
            p.next=new ListNode(sum%10);
            p=p.next;
            if(p1!=null)
                p1=p1.next;
            if(p2!=null)
                p2=p2.next;
        }
        if(carry>0)
            p.next=new ListNode(carry);
        return l.next;
    }
}