Kin.的博客

今日安排 看 图解TCP_IP 第 1 章 完成算法题 完成项目数据库设计和持久层编码 素养提升完成图解TCP_IP第一章的笔记 算法小计787. K 站中转内最便宜的航班 - 力扣（LeetCode） 【最短路/必背模板】涵盖所有的「存图方式」与「最短路算法（详尽注释）」 (qq.com) 这题是一道模板题 运用 Bellman Ford 求解有限制的最短路问题 class Solution { // 总时间复杂度为 O((m+n)k) // 空间复杂度 O(nk) public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { final int INF = 10000 * 101 + 1;; int[][] f = new int[k + 2][n]; for (int i = 0; i < k + 2; i++) { Arrays.fill(f[i], I ...

素养提升完成了《图解HTTP》的阅读，接下来就是定期回顾，温习学过的知识，同时准备开启下一本书的阅读《图解TCP_IP_第5版》

1 算法小计785. 判断二分图 - 力扣（LeetCode）这题不能被描述带偏。我一开始的思路是找如何将图分为两部分，没有特别好的想法 实际上本题采用的方法是染色，让我想起了JVM中垃圾收集的三色标记法，三色标记法的本质也是将所有的对象分为可以被回收的和不能被回收的两个集合，也就是三个状态，白色代表还未被标记，灰色代表正在被标记，黑色代表标记完成 通过配置不同的标记的规则，可以将图划分为两个不同的集合，按照本题给出的条件，图中的每一条边的的两个节点，一个节点来自集合A，一个节点来自集合B，可以推出染色的规则。同一边上的两个节点的颜色不同 做题的思路对于图的题目，可以建模，可以遍历，基本上解决了大部分问题。 遍历的方式有两种，分别为DFS和BFS 首先是DFS，在编写DFS的时候，我认为应该从每个节点开始染色，实际上，如果某个节点已经被染色过，并且不能完全染色，说明以该节点起始的路径都是不可以的 题目中给定的无向图不一定保证连通，因此我们需要进行多次遍历，直到每一个节点都被染色，或确定答案为 false 为止。每次遍历开始时，我们任选一个未被染色的节点，将所有与该节点直接或间接相连的 ...

抽奖策略领域和库表设计抽奖功能拆分 所有奖品整体概率相加，总和为1，概率范围千分位 抽奖为免费抽奖次数 + 用户消耗个人积分抽奖 抽奖活动含总库存，控制运营成本（可以配置无限制库存） 活动延申配置用户库存消耗管理，单独提供表配置各类库存，用户可用总库存，用户可用日库存 部分抽奖规则，需要抽奖n次后解锁，才有机会抽取 抽取完成增加运气值，让用户获得奖品 奖品对接，自身的积分、内部系统的奖品 随机积分，得到随机的积分奖励 策略概率装配处理抽奖的算法一种是空间换时间，另外一总是时间换空间。映射到方案上，空间换时间，是提前计算好抽奖概率分布，用本地内存 guava 或者 redis 存储，最后抽奖的时候通过生成的随机值，在空间内定位即可，复杂度为O(1)。 但要注意，本地内存更快，Redis 相对慢一些。但 Redis 可以直接解决分布式存储问题，本地内存需要让多台分布式机器都保持数据的同步更新，需要引入配置中心以及定时检测的手段，来处理应用启动前/运行中，对活动新增/变更做本地内存做数据加载处理（大厂中一些非常高并发的场景，会申请内存更大的机器来做这样的事情）。 时间 ...

算法小计133. 克隆图 - 力扣（LeetCode） 复习复习 class Solution { public Node cloneGraph(Node node) { if (node == null) return node; Deque<Node> queue = new ArrayDeque<>(); Map<Node, Node> map = new HashMap<>(); queue.offerFirst(node); map.put(node, new Node(node.val)); while (!queue.isEmpty()) { Node cur = queue.pollLast(); for (Node neighbor : cur.neighbors) { if (!map.containsKey(neig ...

1 素养提升完成了HTTP头部的学习 算法笔记133. 克隆图 - 力扣（LeetCode） 一开始还没做出来，惭愧惭愧， /*// Definition for a Node.class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } public Node(int _val, ArrayList<Node> _neighbors) { val = _val; neighbors = _neighbors; } ...

言未出，结局已演千百遍；身未动，心中已过万重山； 行未果，假象苦难愁不展；事已毕，过往仍在脑中演。 勿以有限身，常供无尽愁，应尽便需尽，无复独多虑。 学习记录10 : 30 – 12 : 00

学习记录10:13 –12:02 14:22 – 15:34 15:55 – 17:10 算法小计386. 字典序排数 - 力扣（LeetCode） // 递归解法，对于这类型不好思考遍历顺序的题目，都可以尝试使用递归// 时间复杂度：本质上在搜索一棵节点数量为 n 的多阶树（形态类似于字典树），复杂度为 O(n)// 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> lexicalOrder(int n) { for (int i = 1; i <= 9; i++) dfs(i, n); return ans; } public void dfs(int cur, int limit) { if (cur > limit) return; ans.add(c ...

素养积累今天收集了很多很多有用的书籍，接下来会陆陆续续开始阅读 今天完成了《图解HTTP》前三章的阅读，并做了笔记，感觉受益匪浅，之前对于HTTP的理解停留在形式上，这本书让我对之前积累的知识有了更加形象化的认识 算法小计摆了一天，只做了一道算法题

简单的HTTP协议HTTP协议用于客户端和服务端之间的通信请求访问文本或图像等资源的一端称为客户端，提供资源响应的一 端称为服务器端 通过请求和响应的交换达成通信请求一定是从客户端发出，最后由服务端响应请求，并返回。 请求和响应报文请求报文是由请求方法、请求 URI、协议版本、可选的请求首部字段和内容实体构成的 响应报文基本上由协议版本、状态码（表示请求成功或失败的数字代 码）、用以解释状态码的原因短语、可选的响应首部字段以及实体主体构成 HTTP是不保存状态的协议无状态（stateless）协议：HTTP 协议自身不对请求和响应之间的通信状态进行保存。也就是说在 HTTP 这个级别，协议对于发送过的请求或响应都不做持久化处理 使用 HTTP 协议，每当有新的请求发送时，就会有对应的新响应产 生。协议本身并不保留之前一切的请求或响应报文的信息 这是为了 更快地处理大量事务，确保协议的可伸缩性，而特意把 HTTP 协议设计成如此简单的 HTTP/1.1 虽然是无状态协议，但为了实现期望的保持状态功能，于 是引入了 Cookie 技术。有了 Cookie 再用 HTTP ...