AI 助理
备案控制台
开发者社区 云计算 文章 正文

LeetCode

2024-04-22 39
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： LeetCode

2. 两数相加

  public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ln = new ListNode();
        ListNode p1 = l1, p2 = l2, p = ln;
        // 标志上一位如果超过10，下一位进1，即加一
        int flag = 0;
        while (p1 != null || p2 != null) {
            // p1,p2指向null 则值为0
            int num1 = p1 == null ? 0 : p1.val;
            int num2 = p2 == null ? 0 : p2.val;
            int res = num1 + num2 + (flag == 1 ? 1 : 0);
            p.val = res % 10;
            flag = 0;
            if (res > 9) flag = 1;
            // p1,p2 指向下一个节点,直到指向null为止.
            p1 = p1 == null ? p1 : p1.next;
            p2 = p2 == null ? p2 : p2.next;
            if (p1 == null && p2 == null) {
                // 结束最后一位, 也需进一,
                if (flag == 1) {
                    p = p.next = new ListNode();
                    p.val = 1;
                }
                p.next = null;
            } else
                p = p.next = new ListNode();
        }
        return ln;
    }

3. 无重复字符的最长子串

  public static int lengthOfLongestSubstring(String s) {
        int max = 0;
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                // 存在跳出, 不存在加入
                if(sb.indexOf(chars[j] + "") != -1) break;
                else sb.append(chars[j]);
                if (sb.length() > max) max = sb.length();
            }
            //重置字符串sb
            sb.setLength(0); 
        }
        return max;
    }

7. 整数反转

/**
 * @Author Tiam
 * @Date 2022/6/28 13:13
 * @Description: 7. 整数反转  victory
 */
public class Demo06 {
    public static void main(String[] args) {
        System.out.println(reverse(2432));
    }

    public static int reverse(int x) {
        long n = x % 10;
        while ((x /= 10) != 0) {
            n = n * 10 + x % 10;
        }
        if (n > Integer.MAX_VALUE || n < Integer.MIN_VALUE) return 0;
        return (int)n;
    }
}

8. 字符串转换整数 (atoi)

/**
 * @Author Tiam
 * @Date 2022/6/28 19:02
 * @Description: 8. 字符串转换整数 (atoi) victory
 */
public class Demo07 {
    public static void main(String[] args) {
//        System.out.println(4365 / 100.0);
//        System.out.println(Character.digit('0', 10));
        System.out.println(myAtoi("-91283472332"));
        //System.out.println(Double.parseDouble("-43.234"));
    }

    public static int myAtoi(String s) {
        if ("".equals(s.trim())) return 0;
        char[] chars = s.trim().toCharArray();
        long n = 0;
        //标记负数
        int i = 0, flag = 0;
        if (!Character.isDigit(chars[i])) {
            if (chars[i] == '-') {
                flag = 1;
            } else {
                if (chars[i] != '+') return 0;
            }
            i++;
        }
        for (; i < chars.length; i++) {
            //判断是否为数字
            if (Character.isDigit(chars[i])) {
                n = n * 10 + Character.digit(chars[i], 10);
                if (flag == 0 && n > Integer.MAX_VALUE) {
                    return Integer.MAX_VALUE;
                }
                if (flag == 1 && -n < Integer.MIN_VALUE) {
                    return Integer.MIN_VALUE;
                }
            } else {
                break;
            }
        }
        n = flag == 0 ? n : -n;
        return (int) n;
    }
}

9. 回文数

/**
 * @Author Tiam
 * @Date 2022/6/29 8:12
 * @Description: 9. 回文数  victory
 */
public class Demo08 {
    public static void main(String[] args) {
        System.out.println(isPalindrome(121));
    }

    public static boolean isPalindrome(int x) {
        if (x < 0) return false;
        int n = 0, m = x;
        while (x > 0) {
            n = n * 10 + x % 10;
            x /= 10;
        }
        return m == n ? true : false;
    }
}

704. 二分查找

/**
 * @Author Tiam
 * @Date 2022/6/29 8:41
 * @Description:   704. 二分查找  victory
 */
