一些不常见的面试算法题

平衡二叉搜索树插入算法

对于给定的数据，找出比这个数大的最小回文数（正反读都一样的数），如 12310 -> 12321

leetcode 564
public class hello {//100 999

    public static void main(String[] args) {
        String str="271";

        int len=str.length();
        char[] s=str.toCharArray();
        int flag=0,i;
        for(i=len/2-1;i>=0;--i){
            if(s[i]>s[len-1-i]){flag=1;break;}
            else if(s[i]<s[len-1-i]){ flag=-1;break;}
        }
        if(flag!=1){//前半串要加1
            //s[(len-1)/2]++;
            for(i=(len-1)/2;i>=0;--i){//199 191 999
                s[i]++;
                if(s[i]>'9'){
                    s[i]='0';
                }else break;
            }
            if(s[0]=='0'){//999 9999
                s[0]='1';
                len++;
                s[len/2]='0';
            }
        }
        for(i=0;i<len/2;++i)
            System.out.print((s[i])+" ");
        for(i=(len+1)/2-1;i>=0;--i)
            System.out.println(s[i]+" ");
    }


}

对一个奇数位升序，偶数位降序的链表，进行排序，例如 1->100->20->80->40->30
1
奇偶拆分反转合并链表
从一个数 l 一直与操作到 r ，怎么做最快，复杂度最小
输出交错后的链表(比如链表a-b-c-d-e,交错后输出为a-e-b-d-c)

请对3个有序数组进行归并排序

public static void main(String[] args) {

        System.out.println("Hello World!");
//        int[][] arr = {{1,4,5},{1,3,4}};
        List<List<Integer>> arr = new ArrayList<>();
        arr.add(Arrays.asList(1,4,5));
        arr.add(Arrays.asList(1,3,4));
        arr.add(Arrays.asList(1,8,9,10));
        System.out.println(arr);

        List<Integer> res = merge(arr);

        System.out.println(res);
    }

     private static List<Integer> merge(List<List<Integer>> arr) {
        List<Integer> res = new ArrayList<>();
        if(arr.size() == 0) return res;
        if(arr.size() == 1) return arr.get(0);
        if(arr.size() == 2) return helper(arr.get(0),arr.get(1));
        int left = 0, right = arr.size() - 1;
        int mid = left + (right - left) / 2;
        List<List<Integer>> tmp1 = new ArrayList<>();
        List<List<Integer>> tmp2 = new ArrayList<>();

        for(int i = 0; i < mid ; i++)
        {
            tmp1.add(arr.get(i));
        }
         for(int i = mid ; i <= right; i++)
         {
             tmp2.add(arr.get(i));
         }
         return helper(merge(tmp1),merge(tmp2));
    }

    private static List<Integer> helper(List<Integer> merge, List<Integer> merge1) {
         int i = 0, j = 0;
         List<Integer> res = new ArrayList<>();
         while(i < merge.size() && j < merge1.size())
         {
            if(merge.get(i) < merge1.get(j))
            {
                res.add(merge.get(i++));
            }
            else{
                res.add(merge1.get(j++));
            }
         }
        while(i < merge.size())
        {
                res.add(merge.get(i++));
        }
        while(j < merge1.size())
        {
            res.add(merge1.get(j++));
        }
        return res;

    }

掷骰子走路，1～6，给定的输入n，走到第n个格子有多少种走法
青蛙跳格子，数组里元素表示该位置石头个数，每次跳3-5格，问跳出数组最少踩多少石头
.给一个正整数，表示成一个或多个不同的正整数的和，输出所有的解决方案
找出数组里出现次数大于n/k的数
给一个矩阵，从右上角往左下角一层一层斜着遍历
一个int数组，找出两个异或最大的数字，时间要求O(n)
四个int数组，从每个数组里边挑一个数，加起来等于指定数，要求打印出所有非重复的组合，要求最大n2
查找有序数组中一个目标值出现的第一次位置，没有找到返回 -1
二分查找在升序数组中找出绝对值最小的那个数
给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内
字符串数组两个字符串的最小距离
实现洗牌算法
单链表高位在前、低位在后，大数计算
阶乘
合并数组
一道矩阵相乘
求连续子序列乘积为完全平方数的最大长度
定一个升序数组，可能会有重复的数字，将数组里的数平方后，有多少不同的数
:两个大数字符串求和输出字符串
任意数组中的第一个缺失的正整数
字符串反转
.给你一个数组和一个target，找出和是target整数倍的连续子串
I am student 返回 student am I 不用split
给一个分数n/m，如果这个分数是无线循环小数，找出循环位。
排序数组，平方后，数组当中有多少不同的数字（相同算一个）
一个数据先递增再递减，找出数组不重复的个数，比如 [1, 3, 9, 1]，结果为3，不能使用额外空间，复杂度o(n)
某一个大文件被拆成了N个小文件，每个小文件编号从0至N-1，相应大小分别记为S(i)。给定磁盘空间为C，试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小
1

