521. 最长特殊序列 Ⅰ【简单题】【每日一题】
思路：【脑筋急转弯】
字符串a、b相等时，因为互为对方的子串，此时存在题目要求的特殊序列，更别提最长特殊序列了，直接返回-1。当字符串a、b不相等时，如果字符串长度不同，那么肯定直接返回字符串长度较大的那个就行，因为长度大的那个字符串本身，既满足是自己的子串，又满足不是对方子串，又满足长度最长；如果字符串长度相同，那么返回任意字符串长度即可（反正两个长度都一样），此时也满足，字符串是自己子串，不是对方子串，且长度最长。综上，当a、b相等时，返回-1，否则，返回两个字符串长度较大的那个长度。
代码：
class Solution {
public int findLUSlength(String a, String b) {
return a.equals(b) ? -1 : Math.max(a.length(),b.length());
}
}
47. 全排列 II【中等题】
思路：【题解的回溯】
先对数组排序方便以后去重。回溯函数： 回溯终点：回溯层数pos=数组长度或数组遍历结束； 回溯中：从0开始遍历nums数组，如果当前位置i的元素被使用过，即标记数组used[i]=true，或者当前元素与上一个元素重复且上一个元素未被使用过，那么不能选择当前元素，跳过本层循环进入下一层；如果当前位置的元素未被使用过或者虽然与上一个元素重复但是上一个元素已被使用过，此时将当前元素添加到list集合中，并将当前位置对应的标记数组置为true表示当前位置元素已被使用，此时带着list，ans，used，进入pos+1层递归。
回溯后：回溯结束返回上一层回溯，并将当前位置使用状态还原为false，将list中最后一个元素移除。
代码：
class Solution {
public List> permuteUnique(int[] nums) {
List> ans = new ArrayList<>();
List list = new ArrayList<>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums,ans,0,list,used);
return ans;
}
public void dfs(int[] nums,List> ans,int pos,List list,boolean[] used){
if (pos == nums.length){
ans.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] || (i>0 && nums[i] == nums[i-1] && !used[i-1])){
continue;
}
list.add(nums[i]);
used[i] = true;
dfs(nums,ans,pos+1,list,used);
used[i] = false;
list.remove(pos);
}
}
}
50. Pow(x, n)【中等题】
思路：
这题我只能说，暴力遍历是可以过的，也是我菜，看了题解原来还可以这样~先把一些特殊情况剔除掉（具体在代码注释里），然后下边开始递归。递归的时候，n大于0，则返回pow(x,n)，x小于0 则返回 1/pow(x,-n)。递归终止条件：n == 0时，返回1。每次递归先判断n是不是等于0，是就返回0，不是就将n减半继续递归。递归到终点结束后，设y为x的当前n的减半次幂，判断当前的n是否是偶数，是则返回y的平方，不是则返回y的平方再乘x。
代码：
class Solution {
public double myPow(double x, int n) {
if (n == 0 || x == 1){//0次幂 或者 1的次方，直接返回1
return 1;
}
if (x == 0 || n == Integer.MIN_VALUE){//0的次方 或者 n是int下界，直接返回0，特殊情况 x =-1，n是int下界时返回1
return x == -1 ? 1 : 0;
}
if (x == -1){//x是-1时，n是偶数返回1，n是奇数，返回-1
return n % 2 == 0 ? 1 : -1;
}
return n > 0 ? pow(x,n) : 1 / pow(x,-n);
}
public double pow(double x,int n){
if (n == 0){
return 1;
}
double y = pow(x,n/2);
return n % 2 == 0 ? y*y : y * y * x;
}
}