public class Demo09 {
    public int search(int[] nums, int target) {
        int low = 0,high = nums.length-1,mid;
        while (low<=high){
            mid = (low + high)/2;
            if(nums[mid]>target)
                high = mid - 1;
            else if(nums[mid]<target)
                low = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

278. 第一个错误的版本

/**
 * @Author Tiam
 * @Date 2022/6/29 8:47
 * @Description: 278. 第一个错误的版本   false false true true true
 *                                  victory
 */
public class Demo10 {
    public static void main(String[] args) {
        System.out.println(firstBadVersion(2126753390));
    }

    public static int firstBadVersion(int n) {
        long low = 1, high = n, mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (isBadVersion((int) mid) && !isBadVersion((int) mid - 1))
                return (int) mid;
            else if (isBadVersion((int) mid)) {
                high = mid - 1;
            } else
                low = mid + 1;
        }
        //无解抛出异常
        throw new IllegalArgumentException("The equation has no solution");
    }

    static boolean isBadVersion(int n) {
        if (n >= 1702766719)
            return true;
        else
            return false;
    }
}

35. 搜索插入位置

/**
 * @Author Tiam
 * @Date 2022/6/29 10:01
 * @Description: 35. 搜索插入位置  victory
 *                   在升序数组nums中，寻找target，找到返回其下标，没找到返回其待插入的位置。
 */
public class Demo11 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 4;
        System.out.println(searchInsert(nums, target));
    }

    public static int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] > target)
                high = mid - 1;
            else if (nums[mid] < target)
                low = mid + 1;
            else
                return mid;
        }
        return low;
    }
}

删除排序数组中的重复项

/**
 * @Author Tiam
 * @Date 2022/6/29 12:23
 * @Description:  删除排序数组中的重复项  victory
 */
public class Demo12 {
    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicates_(nums));
    }

    public static int removeDuplicates(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length - count - 1; ) {
            if (nums[i] == nums[i + 1]) {
                for (int j = i + 1; j < nums.length - count - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                count++;
            } else i++;
        }
        return nums.length - count;
    }
    /** 方式二 */
    public static int removeDuplicates_(int[] nums) {
        int p = 0, q = 1;
        for(;q < nums.length;q++)
            //寻找右指针与当前p不同的值, 存储到p的下一位.
            if(nums[p] != nums[q]) nums[++p] = nums[q];
        return ++p;
    }
}

买卖股票的最佳时机 II

/**
 * @Author Tiam
 * @Date 2022/6/29 13:01
 * @Description: 买卖股票的最佳时机 II   victory
 */
public class Demo13 {
    public static void main(String[] args) {
        //int[] nums = {1,2,3,4,5};
        //int[] nums = {7,1,5,3,6,4};
        //int[] nums = {7,6,4,3,1};
        int[] nums = {2, 1, 2, 0, 1};
        System.out.println(maxProfit(nums));

    }

    public static int maxProfit(int[] prices) {
        // -1 标记未购入
        int in = -1, rise = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i + 1] > prices[i] && in == -1)
                in = prices[i];
            if (prices[i + 1] < prices[i] && in != -1) {
                rise += prices[i] - in;
                in = -1;
            } else if (i + 1 == prices.length - 1 && in != -1) {
                rise += prices[i + 1] - in;
                in = -1;
            }
        }
        return rise;
    }
}

实现 pow(x, n)

/**
 * @Author Tiam
 * @Date 2022/6/29 14:38
 * @Description: 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
 */
public class Demo14 {
    public static void main(String[] args) {
        System.out.println(myPow(2.00000, -2147483648));
        System.out.println(myPow_(5, -1));
    }
    /** x的n次方,适用于正整数求幂 */
    public static int myPow_(int x, int n) {
        int r = 1;
        while (n > 1) {
            if ((n & 1) == 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r * x;
    }

    public static double myPow(double x, int n) {
        //特殊情况
        if (x == 1) return 1;
        if (x == 0) return 0;
        if (x == -1) return n % 2 == 0 ? 1 : -1;
        if (n == Integer.MIN_VALUE) return 0.0;
        int flag = 0;
        if (n < 0) {
            n = -n;
            flag = 1;
        }
        double res = 1.0;
        for (int i = 0; i < n; i++) {
            res *= x;
        }
        return flag == 0 ? res : 1 / res;
    }
}

存在重复元素,返回true,否则 false

/**
 * @Author Tiam
 * @Date 2022/6/30 8:28
 * @Description:  存在重复元素,返回true,否则 false
 */
public class Demo15 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        System.out.println(containsDuplicate_1(nums));
    }
    public static boolean containsDuplicate(int[] nums) {
        for (int i = 0; i<nums.length;i++){
            for (int j = i+1; j < nums.length; j++) {
                if(nums[j] == nums[i])
                    return true;
            }
        }
        return false;
    }
    public static boolean containsDuplicate_(int[] nums) {
        // 先排序后,重复的元素会相邻
        Arrays.sort(nums);
        for (int i = 0; i<nums.length-1;i++){
            if(nums[i] == nums[i+1])
                return true;
        }
        return false;
    }
    /**
     * set集合不能含有重复元素
     * add 添加元素时,如含有重复元素则添加失败返回 false
     * 较上面效率更高
     */
    public static boolean containsDuplicate_1(int[] nums) {
        HashSet<Object> objects = new HashSet<>();
        for(int i: nums){
            if(!objects.add(i))
                return true;
        }
        return false;
    }
}

