sunyiwen / blog Goto Github PK

View Code? Open in Web Editor NEW

0.0 2.0 0.0 49.36 MB

记录日常学习和工作～

leetcode frontend

blog's Introduction

Even's Blog

记录学习日常和工作～

Leetcode

算法模版

归并排序&快速排序

其他

blog's People

Contributors

Watchers

blog's Issues

Intersection Observer API实现模块滚动聚焦

场景

页面在滚动过程中，根据当前视图中展示的模块聚焦到对应的标签上。

版本1（可直接查看优化的版本2）

第一个版本是在微信小程序上实现的，当时的想法就非常的简单粗暴，也正因为如此，该页面的性能非常的差。基本的实现方式如下：

获取每个模块在当前页面的尺寸
监听页面的onPageScroll事件，在回调事件中遍历每个模块的的尺寸和位置配合scrollTop进行计算，得到一个合适的聚焦索引
针对模块的高度是否大于可视区实现不同的计算，有大量的分支逻辑
查看了微信官方的渲染性能优化，不禁打了个寒颤，这简直就是在性能雷区上蹦迪😱～

版本2

这个页面本质还是一个长列表，于是就靠着虚拟列表的方向探索，但是由于该页面交互还存在着点击某个标签定位到具体模块的交互，虚拟列表在快速滚动的时候存在白屏现象，一开始的点击跳转也会因为位置不准确导致定位不准。虚拟列表实现上使用的Intersection Observer API吸引了我的目光。而微信API中也有对应的实现，果断开始尝试。

Intersection Observer API 存在的问题

初始化Observer的时候需要设置相交阈值，该相交阈值指的是相交区域 / 目标元素，而我期望该值对应的是相交区域 / 参照元素。若设置了一个相对比较大的阈值，若目标元素的尺寸是参照元素的几十倍的时候，得到的值会无限接近于0，也就无法触发相应的回调
列表中单个模块的高度参差不齐，一个可视区中可以存在多个模块，也可能无法容纳一个模块

如上图所示，模块0， 1， 2 都会触发相交回调，但是聚焦索引不是2，而是0。

解决

针对第一个问题，若把阈值列表中的值分散的太细，则触发的次数过多，没有必要。只监听模块进入视图区域和离开视图区域的情况。默认的Observer配置就可以达到这个效果。

针对问题二，若遇到上述情形。0，1，2三个模块都触发了，但是索引只聚焦在0处。至于什么时候聚焦到1处，则是0退出区域的时候。而队列的数据结构正好可以模拟这种状态。第一个元素离开的时候，从队列中把队头的数据取出。每次取队头的元素作为当前的聚焦索引。

if (isIntersecting) { 
  queue.push(id); // 模块进入
} else {
  queue.shift(); // 模块离开
}

特殊情况处理

若列表仅朝着单一的方向且不存在来回滑动的时候，以上的队列方式可以正常操作。若页面存在来回滚动的情况，需要增加一步特殊处理。

上图中，页面滚到底的时候，此时队列中有3， 4。

此时若向上滚动，4（最后一个模块）离开区域就需要把队尾元素弹出，显然此时队尾元素是3，清除后此时的模块依旧聚焦在4。针对这种情况，将队列中的数据逆置，再进行队尾元素的弹出操作。同理，向上划到顶部之后再向下滚动也是这种情况。

if (entry.isIntersecting) {
  queue.push(id);
} else {
  if (
    queue.length > 0 &&
    (activeKey == 0 || activeKey == lastIndex) &&
    (queue[queue.length - 1] == activeKey)
  ) {
    queue.reverse();
  }
  queue.shift();
}

若没有滑动到底部或者顶部的时候改变滚动属性，此时也要相应的调整队列中的顺序，始终保持队列中数据递增或者递减。

if (entry.isIntersecting) {
  if (queue.length > 0 && Math.abs(id - queue[queue.length - 1]) !== 1) {
    queue.reverse();
  }
  queue.push(id);
} else {
  if (
    queue.length > 0 &&
    (activeKey == 0 || activeKey == lastIndex) &&
    queue[queue.length - 1] == activeKey
  ) {
    queue.reverse();
  }
  queue.shift();
}

插入过程中限制来相邻两个数的差值的绝对值为1并不能保证队列中没有数组重复，引入Set数据结构保证数据的唯一性，可以改写为：

if (isIntersecting) {
  if (!queueSet.has(id)) {
    if (queue.length > 0 && Math.abs(id - queue[queue.length - 1]) !== 1) {
      queue.reverse();
    }
    queue.push(id);
    queueSet.add(id);
  }
} else {
  if (
    queue.length > 0 &&
    (activeKey.value == 0 || activeKey.value == lastIndex) &&
    queue[queue.length - 1] == activeKey.value
  ) {
    queue.reverse();
  }
  if (id == queue[0]) {
    queueSet.delete(queue[0]);
    queue.shift();
  }
}

