跳转至

博客

  • 分类于 札记
  • 需要 2 分钟阅读时间

Istio 架构

Istio 就是 Service Mesh2 架构的一种实现，服务之间的通信（比如这里的 Service A 访问 Service B）会通过代理（默认是 Envoy1）来进行。

  • 分类于 算法
  • 需要 1 分钟阅读时间

关于算法中的问题总结

在刷题的过程中遇到了一些经典问题和经典解法，我觉得很有必要对其进行归纳与总结，避免未来遇到同样的问题捉急。

  • 分类于 算法
  • 需要 3 分钟阅读时间

递归/回溯

递归是计算机科学中的一个重要概念。它是许多其他算法和数据结构的基础。然而，对于许多初学者来说，掌握它可能是一件非常棘手的事情。

每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题成为一个不可以拆分的、可以直接求解的最简单问题。

为了确保递归函数不会导致无限循环，它需要包含：

一个简单的基本案例（basic case）（或一些案例）， 能够不使用递归来产生答案的终止方案。 一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。 注意，函数可能会有多个位置进行自我调用（这是分治算法）。

  • 分类于 算法
  • 需要 4 分钟阅读时间

深度优先搜索

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次.

因发明「深度优先搜索算法」，约翰 · 霍普克洛夫特与罗伯特 · 塔扬在1986年共同获得计算机领域的最高奖：图灵奖。

  • 分类于 算法
  • 需要 7 分钟阅读时间

广度优先搜索

广度优先搜索算法（Breadth-First Search，缩写为 BFS），又称为宽度优先搜索，是一种图形搜索算法。简单的说，BFS 是从根结点开始，沿着树的宽度遍历树的结点。如果所有结点均被访问，则算法中止。

  • 分类于 算法
  • 需要 6 分钟阅读时间

双指针

双指针从广义上来说，是指用两个变量在线性结构上遍历而解决的问题。狭义上说，

  • 对于数组，指两个变量在数组上相向移动解决的问题；

  • 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题。

  • 分类于 算法
  • 需要 3 分钟阅读时间

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，可以在数据规模的对数时间复杂度内完成查找。

二分查找可以应用于数组，是因为数组具有有随机访问的特点，并且数组是有序的。

二分查找体现的数学思想是「减而治之」，可以通过当前看到的中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。

二分查找问题也是面试中经常考到的问题，虽然它的思想很简单，但写好二分查找算法并不是一件容易的事情。

  • 分类于 算法
  • 需要 5 分钟阅读时间

滑动窗口

滑动窗口指的是这样一类问题的求解方法，在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。

使用滑动窗口解决的问题通常是暴力解法的优化，掌握这一类问题最好的办法就是练习，然后思考清楚为什么可以使用滑动窗口。