给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，问能否在这个字符串中找到一个长度为m的连续子串，使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，acbd，3
算法题，一个有序数组，从随机一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数
链表实现一个栈
求完全二叉树的节点个数，小于O(n)，并分析复杂度
写一个函数，求平方根，函数参数为目标数字和精度，测试案例 fn(4.1,0.001) fn(501.1,0.001) fn(0.045,0.001)
给定一个 0-4随机数生成器如何生成0-6随机数

中文数字转阿拉伯数字，字符串处理问题

中文数字格式：一万三千五百四十一

阿拉伯数字格式：13541

中文数字中要分单位和数字分别处理，可以用两个数组分别保存中文数字和中文单位，每次循环扫描给的中文数字，去匹配对应的数字。中文数字数字可以用数组下标对应数字。

public class Solution{
   static char[] cnArr = {'零','一', '二', '三', '四', '五', '六', '七', '八', '九'};
   static char[] chArr = {'十', '百', '千', '万', '亿'};
public static int chineseNumToArabicNum(String chineseNum) {
    int result = 0;
    int temp = 1;//存放一个单位的数字如：十万
    int count = 0;//判断是否有表示单位的文字
    for (int i = 0; i < chineseNum.length(); i++) {
        boolean b = true;//判断是否是单位
        char c = chineseNum.charAt(i);
        for (int j = 0; j < cnArr.length; j++) {//非单位，即数字
            if (c == cnArr[j]) {
                if (count != 0) {//添加下一个单位之前，先把上一个单位值添加到结果中
                    result += temp;
                    temp = 1;
                    count = 0;
                }
                // 下标+1，就是对应的值
                temp = j;
                b = false;
                break;
            }
        }
        if (b) {//单位{'十','百','千','万','亿'}
            for (int j = 0; j < chArr.length; j++) {
                if (c == chArr[j]) {
                    switch (j) {
                        case 0:
                            temp *= 10;
                            break;
                        case 1:
                            temp *= 100;
                            break;
                        case 2:
                            temp *= 1000;
                            break;
                        case 3:
                            temp *= 10000;
                            break;
                        case 4:
                            temp *= 100000000;
                            break;
                        default:
                            break;
                    }
                    count++;
                }
            }
        }
        if (i == chineseNum.length() - 1) {//遍历到最后一个字符
            result += temp;
        }
    }
    return result;
}
}

三个线程循环打印ABC**

public class hello {
    //1->100->20->80->40->30    1->20-30->40->80->100
    static class ListNode
    {
        int val;
        ListNode(int x)
        {
            val=x;
        }
        ListNode next;
    }
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        ListNode l2=new ListNode(100);
        ListNode l3=new ListNode(20);
        ListNode l4=new ListNode(80);
        l1.next=l2;
        l2.next=l3;
        l3.next=l4;
        l4.next=null;
//        while(l1!=null)
//        {
//            System.out.println(l1.val);
//            l1=l1.next;
//        }
        help(l1);
        while(l1!=null)
        {
            System.out.println(l1.val);
            l1=l1.next;
        }
    }
    public static ListNode help(ListNode head)
    {
        if(head==null || head.next==null)
        {
            return head;
        }
        ListNode h1=head,t1=head;
        ListNode h2=head.next,t2=h2;
        while(t1.next!=null && t2.next!=null)
        {
            t1.next=t2.next;
            t1=t1.next;
            t2.next=t1.next;
            t2=t2.next;
        }
        t1.next=null;
        ListNode temp=reverse(h2);
        ListNode res=mergeTwoLists(temp,h1);
        return res;

    }
    public static ListNode reverse(ListNode head)
    {
       if(head==null || head.next==null) return head;
       ListNode temp=reverse(head.next);
       head.next.next=head;
       head.next=null;
       return temp;
    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode curr=dummy;
        ListNode p=l1,q=l2;
        while(p!=null&&q!=null)
        {
            int x=p.val;
            int y=q.val;
            if(x<y)
            {
                curr.next=p;
                p=p.next;

            }
            else
            {
                curr.next=q;
                q=q.next;

            }
            curr=curr.next;
        }
        if(p!=null) curr.next=p;
        if(q!=null) curr.next=q;
        return dummy.next;
    }
}

