Du Yao's blog

设计 RandomPool结构设计一种结构,在该结构中有如下三个功能: insert(key):将某个key加入到该结构,做到不重复加入。 delete(key):将原本在结构中的某个key移除。 getRandom():等概率随机返回结构中的任何一个key。要求：Insert、delete 和 getRandom 方法的时间复杂度都是 O(1)。 思路getRandom()要随机就要知道这个结构中的元素个数，且保证都存在而删除会导致某个元素消失，这样的话元素不连续，getRandom()会出错因此本题的考点是删除但是使得元素连续解决方案是删除时将该删除元素与最后一个元素换位置，删除最后一个元素，这个就会连续而用O(1)找到元素的方法是hashMap 阅读全文...

设计有setAll功能的哈希表哈希表常见的三个操作是 put、get 和 containsKey,而且这三个操作的时间复杂度为 O(1)。现在想加一个 setAll 功能,就是把所有记录的 value 都设成统一的值。请设计并实现 这种有 setAll 功能的哈希表,并且 put、get、containsKey 和 setAll 四个操作的时间复杂度 都为 O(1)。 思路setAll是把所有数据设置为同一个值,但是时间复杂度是 O(1) 普通做法遍历hashMap然后把值都修改成同一个值这样的时间复杂度一定不是O(1) O(1)做法因此提出时间戳的概念，就是setAll变为单独一个部分，加上一个时间戳，普通数据也加上一个时间戳取数据的时候要判断是从setAll取还是从普通数据取，这个取决于对应的时间戳 在普通的hashMap中value就是一个普通的值，而这里把普通数据value设置为一个带有时间戳的value，即一个新的数据结构，包含时间戳和value每次对于添加value都要更新时间戳 阅读全文...

二叉树的序列化和反序列化二叉树被记录成文件的过程，叫做二叉树的序列化，通过文件内容重建原来二叉树的过程叫做二叉树的反序列化。给定一棵二叉树的头节点head，并已知二叉树节点值的类型为32位整型。请设计一种二叉树序列化和反序列化的方案并用代码实现。 应用：判断两颗二叉树中是否有子树完全相同，先序列化为文件，然后kmp 思路将每个树的节点的值放在字符串中，用一个分隔符分开来，不然会引起歧义，然后将空节点也用特殊符号代替本题用!代表分隔符，用#表示空结点思路就是先序遍历和层次遍历，注意处理过程稍有不同 阅读全文...

两个单链表相交的一系列问题单链表可能有环,也可能无环。给定两个单链表的头节点 head1 和 head2, 这两个链表可能相交,也可能不相交。请实现一个函数,如果两个链表相交,请返回相交 的第一个节点;如果不相交,返回 null 即可。要求:如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。 思路本题目可以拆分为2大问题 是否有环 是否相交 然后又可以拆分为多个子问题 判断单链表是否有环，如果有找出入环点 两个无环链表是否相交 两个有环链表是否相交 一个有环链表和一个无环链表是否相交 阅读全文...

判断一个链表是否为回文结构给定一个链表的头节点head，请判断该链表是不是回文结构。例如：1->2->1，返回true。1->2->2->1，返回true。15->6->15，返回true。1->2->3，返回false。 思路 & 代码123456789//链表结构public static class Node { public int value; public Node next; public Node(int data) { this.value = data; }} 阅读全文...

如何仅用递归函数和栈操作逆序一个栈一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，而不能用另外的数据结构。 思路如果仍然允许使用其他栈，那么每次要取得栈底元素，然后投入到栈中int getAndRemoveLastElement(Stack<Integer> stack)是取得栈底，并且保持栈的状态result栈顶，依次为5,4,3,2,1，然后栈空返回1last是得到的栈底元素，即刚刚的返回的1，最后又返回last为1可见递归过程中last一直都是1依次压入result，2,3,4,5，这个过程就还原了栈 阅读全文...

排成一条线的纸牌博弈问题给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。例如:arr=[1,2,100,4]。开始时玩家A只能拿走1或4。如果玩家A拿走1，则排列变为[2,100,4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A。如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4，因为拿了4之后玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。arr=[1,100,2]。开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100。所以返回100。 阅读全文...

表达式得到期望结果的组成种数给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到desired的结果。express=“1^0|0|1”，desired=false。只有1^((0|0)|1)和1^(0|(0|1))的组合可以得到false。返回2。express=“1”，desired=false。没有组合可以得到false。返回0。 阅读全文...

字符串的交错组成给定三个字符串str1、str2和aim。如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成。str1=“AB”，str2=“12”。那么“AB12”、“A1B2”、“A12B”、“1A2B”和“1AB2”等等都是str1和str2交错组成。 阅读全文...

最小编辑代价给定两个字符串str1和str2，再给定三个整数ic、dc和rc分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。str1=“abc”，str2=“adc”，ic=5，dc=3，rc=2。从“abc”编辑成“adc”，把’b’替换成’d’是代价最小的。所以返回2。str1=“abc”，str2=“adc”，ic=5，dc=3，rc=100。从“abc”编辑成“abd”，先删除’b’然后插入’d’是代价最小的。所以返回8。str1=“abc”，str2=“abc”，ic=5，dc=3，rc=2。不用编辑了，本来就是一样的字符串。所以返回0。 阅读全文...