约瑟夫环问题 题目 在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号  思路 首先读懂题目的意思，从第一个开始报数，报到指定间隔的数就把该序号的人移除环形链表，如此反复循环，直到只剩下一个，举个形象的例子如下： 如果，现在有 7 个人围成一条...

题目 两个线程轮流打印 1 - 100，必须使用 ReentrantLock 实现 思路 使用 condition 和 reentrantlock 即可配合实现有序，一个线程中调用 condition.await，该线程就会加入该 condition 对应的等待队列，再从另一个线程唤醒 condition 的线程，就可以让线程相互协作 class T1 extends Thread { Lock lock; Condition c1; Condition c2; private AtomicInteger count; public T1(Lock lock, Condition c1, Co...

小米一面（20 min）   常规问题，大家肯定都懂，就分析个常见的源码之类的     自我介绍    HashMap 1.8 原理    MySQL（索引结构、事务深入解析，范围查询相关问题）    JVM 内存分区    JVM 类加载    锁膨胀    可冲入锁原理    重量锁原理    手写单例模式，双重检验锁    Spring 原理，知道多少说多少    Mybaties 原理（不懂）    小米二面（60 min）    过了两周，作为一个合格的备胎，被小米捞起来吊打了，但没被阿里吊打得那么难受了。。。      自我介绍一下     （上次阿里 “熟悉” 踩雷，这次不敢了，...

题目 对于字符串x和y, 如果擦除x中的某些字母(有可能全擦掉或者都不擦)能够得到y,我们就称y是x的子序列。例如."ncd"是"nowcoder"的子序列,而"xt"不是。现在对于给定的一个字符串s,请计算出字典序最大的s的子序列。  输入包括一行,一个字符串s,字符串s长度length(1 ≤ length ≤ 50).s中每个字符都是小写字母 输出一个字符串,即字典序最大的s的子序列。 输入：test 输出：tt思路 一开始想着回溯，或者用 indexOf 去循环判断，但都失败了！参考了一下大佬写法，总而言之是有规律的：  总是在当前已经确定字符的后面的序列去查找 确定字符字典序前面的总...

阿里一面（35 min）  请问哪里能找到比我被吊打得更惨的选手？   自我介绍一下 自我介绍：....平时我学习也有深入源码去分析，我对 Java 并发编程比较熟悉（这句劝退警告）....   讲讲 hashmap  balabala   停，说说为什么链化阈值是 6 ，树化阈值是 8？ 经验吧...   经验？（笑）肯定不是，6 和 8 怎么算的？ emm...沉默（1 分钟）   链表时间复杂度多少？红黑树时间复杂度多少？ O(n) / O(logn)   那到底怎么算的还不会么？ emm...沉默（1 分钟）   链表平均时间杂度多少？ 还是 O(n) 啊...   不是，平均是 O(...

题目 昨晚写的，题目有点忘记，输入一个字符串，1 - n 个点，然后每个点一个机器人，并且标记，'L' 或者 'R'，机器人碰到 'L' 往左走，碰到 'R' 往右走，并且每个机器人走 1000 次，最后每个点上的机器人有几个？ 并且，保证第 1 个点是 'R' ，第 n 个点是 'L' 思路 最后每个点必定会走入一个，L R 的循环圈中，判断最后要进入 L R 循环圈中的时候，那一个位置是偶数，那么该位置的值就加一 对字符串每个字符标记都执行以上流程即可 class Main { public static void main(String[] args) throws IOExceptio...

题目 给出一个正整数n，请给出所有的包含n个'('和n个')'的字符串，使得'('和')'可以完全匹配。 例如：'(())()'，'()()()' 都是合法的； '())()('是不合法的。 输入描述: 输入为1个正整数输出描述: 输出为所有合法的字符串，用英文逗号隔开示例1 输入：2 输出：(()),()()思路 回溯想了半天不对，过了 20% ，参考评论区大佬写的，本意也是深搜 import java.util.*; import java.io.*; class FindLegalStr { private static ArrayList<String> paths = n...

题目 给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。 例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。 思路 暴力解，可以过： import java.io.*; public class Main { public static void main(String[] ars) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = bf.read...

题目 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入：一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 思路 先学习回溯的基本套路，这里使用回溯法解，那么思考回溯的那些玩意有啥：  path 是啥 ？StringBuilder paths 是啥 ？TreeSet 状态重置哪一些东西？重置使用状态 visited[] 以及 StringBuilder 的最后一个字符  具体是这样的：  排列组合中用过的字符不能再用，所以要用 boolean vi...

题目 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 思路 理解题意：  虽然不能创建新的结点，但可以利用额外的数据结构来存储 二叉排序树：左孩子 < 根结点 < 右孩子，所以根据中序遍历，左中右，可以遍历到一个有序的序列  那么：  第一步：利用递归 / 非递归中序遍历，存在一个数组 or 一个队列 第二部：更新队列里的结点的 left and right 两个字段的引用，连成一条链表  class BiTreeAndDoubleLinkedList { public TreeNode Convert(TreeN...

剑指 - 复杂链表的复制 题目 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 思路  用一个 hashmap 建立新旧链表节点的对应的结点关系 迭代旧链表，从而在 hashmap 中更新新链表的 next 与 random 两个字段  class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; Rando...

剑指 - 二叉树中和为某一值的路径 题目 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 思路 回溯法的最佳实践！ 注意题的要义是根结点到叶子结点值为和才是路径，所以在这次的题目中不断对树的每一个孩子进行一个新的状态的递归求和，当回溯的时候，就需要进行状态重置，而状态重置在本题中需要进行两次！  一次是左子树完事，回溯，状态重置 一次是右子树完事，回溯，状态重置  而且分外注意！对于叶子结点要额外处理，叶子结点的左右孩子都为 null，对于...

题目 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路 二叉搜索树，举例如下：   结合图中分析：  一棵 BST ：左孩子 < 根结点 < 右孩子 一棵 BST 的左子树或者右子树都是 BST  后序遍历是，左右根：[3, 4, 9, 5, 12, 11, 10]，结合图再从左往右分析后序序列，分析子树，可以发现：  [3, 4, 9, 5] 10 [12, 11] [3, 4] 5 [9] [3] 4  [12] 11   发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后...

剑指 - 合并两个有序链表 题目 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 思路 按照归并排序的去写即可，只不过现在归并从数组变成了链表节点，下面的代码可能比较冗余，但还是比较容易理解的 public class MergeTwoOrderList { public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } ListNode newList ...