1
2

43. **平方后，数组当中有多少不同的数字**

public class Solution {
public int diffSquareNum(int nums[]) {
    int n = nums.length;
    if(n == 0 || nums == null){
        return 0;
    }
    int sum = 0;
    int left = 0;
    int right = n - 1;
    while(left <= right){
        if(nums[left] + nums[right] == 0){
            sum++;
            int temp = nums[left];
            //这里开始去掉后面重复的数字
            while(left <= right && nums[left] == temp)
                left++;
            while(left <= right && nums[right] == -temp)
                right--;
        }
        else if(nums[left] + nums[right] < 0){
            sum++;
            int temp = nums[left];
            while(left <= right && nums[left] == temp)
                left++;
        }
        else {
            sum++;
            int temp = nums[right];
            while(left <= right && nums[right] == temp)
                right--;
        }
    }
    return sum;
}
}
1
2
3
4

43

给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，问能否在这个字符串中找到一个长度为m的连续子串，使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，acbd，

public class hello {
public static void main(String[] args) {
char[] c={'a','c','b','d'};
String s="tbcacbdata";
int res=help(c,s);
System.out.println(res);
}
public static int help(char[] ch,String s)
{

    if(ch.length > s.length()){
        return -1;
    }
    for(int i = 0; i <= s.length() - ch.length+1; i++){
        //每次匹配长度为m的子串
        if(matchs(ch,s.substring(i,i+ch.length)))
            return i;
    }
    return -1;
}
private static boolean matchs(char[] ch,String s){
    for(int i = 0; i < s.length();i++){
        //返回-1说明字符串中不包含这个字符
        if(s.indexOf(ch[i]) == -1)
            return false;
    }
    return true;
}

}

1 2	44.一个有序数组，从随机一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数

public class findNumInRotateArr {

public static double minNumberInRotateArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] < nums[right]) {
            right = mid;
        } else if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right--;
        }
    }
    int size = nums.length;
    if (size % 2 == 1) {
        return nums[(left + size / 2) % size];
    } else {
        return (double) (nums[(left + size / 2) % size] + nums[(left + (size - 1) / 2) % size]) / 2;
    }
}

public static void main(String[] args) {
    int[] arr = {6, 7, 8, 1, 2, 3, 4, 5};
    System.out.println(minNumberInRotateArray(arr));
}

}


45.给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 *O(n)*。

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。


46.高考成绩2000万数据，分数0-750，如何快速知道你的排名，如何知道任一分数排名 --->桶排序

桶[排序]()    (Bucket sort)的工作的原理：假设输入数据   服从均匀分布   ，将数据分到有限数量的桶里，每个桶再分别[排序]()（有可能再使用别的[排序]()[算法]()或是以递归方式继续使用桶[排序]()进行排）。   

    [算法]()描述：   

    设置一个定量的数组当作空桶；   

    遍历输入数据，并且把数据一个一个放到对应的桶里去；   

    对每个不是空的桶进行[排序]()；   

    从不是空的桶里把排好序的数据拼接起来。

public class Solution {
public ArrayList bucketSort(int[] scores){
//先确定最大最小值，来确定范围
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < scores.length;i++){
max = Math.max(max,scores[i]);
min = Math.min(min,scores[i]);
}
//计算出桶数
//int bucketNum = (max - min)/scores.length + 1;
//这里直接给出751个桶
int bucketNum = 751;
ArrayList<ArrayList> list = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
list.add(new ArrayList());
}

  //将每个元素放入桶
  for(int i = 0; i < scores.length;i++){
      //本题中这里放元素也可以简化
      //list.get((scores[i] - min)/bucketNum).add(scores[i]);
      list.get(scores[i]).add(scores[i]);
  }

  //桶内排序,本题中可以省略这一步
  for(int i = 0; i< list.size();i++){
      Collections.sort(list.get(i));
  } 
  return list;
}

}


47.

**最大栈（最小栈）**

