lintcode 最小分解描述给定一个正整数a，找到最小的正整数b，它的每个数字相乘之后等于a。如果没有答案，或者答案不符合32位整数，则返回0 样例给定 a = 48, 返回 68. 给定 a = 15, 返回 35. 思路相当于因式分解，2~9依次尝试除即可 12345678910111213141516171819202122232425class Solution {public ...

lintcode 两数之和描述给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。 样例给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1]. 思路首先，最容易想到的就是对于第i个 从j = i + 1开始往后 ...

描述给定一个数组，返回具有重复元素的最短子数组长度。 如果数组没有具有重复元素的子数组，则返回 -1。0 <= arr.length <= 10^6 样例样例 1： 输入：[1,2,3,1,4,5,4,6,8]输出：3解释：具有重复元素的最短子数组是 [4,5,4]。样例 2： 输入：[1,1]输出：2解释：具有重复元素的最短子数组是 [1,1]。 思考使用一个map 记录一下每个元素 ...

描述给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。 最近公共祖先是两个节点的公共的祖先节点且具有最大深度。 样例样例 1: 输入: 给定如下的一棵树，只有一个节点: 1 LCA(1,1) = 1 样例 2: 输入: 给如下的一颗树 4 / \ 3 7 / \ 5 6 LCA(3, 5) = `4` LCA(5, 6) = `7` LCA( ...

描述给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。 样例样例 1: 输入:”abcdzdcab”输出:”cdzdc”样例 2: 输入:”aba”输出:”aba” 思考使用Manacher算法。在每个字符后面增加一个#号，使得所有的回文串都变成奇数长度，维护一个一维数组用来记录新的字符串中以每个字符为中心的回文串的长度/2 + 1，并且这个长 ...

描述给定一个字符串所表示的括号序列，包含以下字符： ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’， 判定是否是有效的括号序列。 括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]” 则是无效的括号。 样例样例 1： 输入：”([)]”输出：False样例 2： 输入：”()[]{}”输出：True 挑战O(n)的时间，n 为括号的个数。 思路遍历字 ...

lintcode 染色问题描述有一个圆形，分成n个扇形，用m种颜色给每个扇形染色，相邻扇形颜色不能相同。求方案总数。 不考虑对称性。 由于这个数可能很大，因此只需返回方案数模1e9 + 7。 1≤n≤1051 1≤n≤10​^5​​ 1≤m≤1051 1≤m≤10​5​^5 样例给定n = 2，m = 3，返回6。 解释：一个圆划分为 2 个扇形，用 3 种颜色上色方案有“黑红，黑白，白红，白黑 ...

描述在一排树中，第 i 棵树产生 tree[i] 型的水果。你可以从你选择的任何树开始，然后重复执行以下步骤： 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。移动到当前树右侧的下一棵树。如果右边没有树，就停下来。请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。 你有两个篮子，每个篮子可以携带任何数量的水 ...

lintcode 树上最长距离描述给出由n个结点，n-1条边组成的一棵树。求这棵树中距离最远的两个结点之间的距离。给出三个大小为n-1的数组starts,ends,lens,表示第i条边是从starts[i]连向ends[i]，长度为lens[i]的无向边。 返回的是树上任意两个结点的最远距离，而不是树的深度，注意给定的边是无向边。题目保证给出的边一定能构成一棵树。 1≤n≤1∗10^5​​​1≤ ...

描述在一块大小为 2x3 的板上，有 5 块瓦片，分别用整数 1 到 5 表示，还有一块空地用 0 表示。 一次移动表示 0 与其相邻的四个方向之一的数字交换位置。 当且仅当 这块板 上的瓦片摆放状态为 [[1,2,3],[4,5,0]] 时，才能说这块板存在的问题被解决了。 board 会以上面讲的 2 x 3 大小的数组形式输入 。board[i][j] 会是 [0, 1, 2, 3, 4, ...