算法问题——数组问题

350. 两个数组的交集 II

/**
 * Copyright (C), 2018-2020
 * FileName: 两个数组的交集II
 * Author:   xjl
 * Date:     2020/9/2 14:31
 * Description:
 */
package 数组专题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class 两个数组的交集II {

    @Test
    public void test() {
        int[] array1 = {4, 9, 5};
        int[] array2 = {9, 4, 9, 8, 4};
        int[] intersect = intersect2(array1, array2);
        for (int value : intersect) {
            System.out.print(value + "--");
        }
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        //存放的结果
        HashMap map1 = new HashMap();
        for (int i = 0; i < nums1.length; i++) {
            if (!map1.containsKey(nums1[i])) {
                map1.put(nums1[i], 1);
            } else {
                map1.put(nums1[i], map1.get(nums1[i]) + 1);
            }
        }
        HashMap map2 = new HashMap();
        for (int i = 0; i < nums2.length; i++) {
            if (!map2.containsKey(nums2[i])) {
                map2.put(nums2[i], 1);
            } else {
                map2.put(nums2[i], map2.get(nums2[i]) + 1);
            }
        }
        HashMap res = new HashMap();
        for (int v2 : map2.keySet()) {
            if (map1.containsKey(v2)) {
                if (map2.get(v2) > map1.get(v2)) {
                    res.put(v2, map1.get(v2));
                } else {
                    res.put(v2, map2.get(v2));
                }
            }
        }

        ArrayList list = new ArrayList();
        for (int i : res.keySet()) {
            for (int j = 0; j < res.get(i); j++) {
                list.add(i);
            }
        }

        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    /**
     * 采用的是是一个hashmap来实现
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect2(int[] nums1, int[] nums2) {
        //存放的结果
        HashMap map1 = new HashMap();
        for (int i = 0; i < nums1.length; i++) {
            if (!map1.containsKey(nums1[i])) {
                map1.put(nums1[i], 1);
            } else {
                map1.put(nums1[i], map1.get(nums1[i]) + 1);
            }
        }
        ArrayList list = new ArrayList();

        for (int i = 0; i < nums2.length; i++) {
            if (map1.containsKey(nums2[i]) && map1.get(nums2[i]) != 0) {
                list.add(nums2[i]);
                map1.put(nums2[i], map1.get(nums2[i]) - 1);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    //先对元素进行排序
    public int[] intersect3(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] intersection = new int[Math.min(nums1.length, nums2.length)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

14. 最长公共前缀

/**
 * Copyright (C), 2018-2020
 * FileName: 最长公共前缀
 * Author:   xjl
 * Date:     2020/9/2 18:35
 * Description:
 */
package 数组专题;

import org.junit.Test;

import java.util.Arrays;

public class 最长公共前缀 {
    /**
     * 采用的是是分治理而知的思想的算法
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix4(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        } else {
            return longestCommonPrefix(strs, 0, strs.length - 1);
        }
    }

    /**
     * 递归的函数
     * @param strs
     * @param start
     * @param end
     * @return
     */
    public String longestCommonPrefix(String[] strs, int start, int end) {
        //表示一个String
        if (start == end) {
            return strs[start];
        } else {
            int mid = (end - start) / 2 + start;
            String lcpLeft = longestCommonPrefix(strs, start, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);
            //调用比较的函数
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    /**
     * 找到两个字符相同的部分
     * @param lcpLeft
     * @param lcpRight
     * @return
     */
    public String commonPrefix(String lcpLeft, String lcpRight) {
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, minLength);
    }

    /**
     * 方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，
     * 比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length(); //列数
        int count = strs.length;//行数

        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    /**
     * 将字符串排序直接比较第一个和最后一个相同的就行
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        Arrays.sort(strs);
        String world1 = strs[0];
        String world2 = strs[strs.length - 1];
        while (world2.indexOf(world1) != 0) {
            world1 = world1.substring(0, world1.length() - 1);
        }
        return world1;
    }

    /**
     * 遍历的字符串
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String s0 = strs[0];
        for (int i = 1; i < strs.length; i++) {
            //找到两个字符的公共组的 在将值复制 到下一个比较
            String s1 = strs[i];
            int k = 0, j = 0;
            while (k < s1.length() && j < s0.length()) {
                if (s0.charAt(j) != s1.charAt(j)) {
                    break;
                } else {
                    k++;
                    j++;
                }
            }
            s0 = s0.substring(0, k);
        }
        return s0;
    }

    @Test
    public void test() {
        String[] str = {"flower", "flow", "flight"};
        String s = longestCommonPrefix2(str);
        System.out.println(s);
    }
}