Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

算法存档 #88

Open
yihong0618 opened this issue Dec 11, 2019 · 3 comments
Open

算法存档 #88

yihong0618 opened this issue Dec 11, 2019 · 3 comments
Labels
技术文章 技术文章

Comments

@yihong0618
Copy link
Owner

yihong0618 commented Dec 11, 2019

深度优先用栈,广度优先用队列
图的广度优先和深度优先遍历(BFS和DFS)

@yihong0618 yihong0618 added the 技术文章 技术文章 label Dec 11, 2019
@yihong0618
Copy link
Owner Author

二叉搜索树

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。
  5. ES6的实现

@yihong0618
Copy link
Owner Author

leetcode 453
这题其实是道数学题,想了好久没想到,值得记录下:
已知:数列nums,初始和s0,长度n,最小的数为m
假设移动k步

  • 每移动一步,n-1个数会被+1,则最终和s = s0 +(n-1) x k
  • 平均数为 s/n
  • 最小数每次移动都被+1,因此有:k =s/n -m
  • 即:(s0 +(n-1) x k)/n -m =k
  • 求得: k = s0 - m x n

@yihong0618
Copy link
Owner Author

今天刷LeetCode 207号题,发现毫无思路,应该是第一道“图”相关的题,记录一下。
根据《算法概论》中对有向无环图的讲解,判断一个有向图是否有环,有两个算法:

拓扑排序

即找出该图的一个线性序列,使得需要事先完成的事件总排在之后才能完成的事件之前。如果能找到这样一个线性序列,则该图是一个有向无环图

DFS

遍历图中的所有点,从i点出发开始DFS,如果在DFS的不断深入过程中又回到了该点,则说明图中存在回路。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
技术文章 技术文章
Projects
None yet
Development

No branches or pull requests

1 participant