naive的博客

图的存储方式 邻接表法，每个点记录自己的直接邻居，以点集作为单位 邻接矩阵 题目中给的结构不是常见的结构，将其转换为常见的结构再调用算法 数据结构 图 123456789public class Graph { // 点集、边集 public HashMap<Integer, Node> nodes; public HashSet<Edge> edges; public Graph(){ nodes = new HashMap<>(); edges = new HashSet<>(); }} 点 123456789101112131415public class Node { public int value; public int in; //入度 public int out; //出度 public ArrayList<Node> nexts; // 直接邻 ...

题目一 LRU设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能。set(key, value):将记录(key, value)插入该结构。get(key):返回key对应的value值。【要求】1.set和get方法的时间复杂度为0(1)⒉.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的3.当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的【举例】 12345假设缓存结构的实例是cache，大小为3，并依次发生如下行为1.cache. set ("A"，1)。最常使用的记录为("A",1)2.cache.set("B",2)。最常使用的记录为("B",2)，("A",1)变为最不常使用的3.cache.set("C",3)。最常使用的记录为("C",2)，("A",1)还是最不常使用的4.cache. get("A")。最常使用的记录为 ...

题目二 express的组合给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到desired的结果。【举例】express="1^0|0l1"，desired=false只有1^((0|0)|1)和1^(0|(0/1))的组合可以得到false，返回2。 express="1"，desired=false无组合则可以得到false，返回0 解： 写一个函数，这个函数负责计算在L-R上满足desired的可能性有多少种,范围尝试 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778public static int num1(String express, boolean ...

题目一把一个数字用中文表示出来。数字范围为[0, 99999]。为了方便输出，使用字母替换相应的中文，万W千Q百B十S 零L。使用数字取代中文数字注:对于11应该表示为一十一(1S1)，而不是十一(S1)输入描述:数字0（包含）到99999(包含）。输出描述:用字母替换相应的中文，万W千Q百B 十S 零L示例1:输入12001输出1W2QL1 题目二给定一个整数数组A，长度为n，有1<= A[i] <=n，且对于[1,n]的整数，其中部分整数会重复出现而部分不会出现。实现算法找到[1, n]中所有未出现在A中的整数。提示:尝试实现0(n)的时间复杂度和0(1)的空间复杂度（返回值不计入空间复杂度）。输入描述:一行数字，全部为整数，空格分隔A0 A1 A2 A3.. .输出描述:一行数字，全部为整数，空格分隔RO R1 R2 R3.. . 示例1:输入1 3 4 3输出2 123456789101112131415161718192021222324public static void printNumberNotInArray(int[] arr){ if ...

需求 支持设定过期时间，精度到秒 支持设定最大内存，当内存超出时做出合适的处理 支持并发安全 按照以下接口要求实现 12345678910111213141516type cache 1ntertace { //size : 1KB 100KB 1MB 2MB 1GB SetMaxMemory(size string) bool/ //将value写入缓存 Set(key string, val interface{}, expire time. Duration) bool //根据key值获取value Get(key string)(interface{}, bool) //删除key值 Del(key string) bool //判断key是否存在 Exists(key string) bool //清空所有key Flush() bool //获取缓存中所有key的数量 Keys() int64} 使用示例 123456789cache := NewMemcach ...

ICMPICMP报文结构 ICMP校验和算法 报文内容，相邻两个字节拼接到一起组成一个16bit数，将这些数累加求和 若长度为奇数，则将剩余的1个字节，也累加到求和 得出总和之后，将和值的高16位与低16位不断求和，直到高16位为 以上三步得出结果后，取反，即为校验和 例如 ：根据ICMP的报文可以得出以下的格式 18 | 0 | 0 0 | 0 1 | 0 1 | 1 1 1 1 1 1 1 1 相邻两个字节拼接到一起组成一个16bit数 180 + 00 + 01 + 01 + 11 + 11 + 11 + 11 求和后是一个int32的数，将高16位和低16位求和，直到高位为0 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 ...

题目一 打印目录给你一个字符串类型的数组arr，譬如: 1String[] arr = { "b\\cst", "d\\", "a\\d\\e", "a\\b\\c”}; 你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右进两格，就像这样: 12345678a b c d eb cstd 同一级的需要按字母顺序排列，不能乱。 解 经典前缀树题目 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950public static class Node { public String name; // 有序打印 public TreeMap<String, Node> nextMap; public Node(String name) { this.name ...

题目一 达标字符串字符串只由’0’和’1’两种字符构成，当字符串长度为1时，所有可能的字符串为”0”、”1”;当字符串长度为2时，所有可能的字符串为”00”、”01”、”10”、”11”;当字符串长度为3时，所有可能的字符串为”000”、”001”、 “010”、 “011”、 “100”、”101”、”110”、 “111”如果某一个字符串中，只要是出现’0’的位置，左边就靠着’1’，这样的字符串叫作达标字符串。给定一一个正数N，返回所有长度为N的字符串中，达标字符串的数量。比如，N=3， 返回3，因为只有”101”、”110”、 “111”达标。 解 n=i在长度为i有多少合法的字符串，就规定了在0位置上必须为1，求f(n-1)。 对于n=8，就是0位置为1,求剩下7位置的可能性，f(7),此时就有2中可能性 第一位为1，求f(6)的数量 第一位为0，那么下一位就必须填1，f(5)的数量 f(i) = f(i-1)+f(i-2),此时把问题转化为了斐波那契数列问题。采用递归或动态规划的方式求解,下面是采用的线性代数中将斐波那契数列转换为矩阵相乘的求解方式。 123456789 ...

题目一 猫狗队列实现一种狗猫队列的结构，要求如下: 用户可以调用add方法将cat类或dog类的实例放入队列中; 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出; 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出; 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出; 用户可以调用isEmpty方法，检查队列中是否还有dog或cat 的实例; 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例; 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。 要求以上所有方法时间复杂度都是0(1)的 题目二 最小栈实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。要求: pop、push、getMin操作的时间复杂度都是O(1) ; 设计的栈类型可以使用现成的栈结构 leetcode155 最小栈 解 准备2个栈，一个数据栈，一个最小栈；入栈时数据栈直接入，最小栈查看栈顶元素是否比当前数小，小就继续压入最小的数，否则压入 ...