package org.example.interview.practice;

import java.util.Arrays;

/**
 * @author xianzhe.ma
 * @date 2021/7/24
 */

public class NC_91_LONGEST_INCRE_SUBARRY {

    public static int[] LIS (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        int[] subset = new int[arr.length + 1];
        int len = 0;
        for (int i = 0; i < arr.length; i++) {
            if (subset[len] < arr[i]) {
                len += 1;
                subset[len] = arr[i];
                dp[i] = len;
            } else {
                int idx = Arrays.binarySearch(subset, 0, len, arr[i]);
                if (idx < 0) {
                    idx = -(idx + 1);
                }
                subset[idx] = arr[i];
                dp[i] = idx;
            }
        }
        int[] res = new int[len];
        for (int i = arr.length - 1; i >= 0; i--) {
            if (dp[i] == len) {
                res[--len] = arr[i];
            }
        }
        return res;
    }
    public static void printArr(int[] arr) {
        for (int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static int[] LIS2 (int[] arr) {
        int length = arr.length;
        int[] subSet = new int[length + 1];
        int[] dp = new int[length];
        int len = 0;
        for (int i= 0;i <  length; i++) {
            if (subSet[len] < arr[i]) {
                len ++;
                subSet[len] = arr[i];
                dp[i] = len;
            } else {
                int index = Arrays.binarySearch(subSet, 0,len, arr[i]);
                if (index < 0) {
                    index = -(index + 1);
                }
                subSet[index] = arr[i];
                dp[i] = index;//index就是长度，因为subSet下标0永远是0
            }
        }
        int[] res = new int[len];
        for (int i = arr.length - 1; i >= 0; i--) {
            if (dp[i] == len) {
                res[--len] = arr[i];
            }
        }
        return res;
    }
    public static void main (String[] args) {
//        int[] arr = {1,2,3,4,5,6,7};
//        int index = Arrays.binarySearch(arr, 0, arr.length, 1);
//        System.out.println(index);
        int[] arr = {2,1,5,3,6,4,8,9,7};
        printArr(LIS2(arr));

//        int[] arr2 = {1,1,2,3,4};
//        int index = Arrays.binarySearch(arr2, 0, 5, 1);
//        System.out.println(index);
    }
}

package org.example.interview.practice;

/**
 * @author xianzhe.ma
 * @date 2021/7/15
 */

public class NC_92_LCSII {

    public static String LCS (String s1, String s2) {
        // write code here
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1 == 0 || len2 == 0)
            return "-1";
        int[][] dp = new int[len1+1][len2+1];
        for(int i = 0; i < len1+1; i++){
            for(int j = 0; j < len2+1; j++){
                //初始化行列第一个元素
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        //找出一个最长的公共子序列
        StringBuilder sb = new StringBuilder();
        int s1L = len1, s2L = len2;
        while(s1L != 0 && s2L != 0){
            if (s1.charAt(s1L-1) == s2.charAt(s2L-1)){
                sb.append(s1.charAt(s1L - 1));
                s1L--;
                s2L--;
            }else{
                if (dp[s1L-1][s2L] > dp[s1L][s2L-1]){
                    s1L--;
                }else{
                    s2L--;
                }
            }
        }
        if(sb.length() == 0)
            return "-1";
        return sb.reverse().toString();
    }

    public static String LCSii (String s1, String s2) {
        // write code here
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1 == 0 || len2 == 0)
            return "-1";
        int[][] dp = new int[len1+1][len2+1];
        for(int i = 0; i < len1+1; i++){
            for(int j = 0; j < len2+1; j++){
                //初始化行列第一个元素
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        //找出一个最长的公共子序列
        StringBuilder sb = new StringBuilder();
        int s1L = len1, s2L = len2;
        while(s1L != 0 && s2L != 0){
            if (s1.charAt(s1L-1) == s2.charAt(s2L-1)){
                sb.append(s1.charAt(s1L - 1));
                s1L--;
                s2L--;
            }else{
                if (dp[s1L-1][s2L] > dp[s1L][s2L-1]){
                    s1L--;
                }else{
                    s2L--;
                }
            }
        }
        if(sb.length() == 0)
            return "-1";
        return sb.reverse().toString();
    }

    public static void main (String[] args) {
        String s1 = "1A2C3D4B56";
        String s2 = "B1D23A456A";
        System.out.println(LCS (s1, s2));

    }
}

package org.example.interview.practice;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author xianzhe.ma
 * @date 2021/11/9
 */

public class NC_93_LRU {

    public int[] LRU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<Integer, Integer>() {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > k; // 大于限定的 lru 大小时删除最老的元素
            }
        };

        for (int[] e : operators) {
            if (e[0] == 1) {
                lru.put(e[1], e[2]);
            } else {
                int value = -1;
                if (lru.containsKey(e[1])) {
                    value = lru.remove(e[1]); // 删除
                    lru.put(e[1], value); // 重新插入，成为最新的元素
                }
                res.add(value);
            }
        }

        return res.stream().mapToInt(Integer::valueOf).toArray(); // 转换为数组
    }
}