使用辅助栈：
public class MaxStack{
private Stack stack;
private Stack helper;
public MaxStack(){
stack = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
if(helper.isEmpty() || helper.peek() <= x){
helper.push(x);
}
stack.push(x);
}
public void pop(){
if(stack.peek() == helper.peek()){
helper.pop();
}
stack.pop();
}
public int peek(){
if(!helper.isEmpty()){
return stack.peek();
}
throw new RuntimeException(“栈中元素为空”);

}
public int getMax(){
    if(!helper.isEmpty()){
        return helper.peek();
    }
    throw new RuntimeException("最大值栈中元素为空");
}

}
用最大值标记，存入数据栈中，空间复杂度降到O(1)
public class MaxStack {
private Stack stack;
public MaxStack(){
stack = new Stack<>();
}
int max = Integer.MIN_VALUE;
public void push(int x){
if(max <= x){
if(!stack.isEmpty()){
stack.push(max);
}
max = x;
}
stack.push(x);
}
public void pop(){
if(stack.peek() == max){
stack.pop();
max = stack.pop();
}else{
stack.pop();
}
}
public int getMax(){
return max;
}
}

1 2	48. 链表实现一个栈

public class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val =val;
}
}
public class ListToStack{
public ListToStack(){
ListNode head;
}
public void push(int x){
ListNode node = new ListNode(x);
node.next = head.next;
head.next = node;
}
public int pop(){
ListNode node = head.next;
head.next = node.next;
node.next = null;
return node.val;
}
public int peek(){
return head.next.val;
}
}


### 48.一个形如 123456789101112……的字符串，输入一个n（很大很大），输出字符串第n个字符

## 49.版本数字比较，比如"1.10.0"版本比"1.8.1"版本新，不允许使用split等函数

## 50.中缀表达式转后缀

1、任何中缀表达式都由运算数，运算符，括号（大，中，小），这三部分组成。

2、从中缀表达式的左边开始扫描（脑中自己想像的），若遇到运算数时，则直接将其输出（不压入堆栈）。

3、若遇到左括号，则将其压栈。

4、若遇到右括号，表达括号内的中缀表达式已经扫描完毕。这时需将栈顶的运算符依次弹出并输出，直至遇到左括号[左括号弹出但不输出]。

5、若遇到的是运算符：a、如果该运算符的优先级大于栈顶运算符的优先级时，将其压栈

                  b、如果该运算符的优先级小于栈顶运算符的优先级时，将栈顶运算符弹出并输出，接着和新的栈顶运算 符比较，若大于，则将其压栈，若小于，继续将栈顶运算符弹出并输出......(一直递归下去，直至运算符大于栈顶云算符为止)。

6、最后一步，若扫描到中缀表达式的末尾[即扫描结束]，若堆栈中还有存留的运算符依次弹出并输出即可。

public class hello {//100 999

public static void calculate(String string) {
    Stack<String> operator = new Stack<>();//操作符栈
    List<String> list = new ArrayList<>();//结果集
    char[] s = string.toCharArray();
    //遍历表达式
    // 1+(2-4*3)
    // 1 2 4 3 * - +
    // 1+(2-4*3)*5
    // 1 2 4 3 * - +5-
    for (int i = 0; i < s.length; i++) {
        if (s[i] == ' ')
            continue;
        if (s[i] >= '0' && s[i] <= '9'){
            StringBuilder stringBuilder = new StringBuilder();
            while (i < s.length && s[i] >= '0' && s[i] <= '9'){
                stringBuilder.append(s[i]);
                i++;
            }
            i--;
            list.add(stringBuilder.toString());
        }//正则表达式匹配数字，对应思路1
        else if (s[i] == '('){//对应思路2
            operator.push(String.valueOf(s[i]));
        }else if (s[i] == ')'){//对应思路3
            while (!operator.peek().equals("(")){
                list.add(operator.pop());
            }
            operator.pop();
        }else{//对应思路4
            while (!operator.isEmpty() && priority(operator.peek()) >= priority(String.valueOf(s[i]))){
                list.add(operator.pop());
            }
            operator.push(String.valueOf(s[i]));
        }
    }
    // 1+(2-4*3)  1 2 4 3 * - +
    // 1+(2*4-3)  1 2 4 * 3 - +
    while (!operator.isEmpty())
        list.add(operator.pop());
    System.out.println(list.size());

// Stack nums = new Stack<>();
// for (int i = 0; i < list.size(); i++) {
// if (list.get(i).equals(“+”)){
// nums.push(nums.pop() + nums.pop());
// }else if (list.get(i).equals(“-“)){
// nums.push(-(nums.pop() - nums.pop()));
// }else if (list.get(i).equals(“*”)){
// nums.push(nums.pop() * nums.pop());
// }else if (list.get(i).equals(“/“)){
// int num1 = nums.pop();
// int num2 = nums.pop();
// nums.push(num2 / num1);
// } else
// nums.push(Integer.parseInt(list.get(i)));
// }
//
// return nums.pop();//弹出栈中元素返回结果
}
//计算符优先级
private static int priority(String oper){
if (oper.equals(“+”) || oper.equals(“-“))
return 0;
else if (oper.equals(“*”) || oper.equals(“/“))
return 1;
else return -1;
}
public static void main(String[] args) {
String s=”1+(2*4-3)”;
calculate(s);
}
}


