625. 最小因式分解
给定一个正整数 a，找出最小的正整数 b 使得 b 的所有数位相乘恰好等于 a。
如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。
思路：
- dfs 求得所有的解集合，取最小的值。dfs注意剪枝：232减去，因为232>223。复杂度高。
- 贪心算法，从个位往前添加因子，能除9就先除9不除3*3；
class Solution {
public int smallestFactorization(int a) {
if(a<=9){
return a;
}
List<Integer> list = new ArrayList();
for(int i=9;i>1;i--){
if(a==1){
break;
}
while(a%i==0){
a = a/i;
list.add(i);
}
}
Collections.reverse(list);
if(a!=1){
return 0;
}else{
int base = 1;
int result =0;
if(list.size()>=10){
return 0;
}
for(int i=list.size()-1;i>=0;i--){
result += list.get(i)*base;
base = base*10;
}
return result;
}
}
}
1024. 视频拼接
难度中等38 收藏 分享 切换为英文 关注 反馈
你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
示例 1：
输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
输出：3
解释：
我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。
解法： 贪心算法。能选择9作为最后，不选择3，4，5，6，7，8；
class Solution {
public int videoStitching(int[][] clips, int T) {
int count = 0;
int max = 0;
for(int i=0;i<=T;){
for(int j=0;j<clips.length;j++){
// 在所有片段中选择满足i且右边界最大的。直接跳到右边界，接着循环。
if(clips[j][0]<=i){
max = Math.max(max,clips[j][1]);
}
}
// 如果最右也比i小，说明该点缺失。
if(max<=i){
return -1;
}
i = max;
count++;
if(max==T){
break;
}
}
return count;
}
}
588. 设计内存文件系统
设计一个内存文件系统，模拟以下功能：
ls： 以字符串的格式输入一个路径。如果它是一个文件的路径，那么函数返回一个列表，仅包含这个文件的名字。如果它是一个文件夹的的路径，那么返回该 文件夹内 的所有文件和子文件夹的名字。你的返回结果（包括文件和子文件夹）应该按字典序排列。
mkdir：输入一个当前不存在的 文件夹路径 ，你需要根据路径名创建一个新的文件夹。如果有上层文件夹路径不存在，那么你也应该将它们全部创建。这个函数的返回类型为 void 。
addContentToFile： 输入字符串形式的 文件路径 和 文件内容 。如果文件不存在，你需要创建包含给定文件内容的文件。如果文件已经存在，那么你需要将给定的文件内容 追加 在原本内容的后面。这个函数的返回类型为 void 。
readContentFromFile： 输入 文件路径 ，以字符串形式返回该文件的 内容 。
注意：以两个hashMap去表示文件系统；
Map<String, String> files：文件； 名字：文件
Map<String, Dir> dirs: 文件夹； 名字：文件夹；
public class FileSystem {
class Dir {
HashMap < String, Dir > dirs = new HashMap < > ();
HashMap < String, String > files = new HashMap < > ();
}
Dir root;
public FileSystem() {
root = new Dir();
}
public List < String > ls(String path) {
Dir t = root;
List < String > files = new ArrayList < > ();
if (!path.equals("/")) {
String[] d = path.split("/");
for (int i = 1; i < d.length - 1; i++) {
t = t.dirs.get(d[i]);
}
if (t.files.containsKey(d[d.length - 1])) {
files.add(d[d.length - 1]);
return files;
} else {
t = t.dirs.get(d[d.length - 1]);
}
}
files.addAll(new ArrayList < > (t.dirs.keySet()));
files.addAll(new ArrayList < > (t.files.keySet()));
Collections.sort(files);
return files;
}
public void mkdir(String path) {
Dir t = root;
String[] d = path.split("/");
for (int i = 1; i < d.length; i++) {
if (!t.dirs.containsKey(d[i]))
t.dirs.put(d[i], new Dir());
t = t.dirs.get(d[i]);
}
}
public void addContentToFile(String filePath, String content) {
Dir t = root;
String[] d = filePath.split("/");
for (int i = 1; i < d.length - 1; i++) {
t = t.dirs.get(d[i]);
}
t.files.put(d[d.length - 1], t.files.getOrDefault(d[d.length - 1], "") + content);
}
public String readContentFromFile(String filePath) {
Dir t = root;
String[] d = filePath.split("/");
for (int i = 1; i < d.length - 1; i++) {
t = t.dirs.get(d[i]);
}
return t.files.get(d[d.length - 1]);
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem obj = new FileSystem();
* List<String> param_1 = obj.ls(path);
* obj.mkdir(path);
* obj.addContentToFile(filePath,content);
* String param_4 = obj.readContentFromFile(filePath);
*/
469. 凸多边形
给定一个按顺序连接的多边形的顶点，判断该多边形是否为凸多边形。（凸多边形的定义）
注：
- 顶点个数至少为 3 个且不超过 10,000。
- 坐标范围为 -10,000 到 10,000。
- 你可以假定给定的点形成的多边形均为简单多边形（简单多边形的定义）。换句话说，保证每个顶点处恰好是两条边的汇合点，并且这些边 **互不相交 **。
示例 1：
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">[[0,0],[0,1],[1,1],[1,0]]
输出： True
</pre>
示例 2：
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">[[0,0],[0,10],[10,10],[10,0],[5,5]]
输出： False
</pre>
解法： 向量叉积全为正/全为负。 a,b 均为向量。
* 叉积小于0，那么a在b的逆时针方向，
* 叉积大于0，a在b的顺时针方向
* 叉积等于0，a,b方向相同
import java.util.List;
class Solution {
public boolean isConvex(List<List<Integer>> points) {
boolean positive = false;
boolean negative = false;
int n = points.size();
for(int i=0;i<points.size();i++){
if(crossMult(points.get(i),points.get((i+1)%n),points.get((i+2)%n))>0){
positive = true;
}else if(crossMult(points.get(i),points.get((i+1)%n),points.get((i+2)%n))<0){
negative = true;
}
if(positive&&negative){
return false;
}
}
return true;
}
public int crossMult(List<Integer> A, List<Integer> B , List<Integer> C){
/**
* 使用向量叉积，
* a = (x1,y1)
* b = (x2,y2)
* aXb = x1y2-x2y1
* 叉积小于0，那么a在b的逆时针方向，
* 叉积大于0，a在b的顺时针方向
* 叉积等于0，a,b方向相同
*/
int xA = A.get(0) - B.get(0);
int xC = C.get(0) - B.get(0);
int yA = A.get(1) - B.get(1);
int yC = C.get(1) - B.get(1);
return xA*yC - xC*yA;
}
}
887. 鸡蛋掉落
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
思路： 解题需要求得，最坏情况下的最小次数N；
ex： N = 7； K = 1；为了得到准确楼层，只能从1层到7层依次遍历。此时最坏情况就是第7层刚好碎，准确楼层为7。次数为7。
以某i层扔下为例子，如果碎了，dp[K-1,i-1]；如果没碎，dp[K,i+1~N] = dp[K,N-i];
最坏情况就是取更大的，max（dp[K-1,i-1],dp[K,N-i]);
最小次数，就是遍历i，取得最小的次数。此时得到解。
for(int i=1;i<=N;i++){
res = min(res,max((dp[K-1,i-1],dp[K,N-i]));
}
可以利用hashMap存储已经记录下的值，作为优化。
但这种优化不够，由于dp[K-1,i-1] 随着i递增，dp[K,N-i]递减。▽。取其最小的最大值，就是取其凹点。因此，用二分法改进。
class Solution {
HashMap<Integer,Integer> map = new HashMap();
public int superEggDrop(int K, int N) {
return dp(K,N);
}
public int dp(int K, int N){
if(K==1){
return N;
}
if(N == 0){
return 0;
}
if(map.containsKey(100*N+K)){
return map.get(100*N+K);
}
int res = Integer.MAX_VALUE;
// 二分： dp(K,i-1)随着i递增，dp(K-1,N-i) 随着i递减
// 二者相加，得到类似▼形状，二者相等时，Math.min(res,Math.max(dp(K,i-1),dp(K-1,N-i))+1)值最小。
// 因为不相等时，总是取更大的（更上面的），即取凹点。
int low = 1;
int high = N;
while(low<=high){
int mid = (low+high)/2;
int left = dp(K-1,mid-1);
int right = dp(K,N-mid);
if(left<right){
low = mid + 1;
res = Math.min(res,right + 1);
}else if(left >= right){
high = mid -1;
res = Math.min(res,left + 1);
}
}
map.put(100*N+K,res);
return res;
}
}
1153. 字符串转化
给出两个长度相同的字符串，分别是 str1 和 str2。请你帮忙判断字符串 str1 能不能在 零次 或 多次 转化后变成字符串 str2。
每一次转化时，将会一次性将 str1 中出现的 所有 相同字母变成其他 任何 小写英文字母（见示例）。
只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 True，否则返回 False。
示例 1：
输入：str1 = "aabcc", str2 = "ccdee"
输出：true
解释：将 'c' 变成 'e'，然后把 'b' 变成 'd'，接着再把 'a' 变成 'c'。注意，转化的顺序也很重要。
示例 2：
输入：str1 = "leetcode", str2 = "codeleet"
输出：false
解释：我们没有办法能够把 str1 转化为 str2。
思路： 示例一的规则；a->c b->d c->e，如果aabbcc a -> ccdee f则返回false；
利用HashMap记录转换规则（顶多26个字母），当出现重复字母，判断对应的str2字符是否与规则中的相同。如果str2有26个字母，将形成死循环。
class Solution {
public boolean canConvert(String str1, String str2) {
if(str1.length()!=str2.length()){
return false;
}
if(str1.equals(str2))
return true;
HashMap<Character,Character> map = new HashMap();
Set<Character> set=new HashSet<>();
for(int i=0;i<str1.length();i++){
if(!map.containsKey(str1.charAt(i))){
map.put(str1.charAt(i),str2.charAt(i));
}else{
if(str2.charAt(i)!=map.get(str1.charAt(i))){
return false;
}
}
set.add(str2.charAt(i));
}
return set.size()<26;
}
}
632. 最小区间
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。</pre>
原始思路：
所有数字形成的集合T[0,4,5,9,12,18....]，遍历整个数字集合，找到该数字的其他列表中大于该数字的最小数字集Y，其min为该数字，其max为max{数字集}。
进一步思考讨论：
如果T中该数字的下一个数字，就是该数字列表中的下一个数字，则Y不变。数字集变成{x_next,Y}
如果T中该数字的下一个数字，不是其原先列表的下一个数字，那么必为Y中的一个数字。
如y2，则y3至yn不变，Y集合变成{x_next,y3至yn}。数字集为{x_next,y2,y3~至} -> {x_next,Y}。
因此，通过K路指针法，维护K个指针指向数字集中的数字。int[] next = new int[nums.length];如果该指针指向的数字超过了该列表的长度，则退出循环。
通过最小堆，维护指向最小数所在列表的指针。
code如下：
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int minx = 0, miny = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int[] next = new int[nums.size()];
boolean flag = true;
// 最小堆维护的是当前的最小值，在哪个列表中。注意该堆的比较器。
PriorityQueue<Integer> min_queue = new PriorityQueue<Integer>((i,j) -> nums.get(i).get(next[i])-nums.get(j).get(next[j]));
// 初始化堆
for(int i=0;i<nums.size();i++){
min_queue.offer(i);
max = Math.max(max,nums.get(i).get(0));
}
// 从堆中取得当前最小元素所在的列表。根据next[i]，取得其所在位置，多路指针法，类似于丑数；
// 经前面分期，第二个列表就是min_i在其列表的后一位及其之前其他数字组成的区间。最小值由最小堆（决定min_i）及next[min_i]维护，
// 最大值由max = Math.max(max, nums.get(min_i).get(next[min_i]))维护。
for(int i=0;i<nums.size()&&flag;i++){
for(int j=0;j<nums.get(i).size()&&flag;j++){
int min_i = min_queue.poll();
// 选择更小的区间
if(miny-minx> max - nums.get(min_i).get(next[min_i])){
miny = max;
minx = nums.get(min_i).get(next[min_i]);
}
// 由于next改变，min_i加入堆后，堆结构也会改变
next[min_i]++;
if(next[min_i]>=nums.get(min_i).size()){
flag = false;
break;
}
min_queue.offer(min_i);
max = Math.max(max, nums.get(min_i).get(next[min_i]));
}
}
return new int[]{minx,miny};
}
}
330. 按要求补齐数组
给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 *nums *中，使得 [1, n] 区间内的任何数字都可以用 *nums *中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
输入: nums = [1,3], n = 6
输出: 1
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。
思路： 确认其所覆盖的区间，初始化区间为[1,1);
当区间right > n 时，则完成。初始化nums的索引index=0；
for(int i=1;i<=n;)，每次将i更新为区间的right，避免重复计算。
如果nums[index]<i，由于现在的区间是[1,right]即[1,i]。通过将区间内的所有数+nums[index]得到新的区间 [1,right+nums[index]]；更新i为新值，并且将index右移一位。
如果nums[index]>i，则需要新增i在nums中，作为新加数，此时right更新为2i;而index不变。
如果index超过索引长度，需要新增i在nums作为新加数，同样更新right = 2i；
代码：
class Solution {
public int minPatches(int[] nums, int n) {
long right = 1;
int index = 0;
int count = 0;
for(long i=1;i<=n;){
if(index<nums.length&&nums[index]>i){
count ++;
right = 2*i; //[1,2i)
}
else if(index<nums.length&&nums[index]<=i){
// 不一定要添加；
right += nums[index];
index ++; // [1,i+nums[index]];
}else{
right = 2*i;
count++;
}
i = right;
}
return count;
}
}
818. 赛车
你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）
你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶 。
当车得到指令 "A" 时, 将会做出以下操作： position += speed, speed *= 2。
当车得到指令 "R" 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1 ；否则将车速调整为 speed = 1。 (当前所处位置不变。)
例如，当得到一系列指令 "AAR" 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。
现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。
示例 1:
输入:
target = 3
输出: 2
解释:
最短指令列表为 "AA"
位置变化为 0->1->3
示例 2:
输入:
target = 6
输出: 5
解释:
最短指令列表为 "AAARA"
位置变化为 0->1->3->7->7->6
解题思路： Math.pow(2,i) = 1<<i;
假设： k-1次A到k次A之间包含了target；
则有两种前进方式:
①：
先来（k-1）个A，如果此时刚好为target，return；
如果不是，反向操作R后。后退j（j<(k-1)，R反向掉头。此时target= target - 1<<(k-1)-1<<j;
具体后退多少个j。取 所有递归里最小的。
②：
来(k)个A,总距离为 2^k-1即 （1<<k）-1
，R，target = (1<<(k))-1-target；递归求解；
取 1和2中更小的那个。
class Solution {
public int racecar(int target) {
int res = dp(target);
return res;
}
public int dp(int target){
if(target <=0){
return 0;
}
if(target == 1){
return 1;
}
if(target == 2){
return 4;
}
int n = 0;
for(int i=0;i<target;i++){
if((1<<i)>target){
n = i;
break;
}
}
if(target+1==(1<<n)){
return n;
}
int min = Integer.MAX_VALUE;
for(int j=0;j<n-1;++j){
min = Math.min(min,dp((int) target-(1<<(n-1))+(1<<j))+n-1+j+2);
}
return Math.min(min,dp((1<<(n))-1-target)+n+1);
}
}
注意: 1. 1<<i = 2^i; 2. 如果往回倒，具体倒多少个A，要遍历取最小的。 3. 利用数组记录递归值，减少复杂度
