LeetCode 刷题记录：Java/C++ 算法实战

本文记录了在 LeetCode 上解决多道经典算法题的实践过程，涵盖链表、数组和字符串操作，并提供了 C++ 和 Java 两种语言的解法。旨在分享刷题经验，提升算法能力。

预计阅读 2 分钟 最后更新
  • 算法
  • 编程实践

2. Add Two Numbers

Medium

Topics

Companies

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

image-20240829104904406

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // 使用一个虚拟头节点
    ListNode* res = &dummy;
    int carry = 0;

    while (l1 != nullptr || l2 != nullptr || carry) {
        int sum = carry;
        if (l1 != nullptr) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2 != nullptr) {
            sum += l2->val;
            l2 = l2->next;
        }

        carry = sum / 10;
        res->next = new ListNode(sum % 10);
        res = res->next;
    }

    return dummy.next;
}

};

这里设计到的语法：

ListNode dummy(0); // 初始化节点struct，初始化值为0
res->next = new ListNode(sum % 10); // 新增节点，并设置初值

  1. Median of Two Sorted Arrays

    Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

    The overall run time complexity should be O(log (m+n)).

    Example 1:

    Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

    Example 2:

    Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
    import java.util.ArrayList;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int sum = m + n;
        int i = 0,j =0;
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        while (i<m && j<n) {
            if (nums1[i] <= nums2[j]) {
                list1.add(nums1[i]);
                i++;
            }else if (nums1[i] > nums2[j]) {
                list1.add(nums2[j]);
                j++;
            }
        }
        if (j < n){
            while (j < n){
                list1.add(nums2[j]);
                j++;
            }
        }
        if (i < m){
            while (i < m){
                list1.add(nums1[i]);
                i++;
            }
        }
        System.out.println(list1);
        if (sum % 2 == 0){
            return (double) (list1.get(sum / 2 -1) + list1.get(sum / 2)) / 2;
        }else {
            return (double) (list1.get(sum / 2));
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findMedianSortedArrays(new int[]{1, 3, 5}, new int[]{2, 4}));
    }
}

  2. Longest Palindromic Substring

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0,max_length = 1;
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < len-1; i++) {
            if (s.charAt(i) == s.charAt(i+1)) {
                dp[i][i+1] = true;
                start = i;
                max_length = 2;
            }
        }

        for (int l = 3 ;l <s.length() + 1;l++) {
            for (int i =0 ;i<s.length() - l + 1;i++) {
                if (s.charAt(i) == s.charAt(i+l-1) && dp[i+1][i+l-2]) {
                    dp[i][i+l-1] = true;
                    start = i;
                    max_length = l;
                }
            }
        }
        System.out.println(max_length);
        return s.substring(start, start + max_length);

    }

  3. Zigzag Conversion

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

    Example 2:

    Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
    public String convert_opt(String s, int numRows) {
    if (numRows == 1) return s;  // 如果只有一行，则直接返回原字符串

    StringBuilder res = new StringBuilder();
    int len = s.length();
    int cycleLength = 2 * numRows - 2; // 一个周期的长度，即从上到下再从下到上的字符跨度

    for (int row = 0; row < numRows; row++) {
        // 遍历每一行
        for (int i = row; i < len; i += cycleLength) {
            // 添加当前行和当前索引的字符
            res.append(s.charAt(i));

            // 处理在中间行（除了最上面和最下面的行）需要额外添加的字符
            int secondCharIndex = i + cycleLength - 2 * row;
            if (row != 0 && row != numRows - 1 && secondCharIndex < len) {
                res.append(s.charAt(secondCharIndex));
            }
        }
    }

    return res.toString();
}

  4. Reverse Integer

    Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

    Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

    Example 1:

    Input: x = 123
Output: 321

    Example 2:

    Input: x = -123
Output: -321

    Example 3:

    Input: x = 120
Output: 21
    public int reverse(int x) {

    if (x == 0) return 0;


    String s = String.valueOf(Math.abs(x));
    String reversed = new StringBuilder(s).reverse().toString();

    try {
        long result = Long.parseLong(reversed);
        // 处理负数
        if (x < 0) {
            result = -result;
        }

        // 检查是否溢出
        if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
            return 0;
        }

        return (int)result;
    } catch (NumberFormatException e) {
        // 处理可能的数字格式异常
        return 0;
    }
}

8. String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

  1. Whitespace: Ignore any leading whitespace (" ").
  2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present. 符号：通过检查下一个字符是否为 '-' 或 '+' 来确定符号，如果两者都不存在则假设为正数。
  3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0. 转换：跳过前导零，读取整数，直到遇到非数字字符或字符串结尾。如果未读取到任何数字，则结果为 0。
  4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

public int myAtoi(String str) {

    if(str==null|str.isEmpty()) return 0;
    str=str.trim();
    if(str.isEmpty()) return 0;
    int i = 0;
    int sign = 1;
    int result = 0;
    if (str.charAt(i)=='-') {
        sign = -1;
        i++;
    }else if (str.charAt(i)=='+') {
        i++;
    }
   while (i < str.length() && Character.isDigit(str.charAt(i))) {
       int n = str.charAt(i) - '0';
       if (result > Integer.MAX_VALUE / 10 ||
               (result == Integer.MAX_VALUE / 10 && n > Integer.MAX_VALUE % 10)) {
           // Will overflow with this digit
           return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
       }
       result = result * 10 + n;
       i++;
   }
   return result * sign;
}

9. Palindrome Number

Given an integer x, return true if x is a palindrome*, and* false otherwise

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int len = s.length();
        for (int i = 0; i < len/2; i++) {
            if (s.charAt(i) != s.charAt(len-i-1)) {
                return false;
            }
        }
        return true;
    }

留言讨论

0 条留言

正在加载留言...