## 51.滑动窗口

某一个大文件被拆成了N个小文件，每个小文件编号从0至N-1，相应大小分别记为S(i)。给定磁盘空间为C，试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。 

滑动窗口   ：每次记录窗口内的总和，和小于C，记录剩余空间，再窗口右端右移，和大于C，就窗口左端右移，小于C情况下比较剩余空间取最小值。

public class Solution {
public int[] findMin(int[] s,int c){
int i = 0;
int j = 0;
int minValue = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
int right = 0;
while(j <= s.length){
if(sum <= c){
j++;
sum += s[j];
minValue = Math.min(minValue,c - sum);
if(minValue == c - sum){
left = i;
right = j;
}
}else{
i++;
sum -= s[i];
}
}
int nums = new int[right - left];
for(int k = left;k < right;k++){
nums[k - left] = s[k];
}
return nums;
}
}

1 2	52.求有序链表的中位数

public class Test {
//【快慢指针————求一个有序链表的中位数】
public static double sortedListMedian(ListNode head) {
if(head == null)
System.out.println(“链表不能为空！”);
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast.next == null) //说明链表有奇数个节点，此时slow正好是中位数
return slow.val * 1.0;
else //说明链表有偶数个节点，此时(slow+slow.next)/2是中位数
return (slow.val + slow.next.val) / 2.0;
}

//返回由一个数组生成的链表的头结点
private static ListNode makeListByArray(int[] array) {
    ListNode dummyHead = new ListNode(-1);
    ListNode cur = dummyHead;
    for (int i = 0; i < array.length; i++) {
        cur.next = new ListNode(array[i]);
        cur = cur.next;
    }
    return dummyHead.next;
}
//主函数
public static void main(String[] args) {
    int[] array = {0,1,2,3,4,5};
    ListNode head = makeListByArray(array);
    double ans = sortedListMedian(head);
    System.out.println(ans);
}

}

// 链表节点定义
class ListNode {
int val;
ListNode next;

public ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
}
public ListNode(int val) {
    this(val,null);
}

}

1 2	53.**题目：合并K个有序数组

输入: [[1,2,3], [1,2]]
输出: [1,1,2,2,3]


在 O(N log k) 的时间复杂度内完成：*N* 是所有数组包含的整数总数量。***k\* 是数组的个数**。

解法：N个数组进行两两合并，合并后的数组再继续执行合并过程，最后合成N*M的有序数组。可以认为合并这个递归过程发生了logN次，每一次合并的过程都是N*M个数合并，所以每一次合并的时间复杂度为N*M,总的时间复杂度就是N*M*logN

public class hello {//100 999

public static void main(String[] args) {
    int[][] arr={{1,2,3},{5,6},{3,4},{1,3}};
    int[] res=mergekSortedArrays(arr);
    System.out.println(res);
}
public static int[] mergekSortedArrays(int[][] arrays) {
    // write your code here
    if(arrays == null || arrays.length == 0)
        return null;

    return helper(arrays, 0, arrays.length-1);

}

private static int[] helper(int[][] arrays, int l, int r){
    int mid = l + (r-l)/2;
    if(l<r)
    {
        int[] left = helper(arrays, l, mid);
        int[] right = helper(arrays, mid+1, r);

        return merge2Arrays(left, right);
    }
    return arrays[l];
}

private static int[] merge2Arrays(int[] a, int[] b){
    int[] res = new int[a.length + b.length];

    int i=0, j=0;
    for(int k=0; k<res.length; k++){
        if(i >= a.length)
            res[k] = b[j++];
        else if(j >= b.length)
            res[k] = a[i++];
        else if(a[i] < b[j])
            res[k] = a[i++];
        else
            res[k] = b[j++];
    }

    return res;
}

}