977. 有序数组的平方

/**
 * @Author Tiam
 * @Date 2022/6/30 9:00
 * @Description: 977. 有序数组的平方
 */
public class Demo16 {
    public static void main(String[] args) {
        System.out.println(5);
    }
    public int[] sortedSquares(int[] nums) {
        int[] squares = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            squares[i] = nums[i] * nums[i];
        }
        Arrays.sort(squares);
        return squares;
    }

    public int[] sortedSquares_(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] *= nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

189. 轮转数组

/**
 * @Author Tiam
 * @Date 2022/6/30 9:30
 * @Description: 189. 轮转数组
 */
public class Demo17 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 3};
        rotate(nums, 2);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 超时 overtime
     */
    public void rotate_(int[] nums, int k) {
        int temp;
        for (int i = 0; i < k; i++) {
            temp = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }
    }

    public static void rotate(int[] nums, int k) {
        // 复制数组
        int[] nums_ = Arrays.copyOf(nums, nums.length);
        for (int i = 0; i < nums.length; i++) {
            int j = i + k;
            if (j > nums.length - 1) j %= nums.length;
            nums[j] = nums_[i];
        }
    }
}
梦中千秋
目录
相关文章
菊头蝙蝠
|
6月前
leetcode-1447：最简分数
leetcode-1447：最简分数
菊头蝙蝠
46 0
菊头蝙蝠
|
6月前
|
Java
leetcode-474：一和零
leetcode-474：一和零
菊头蝙蝠
39 0
ruicore
|
算法 Python
LeetCode 386. Lexicographical Numbers
给定一个整数 n, 返回从 1 到 n 的字典顺序。
ruicore
84 0
LeetCode 386. Lexicographical Numbers
白月光永恒
|
人工智能 算法
leetcode第41题
对于这种要求空间复杂度的，我们可以先考虑如果有一个等大的空间，我们可以怎么做。然后再考虑如果直接用原数组怎么做，主要是要保证数组的信息不要丢失。目前遇到的，主要有两种方法就是交换和取相反数。
白月光永恒
89 0
leetcode第41题
白月光永恒
leetcode第39题
对回溯法又有了更深的了解，一般的架构就是一个大的 for 循环，然后先 add，接着利用递归进行向前遍历，然后再 remove ，继续循环。而解法二的动态规划就是一定要找到递进的规则，开始的时候就想偏了，导致迟迟想不出来。
白月光永恒
91 0
leetcode第39题
白月光永恒
leetcode第54题
在 leetcode 的 solution 和 discuss 看了下，基本就是这个思路了，只是实现上有些不同，怎么用来标记是否走过，当前方向，怎么遍历，实现有些不同，但本质上是一样的。就是充分理解题意，然后模仿遍历的过程。
白月光永恒
101 0
leetcode第54题
白月光永恒
|
算法
leetcode第42题
也就是红色区域中的水， 数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。 原则是高度小于 2，temp ++，高度大于等于 2，ans = ans + temp，temp = 0。 temp 初始化为 0 ，ans 此时等于 2。 height [ 0 ] 等于 0 < 2，不更新。 height [ 1 ] 等于 1 < 2，不更新。 height [ 2 ] 等于 0 < 2， 不更新。 height [ 3 ] 等于 2 >= 2， 开始更新 height [ 4 ] 等于 1 < 2，temp = temp + 1 = 1。 h
白月光永恒
100 0
leetcode第42题
白月光永恒
leetcode第34题
从左向右遍历，一旦出现等于 target 的值就结束，保存当前下标。如果从左到右没有找到 target，那么就直接返回 [ -1 , -1 ] 就可以了，因为从左到右没找到，那么从右到左也一定不会找到的。如果找到了，然后再从右到左遍历，一旦出现等于 target 的值就结束，保存当前下标。 时间复杂度是 O（n）并不满足题意，但可以了解下这个思路，从左到右，从右到左之前也遇到过。
白月光永恒
70 0
leetcode第34题
白月光永恒
|
算法
leetcode第32题
这几种算法，暴力破解和动态规划我觉得想的话，还是能分析出来的话，最后两种算法感觉是去挖掘题的本质得到的算法，普适性不是很强。但最后一种算法，从左到右，从右到左，是真的强。
白月光永恒
96 0
leetcode第32题
白月光永恒
leetcode第16题
受到上一题的启发，没有看的，推荐大家可以看一下。我们完全可以先将数组排序，然后先固定一个数字，然后利用头尾两个指针进行遍历，降低一个 O（n）的时间复杂度。 如果 sum 大于 target 就减小右指针，反之，就增加左指针。
白月光永恒
80 0
leetcode第16题