LeetCode刷题记录

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.

/**
 * 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); // 新增节点，并设置初值

4. 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}));
   	}
   	}

5. 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);
   	}

6. 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();
   	}

7. 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;

    }