队列中的数据维护需要保证以下几点：

数据唯一
递增/递减（始终保持）

交互优化

如上图所示，划到底部的时候，队列中的第一个元素应该是3，若按照此种方式，就永远没有机会聚焦到模块4上，针对最后一个模块，若队列中的最后一个元素是最后一个模块，则直接用该模块作为聚焦模块。底部向上回归到顶部的时候同理；

if (queue.length > 0) {
  if (queue[queue.length - 1] == 0 || queue[queue.length - 1] == lastIndex) {
    activeKey.value = queue[queue.length - 1];
  } else {
    activeKey.value = queue[0];
  }
}

Demo代码

https://github.com/SunYiwen/blog/blob/main/examples/intersection-observer-demo/src/App.vue

leetcode-BiNode

BiNode

链接：https://leetcode-cn.com/problems/binode-lcci/

二叉搜索树

若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
任意结点的左、右子树也分别为二叉搜索树。

测试样例

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

分析

根据输入的值来构建整棵二叉搜索树：

由二叉搜索树的特点可以分析出通过中序遍历能够获得一个非递减的序列，即前一个节点的值小于等于后面一个节点的值。而题目中要求转换的单向链表的顺序也就是中序遍历的顺序。要求改造后的链表节点：

node → left = NULL;
node → right = nextNode;

按照中序遍历的顺序，以上图为例，可以看到值为1的节点的right应该指向值为2的节点，而值为3的节点的right应该指向值为4的节点。

题目中给出的节点root指向的是树的根节点，而最后转换的单向链表的节点应该指向的是中序遍历中的第一个节点，也就是图中值为0的节点。

步骤

STEP1：对整棵树进行中序遍历

void dfs(TreeNode *root) {
	if (root != NULL) {
		dfs(root->left);
		dfs(root->right);
	}
}

STEP2: 在中序遍历的基础上改变节点left和right的指向。增加全局的pre来保存中序关系中的前一个节点。同时需要获取第一个节点作为单向链表的头节点指向。

void dfs(TreeNode *root) {
        if (root != NULL) {
            dfs(root->left);
            root->left = NULL;
            if (pre == NULL) {
                ans = root;
            } else {
                pre->right = root;
            }
            pre = root;
            dfs(root->right);
        }
    }

Code

class Solution {
public:
    vector<TreeNode*> v;
    TreeNode *pre, *ans;

    TreeNode* convertBiNode(TreeNode* root) {
        if (root == NULL) {
            return root;
        }

        dfs(root);
        return ans;
    }

    void dfs(TreeNode *root) {
        if (root != NULL) {
            dfs(root->left);
            root->left = NULL;
            if (pre == NULL) {
                ans = root;
            } else {
                pre->right = root;
            }
            pre = root;
            dfs(root->right);
        }
    }
};

Hash History 模式

1、hash模式在url的外观上会携带 # 符号，对比启用hash模式和history模式的情况下访问works路径：

2、兼容性（具体的兼容性差异还未找到明确的）
History API 的浏览器兼容版本

3、hash值不会携带在url上向服务器发送请求

在hash和history模式下同时在url上访问works路径，可以看到浏览器实际发送的请求url是不同的。

当服务器没有覆盖所有的路由时，即使用户随意更改一个服务器没有支持的url，服务器也不会返回404，因为该不存在的路由根本就不会传递到服务器。

TwoSum

链接：https://leetcode-cn.com/problems/two-sum/

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

分析

看到题目，第一感觉就是利用两层循环就可以得到一个O(n^2)时间复杂度的解法，若是想要得到一个O(n)时间复杂度的解法就可以想到使用map。通过在map中以数字的值作为key，在数组中的索引作为value来进行存储。可以在一次遍历的过程中验证之前存储的map中能否找到对应的key。

Code

vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        vector<int> ans;
        for (int i=0; i<nums.size(); i++) {
            map<int,int>::iterator find = m.find(target - nums[i]);

            if (find != m.end()) {
                ans.push_back(find->second);
                ans.push_back(i);
                return ans;
            }

            m.insert(pair<int, int>(nums[i], i));
        }

        ans.push_back(-1);
        ans.push_back(-1);
        
        return ans;
}

相交链表

链接： https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

分析

这是一道leetcode标记为简单的题目，题目要求找到两条链表中相交的节点，乍一看若是不考虑时间复杂度和空间复杂度，直接利用两层循环遍历或者增加一个set就可以完成。但是若是将时间复杂度限制在O(m+n)，额外使用O(1)内存的情况下就至少不是一下子就可以解决了。

