移除元素
题目：27. 移除元素 - 力扣（LeetCode）
给你一个数组?nums?和一个值?val，你需要?原地?移除所有数值等于?val?的元素，并返回移除后数组的新长度。
快慢指针：
public int removeElement(int[] nums, int val) {
int l = 0;
for (int r = 0; r < nums.length; r++)
if (nums[r] != val) nums[l++] = nums[r];
return l;
}
删除有序数组中的重复项
题目：26. 删除有序数组中的重复项 - 力扣（LeetCode）
给你一个?升序排列?的数组?nums?，请你?原地?删除重复出现的元素，使每个元素?只出现一次?，返回删除后数组的新长度。元素的?相对顺序?应该保持?一致?。
快慢指针：
public int removeDuplicates(int[] nums) {
int l = 1;
for (int r = 1; r < nums.length; r++)
if (nums[r] != nums[l - 1]) nums[l++] = nums[r];
return l;
}
移动零
题目：283. 移动零 - 力扣（LeetCode）
给定一个数组?nums，编写一个函数将所有?0?移动到数组的末尾，同时保持非零元素的相对顺序。
快慢指针：
class Solution {
public void moveZeroes(int[] nums) {
for (int l = 0, r = 0; r < nums.length; r++)
if (nums[r] != 0) swap(nums, l++, r);
}
void swap(int[] nums, int i, int j) {
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
}
不使用交换的双指针：
public void moveZeroes(int[] nums) {
int l = 0;
for (int r = 0; r < nums.length; r++)
if (nums[r] != 0) nums[l++] = nums[r];
while (l < nums.length) nums[l++] = 0;
}
比较含退格的字符串*
题目：844. 比较含退格的字符串 - 力扣（LeetCode）
给定?s?和?t?两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回?true?。#?代表退格字符。
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
从前往后重构字符串：
class Solution {
public boolean backspaceCompare(String s, String t) {
return getString(s).equals(getString(t));
}
public String getString(String s) {
StringBuilder sb = new StringBuilder();
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i++) {
if (cs[i] != '#') sb.append(cs[i]);
else if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
}
return sb.toString();
}
}
从后往前重构字符串：
class Solution {
public boolean backspaceCompare(String s, String t) {
return getString(s).equals(getString(t));
}
private String getString(String s) {
StringBuilder sb = new StringBuilder();
char[] cs = s.toCharArray();
int size = 0;
for (int i = cs.length - 1; i >= 0; i--) {
if (cs[i] == '#') size++;
else if (size == 0) sb.append(cs[i]);
else size--;
}
return sb.toString();
}
}
O(1) 空间复杂度做法：比较难。。。
有序数组的平方
题目：977. 有序数组的平方 - 力扣（LeetCode）
给你一个按?非递减顺序?排序的整数数组?nums，返回?每个数字的平方?组成的新数组，要求也按?非递减顺序?排序。
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int l = 0, r = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[l] + nums[r] < 0) {
res[i] = nums[l] * nums[l++];
} else {
res[i] = nums[r] * nums[r--];
}
}
return res;
}
反转字符串
题目：344. 反转字符串 - 力扣（LeetCode）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组?s?的形式给出。
使用位运算进行交换操作：
public void reverseString(char[] s) {
int size = s.length - 1;
for (int i = 0; i < s.length / 2; i++) {
int j = size - i;
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
}
一般可以将 反转字符数组 抽取成模板（经常会用到这个函数）
class Solution {
public void reverseString(char[] s) {
reverse(s, 0, s.length - 1);
}
void reverse(char[] cs, int l, int r) {
while (l < r) {
cs[l] ^= cs[r];
cs[r] ^= cs[l];
cs[l++] ^= cs[r--];
}
}
}
替换空格
请实现一个函数，把字符串?s?中的每个空格替换成"%20"。
题目：剑指 Offer 05. 替换空格 - 力扣（LeetCode）
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c != ' ') sb.append(c);
else sb.append("%20");
}
return sb.toString();
}
反转链表：递归 + 迭代 + 头插法
题目：206. 反转链表 - 力扣（LeetCode）
给你单链表的头节点?head?，请你反转链表，并返回反转后的链表。
双指针：
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
递归：
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
头插法：空间 O(n)
public ListNode reverseList(ListNode head) {
ListNode res = null;
for (ListNode x = head; x != null; x = x.next)
res = new ListNode(x.val, res);
return res;
}
删除链表的倒数第 N 个节点*
题目：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。
快慢指针：
- 快指针先走 n 步，然后和慢指针同时开始走
- 当快指针指向最后一个节点，此时慢指针指向的便是要删除的节点（的前一个节点）
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || head.next == null) return null;
ListNode fast = head, slow = head;
while (n-- > 0) fast = fast.next;
if (fast == null) return head.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
快慢指针 + 虚拟头节点：
一般使用虚拟头节点可以不用处理特殊情况
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode vn = new ListNode(0, head);
ListNode slow = vn, fast = vn;
while (n-- > 0) fast = fast.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return vn.next;
}
递归：
class Solution {
int cur = 0;
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
head.next = removeNthFromEnd(head.next, n);
cur++;
if (cur == n) return head.next;
return head;
}
}
环形链表：快慢指针
题目：141. 环形链表 - 力扣（LeetCode）
给你一个链表的头节点?head?，判断链表中是否有环。
快慢指针：
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
哈希：
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null && !set.contains(head)) {
set.add(head);
head = head.next;
}
return head != null;
}
环形链表 II**
题目：142. 环形链表 II - 力扣（LeetCode）
给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。
快慢指针 判断环 + 找环入口：
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
哈希：
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null && !set.contains(head)) {
set.add(head);
head = head.next;
}
return head;
}
链表相交*
题目：面试题 02.07. 链表相交 - 力扣（LeetCode）
给你两个单链表的头节点?headA?和?headB?，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回?null?。
双指针：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA, curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) {
lenA++;
curA = curA.next;
}
while (curB != null) {
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
if (lenA > lenB) for (int i = 0; i < lenA - lenB; i++) curA = curA.next;
else for (int i = 0; i < lenB - lenA; i++) curB = curB.next;
while (curA != null) {
if (curA == curB) return curA;
curA = curA.next;
curB = curB.next;
}
return curA;
}
巧妙做法：
- a 走完走 b，b 走完走 a，如果有相交点，必然会遇到
- 如果没有相交点，最终会在相遇在
null
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode h1 = headA, h2 = headB;
while (h1 != h2) {
h1 = (h1 == null) ? headB : h1.next;
h2 = (h2 == null) ? headA : h2.next;
}
return h1;
}
哈希：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet<>();
ListNode p = headA;
while (p != null) {
set.add(p);
p = p.next;
}
p = headB;
while (p != null) {
if (set.contains(p)) return p;
p = p.next;
}
return null;
}
三数之和**
题目：15. 三数之和 - 力扣（LeetCode）
给你一个整数数组?nums?，判断是否存在三元组?[nums[i], nums[j], nums[k]]?满足?i != j、i != k?且?j != k?，同时还满足?nums[i] + nums[j] + nums[k] == 0?。请你返回所有和为?0?且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
思路：
- 排序数组
- 定义 i, j, k 三个指针。遍历 i，将问题转化成在 i 之后的数组中寻找
nums[j] = nums[k] = -nusm[i] - 注意寻找同时要去重
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
if (nums[0] > 0 || nums[n - 1] < 0) return res;
for (int i = 0; i < n; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1, target = -nums[i];
while (j < k) {
if (nums[j] + nums[k] < target) j++;
else if (nums[j] + nums[k] > target) k--;
else {
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
while (j < k && nums[j] == nums[j + 1]) j++;
while (j < k && nums[k] == nums[k - 1]) k--;
j++;
k--;
}
}
}
return res;
}
四数之和
题目：18. 四数之和 - 力扣（LeetCode）
给你一个由?n?个整数组成的数组?nums?，和一个目标值?target?。请你找出并返回满足下述全部条件且不重复的四元组?[nums[a], nums[b], nums[c], nums[d]]?（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d?< na、b、c?和?d?互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按?任意顺序?返回答案 。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
if (n < 4) return res;
Arrays.sort(nums);
if (nums[0] > 0 && target <= 0 || nums[n - 1] < 0 && target >= 0) return res;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
int k = j + 1, l = n - 1;
while (k < l) {
int sum = nums[i] + nums[j] + nums[k] + nums[l];
if (sum < target) k++;
else if (sum > target) l--;
else {
res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++;
l--;
}
}
}
}
return res;
}
分割线 -----
无重复字符的最长子串*
题目：3. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串?s?，请你找出其中不含有重复字符的?最长子串?的长度。
双指针：
public int lengthOfLongestSubstring(String s) {
char[] cs = s.toCharArray();
int[] map = new int[128];
int res = 0;
for (int l = 0, r = 0; r < cs.length; r++) {
map[cs[r]]++;
while (map[cs[r]] > 1) map[cs[l++]]--;
res = Math.max(res, r - l + 1);
}
return res;
}
|