foreword

All current algorithms have been run using test cases, but 100% test cases are not guaranteed. If there are problems, please contact for criticism~

I would like to thank Zuo Dashen for giving me a new understanding of algorithms!

problem introduction

original question
Given a string chars, two characters char1, char2, find the shortest distance between char1 and char2 in chars
Such as:
chars = [1,3,3,3,2,3,1], char1 = 1, char2 = 2
The result is: 2
advanced questions
On the basis of the original problem, sacrifice space complexity in exchange for time complexity, and can achieve the shortest distance between any char1 and char2 to obtain a complexity of O(1)

solution

Original question:
1. First apply for two variables index1 and index2. index1 represents the last index of char1 found, index2 represents the last index of char2 found
2. Update index1 and index2 each time char1 and char2 are found, and then calculate the distance between index1 and index2 to find the minimum value.
advanced questions
1. Apply for a map, the key is of Char type, the value is of Map type, the mapkey of value is of Char type, and the value is of Integer type, that is, Map<Character, Map<Character, Integer>
2. Traversing chars, every time a new chars[i] is added, all key s of char[0...i] are updated, and the distance between chars[i] is recalculated
Space complexity: O(n^2), query time complexity O(1)

code writing

java language version

Original question:

   /**
     * Second round of testing: Question 1
     * @return
     */
    public static int minDisCp1(char[] chars, char c1, char c2) {
        if (chars == null || chars.length == 0) {
            return -1;
        }
        if (c1 == c2) {
            return 0;
        }
        // The most recent occurrence of c1
        int last1 = -1;
        // The most recent occurrence of c2
        int last2 = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != c1 && chars[i] != c2) {
                continue;
            }
            if (chars[i] == c1) {
                last1 = i;
                if (last2 != -1) {
                    min = Math.min(min,i - last2);
                }
            }
            if (chars[i] == c2) {
                last2 = i;
                if (last1 != -1) {
                    min = Math.min(min, i - last1);
                }
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }

advanced questions

    public static void main(String[] args) {
        //System.out.println(minDisCp1(new char[]{'1', '3', '3', '3', '2', '3', '1'}, '1', '2'));
        MinDistanceCp2 minDistanceCp2 = new MinDistanceCp2(new char[]{'1', '3', '3', '3', '2', '3', '1'});
        minDistanceCp2.getMinDis('1', '2');
    }


    /**
     * Advanced questions are implemented using tool classes
     */
    public static class MinDistanceCp2{
        private Map<Character, Map<Character, Integer>> map;

        public MinDistanceCp2(char[] chars) {
            this.map = new HashMap<>();
            init(chars);
        }

        /**
         * Initialize the statistical shortest distance to fill the map
         * @param chars
         */
        private void init(char[] chars) {
            if (chars == null || chars.length == 0) {
                return;
            }
            for (int i = 0; i < chars.length; i++) {
                if (!map.containsKey(chars[i])) {
                    map.put(chars[i], new HashMap<>());
                    // distance from self is 0
                    map.get(chars[i]).put(chars[i], 0);
                }
                dealChar(chars, i);
            }
        }

        /**
         * Traverse all arrays and update the closest distance
         * @param index
         * @Param chars
         */
        private void dealChar(char[] chars, int index) {
            for (int i = 0; i < index; i++) {
                int dis = index - i;
                Map<Character, Integer> mapI = this.map.get(chars[i]);
                Map<Character, Integer> mapIndex = this.map.get(chars[index]);
                // update at i
                if (mapI.get(chars[index]) == null || mapI.get(chars[index]) > dis) {
                    mapI.put(chars[index], dis);
                }
                // update index
                if (mapIndex.get(chars[i]) == null || mapIndex.get(chars[i]) > dis) {
                    mapIndex.put(chars[i], dis);
                }
            }
        }

        /**
         * Get the shortest distance
         * @param c1
         * @param c2
         * @return
         */
        private int getMinDis(char c1, char c2) {
            if (map.get(c1) == null || map.get(c2) == null) {
                return 0;
            }
            return map.get(c1).get(c2) == null ? -1 : map.get(c1).get(c2);
        }
    }

c language version

learning

c++ language version

learning

Thinking and perception

On the surface, this question is to calculate the shortest distance in a string, but in fact it can be abstracted into a tool class, and characters can be turned into generic types. We can use this idea to calculate the shortest distance between two objects in any object array, and the business is also There will be this demand.
Another thing to note is that for the 8 basic variables of HashMap here, due to the jvm constant pool and boxing and unboxing operations, we can directly put the constants, and when using objects as key s, there may be what you think are equal Two objects (equal in value) but can exist in the map as two key s at the same time. The reason is because the logic of hashmap to judge whether the key s are equal is:
1. First, find the coordinates of the tab in the Node list, that is, the head node in the array, through the hash value (here the hash is not the hashcode, but the XOR result of the upper 16 bits and the lower 16 bits). If p is null, then directly line 630 , indicating that the bucket is empty.
2. If it is not null, it means that the bucket has a value. At this time, the logic for judging the existence of the key is in line 633 and 634. It means that the hash is equal (conflict) and the key address in the Node object is equal or equals is true (can be rewritten ) when the two objects are equal.

Therefore, if we use an object as a key, different objects have the same value, we need to rewrite equals and hashcode, and hashcode must be rewritten to pass the judgment of line 633, which is why a question often asked in interviews: equals rewriting , Why must the hashcode be rewritten?

There will be an interpretation of the source code of the basic data structure of java later, everyone is welcome to come and guide~

write at the end

Programs and codes are only for learning and thinking, do not abuse them at will! If there are mistakes and unreasonable places, be sure to criticize and correct~
If you need git source code, please email to 2260755767@qq.com
Thanks again to Zuo Dashen for pointing out the maze of my algorithm!