题目1:路灯问题
//s中只有'.'和'x'两种字符
//路灯影响三个位置
//至少需要多少灯,可以把.都点亮
public static int minLight(String s){
char[] str = s.toCHarArray();
int index = 0;
int light = 0;
//当你来到i位置,一定保证之前的灯,彻底不会影响i位置
int i = 0;
while(index < str.length){
if (str[index] == 'X'){
index++;
}else{//str[index] == "."
light++;
if(index + 1 == str.length){
break;
}else{//如果下面有位置
if(str[index+1] == 'X'){
index = index + 2;
}else{//下个位置是点
index = index + 3
}
}
}
}
return light;
}
题目2:已知一棵二叉树中没有重复节点,给定前序遍历和中序遍历数组,得出后序遍历数组
递归: int[ ] pre int[ ] in 生成 int[] pos
写一个函数,利用pre[prei.....prej]结合in[ini .....inj]生成pos[posi.....posj]
pre: a b d e c 中左右
in : d b e a c 左中右
pos: d b e c a 左右中
public static void set(int[] pre, int[] in, int[] pos, int prei, int prej, int ini, int inj, int posi, int posj, HashMapinMap){ if(prei > prej){ return; } if(prei == prej){ //只剩下一个数了,直接填 pos[posi] = pre[prei]; return; } pos[posj] = pre[prei]; int find = inMap.get(pre[prej]); set(pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1); set(pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1); } //优化 public static int[] getPostArray(int[] pre, int[] in){ if (pre == null){ return null; } int N = pre.length; int[] pos = new int[N]; HashMap inMap = new HashMap<>(); for(int i = 0; i < in.length; i++){ inMap.put(in[i], i); } set(pre, in, pos, 0, N - 1, 0, N - 1, 0, N-1, inMap); return pos; }
优化:中序遍历数组改成建一张HashMap
题目3:把数字转化成汉字
小范围到大范围
先搞定 1~19,然后处理1~99,接着1~999
中文:先搞定1~99,1~999....... 然后再处理一些特殊情况
题目4:求完全二叉树的节点的个数
1.先看深度
2.右树最左节点到了最后一层,则左树是满二叉树,右树是完全二叉树,递归
右树最左节点没到最后一层,右树是满二叉树,递归左树
//请保证head为头的树是完全二叉树
public static int nodeNum(Node head){
if (head == null){
return 0;
}
return bs(head, 1, mostLeftLevel(head, 1));
}
//node在第level层, h是总的深度, (h永远不变,全局变量)
//以node为头的完全二叉树,节点个数是多少
public static int bs(Node node, int Level, int h){
if (Level == h){
return 1;
}
if(mostLeftLevel(node.right, Level + 1) == h){
return (1 << (h - Level)) + bs(node.right, Level + 1, h);
}else{
return (1 << (h - Level - 1)) + bs(node.left, Level + 1, h);
}
}
//如果node在第level层
//求以node为头的子树, 最大深度是多少
//node为头的子树,一定是完全二叉树
public static int mostLeftLevel(Node node, int level){
while(node != null){
level++;
node = node.left;
}
return level - 1;
}
题目5:最长递增子序列问题
经典方法:遍历+动态规划
dp最大的就是结果
优化方法:用ends数组,初始化为都是无效区,ends[i]是所有长度为i+1的递增子序列中,最小结尾的值
在ends的有效区里二分的找大于nums[i] 数最左的位置,然后更新
使得长度短的递增子序列结尾小于长度大的递增子序列结尾,使得有效区必有序
构造单调性
public static int lengthOfLIS1(int[] nums) {
if(nums.length==1)return 1;
int n=nums.length;
int[] dp=new int[n];
int[] ends=new int[n];
Arrays.fill(ends,Integer.MIN_VALUE);
dp[0]=1;
ends[0]=nums[0];
int index=0;
int res=Integer.MIN_VALUE;
for (int i = 1; i < dp.length; i++) {
int left=0;
int right=index+1;
int mid=left+((right-left)>>1);
while(left!=right){
if(nums[i]<=ends[mid]){
right=mid;
}else {
left=mid+1;
}
mid=left+((right-left)>>1);
}
if(nums[i]>ends[mid]){
ends[++index]=nums[i];
dp[i]=index+1;
res=Math.max(res,dp[i]);
continue;
}
ends[mid]=nums[i];
dp[i]=mid+1;
res=Math.max(res,dp[i]);
if(ends[i]==-22) System.out.println(Arrays.toString(ends));
}
System.out.println(Arrays.toString(dp));
return res;
}
题目6:表示区间内能否被整除
1034 % 3 等价于 1 + 0 + 3 + 4 %3



