leetcode题库

一、两数之和

原题链接

• 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
• 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
• 你可以按任意顺序返回答案。

Python解法

1、暴力解法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #获取nums数组的长度
        n = len(nums)
        
        #两次循环
        for i in range(n - 1):
            for j in range(i + 1, n):
                if target == nums[i] + nums[j]:
                    return [i, j]
        #若是没有找到则返回[]空列表
        return []

2、dict集合（哈希表）解法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #创建一个空dict集合
        num_to_index = dict()
 
        #使用enumerate()方法获取nums数组的 （索引，值）的迭代器对象，并进行遍历
        for index,num in enumerate(nums):
            complement = target - num  #计算与当前数字匹配的补数
            if complement in num_to_index:
                return [num_to_index[complement], index]  # 找到补数在哈希表中的索引，以及当前数字的索引
            num_to_index[num] = index # 将当前数字添加到哈希表中
        return [] # 如果没有找到匹配的组合，返回空列表

Java解法

1、暴力解法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }
}

2、HashMap集合（哈希表）解法

class Solution {
    public int[] twoSum(int[] nums, int target) {
 
        HashMap<Integer, Integer> hashMap = new HashMap<>();
 
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
 
            if (hashMap.containsKey(complement)) {
                return new int[]{hashMap.get(complement), i};
            }
            hashMap.put(nums[i], i);
        }
        return new int[]{};
    }
}

二、两数相加

原题链接

• 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
• 请你将两个数相加，并以相同形式返回一个表示和的链表。
• 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

Python解法

class ListNode(object):
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next
 
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        virtual_head = ListNode()
        current = virtual_head
        carray = 0
 
        while l1 is not None or l2 is not None or carray != 0:
            val1 = l1.val if l1 is not None else 0
            val2 = l2.val if l2 is not None else 0
 
            total = val1 + val2 + carray
            carray = total // 10
 
            current.next = ListNode(total % 10)
            current = current.next
 
            if l1 is not None:
                l1 = l1.next
 
            if l2 is not None:
                l2 = l2.next
 
        return virtual_head.next
 
    def print_list(self,head):
        while head is not None:
            print(head.val," -> ",end="")
            head = head.next
        print("None")
 
    def main(self):
        l1 = ListNode(9,ListNode(9))
        l2 = ListNode(1,ListNode(1))
        self.print_list(self.addTwoNumbers(l1, l2))
 
if __name__ == '__main__':
    s = Solution()
    s.main()

Java解法

/**
 * 单链表中的节点：
 * 节点是单链表中的基本单元
 * 每一个节点Node都有两个属性
 *    一个属性：是存储的数据
 *    另一个属性：是下一个节点的内存地址
 */
class ListNode {
    //实例变量 val 存储的数据
    int val;
    //实例变量 next 下一个节点的引用（内存地址）
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
 
public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // 创建一个虚拟头节点
        ListNode current = dummyHead; // 指向当前节点的指针
        int carry = 0; // 进位的初始值为0
 
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = l1 != null ? l1.val : 0; // 获取链表l1当前节点的值，如果为null，则默认为0
            int val2 = l2 != null ? l2.val : 0; // 获取链表l2当前节点的值，如果为null，则默认为0
 
            int total = val1 + val2 + carry; // 计算当前位的和，加上进位
            carry = total / 10; // 更新进位
 
            current.next = new ListNode(total % 10); // 创建新节点，存储当前位的值
            current = current.next; // 移动当前指针到新节点
 
            if (l1 != null) l1 = l1.next; // 如果链表l1还有下一个节点，移动l1指针到下一个节点
            if (l2 != null) l2 = l2.next; // 如果链表l2还有下一个节点，移动l2指针到下一个节点
        }
 
        return dummyHead.next; // 返回虚拟头节点的下一个节点作为结果链表的头节点
    }
 
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> "); // 输出节点的值
            head = head.next; // 移动指针到下一个节点
        }
        System.out.println("null"); // 输出链表结束标志
    }
 
    public static void main(String[] args) {
        AddTwoNumbers solution = new AddTwoNumbers();
 
        // 创建示例链表：342 表示为 2->4->3
        ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
 
        ListNode result = solution.addTwoNumbers(l1, l2);
        printList(result);  // 输出: 7 -> 0 -> 8 -> null
    }
}

三、无重复字符的最长子串

原题链接

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

Python解法

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_list = list()
 
        max_lenght = 0
        left = 0
 
        for right in range(len(s)):
            current_char = s[right]
            while current_char in char_list:
                char_list.remove(s[left])
                left += 1
            char_list.append(current_char)
            max_lenght = max(max_lenght, len(char_list))
        return max_lenght

Java解法

import java.util.*;
 
/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s){
        ArrayList<Character> list = new ArrayList<>(); //用于存储当前窗口中的字符
 
        int maxLength = 0; //记录最长子串的长度
        int left = 0; //左指针，窗口的起始位置
 
        for (int right = 0; right < s.length(); right++){
 
            while (list.contains(s.charAt(right))){
                list.remove((Character) s.charAt(left));
                left++;
            }
            list.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
 
    public static void main(String[] args) {
        LengthOfLongestSubstring l = new LengthOfLongestSubstring();
        System.out.println(l.lengthOfLongestSubstring("pwwkew"));
    }
}

四、最长回文串

原题链接

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

Python解法

1、暴力解法

class Solution:
	def longestPalindrome(self, s: str) -> str:
		s_length = len(s)
		if s_length < 2:
			return s
 
		max_length = 1
		start = 0
		char_list = list(s)
 
		for i in range(s_length - 1):
				for j in range(i + 1, s_length):
						if j - i + 1 > max_length and self.valicPalindromic(char_list, i, j):
								max_length = j - i + 1
								start = i
		return "".join(char_list[start: start + max_length])
 
	def valicPalindromic(self, char_list, left, right):
		while left < right:
			if char_list[left] != char_list[right]:
					return False
			left += 1
			right -= 1
		return True

2、中心扩展解法

def expandAroundCenter(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left + 1:right]
 
def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s
 
    start = 0
    end = 0
 
    for i in range(n):
        len1 = len(expandAroundCenter(s, i, i))
        len2 = len(expandAroundCenter(s, i, i + 1))
        max_len = max(len1, len2)
 
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
 
    return s[start:end + 1]
 
# 示例用法
s = "babad"
result = longestPalindrome(s)
print(result)  # 输出 "bab" 或 "aba"

Java解法

1、暴力解法

class Solution {
    public boolean validPalindromic(char[] charArray, int left, int right){
		while(left < right){
			if(charArray[left] != charArray[right]){
				return false;
			}
			left++;
			right--;
		}
		return true;
	}
	
	public String longestPalindrome(String s){
		int len = s.length();
		if(len < 2){
			return s;
		}
		
		int maxLen = 1;
		int start = 0;
		char[] charArray = s.toCharArray();
		
		for(int i = 0; i < len - 1; i++){
			for(int j = i + 1; j < len; j++){
				if(j - i + 1 > maxLen && validPalindromic(charArray, i, j)){
					maxLen = j - i + 1;
					start = i;
				}
			}
		}
		return s.substring(start, start + maxLen);
	}
}

2、中心扩展解法

public class LongestPalindromic{
	public String expandAroundCenter(String s, int left, int right){
		while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
			left--;
			right++;
		}
		return s.substring(left + 1, right);
	}
	
	public String longestPalindromic(String s){
		int len = s.length();
		if(len < 2){
			return s;
		}
		
		int start = 0;
		int end = 0;
			
		for(int i = 0; i < len; i++){
			int oddLen = expandAroundCenter(s, i, i).length();
			int evenLen = expandAroundCenter(s, i, i + 1).length();
			
			int maxLen = Math.max(oddLen, evenLen);
			
			if(maxLen > end - start){
				start = i - (maxLen - 1) / 2;
				end = i + maxLen / 2;
			}
		}
		
		return s.substring(start, end + 1);
	}
	
	public static void main(String[] args){
		LongestPalindromic l = new LongestPalindromic();
		
		String s = "cbbd";
		String result = l.longestPalindromic(s);
		System.out.println(result);
		
	}
}

五、N字形变换

原题链接

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

Python解法

class Solution(object):
    def convert(self, s:str, numRows:int) -> str:
        n, r = len(s), numRows
        
        if r == 1 or n <= r:
            return s
        
        t = 2 * r - 2
        c = (n + t) // t * (r - 1)
        
        my_list = [[None] * c for i in range(r)]
        
        x = 0
        y = 0
        
        for i in range(n):
            my_list[y][x] = s[i]
            if i % t < r - 1:
                y += 1
            else:
                y -= 1
                x += 1
        
        return_list = list()
        
        for row in my_list:
            for col in row:
                if col is not None:
                    return_list.append(col)
        
        return "".join(return_list)
 
 
