![1.png](http://static.itsharecircle.com/231218/f3762dc802ff57be143d2b6bfeac0bd1.png)
前端高手特训 从0到1带你手写一个微信小程序底层框架,今天就带着大家从0到深入学习小程序框架底层原理,无论你是一位新手,还是一位有经验的开发者,能够自研一套小程序底层框架,都是你突破技术瓶颈有效途径。
今天就由我带领大家从架构设计 ,原理剖析,再到源码的实现,一步步地实战构建一个完整的微信小程序底层框架,让你深度掌握小程序双线程原理,助力你具备把握最佳机会的能力和提升获取心仪Offer的成功率,成为一个真正有实力的技术人才 。
小程序使用的是Exparser组件模型,Exparser组件模型与Web Components中的shadow DOM高度相似,微信为什么使用自定义组件框架,而不使用Web Components呢?主要还是出于安全考虑,并且方便管控。既然Exparser组件框架与shadow DOM高度相似,那么我们首先来了解一下shadow DOM。
本题比较特殊,我们要删除目前所在的节点,而没有它的前趋节点。题目已经告诉我们删除的不是尾节点,我们可以拷贝它的后继节点内容到它本身的位置。这样链表里有两个内容相同的节点——即它的后继节点出现了两次,我们把它的后继节点删除即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
}
思路分析:滑动窗口——和我们之前讲的链表找环问题类似。快指针每次走两步,慢指针每次走一步,如此快指针移动到链表末尾的时候,慢指针刚好移动到中间。注意细节,链表长度的奇偶性,以及如何判断末尾等。
代码
/**
* 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 middleNode(ListNode head) {
for (ListNode temp = head; temp != null && temp.next != null; temp = temp.next.next, head = head.next)
;
return head;
}
}
思路分析:
可以在push时进行反向操作。
class MyStack {
private Queue<Integer>[] q;
private int getInd() {
return q[0].isEmpty() ? 1 : 0;
}
/** Initialize your data structure here. */
public MyStack() {
q = new Queue[2];
for (int i = 0; i < 2; ++i) {
q[i] = new LinkedList<>();
}
}
/** Push element x onto stack. */
public void push(int x) {
q[getInd()].add(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
final int ind = getInd();
for (; q[ind].size() > 1; q[ind ^ 1].add(q[ind].poll()))
;
return q[ind].poll();
}
/** Get the top element. */
public int top() {
int r = pop();
push(r);
return r;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q[0].isEmpty() && q[1].isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
思路分析:把0和n加到端点里,得到数组c,排序后任意一段木棍可以用c中两个元素表示。定义dp[i][j]表示从端点c[i]到c[j]的木棍都切好后的最小代价。
dp[i][j] = 0 对于j <= i + 1
dp[i][j] = min(dp[i][k] + dp[k][j]) + c[j] - c[i] i < k < j 枚举切点k,分别切两段。
class Solution {
public int minCost(int n, int[] cuts) {
int[] c = new int[cuts.length + 2];
c[1] = n;
System.arraycopy(cuts, 0, c, 2, cuts.length);
Arrays.sort(c);
final int m = c.length;
int[][] dp = new int[m][m];
for (int d = 2; d < m; ++d) {
for (int i = 0; i + d < m; ++i) {
final int j = i + d;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; ++k) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
dp[i][j] += c[j] - c[i];
}
}
return dp[0][m - 1];
}
}
思路分析:设dp[i][j]表示从s的长度为i的前缀中删掉不超过k个字符最终得到的最短压缩串长度。
dp[0][j] = 0, 空串。
dp[i][j] = min(dp[i - 1][j - 1], dp[p][j - x] + (y个s.charAt(i - 1)的压缩长度)) 其中p < i, 设c = s.charAt(i - 1), x是s.charAt(p…i)中非c出现的次数,要删掉它们, 而y是其中c出现的次数,要全部保留。实际上我们枚举了目前压缩串最后一部分中删掉c和保留y个c的全部可能性。
class Solution {
private int getLen(int x) {
if (x == 1) {
return 1;
}
if (x < 10) {
return 2;
}
if (x < 100) {
return 3;
}
return 4;
}
public int getLengthOfOptimalCompression(String s, int k) {
final int n = s.length();
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; ++i) {
final char c = s.charAt(i - 1);
for (int j = 0; j <= k; ++j) {
dp[i][j] = j > 0 ? dp[i - 1][j - 1] : Integer.MAX_VALUE;
for (int p = i - 1, num = 0, t = j; p >= 0; --p) {
if (s.charAt(p) == c) {
++num;
} else if (--t < 0) {
break;
}
dp[i][j] = Math.min(dp[i][j], getLen(num) + dp[p][t]);
}
}
}
return dp[n][k];
}
}
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码`
- 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传