我的第一想法是，将两个指针均从两条链表的头节点开始向后移动，但若是两条链表的长度不一样，则再无相见的可能。开头不行，那就看看结尾，我们可以找到一个非常明显的规律，若是我们可以从链表的尾节点处往前遍历，那么就一定可以在线性的时间内找到那个节点。但是我们既不能改变现有的结构，也不能使用额外过多的空间。

为了让两个指针前进的步调一致，那么就要让节点多的那个指针先往前走几步，这样两个指针在接下来的路途中就可以保持步调一致了。

步骤

STEP1: 找到两条链表之间的数量差异

int n = 0, m = 0;
ListNode *p1, *p2;

p1 = headA;
p2 = headB;

while(p1 != NULL) {
        p1 = p1->next;
        n++;
}

while(p2 != NULL) {
        p2 = p2->next;
        m++;
}

int step = fabs(n-m);

STEP2: 让节点多的先走几步

if (n - m > 0) {
    while (step) {
      headA = headA->next;
      step--;
    }
  } else if (n - m < 0) {
    while (step) {
      headB = headB->next;
      step--;
    }
  }

STEP3: 两个指针同步向前走，判断是否一致

  while (headA != NULL) {
    if (headA == headB) {
      return headA;
    } else {
      headA = headA->next;
      headB = headB->next;
    }
  }

Code

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  if (headA == NULL || headB == NULL) {
    return NULL;
  }

  int n = 0, m = 0;
  ListNode *p1, *p2;

  p1 = headA;
  p2 = headB;

  while (p1 != NULL) {
    p1 = p1->next;
    n++;
  }

  while (p2 != NULL) {
    p2 = p2->next;
    m++;
  }

  int step = fabs(n - m);

  if (n - m > 0) {
    while (step) {
      headA = headA->next;
      step--;
    }
  } else if (n - m < 0) {
    while (step) {
      headB = headB->next;
      step--;
    }
  }

  while (headA != NULL) {
    if (headA == headB) {
      return headA;
    } else {
      headA = headA->next;
      headB = headB->next;
    }
  }

  return NULL;
}

归并排序&快速排序

归并排序

void merge(vector<int> &v, int l1, int r1, int l2, int r2) {
    vector<int> temp;
    int i = l1, j = l2;
    while(i <= r1 && j <= r2) {
        if (v[i] <= v[j]) {
            temp.push_back(v[i++]);
        } else {
            temp.push_back(v[j++]);
        }
    }
    
    while(i <= r1) {
        temp.push_back(v[i++]);
    }
    
    while(j <= r2) {
        temp.push_back(v[j++]);
    }
    
    int pos = l1;
    for(int k=0; k<temp.size(); k++) {
        v[pos++] = temp[k];
    }

}

void merge_sort(vector<int> &v, int start, int end) {
    if (start >= end) {
        return;
    }
    
    int mid = (start + end) >> 1;
    merge_sort(v,start, mid);
    merge_sort(v, mid+1, end);
    merge(v, start, mid, mid+1, end);
}

快速排序

void quick_sort(vector<int> &v, int start, int end) {
    if (start >= end) {
        return;
    }
    
    int l = start, r = end;
    while(l < r) {
        while(l < r && v[r] >= v[start]) {
            r--;
        }
        
        while(l < r && v[l] <= v[start]) {
            l++;
        }
        
        if (l < r) {
            swap(v[l], v[r]);
        }
    }
    
    swap(v[start], v[l]);
    quick_sort(v, start, l-1);
    quick_sort(v, l+1, end);
}

sunyiwen / blog Goto Github PK

blog's Introduction

Even's Blog

Leetcode

算法模版

其他

blog's People

Contributors

Watchers

blog's Issues

Intersection Observer API实现模块滚动聚焦

场景

版本1（可直接查看优化的版本2）

版本2

Intersection Observer API 存在的问题

解决

特殊情况处理

交互优化

Demo代码

BiNode

二叉搜索树

测试样例

分析

步骤

STEP1：对整棵树进行中序遍历

STEP2: 在中序遍历的基础上改变节点left和right的指向。增加全局的pre来保存中序关系中的前一个节点。同时需要获取第一个节点作为单向链表的头节点指向。

Code

TwoSum

题目描述

分析

Code

相交链表

分析

步骤

STEP1: 找到两条链表之间的数量差异

STEP2: 让节点多的先走几步

STEP3: 两个指针同步向前走，判断是否一致

Code

归并排序

快速排序

Recommend Projects

Recommend Topics

Recommend Org