算法笔记
新题
这题我一开始的思路完全按照了旋转数组去做，实际上没有必要
链表的结构不需要像数组一样，没有数组的覆盖问题，只需要找到几个关键的节点，断开，在连接就好
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) return head;
ListNode cur = head;
int size = 0;
ListNode rEnd = null;
while (cur != null) {
if (cur.next == null) {
rEnd = cur;
}
cur = cur.next;
size++;
}
k %= size;
if (k == 0) return head;
ListNode lHead = head;
ListNode lEnd = lHead;
ListNode rightH = head;
for (int i = 0; i < size - k; i++) {
rightH = rightH.next;
if (i == size - k - 2) {
lEnd = rightH;
}
}
lEnd.next = null;
head = rightH;
rEnd.next = lHead;
return head;
}
}
|
核心问题就是找到4个关键节点，要注意节点的初始化，4个关键节点，找相邻中考前的两个，可以避免循环过程中因为i的原因导致的初始化失败
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == right) return head;
ListNode nHead = new ListNode(-1, head);
ListNode cur = nHead;
head = nHead;
ListNode midBeginLeft = head;
ListNode midBegin = head;
ListNode midEnd = head;
ListNode midEndRight = head;
for (int i = 0; i < right; i++) {
cur = cur.next;
if (i == left - 2) {
midBeginLeft = cur;
} else if (i == right - 1) {
midEnd = cur;
}
}
midBegin = midBeginLeft.next;
midEndRight = midEnd.next;
ListNode pre = null;
cur = midBegin;
while (cur != null && cur != midEndRight) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
midBeginLeft.next = midEnd;
midBegin.next = midEndRight;
return head.next;
}
}
|
比较暴力的做法，直接录下所有的节点，然后依次处理
class Solution {
public void reorderList(ListNode head) {
Map<Integer, ListNode> map = new HashMap<>();
int index = 0;
ListNode cur = head;
while (cur != null) {
map.put(index++, cur);
cur = cur.next;
}
int size = index;
int n = size - 1;
ListNode nHead = new ListNode(-1, head);
head = nHead;
cur = head;
for (int i = 0; i < size / 2; i++) {
cur.next = map.get(i);
cur.next.next = map.get(n - i);
cur = cur.next.next;
}
if (size % 2 != 0) {
cur.next = map.get(size / 2);
cur.next.next = null;
} else {
cur.next = null;
}
}
}
|
暴力做法优化 双指针求中间节点，反转后半段，合并两个链表
class Solution {
public void reorderList(ListNode head) {
ListNode mid = getMidAndSlice(head);
ListNode l1 = head;
ListNode l2 = mid;
l2 = reverse(l2);
mergeTwoList(l1, l2);
}
public ListNode getMidAndSlice(ListNode head) {
ListNode pre = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if (fast == null) {
pre.next = null;
return slow;
} else {
pre = slow;
slow = slow.next;
pre.next = null;
return slow;
}
}
public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode next = null;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public ListNode mergeTwoList(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
while (l1 != null && l2 != null) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
while (l1 != null) {
cur.next = l1;
l1 = l1.next;
}
return head.next;
}
}
|
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
|
这题不错，好好记一记
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offerFirst(root);
boolean flag = true;
while (!queue.isEmpty()) {
List<Integer> temp = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
if (flag) {
TreeNode cur = queue.pollLast();
if (cur.left != null) {
queue.offerFirst(cur.left);
}
if (cur.right != null) {
queue.offerFirst(cur.right);
}
temp.add(cur.val);
} else {
TreeNode cur = queue.pollFirst();
if (cur.right != null) {
queue.offerLast(cur.right);
}
if (cur.left != null) {
queue.offerLast(cur.left);
}
temp.add(cur.val);
}
}
ans.add(new ArrayList<>(temp));
flag = !flag;
}
return ans;
}
}
|
旧题
没什么好说的，最基本的模板题，注意循环的条件，注意addition的使用
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int addition = 0;
ListNode head = new ListNode(-1);
ListNode cur = head;
while (l1 != null || l2 != null) {
if (l1 != null && l2 != null) {
int sum = (l1.val + l2.val + addition) % 10;
addition = (l1.val + l2.val + addition) / 10;
cur.next = new ListNode(sum);
l1 = l1.next;
l2 = l2.next;
}
else if (l1 == null && l2 != null) {
int sum = (l2.val + addition) % 10;
addition = (l2.val + addition) / 10;
cur.next = new ListNode(sum);
l2 = l2.next;
}
else if (l1 != null && l2 == null) {
int sum = (l1.val + addition) % 10;
addition = (l1.val + addition) / 10;
cur.next = new ListNode(sum);
l1 = l1.next;
}
cur = cur.next;
}
if (addition != 0) {
cur.next = new ListNode(addition);
}
return head.next;
}
}
|
美团面试考过，注意循环的条件，注意如果存在相同的元素，那么就需要消除，如果不存在，就else到下一个，到下一个节点的操作不是公共的操作
class Solution {
public ListNode deleteDuplicates(ListNode head) {
head = new ListNode(-1, head);
ListNode cur = head;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int val = cur.next.val;
while (cur.next != null && cur.next.val == val) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return head.next;
}
}
|
熟能生巧
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode nHead = new ListNode(-1);
nHead.next = head;
head = nHead;
ListNode pre = head;
ListNode cur = head.next;
while (cur != null && cur.next != null) {
ListNode next = cur.next;
cur.next = next.next;
next.next = cur;
pre.next = next;
pre = cur;
cur = cur.next;
}
return head.next;
}
}
|
模板题
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode cur = headA;
int sizeA = 0;
while (cur != null) {
sizeA++;
cur = cur.next;
}
cur = headB;
int sizeB = 0;
while (cur != null) {
sizeB++;
cur = cur.next;
}
if (sizeA > sizeB) {
for (int i = 0; i < sizeA - sizeB; i++) {
headA = headA.next;
}
} else {
for (int i = 0; i < sizeB - sizeA; i++) {
headB = headB.next;
}
}
while (headA != null && headB != null) {
if (headA == headB) return headA;
headA = headA.next;
headB = headB.next;
}
return null;
}
}
|
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p == root || q == root || root == null) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right != null) return right;
else if (right == null && left != null) return left;
if (left != null && right != null) return root;
return null;
}
}
|
BST的中序遍历是从小到大的
class Solution {
int count;
int ans;
public int kthSmallest(TreeNode root, int k) {
count = k;
find(root);
return ans;
}
public void find(TreeNode root) {
if (root == null) return;
find(root.left);
count--;
if (count == 0) {
ans = root.val;
return;
}
find(root.right);
}
}
|
class Solution {
int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) return 0;
getMaxPath(root);
return ans;
}
public int getMaxPath(TreeNode root) {
if (root == null) return 0;
int leftPath = getMaxPath(root.left);
int rightPath = getMaxPath(root.right);
leftPath = Math.max(0, leftPath);
rightPath = Math.max(0, rightPath);
ans = Math.max(ans, leftPath + rightPath + root.val);
return Math.max(leftPath, rightPath) + root.val;
}
}
|
