NC_121_Permutation NC_122_MATCH_REGEX NC_125_MAX_LEN_SUB_ARRAY_EQUALSK

package org.example.interview.practice;

/**
 * @author xianzhe.ma
 * @date 2021/11/3
 */
import java.util.*;
public class NC_121_Permutation {

    public ArrayList Permutation(String str) {


        int length = str.length();
        ArrayList inputList = new ArrayList<>();
        for (int i = 0;i) {
            char c = str.charAt(i);
            String temp = String.valueOf(c);
            inputList.add(temp);
        }

        String[] array = new String[length];
        inputList.toArray(array);

        ArrayList result = new ArrayList<>();

        doPerm(array, 0, length, result);

        Set set = new HashSet<>();
        set.addAll(result);

        ArrayList result2 = new ArrayList<>();
        result2.addAll(set);
        return result2;
    }

    public void doPerm(String[] array, int start, int end, ArrayList result) {

        if (start == end) {
            int size = array.length;
            StringBuilder stringBuilder = new StringBuilder();
            for (int i=0;i) {
                stringBuilder.append(array[i]);
            }

            result.add(stringBuilder.toString());
            return;
        }

        for (int i= start;i) {
            swap(array, start, i);
            doPerm(array,start+1,end, result);
            swap(array, start, i);
        }

    }

    public void swap(String[] array, int i, int j) {
        String temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

package org.example.interview.practice;

/**
 * @author xianzhe.ma
 * @date 2021/8/22
 */

public class NC_122_MATCH_REGEX {
    public static boolean match (String str, String pattern) {
        // write code here
        int n = str.length();
        int m = pattern.length();
        boolean[][] f = new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                //分成空正则和非空正则两种
                if (j == 0) {
                    f[i][j] = i == 0;
                } else {
                    //非空正则分为两种情况 * 和 非*
                    if (pattern.charAt(j - 1) != '*') {
                        if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')) {
                            f[i][j] = f[i - 1][j - 1];
                        }
                    } else {
                        //碰到 * 了，分为看和不看两种情况
                        //不看
                        if (j >= 2) {
                            f[i][j] |= f[i][j - 2];
                        }
                        //看
                        if (i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[n][m];
    }

    public static void main (String[] args) {
        String str = "aaa";
        String pattern = "aa*";

        match(str, pattern);
    }
}

package org.example.interview.practice;

import java.util.HashMap;
import java.util.Map;

/**
 * @author xianzhe.ma
 * @date 2021/12/31
 * 和为K的连续子数组
 */

public class NC_125_MAX_LEN_SUB_ARRAY_EQUALSK {

    public static int maxlenEqualK(int[] arr, int k) {
        // write code here
        int len = arr.length;
        if (arr == null || len == 0) {
            return 0;
        }
        Map map = new HashMap();
        map.put(0, -1);
        int length = 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - k)) {
                length = Math.max(i - map.get(sum - k), length);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return length;
    }

    public static void main(String[] args) {
        int[] arr = {0,1,2,3};
        maxlenEqualK(arr, 3);
    }
}