The link to the problem: https://blog.csdn.net/weixin_43731108/article/details/136383904
5. Longest Palindromic Substring#
class Solution {
public String longestPalindrome(String s) {
// Dynamic programming
// dp[i][j] indicates that the substring [i, j] is a palindrome
// char(i) == char(j) dp[i][j] = dp[i+1][j-1]
boolean[][] dp = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
dp[i][i] = true;
}
int start = 0;
int right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
if (j == i + 1) {
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
}
if (dp[i][j] == true && j - i + 1 > right - start + 1) {
start = i;
right = j;
}
}
}
return s.substring(start, right + 1);
}
}
class Solution {
public String longestPalindrome(String s) {
// Expand from the center
int maxLen = 0;
int start = 0;
int end = 0;
for (int i = 0; i < s.length() - 1; i++) {
int left = i - 1;
int right = i + 1;
int count = 1;
// Centered on a single character
while (left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)) {
count += 2;
left--;
right++;
}
if (count > maxLen) {
start = left + 1;
end = right - 1;
maxLen = count;
}
// Centered on two characters
if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
left = i - 1;
right = i + 2;
count = 2;
while (left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)) {
count += 2;
left--;
right++;
}
if (count > maxLen) {
start = left + 1;
end = right - 1;
maxLen = count;
}
}
}
return s.substring(start, end + 1);
}
}
151. Reverse Words in a String#
class Solution {
public String reverseWords(String s) {
// Two pointers from the end to find words
int left = s.length() - 1;
int right = s.length() - 1;
StringBuilder sb = new StringBuilder();
while (left >= 0) {
while (left >= 0 && s.charAt(left) == ' ') {
left--;
}
right = left;
while (left >= 0 && s.charAt(left) != ' ') {
left--;
}
sb.append(s.substring(left + 1, right + 1)).append(" ");
}
return sb.toString().trim();
}
}
You can also find words from front to back and insert them at the front (StringBuilder or deque).
186. Reverse Words in a String II 🔒#
Given a character array
s, reverse the order of words in it.A word is defined as a sequence of non-space characters. The words in
swill be separated by a single space.You must design and implement an in-place solution to solve this problem, meaning no extra space should be allocated.
Example 1:
Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"] Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]Example 2:
Input: s = ["a"] Output: ["a"]Constraints:
1 <= s.length <= 105s[i]can be an English letter (uppercase or lowercase), a digit, or a space' '.- There is at least one word in
ssdoes not contain leading or trailing spaces- The problem guarantees that each word in
sis separated by a single space
class Solution {
public void reverseWords(char[] s) {
int n = s.length;
int left = 0, right = 0;
reverse(s, 0, n-1);
while (right < n) {
while (right<n && s[right] != ' ') {
right++;
}
reverse(s, left, right - 1);
right++;
left = right;
}
}
private void reverse(char[] s, int i, int j) {
while(i<j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
i++;
j--;
}
}
}
328. Odd Even Linked List#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
// Separate odd and even linked lists
ListNode odd = head; // Starting point of odd list
ListNode even = head.next; // Starting point of even list
ListNode evenHead = even; // Save the starting point of the even node list
while (even != null && even.next != null) {
odd.next = even.next;
even.next = odd.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
205. Isomorphic Strings#
class Solution {
public boolean isIsomorphic(String s, String t) {
HashMap<Character, Character> reflection = new HashMap<>();
HashSet<Character> ref_set = new HashSet<>();
int len = s.length();
for (int i = 0; i < len; i++) {
char ch_s = s.charAt(i);
char ch_t = t.charAt(i);
if (reflection.containsKey(ch_s)) {
if (reflection.get(ch_s) != ch_t) {
return false;
}
} else {
if (ref_set.contains(ch_t)) {
return false; // Different characters mapped to the same character
}
reflection.put(ch_s, ch_t);
ref_set.add(ch_t); // Add the character that has been mapped
}
}
return true;
}
}
206. Reverse Linked List#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
15. 3Sum#
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums); // Sort
for (int i = 0; i < nums.length; i++) { // First determine an i
if (nums[i] > 0) {
return res;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // Deduplicate i
}
int left = i + 1; // Two pointers
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++; // Deduplicate left
}
while (right > left && nums[right] == nums[right - 1]) {
right--; // Deduplicate right
}
left++;
right--;
}
}
}
return res;
}
}
213. House Robber II#
class Solution {
public int rob(int[] nums) {
// situation1: do not rob the first house
// situation2: do not rob the last house -> degenerates to the ordinary house robber
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));
}
int robRange(int[] nums, int start, int end) {
if (end == start) {
return nums[start];
}
// dp[i]: the maximum amount that can be stolen considering the houses up to index i (including i)
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
}
71. Simplify Path#
class Solution {
public String simplifyPath(String path) {
String[] names = path.split("/");
Deque<String> stack = new ArrayDeque<>(); // Stack or queue
for (String name : names) {
if ("..".equals(name)) { // Parent directory
if (!stack.isEmpty()) {
stack.pollLast();
}
} else if (name.length() > 0 && !".".equals(name)) { // Ignore current directory
stack.offerLast(name);
}
}
StringBuilder sb = new StringBuilder();
if (stack.isEmpty()) {
sb.append("/");
} else {
while (!stack.isEmpty()) {
sb.append("/");
sb.append(stack.pollFirst());
}
}
return sb.toString();
}
}
1. Two Sum#
class Solution {
public int[] twoSum(int[] nums, int target) {
// Number, index
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] { map.get(target - nums[i]), i };
} else {
map.put(nums[i], i);
}
}
return new int[2];
}
}
1239. Maximum Length of a Concatenated String with Unique Characters#
class Solution {
int res = 0;
public int maxLength(List<String> arr) {
boolean[] charset = new boolean[26]; // Used to detect duplicate characters
backtrack(arr, 0, charset, 0);
return res;
}
void backtrack(List<String> arr, int start, boolean[] charset, int count) {
res = Math.max(res, count); // Update the maximum value each time
for (int i = start; i < arr.size(); i++) {
char[] chars = arr.get(i).toCharArray();
boolean[] charset_copy = charset.clone();
boolean flag = false;
for (int j = 0; j < chars.length; j++) {
if (charset_copy[chars[j] - 'a'] == true) { // Duplicate character
flag = true;
break;
} else {
charset_copy[chars[j] - 'a'] = true;
}
}
if (flag == true) {
continue;
}
backtrack(arr, i + 1, charset_copy, count + chars.length);
}
}
}
54. Spiral Matrix#
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
// Define the four boundaries: up, down, left, right
int up_bound = 0, down_bound = matrix.length - 1;
int left_bound = 0, right_bound = matrix[0].length - 1;
while (up_bound <= down_bound && left_bound <= right_bound) {
if (up_bound <= down_bound) { // Up
for (int i = left_bound; i <= right_bound; i++) {
res.add(matrix[up_bound][i]);
}
up_bound++;
}
if (left_bound <= right_bound) {// Right
for (int i = up_bound; i <= down_bound; i++) {
res.add(matrix[i][right_bound]);
}
right_bound--;
}
if (up_bound <= down_bound) {// Down
for (int i = right_bound; i >= left_bound; i--) {
res.add(matrix[down_bound][i]);
}
down_bound--;
}
if (left_bound <= right_bound) { // Left
for (int i = down_bound; i >= up_bound; i--) {
res.add(matrix[i][left_bound]);
}
left_bound++;
}
}
return res;
}
}
1143. Longest Common Subsequence#
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// Dynamic programming
// dp[i][j] indicates the longest common subsequence value of the substring of text1 ending at index i-1 and the substring of text2 ending at index j-1
// char_i == char_j dp[i][j] = dp[i-1][j-1] + 1
// or dp[i][j] = max(dp[i-1][j], dp[i][j-1])
// dp[0][j] = 0; dp[i][0] = 0;
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
415. Add Strings#
class Solution {
public String addStrings(String num1, String num2) {
int ptr1 = num1.length() - 1; // Two pointers
int ptr2 = num2.length() - 1;
int carry = 0; // Carry
StringBuilder sb = new StringBuilder();
while (ptr1 >= 0 && ptr2 >= 0) {
int a = num1.charAt(ptr1) - '0';
int b = num2.charAt(ptr2) - '0';
sb.append((a + b + carry) % 10);
carry = (a + b + carry) / 10;
ptr1--;
ptr2--;
}
while (ptr1 >= 0) {
int a = num1.charAt(ptr1) - '0';
sb.append((a + carry) % 10);
carry = (a + carry) / 10;
ptr1--;
}
while (ptr2 >= 0) {
int b = num2.charAt(ptr2) - '0';
sb.append((b + carry) % 10);
carry = (b + carry) / 10;
ptr2--;
}
if (carry != 0) {
sb.append(carry);
}
return sb.reverse().toString();
}
}
1006. Clumsy Factorial#
This problem can be simulated using a stack, and it doesn't need to be overly complicated.
class Solution {
public int clumsy(int n) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(n); // First push n onto the stack
n--;
int index = 0; // Used to track the operator to be used
while (n > 0) {
if (index % 4 == 0) {
// Multiplication
stack.push(stack.pop() * n);
} else if (index % 4 == 1) {
// Division
stack.push(stack.pop() / n);
} else if (index % 4 == 2) {
// Addition
stack.push(n);
} else {
// Subtraction, need to push negative number onto the stack
stack.push(-n);
}
n--;
index++;
}
// Sum all numbers in the stack
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
}
1090. Largest Values from Labels#
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
// Greedy
int n = values.length;
Integer[] id = new Integer[n];
for (int i = 0; i < n; i++) {
id[i] = i; // Store indices
}
// Sort indices by value in descending order
Arrays.sort(id, (a, b) -> values[b] - values[a]);
// Label and usage count
HashMap<Integer, Integer> map = new HashMap<>();
int sum = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (count == numWanted) {
break;
}
if (map.getOrDefault(labels[id[i]], 0) == useLimit) {
continue;
}
sum += values[id[i]];
count++;
map.put(labels[id[i]], map.getOrDefault(labels[id[i]], 0) + 1);
}
return sum;
}
}
2. Add Two Numbers#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
int sum = val1 + val2 + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
p.next = node;
p = p.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry != 0) {
p.next = new ListNode(carry);
}
return dummy.next;
}
}
445. Add Two Numbers II#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<ListNode> stack1 = new ArrayDeque<>();
Deque<ListNode> stack2 = new ArrayDeque<>();
ListNode ptr = l1;
while (ptr != null) {
stack1.push(ptr);
ptr = ptr.next;
}
ptr = l2;
while (ptr != null) {
stack2.push(ptr);
ptr = ptr.next;
}
ListNode dummy = new ListNode(-1, null);
int carry = 0;
while (!stack1.isEmpty() && !stack2.isEmpty()) {
ListNode a = stack1.pop();
ListNode b = stack2.pop();
int c = (a.val + b.val + carry) % 10;
carry = (a.val + b.val + carry) / 10;
ListNode node = new ListNode(c);
node.next = dummy.next;
dummy.next = node;
}
while (!stack1.isEmpty()) { // Can also return 0 if empty
ListNode a = stack1.pop();
int c = (a.val + carry) % 10;
carry = (a.val + carry) / 10;
ListNode node = new ListNode(c);
node.next = dummy.next;
dummy.next = node;
}
while (!stack2.isEmpty()) {
ListNode b = stack2.pop();
int c = (b.val + carry) % 10;
carry = (b.val + carry) / 10;
ListNode node = new ListNode(c);
node.next = dummy.next;
dummy.next = node;
}
if (carry != 0) {
ListNode node = new ListNode(carry);
node.next = dummy.next;
dummy.next = node;
}
return dummy.next;
}
}
164. Maximum Gap#
class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) {
return 0;
}
Arrays.sort(nums); // O(nlogn) -> Change to use radix sort or bucket sort
int res = 0;
for (int i = 0; i < nums.length - 1; i++) {
res = Math.max(res, nums[i + 1] - nums[i]);
}
return res;
}
}
There is no time for the top ten sorts...
39. Combination Sum#
class Solution {
List<List<Integer>> res;
List<Integer> track;
int sum;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new ArrayList<>();
track = new ArrayList<>();
sum = 0;
backtrack(candidates, target, 0);
return res;
}
void backtrack(int[] candidates, int target, int startIndex) {
if (sum > target) {
return;
}
if (sum == target) {
res.add(new ArrayList<>(track));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
sum = sum + candidates[i];
track.add(candidates[i]);
backtrack(candidates, target, i);
sum = sum - candidates[i]; // Backtrack
track.removeLast();
}
}
}
394. Decode String#
class Solution {
Deque<Integer> numStack = new ArrayDeque<>();
Deque<StringBuilder> stack = new ArrayDeque<>();
public String decodeString(String s) {
int ptr = 0;
stack.push(new StringBuilder());
while (ptr < s.length()) {
char currentChar = s.charAt(ptr);
if (Character.isDigit(currentChar)) {
int num = 0;
while (Character.isDigit(s.charAt(ptr))) {
num = num * 10 + (s.charAt(ptr) - '0');
ptr++;
}
numStack.push(num);
continue; // Skip '['
} else if (currentChar == ']') {
int repeatTimes = numStack.pop();
StringBuilder decodedString = stack.pop();
StringBuilder parent = stack.peek();
for (int i = 0; i < repeatTimes; i++) {
parent.append(decodedString);
}
} else if (currentChar == '[') {
stack.push(new StringBuilder());
} else {
stack.peek().append(currentChar);
}
ptr++;
}
return stack.pop().toString();
}
}
19. Remove Nth Node From End of List#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}