博客

博客中若有侵权或者错误的地方，请及时告知，感谢。

package top.happylaishop.demo.test.test;

import com.alibaba.fastjson.JSON;
import top.happylaishop.demo.summary.utils.CommonUtils;

public class TestArr {

    public static void main(String[] args) {
        int[] datas = new int[]{1,2,3,4,5};
        System.out.println(binarySearch(datas, 5));
        System.out.println("___________________________________________");
        int[] datas2 = new int[]{1,0,1,2,2,0,0,1};
        sortedColor(datas2);
        System.out.println(JSON.toJSONString(datas2));
        System.out.println("___________________________________________");
        int[] datas3 = new int[]{1,0,1,2,2,0,0,1};
        sortedColor2(datas3);
        System.out.println(JSON.toJSONString(datas3));
        System.out.println("___________________________________________");
        System.out.println(noRepeatLength("123ab123nsw2nf"));
        System.out.println("___________________________________________");
        int[] datas4 = new int[]{1,0,1,2,2,0,0,1};
        moveZero(datas4);
        System.out.println(JSON.toJSONString(datas4));
    }

    public static int binarySearch(int[] arr, int target){
        if(arr == null || arr.length == 0) {
            return -1;
        }
        int begin = 0;
        int end = arr.length - 1;
        while(begin <= end) {
            int mid = begin + (end - begin) / 2;
            if(target > arr[mid]) {
                begin = mid + 1;
            } else if(target < arr[mid]) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    // 对只有1，2，3元素的数组进行排序
    // (1)统计每个元素个数
    public static void sortedColor(int[] arr){
        if(arr == null || arr.length == 0) {
            return;
        }
        int[] dataCounts = new int[3];
        for(int i = 0; i < arr.length; i++) {
            dataCounts[arr[i]] = dataCounts[arr[i]] + 1;
        }
        int index = 0;
        for(int i = 0; i < dataCounts.length; i++) {
            if(dataCounts[i] < 1) continue;
            for(int j = 0; j < dataCounts[i]; j++) {
                arr[index++] = i;
            }
        }
    }

    //三路快速排序
    //[0, zero][zero, i][i, two][two, arr.length]
    // zero表示最后一个存放0的位置，two表示最后一个存放2的位置，i表示最后一个存放1的位置
    public static void sortedColor2(int[] arr){
        int zero = -1;
        int two = arr.length;
        for(int i = 0; i < two;) {
            if(arr[i] == 2) {
                CommonUtils.swap(arr, i, --two);
            } else if(arr[i] == 1) {
                i++;
            } else {
                CommonUtils.swap(arr, i, ++zero);
                i++;
            }
        }
    }

    public static int[] sortedArrSumEqualTarget(int[] arr, int target) {
        if(arr == null || arr.length == 0) return new int[]{-1, -1};
        int l = 0;
        int r = arr.length - 1;
        while(l < r) {
            int sum = arr[l] + arr[r];
            if(sum > target) {
                r--;
            } else if(sum < target) {
                l++;
            } else {
                return new int[]{l, r};
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 大于等于给定值的最小的连续子数组
     * @param target
     * @return
     */
    public static int minLengthSumGltTarget(int[] arr, int target) {
        int r = -1;
        int l = 0;
        int sum = 0;
        int res = arr.length + 1;
        while(l < arr.length) {
            if((r + 1 < arr.length) && (sum < target)) {
                r++;
                sum += arr[r];
            } else {
                sum -= arr[l];
                l++;
            }
            if(sum >= target) {
                res = Math.min(res, r - l + 1);
            }
        }
        return res == arr.length + 1 ? -1 : res;
    }

    /**
     * 不重复字符的最长连续字串
     * @param s
     * @return
     */
    public static int noRepeatLength(String s) {
        int[] datas = new int[256];
        int res = 0;
        // 从最最左边开始
        int r = -1;
        // 从最左边开始
        int l = 0;
        int length = s.length();
        while(l < length) {
            if(r + 1 < length && datas[s.charAt(r + 1)] == 0) {
                datas[s.charAt(r + 1)] = datas[s.charAt(r + 1)] + 1;
                r++;
            } else {
                datas[s.charAt(l)] = datas[s.charAt(l)] - 1;
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }

    public static void moveZero(int[] arr) {
        int r = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] != 0) {
                if(i != r) {
                    arr[r] = arr[i];
                }
                r++;
            }
        }
        for(int i = r; i < arr.length; i++) {
            arr[i++] = 0;
        }
    }
}

    public static void main(String[] args) {
        System.out.println(removeSameChar("wzcabcdebef", false));
        System.out.println(removeSameChar("wzcabcdebef", true));

    }

    public static String removeSameChar(String s, boolean isRemoveSameChar) {
        if(s == null || s.length() == 0) {
            return s;
        }
        Character[] charArr = new Character[256];
        Character[] sameCharArr = new Character[256];
        for(int i = 0; i < s.length(); i++) {
            if(charArr[s.charAt(i) - 'a'] != null) {
                sameCharArr[s.charAt(i) - 'a'] = s.charAt(i);
            }
            charArr[s.charAt(i) - 'a'] = s.charAt(i);
        }
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < charArr.length; i++) {
            if(charArr[i] != null && sameCharArr[i] == null) {
                sb.append(charArr[i]);
            }
        }
        return sb.toString();
    }
    // 排列组合 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
    public static List<List<Integer>> pailie(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> data = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            data.add(nums[i]);
        }
        doPaiLie(data, res, 0);
        return res;
    }

    private static void doPaiLie(List<Integer> data, List<List<Integer>> res, int start) {
        if (start == data.size()) {
            res.add(new ArrayList<>(data));
        } else {
            for (int i = start; i < data.size(); i++) {
                Collections.swap(data, start, i);
                doPaiLie(data, res, start + 1);
                Collections.swap(data, start, i);
            }
        }
    }

    // 不重复的数据组合 [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
    public static List<List<Integer>> ziji(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> data = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            data.add(nums[i]);
        }
        doziji(data, res, temp, 0);
        return res;
    }

    private static void doziji(List<Integer> data, List<List<Integer>> res, List<Integer> temp, int start) {
        res.add(new ArrayList<>(temp));
        for (int i = start; i < data.size(); i++) {
            temp.add(data.get(i));
            doziji(data, res, temp, i + 1);
            temp.remove(data.get(i));
        }
    }

    // 排列组合 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
    public static List<List<Integer>> pailie2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> data = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            data.add(nums[i]);
        }
        doPaiLie2(data, res, temp);
        return res;
    }

    private static void doPaiLie2(List<Integer> data, List<List<Integer>> res, List<Integer> tmp) {
        if (tmp.size() == data.size()) {
            res.add(new ArrayList<>(tmp));
        } else {
            for (int i = 0; i < data.size(); i++) {
                if (tmp.contains(data.get(i))) {
                    continue;
                }
                tmp.add(data.get(i));
                doPaiLie2(data, res, tmp);
                tmp.remove(data.get(i));
            }
        }
    }