if __name__ == "__main__":
    s = Solution()
    print(s.convert("PAYPALISHIRING", 3))

Java解法

import java.lang.StringBuilder;
 
public class Solution{
	public String convert(String s, int numRows){
		//n为传入的字符串中的字符个数
		//r为行数
		int n = s.length(), r = numRows;
		
		//如果行数为1 或者 字符总个数小于等于行数的话，说明只需要1列就行，所以直接返回该字符串
		if(r == 1 || n <= r){
			return s;
		}
		
		//一个周期内的字符个数为  行数 + 行数 - 2 = 2行数 - 2
		int t = 2 * r - 2;
		
		//列数，每个周期的列数为  1 + 行数 - 2 = 行数 - 1
		//(n + t) 表示给原始字符中的字符个数在加一个周期，害怕若是不能整除计算错列数，列数可以多但不能少
		int c = (n + t) / t * (r - 1);
		
		//创建一个 r行，c列的二维字符数组
		//二维数组中r表示行数，c表示每一行中的列数
		char[][] chars = new char[r][c];
		
		//使用for循环在二维数组中放置元素
		//i表示字符串中每个字符的索引下标
		//x表示列数
		//y表示行数
		for(int i = 0, x = 0, y = 0; i < n; i++){
			//先在第一行第一列的位置处放置第一个元素
			chars[y][x] = s.charAt(i);
			//判断什么时候应该往下放元素，什么时候应该往右上放元素
			//应该画图找规律
			if(i % t < r - 1){
				y++;
			}else{
				x++;
				y--;
			}
		}
		//创建一个字符串缓冲对象
		StringBuilder stringBuilder = new StringBuilder(); 
		//遍历二维数组
		for(char[] row: chars){
			//遍历一维数组
			for(char col: row){
				//根据字符的ASCII码进行判断该位置处是否有元素
				//char的默认值为 /u0000 换算成十进制为 0，因此不等于0时，该位置处必有元素
				if(col != 0){
					//将该元素添加至字符串缓存对象中
					stringBuilder.append(col);
				}
			}
		}
		//返回字符串缓存对象的字符串表示形式
		return stringBuilder.toString();
	}
	
	public static void main(String[] args){
		Solution solution = new Solution();
		String s = "PAYPALISHIRING";
		int numRows = 3;
		String result = solution.convert(s, numRows);
		System.out.println(result);
	} 
}

六、整数反转

原题链接

1. 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
2. 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
3. 假设环境不允许存储 64 位整数（有符号或无符号）。

Python解法

class IntegerInversion(object):
    def reverse(self, x:int) -> int:
        #将int不可迭代类型转换为str可迭代类型
        strInt = str(x)
        #将str可迭代类型转换转换为list可迭代类型
        strList = list(strInt)
        #判断其第一个元素是否为“-” 号
        if strList[0] == "-":
            strListNoFirstElement = strList[1:]
            strListNoFirstElement.reverse()
            returnInt = int("-" + "".join(strListNoFirstElement))
            return returnInt if returnInt >= -2 **31 and returnInt <= 2 ** 31 -1 else 0
        strList.reverse()
        #将str类型转换为int类型返回
        returnInt = int("".join(strList))
        return returnInt if returnInt >= -2 **31 and returnInt <= 2 ** 31 -1 else 0

Java解法

public class IntegerReverse{
	
	public int reverse(int x){
		long ans = 0;//自动类型转换，0默认为int类型，自动转换为long类型
		while(x != 0){
			//取余依次递推
			ans = ans * 10 + x % 10;
			x /= 10;
		}
		//将long类型的ans强制类型转换为int类型，若是ans没有超出int类型的取值范围 -2147483648 ~ 2147483647 之间
		//则强制类型转换后应该和原数相等，否则即为超出了int类型的取值范围，返回0
		return (int)ans == ans ? (int)ans : 0;
	}
	
	public static void main(String[] args){
		IntegerReverse s = new IntegerReverse();  //2147483647
		
		System.out.println(s.reverse(2147483647));
	}
}

七、字符串转换整数（atoi）

原题链接

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5. 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
6. 返回整数作为最终结果。

注意：

• 本题中的空白字符只包括空格字符 ' ' 。
• 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

Python解法

class Automation(object):
    def __init__(self):
        self.ans = 0
        self.sign = 1
        self.state = "start"
        self.MAX_VALUE = 2147483647
        self.MIN_VALUE = -2147483648
        
        self.table = {
            "start": ["start", "signed", "in_number", "end"],
            "signed": ["end", "end", "in_number", "end"],
            "in_number": ["end", "end", "in_number", "end"],
            "end": ["end", "end", "end", "end"]
        }
    
    def get_col(self, c):
        if c == " ":
            return 0
        
        if c == "+" or c == "-":
            return 1
        
        if c.isdigit():
            return 2
        return 3
    
    def get(self, c):
        self.state = self.table.get(self.state)[self.get_col(c)]
        
        if "in_number" == self.state:
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, self.MAX_VALUE) if self.sign == 1 else min(self.ans, -self.MIN_VALUE)  
        elif "signed" == self.state:
            self.sign = 1 if c == "+" else -1
    
    def main(self, s):
        for i in s:
            self.get(i)
        return self.sign * self.ans
 
if __name__ == "__main__":
    a = Automation()
    s = "-1 23"
    print(a.main(s))

Java解法

import java.util.Map;
import java.util.HashMap;
 
class Automation{
	//ans表示要返回的整数，不带符号
	public long ans = 0;
	//标志位，1表示为正数，-1表示为负数
	public int sign = 1;
	//state状态，默认状态为 start开始状态
	private String state = "start";
	//方法内部类语法
	private Map<String, String[]> table = new HashMap<>(){{
		put("start", new String[]{"start", "signed", "in_number", "end"});
		put("signed", new String[]{"end", "end", "in_number", "end"});
		put("in_number", new String[]{"end", "end", "in_number", "end"});
		put("end", new String[]{"end", "end", "end", "end"});
	}};
	//获取列号
	private int getCol(char c){
		//如果c为空格，则表示第一列
		if(c == ' ') return 0;
		//如果c为 - 或 + 符号 则表示第二列
		if(c == '+' || c == '-') return 1;
		//如果c为 数字，则表示第三列
		if(Character.isDigit(c)) return 2;
		//否则c为其他，表示第四列
		return 3;
	}
	
	public void get(char c){
		//获取当前的状态
		state = this.table.get(state)[this.getCol(c)];
		//如果当前状态为in_number
		if("in_number".equals(state)){
			//由于c是char类型，'0'所对应的ASCII码为48，用于获取char类型所对应的十进制数
			ans = ans * 10 + (c - '0');
			//取最小值
			ans = (sign == 1)? Math.min(ans, (long)Integer.MAX_VALUE): Math.min(ans, -(long)Integer.MIN_VALUE);   
		}else if("signed".equals(state)){
			//在signed符号状态时给sign赋值
			//1 表示为正
			//-1 表示为负
			sign = (c == '+') ? 1 : -1;
		}
	}
}
 
public class Solution{
	public int maAtoi(String s){
		//创建automation对象
		Automation automation = new Automation();
		//遍历字符串中的每个字符
		for(int i = 0; i < s.length(); i++){
			automation.get(s.charAt(i));
		}
		//使用符号 * 值，转换为int类型返回
		return (int) (automation.sign * automation.ans);
	}
	
	public static void main(String[] args){
		Solution s = new Solution();
		String str = "-123";
		int result = s.maAtoi(str);
		System.out.println(result);
	}
}

八、回文数

原文链接

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

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

• 例如，121 是回文，而 123 不是。

Python解法

class Solution:
    def isPalindrome1(self, x: int) -> bool:
        str_int = str(x)
        return str_int == str_int[::-1]
 
    def isPalindrome2(self, x: int) -> bool:
        if x < 0:
            return False
        reversed = 0
        original = x
        while x != 0:
            digit = x % 10
            reversed = reversed * 10 + digit
            x //= 10
        return reversed == original

Java解法

public class Solution {
    public boolean isPalindrome1(int x){
        String strInt = String.valueOf(x);
        int length = strInt.length();
        for(int i = 0; i < length / 2; i++){
            if(strInt.charAt(i) != strInt.charAt(length - 1 - i)) return false;
        }
        return true;
    }
 
    public boolean isPalindrome2(int x){
        // 负数不能是回文数
        if (x < 0){
            return false;
        }
        // 计算 x 的反转数
        int reversed = 0;
        int original = x;
        while (x != 0){
            int digit = x % 10;
            reversed = reversed * 10 + digit;
            x /= 10;
        }
        // 如果反转后的数与原始数相等，则是回文数，否则不是
        return original == reversed;
    }
 
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isPalindrome1(-232));
    }
}