1
2

public class Solution {
/**
* @param arrays: k sorted integer arrays
* @return: a sorted array
*/
public int[] mergekSortedArrays(int[][] arrays) {
// write your code here
if(arrays == null || arrays.length == 0)
return null;

        return helper(arrays, 0, arrays.length-1);

}

private int[] helper(int[][] arrays, int l, int r){
    if(l == r)
        return arrays[l];
    if(l + 1 == r)
        return merge2Arrays(arrays[l], arrays[r]);

    int mid = l + (r-l)/2;
    int[] left = helper(arrays, l, mid);
    int[] right = helper(arrays, mid+1, r);

    return merge2Arrays(left, right);
}

private int[] merge2Arrays(int[] a, int[] b){
    int[] res = new int[a.length + b.length];

    int i=0, j=0;
    for(int k=0; k<res.length; k++){
        if(i >= a.length)
            res[k] = b[j++];
        else if(j >= b.length)
            res[k] = a[i++];
        else if(a[i] < b[j])
            res[k] = a[i++];
        else
            res[k] = b[j++];
    }

    return res;
}

}

1 2	54.无序数组有多少个和为K的子数组

双指针


55.因子分解

给一个正数N，求这个N的所有的因子分解；

N = 12；

Ans = {12},{6,2},{3,4},{3,2,2}

解法：递归

package backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// https://leetcode.com/problems/factor-combinations/
public class FactorCombinations {

public static void main(String[] args) {
FactorCombinations obj = new FactorCombinations();
int n = 12;
List<List> resultList = obj.getFactors(12);
System.out.println(Arrays.toString(resultList.toArray()));
}

public List<List> getFactors(int n) {
List<List> resultList = new ArrayList<List>();
// DFS
dfs(resultList, new ArrayList(), n, 2);
//dfs1(resultList, new ArrayList(), n, 2);

return resultList;

}

private void dfs(List<List> resultList, List list, int n, int start) {
// exit
if (n == 1) {
if (list.size() > 1) {
resultList.add(new ArrayList(list));
}

  return;
}

for (int i = start; i <= n; i++) {
  if (n % i == 0) {
    list.add(i);
    dfs(resultList, list, n / i, i);

    list.remove(list.size() - 1);
  }
}

}


56.有一个日志文件，记录用户登录抖音、登出抖音的时间，求每一时刻在线人数 

   格式为uid login_time logout_time  

   输入: logs = [[1, 0, 5], [2, 0, 6], [3, 0, 3], [4, 1, 2], [5, 1, 3], [6, 2, 3], [7, 3, 4], [8, 4, 6]]  

   输出: [3, 5, 5, 3, 3, 2, 0]（我只写了O(N*M),要求时间复杂夫O(N),还没想到解法，面试官最后说可以用[动态规划]()）

57. String的ip地址转int？

[算法题](https://www.nowcoder.com/jump/super-jump/word?word=算法题)，实现 一个IP地址（10.101.102.103）转成int类型数据。 （IP地址是32个比特，int也是32个比特）

58.前序中序求后续，没有建立二叉树

/**

Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

/
class Solution {
int[] post;
int idx;
public TreeNode buildTree(int[] preorder, int[] inorder) {

if(preorder==null||preorder.length==0||inorder==null||inorder.length==0||preorder.length!=inorder.length) return null;
post=new int[preorder.length];
idx=post.length-1;
help(preorder,0,preorder.length-1,inorder,0,inorder.length-1,0,post.length-1);
for(int i:post)
{
    System.out.print(" "+i)

; }

return null;
}
// 前序 3 9 20 15 7 //
// 中序 9 3 15 20 7
// 后续 9 15 7 20 3 //  
private void help(int[] preorder,int ps,int pd,int[] inorder,int is,int id,int pLeft,int pRight)
{
    if(ps>pd || is>id) return;
    int index=0;
    while(preorder[ps]!=inorder[is+index]) index++;
    post[pRight]=preorder[ps];
    //idx-         
    help(preorder,ps+1,ps+index,inorder,is,is+index-1,pLeft,pLeft+index-1);
    //index-1;
    help(preorder,ps+index+1,pd,inorder,is+index+1,id,pLeft+index,pRight-1);
   // return root;
}

}