Algorithm problem notes
Source: cattle from 🔗 www.nowcoder.com/activity/oj…
Q1: Rebuild binary trees
Ideas:
To reconstruct a binary tree, you must have a middle order + pre-order or a middle order + post-order. Pre-order + post-order is not possible. And it’s usually recursive.
To rebuild the binary tree according to the preorder + middle order, the value of the root node needs to be determined first. According to the definition of pre-traversal, the first value of the pre-traversal result is the value of the root node pre[0] == root.val. Then, the middle-order traversal can be divided into two parts by idX, one is the middle-order traversal result of the left subtree (in[0]~in[IDX-1]), and the other is the middle-order traversal result of the right subtree (in[IDx +1]~in[len-1]). Then recurse this process in the left and right subtrees, Java code implementation reference is as follows:
import java.util.*;
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int len = pre.length;
if(len == 0) {
return null;
}
int rootNodeVal = pre[0];
TreeNode res = new TreeNode(rootNodeVal);
int idx = 0;
for(; idx<len; idx++) {if(in[idx] == rootNodeVal) {
break;
}
}
res.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1.1+idx),
Arrays.copyOfRange(in,0,idx));
res.right = reConstructBinaryTree(Arrays.copyOfRange(pre,1+idx,len),
Arrays.copyOfRange(in,idx+1,len));
returnres; }}Copy the codeQ2: List flipping
This is an advanced version of list flipping, flipping in groups of K. withLc25 2 (https://leetcode-cn.com/problems/reverse-nodes-in-k-group/) 
- Walk through the list to get the length, and then calculate how many groups there are
- Save one node for each group
listVariable, and then iterate from back to frontFlip operation. - Then ribbon the variable to the last node of the previous group
prePoints to thelistThe last node of, and thenpreCopy thelistThe last node of the. - Loop step2 until all components are finished, then return
code1
import java.util.*;
/* * public class ListNode { * int val; * ListNode next = null; *} * /
public class Solution {
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
if (k == 1 || head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
// Calculate how many groups to rotate
int cnt = 0;
ListNode cur = head;
while(cur! =null) {
cur = cur.next;
cnt++;
}
cur = head;
int group = cnt/k;
//
while (group-->0) {
List<ListNode> l = new ArrayList<>();
for (int i=0; i<k; i++){ l.add(cur); cur = cur.next; }for (int i=l.size()-1; i>0; i--){ l.get(i).next = l.get(i-1);
}
pre.next = l.get(l.size()-1);
l.get(0).next = cur;
pre = l.get(0);
}
returndummy.next; }}Copy the codeCode2 doesn’t need to save the list, just flip it bitwise
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
dummy.next = head;
int length = 0;
while(head ! =null) {
length++;
head = head.next;
}
head = dummy.next;
for(int i = 0; i < length / k; i++) {
for(int j = 0; j < k - 1; j++) {
next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
prev = curr;
curr = prev.next;
}
returndummy.next; }}Copy the codeQ3: Determine whether the linked list has rings
Typical fast and slow pointer problem
/** * 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) {
if (head == null || head.next == null) {return false;
}
ListNode slow=head,quick=head.next;
while(quick ! =null) {
if (slow == quick) return true;
slow = slow.next;
quick = quick.next;
if(quick ! =null) {
quick = quick.next;
}else return false;
}
return false; }}Copy the codeQ4 Determines whether the binary tree is symmetric
In a typical tree 🌲 recursive problem, the necessary and sufficient condition for complete symmetry is that the current two nodes have the same value and the left and right children are symmetric respectively.
import java.util.*;
/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; *} * /
public class Solution {
public boolean isSymmetric (TreeNode root) {
// write code here
if (root == null) {
return true;
}
return helper(root.left,root.right);
}
private boolean helper(TreeNode p1,TreeNode p2) {
if (p1 == null || p2 == null) {
return p1 == null && p2 == null;
}
if (p1.val == p2.val) {
return helper(p1.left,p2.right)&&helper(p1.right,p2.left);
}else {
return false; }}}Copy the codeQ5 frog 🐸 jump step problem
dpProblem, the current position can only jump up from the current step -1, or two steps -2, so the state transition equation can be:
dp[n] = dp[n-1]+dp[n-2]
Then the code is as follows:
public class Solution {
public int JumpFloor(int target) {
if (target <= 2) return target;
int[] dp = new int[target+1];
dp[1] = 1;
dp[2] = 2;
for (int i=3; i<=target; i++) { dp[i] = dp[i-1]+dp[i-2];
}
returndp[target]; }}Copy the codeQ6 LRU cache
The cache is a structure for fast access to hot data and the more data the better, but the cache is in memory and takes up precious storage resources. Therefore, a reasonable cache invalidation policy should be adopted. LRU cache is a common cache invalidation policy (LRU can be used as a cache invalidation policy in Redis).
import java.util.*;
public class Solution {
/**
* lru design
* @paramOperators int The OPS *@paramK int The integer the k *@returnInt One-dimensional array */
/**
* lru design
* @paramOperators int The OPS *@paramK int The integer the k *@returnInt One-dimensional array */
public int[] LRU (int[][] operators, int k) {
// write code here
LRUADT lru = new LRUADT(k);
List<Integer> res = new ArrayList<>();
for (int[] op : operators) {
if (op[0] = =1) {
lru.set(op[1],op[2]);
}else {
res.add(lru.get(op[1])); }}int[] r = new int[res.size()];
for (int i=0; i<r.length; i++) { r[i] = res.get(i); }return r;
}
class LRUADT {
Map<Integer,Node> cache;
Node head,tail;
int capacity;
class Node {
int key;
int val;
Node next,prev;
Node(int key,int val) {
this.key = key;
this.val = val;
}
}
LRUADT(int capacity) {
cache = new HashMap<>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
this.capacity = capacity;
}
int get(int key) {
if (cache.containsKey(key)) {
// Set it to the earliest
rotateFirst(key);
return cache.get(key).val;
}else {
return -1; }}void set(int key,int val) {
if (cache.containsKey(key)){
Node n = cache.get(key);
delNode(n);
n.val = val;
addFirst(n);
}else if (cache.size() < capacity) {
Node n = new Node(key,val);
addFirst(n);
cache.put(key,n);
}else {
// Delete the last node
Node del = tail.prev;
delNode(del);
cache.remove(del.key);
Node n = newNode(key,val); addFirst(n); cache.put(key,n); }}void rotateFirst(int key) {
Node cur = cache.get(key);
if (cur.prev == head) {
return;
}
// Delete nodes from the list
delNode(cur);
// Node is added to the front
addFirst(cur);
}
void addFirst(Node n){
Node first = head.next;
head.next = n;
n.prev = head;
n.next = first;
first.prev = n;
}
void delNode(Node n) {
Node prev = n.prev;
Node nxt = n.next;
n.prev = null;
n.next = null; prev.next = nxt; nxt.prev = prev; }}}Copy the codeQ7 merge ordered linked lists
Walk through both lists, adding small nodes to the result each time.
import java.util.*;
/* * public class ListNode { * int val; * ListNode next = null; *} * /
public class Solution {
/ * * * *@paramL1 ListNode class *@paramL2 ListNode class *@returnListNode class * /
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l1 ! =null&& l2 ! =null) {
if (l1.val <= l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
}else{ cur.next = l2; cur = cur.next; l2 = l2.next; }}if(l1 ! =null) {
cur.next = l1;
}else if(l2 ! =null) {
cur.next = l2;
}
returndummy.next; }}Copy the codeQ8 linked list central entry node
C) lc classical algorithm d) Lc classical algorithmfloydThe cognition of circle detection algorithm.
floydRing detection algorithm refer to the following link:
Ref: www.cnblogs.com/xudong-bupt…
The specific code is as follows:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
/** * Floyd ring detection algorithm *@param head
* @return* /
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode quick = head;
while (true) {
slow = slow.next;
quick = quick.next;
if (quick == null) return null;
quick = quick.next;
if (quick == null) return null;
if (slow == quick) break;
}
/ / meet
slow = head;
while(slow ! = quick) { slow = slow.next; quick = quick.next; }returnslow; }}Copy the codeQ9 large number addition
Superlarge number addition and subtraction by string is a classic algorithm problem. Simply add the string from right to left and save the carry value prev
/** * The class name, method name and parameter name have been specified, do not modify, directly return the specified value of the method to calculate the sum of the two numbers *@paramS string The string represents the first integer *@paramT string The string represents the second integer *@returnString The character string */
public String solve (String s, String t) {
// write code here
int len = Math.max(s.length(),t.length());
char[] res = new char[len+1];
int prev = 0;
for (int i=0; i<res.length; i++){int a1=0,a2=0;
if (i < s.length()) {
a1 = s.charAt(s.length()-1-i)-'0';
}
if (i < t.length()) {
a2 = t.charAt(t.length()-1-i)-'0';
}
int v = a1+a2+prev;
if (v >= 10) {
res[res.length-1-i] = (char)((v%10) +'0');
prev = v/10;
}else {
res[res.length-1-i] = (char)(v+'0');
prev = 0; }}if (res[0] = ='0') {return String.valueOf(Arrays.copyOfRange(res,1,res.length));
}else {
returnString.valueOf(res); }}Copy the codeQ10 merges K sorted linked lists
The problem with theQ7 merge ordered linked listsThe core is similar. So we just iteratelistsEach of theListNodeThen find the smallest follow-up answer in the can.
import java.util.*;
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
lists.removeIf(Objects::isNull);
while (lists.size() > 1) {// find min
int idx = -1;
int min = Integer.MAX_VALUE;
for (int i=0; i<lists.size(); i++) { ListNode c = lists.get(i);if(c.val < min) { idx = i; min = c.val; }}// min next
cur.next = lists.get(idx);
cur = cur.next;
ListNode c = lists.get(idx);
if (c.next == null) {
lists.remove(idx);
}else{ lists.set(idx,c.next); }}if (lists.size() == 1) {
cur.next = lists.get(0);
}
returndummy.next; }}Copy the codeconclusion
The above is the ox guest online algorithm question Q1~Q10, after continue to update all the question solution ~