0. 基础知识 参考基础知识博客 1. 朋友圈问题 朋友圈 Nr.527 班上有N名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知A是B的朋友，B是C的朋友，那么我们可以认为A也是C的朋友。所谓的朋友圈，是指所有朋友的集合。 给定一个N * N的矩阵M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第i个和j个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。 解题思路:利用并查集合的思路，根据矩阵的大小初始化并查集合类，每个学生都有编号i[0~N-1]，他们表示每个独立的节点。遍历朋友关系矩阵，当矩阵中M[i][j]=1时，就把...

1.TCP基本认识 2.TCP建立连接 1.TCP连接的三次握手和四次挥手 2.为什么要三握四挥 3.SYN洪泛攻击 4.TIME_WAIT和CLOSE_WAIT的区别 3.TCP断开连接

1. 子网与子网掩码 在计算的时候，注意数清楚主机号的位数，留意主机号不能为全1或者全0，要减去2。 划分子网：85年开始，在IP地址的主机号前面借用若干位作为“子网号字段”，使两级IP地址变为了三级IP地址（网络号 子网号 主机号）。为解决分类IP地址空间利用率低，不够灵活，给每个物理网络分配一个IP导致路由表过大等缺点而引入。 划分子网纯属一个单位内部的事情，单位对外仍然表现为没有划分子网的网络。 子网掩码作用：由于从一个IP数据报的首部无法判断源主机或目的主机所连接的网络是否进行了子网划分，故使用子网掩码来找出IP地址的子网部分。 子网掩码的构成：32位，网络号和子网号全为1，主...

1.并查集合 基本结构 大部分资料参考Awen同学和左同学，在这里表示感谢并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作： isSameSet(find): 它可以被用来确定两个元素是否属于同一子集。 union: 将两个子集合并成同一个集合。 首先并查集本身是一个结构，我们在构造它的时候需要将所有要操作的数据扔进去，初始时每个数据自成一个结点，且每个结点都有一个父指针（初始时指向自己）。 初始时并查集中的每个结点都算是一个子集，我们可以对任意两...

0. 牛客数组输入输出 1.动态容器 变 数组 ArrayList<Integer> vector = new ArrayList<Integer>(); while(sc.hasNext()){ int n = sc.nextInt(); vector.add(n); } // T[] vector.toArray(T[vector.size()]) // 这里注意下，用到了泛型构造 Integer[] arr = vector.toArray(new Integer[vector.siz...

0. 框架模型 基本的框架已经在基础知识介绍过了，比如前中后序的递归，非递归遍历，层次遍历等。 a. 向左右子树要信息的框架 我们的这款框架中要列出所有的可能性，比如说和根节点有关 和 跟节点无关两种。下面介绍解题思路步骤， 首先根据二叉树递归解法的前提，假定可以向左右子树要的信息 考虑得到答案的可能性？列出可能性，和根节点有关么？ 根据可能性，确定左右子树分别需要什么信息 信息汇总，求全集定信息体 写递归 写递归时的步骤如下， 定义好Info结构体 递归函数process的返回Info base case也就是空树返回 从左右子树要信息 根据列出的可能性，把Info中所有的信息加工出来...

1. 用两个栈实现队列 题目描述(两个栈=>队列)：剑指offer面试题第九题：用两个栈实现队列的基本操作(队尾插入，队头弹出，显示队头) 题目分析和解答: 这里借用原书中的话，他教给我们如何先用实例分析题目，然后再抽象成解法。分析过程参考原书和上图，最后总结出，a)删除一个元素的步骤：当stack2不为空时，在stack2的栈顶元素就是最先进入队列的元素，可以弹出。当stack2为空时，我们把stack1的元素逐个弹出并压入stack2.由于先进入队列的元素被压到stack1的底部，经过弹出和压入操作之后，就处于stack2的顶端了，又可以直接弹出。b)插入一个元素的步骤：直接把它插...

