LeetCode 刷题
java

LeetCode 刷题

链表反转链表环形链表两数相加两个非空的链表,表示两个非负的整数。每位数字按照逆序的方式存储,并且每个节点只能存储 一位数字。请将两个数相加,并以相同形式返回一个表示和的链表。回文链表数组移除元素综合罗...

花野猫

花野猫

更新于 2024-05-14

6178

链表

反转链表

java
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}

环形链表

java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}

两数相加

两个非空的链表,表示两个非负的整数。每位数字按照逆序的方式存储,并且每个节点只能存储 一位数字。请将两个数相加,并以相同形式返回一个表示和的链表。

java
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
}

回文链表

java
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
java
class Solution {
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode){
if(currentNode!=null){
if(!recursivelyCheck(currentNode.next)){
return false;
}
if(currentNode.val!=frontPointer.val){
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
}

数组

移除元素

java
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}

综合

罗马数字转整数

java
class Solution {
Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {
{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}
};
public int romanToInt(String s) {
int ans = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int value = symbolValues.get(s.charAt(i));
if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
ans -= value;
} else {
ans += value;
}
}
return ans;
}
}

加一

java
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0)
return digits;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}

赎金信

java
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
for (int i = 0; i < ransomNote.length(); i++) {
String c = String.valueOf(ransomNote.charAt(i));
if (magazine.contains(c)) {
magazine = magazine.replaceFirst(c, "");
} else {
return false;
}
System.out.println(magazine);
}
return true;
}
}

最长连续序列

java
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
return longestStreak;
}
}

有效的括号

java
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {
{
put(')', '(');
put(']', '[');
put('}', '{');
}
};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}

二叉树的最大深度

java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}

对称二叉树

java
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}

二叉树的层平均值

java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> averages = new ArrayList<Double>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
double sum = 0;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
TreeNode left = node.left, right = node.right;
if (left != null) {
queue.offer(left);
}
if (right != null) {
queue.offer(right);
}
}
averages.add(sum / size);
}
return averages;
}
}

二叉树的层序遍历

java
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (root == null) {
return new ArrayList();
}
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> oneLevel = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
oneLevel.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
list.add(oneLevel);
}
return list;
}
}

二叉搜索树的最小绝对值

java
class Solution {
int pre;
int ans;
public int getMinimumDifference(TreeNode root) {
ans = Integer.MAX_VALUE;
pre = -1;
dfs(root);
return ans;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (pre == -1) {
pre = root.val;
} else {
ans = Math.min(ans, root.val - pre);
pre = root.val;
}
dfs(root.right);
}
}

二叉搜索树中第K小的元素

java
class Solution {
List<Integer> list = new ArrayList<Integer>();
public int kthSmallest(TreeNode root, int k) {
dfs(root);
System.out.print(list);
return list.get(k - 1);
}
private void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.left);
list.add(node.val);
dfs(node.right);
}
}