LifelongCode

题解

知识点总结(3) 秋招面经(15)

/ 注册

全部文章 / 题解（共110篇）

NC44：通配符匹配来自专栏

思路1：动态规划在给定的模式 p 中，只会有三种类型的字符出现：小写字母 a-z，可以匹配对应的一个小写字母；问号 ?，可以匹配任意一个小写字母；星号 *∗，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母其中「小写字母」和「问号」的匹配是确定的，而「星号」的匹配是不确定的，因...

2021-06-04

6 1193

NC94：设计LFU缓存结构来自专栏

LFU算法：least frequently used，最近最不经常使用算法；如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。 set(key,value)：将记录(key,value)插入该结构。当缓存满时，将访...

2021-06-02

5 1186

JZ67：剪绳子来自专栏

解法1：动态规划当n=1时，最大乘积只能为0；当n=2时，最大乘积只能为1；当n=3时，最大乘积只能为2；当n=4时，可以分为如下几种情况:1111，121，13，2*2，最大乘积为4；往下推时，发现n≥4时，可以把问题变成几个小问题，即：如果把长度n绳子的最大乘积记为f(n)，则有：f...

2021-05-28

0 484

JZ66：机器人的运动范围来自专栏

首先在某个节点处，要调用递归来决定某个位置的下一步去哪，此时有4个选择，每个选择都会进入下一个递归调用。当进入某个位置时，应当标记这个位置已访问过，避免之后又来到这里，从而重复计算，因此设计一个boolean的数组，这里设计的二维，也可以通过压缩，使用一维数组来表征某个位置是否访问。二维就是记录横纵...

2021-05-28

0 640

JZ59：按之字形顺序打印二叉树来自专栏

使用链表的辅助空间来实现，利用链表的反向迭实现逆序输出解法1：增加两个TreeNode：last和nlastlast：表示当前遍历层最右结点nlast：表示下一层最右结点遍历时，每次将nlast指向插入队列元素，最后一个插入结点时即最右结点。插入左右孩子之后，检测last是否为当前输出结点，若是，...

2021-05-27

0 514

JZ60：把二叉树打印成多行来自专栏

解法1：增加两个TreeNode：last和nlast last：表示当前遍历层最右结点 nlast：表示下一层最右结点遍历时，每次将nlast指向插入队列元素，最后一个插入结点时即最右结点。插入左右孩子之后，检测last是否为当前输出结点，若是，则表示需要进行换行，并将last指向下一层的n...

2021-05-27

0 565

JZ57：二叉树的下一个结点来自专栏

思路： 1.如果有右孩子，后继节点就是最左边的 2.如果没有右孩子，判断是否是父节点的左孩子，是的话，返回，不是继续往上找 3.找不到就是null 即：如果一个结点有右子树，就将它右子树上最左的结点返回，否则将当前结点的指针往上窜，当窜到它是它父结点的左结点时停止，此时那个父结点就是原结点的后继...

2021-05-27

0 525

JZ56：删除链表中重复的结点（不保留/保留）来自专栏

删除有序链表中重复出现的元素（不保留）给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为1→2→3→3→4→4→5, 返回1→2→5.给出的链表为1→1→1→2→3, 返回2→3. 输入 {1,2,2} 返回值 {1}解法1：伪结点&...

2021-05-27

0 661

JZ51：构建乘积数组来自专栏

方法1：遍历思路：也就是B[i]=A[0]*A[1]...A[n] 其中不包括A[i]; //-------------复杂度为O(n^2)---------- public int[] multily1(int[] A){ if(A.length==0){ ...

2021-05-26

0 520

JZ48：不用加减乘除做加法来自专栏

首先看十进制是如何做的： 5+7=12，三步走第一步：相加各位的值，不算进位，得到2。第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。同样我们可以用三步走的方式计算二进制值相加： 5...

2021-05-26

0 630