0. 概述 总结一些面试机试中的题目，他们可能是力扣中的原题，都是加工过的，但是其内核还是力扣上的原题，很多题需要两种以上方法的叠加，很有挑战性！ 1. 动态规划 倒买装备 出自 小红书在游戏中，击败魔物后，薯队长获得了N件宝物，接下来得把这些宝物卖给宝物回收员来赚点小钱。这个回收员有个坏毛病，每次卖给他一件宝物后，之后他就看不上比这件宝物差的宝物了。 在这个世界中，衡量宝物的好坏有两个维度，稀有度X和实用度H，回收员在回收一个宝物A后，下一个宝物的稀有度和实用度都不能低于宝物A。那么薯队长如何制定售卖顺序，才能卖给回收员宝物总个数最多。 输出描述:一个整数，表示最多可以卖出的宝物数 示例1...

2. 完全背包 零钱兑换(完全背包-求极值) 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例输入: coins = [1, 2, 5], amount = 11输出: 3解释: 11 = 5 + 5 + 1 回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少数（原问题），如果你知道凑出 amount = 10 的最少数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的XXX）就是原问题的答案。因为XXX的数量是没有限制...

0. 回溯模版 a.迷宫问题 在棋盘上可以从任意起点出发，期望到达指定目的地。规定移动方向，比如向上下左右每次移动一格，棋盘中会有障碍物等，问是否能到达目的地。 遇到访问过的格子返回false，是因为在迷宫问题中，这一步是障碍物走不通，在单词搜索中不能走入之前走过的格子。 public boolean dfs(int i, int j, int pathNum){ // base case: 结束条件 // 把越界和访问过这些条件放在最外面 if (i<0 || i>=N || j<0 || j>=M || visited[i][j]){ ...

1. 入门 1. 求int型正整数在内存中存储时1的个数 题目描述:输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。输入: 输入一个整数（int类型）输出: 这个数转换成2进制后，输出1的个数示例： 5 得到 2 解法一：正整数转换成二进制，每次整除2，直到商为0，每次得到的余数(0或者1)组合起来就是它的二进制 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.i...

1.进程 1. 进程和线程的区别 参考知乎的解答，感谢热心网友。 课本上的是 “进程是资源分配的最小单位，线程是CPU调度的最小单位”。如何理解呢？ 进程和线程都是一个时间段的描述，是CPU工作时间段的描述。是运行中的程序指令的一种描述，这需要与程序中的代码区别开来。一个重要的事实就是CPU太快了，除了寄存器，其他外设更不上它的速度。那当多个任务要执行的时候（并发模式），在CPU看来就是轮流着来。而且因为速度差异，CPU实际的执行时间和等待执行的时间是数量级的差异，但在我们看来这些任务就仿佛是同时在执行。 一个进程处于就绪态，会被分配在就绪队列中，等待CPU的执行。执行一段程序代码，实现一个功...

1. 函数指针 1.1 基本概念 程序运行期间，每个函数都会占用一段连续的内存空间。而函数名就是该函数所占内存区域的起始地址(也称“入口地址”)。 我们可以将函数的入口地址赋给一个指针变量，使该指针变量指向该函数。然后通过指针变量就可以调用这个函数。这种指向函数的指针变量称为“函数指针”。 定义形式：类型名 (* 指针变量名)(参数类型1, 参数类型2,...); 类型名是返回的数据类型例如： int (*pf)(int ,char); 使用方法：用一个原型匹配的函数的名字给一个函数指针赋值，要通过函数指针调用它所指向的函数，写法为: 函数指针名(实参表); 1.2 用例- 函数指针和qso...

0. 模版技巧总结 DP数组边界条件 在很多的题目中，动态数组依赖上边和左边的数，dp[i][j] = dp[i-1][j]+dp[i][j-1]，这就使得我们不得不处理复杂的边界情况，单独的为第一行和第一列，乃至dp[0][0]去计算数值，非常麻烦！ 比如在最长公共子序列问题中，要单独处理边界，原因就是后续的传递公式中dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);，必须要考虑i和j要大于0。 int[][] dp = new int[M][N]; dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : ...