编程知识 cdmana.com

Common algorithm-02 double pointer

2 Double pointer

2.1 Introduce

  • Algorithmic thought
    • Double pointers are mainly used to traverse arrays , Two pointers point to different elements , In order to accomplish the task together . It can also be extended to multiple pointers of multiple arrays .
    • If two pointers point to the same array , Traversal direction is the same and will not intersect , It is also called The sliding window ( The area surrounded by two pointers is the current window ), Often used for Interval search .
    • If two pointers point to the same array , But the traversal direction is opposite , It can be used for Search for , The array to be searched is often ordered .

2.2 Two Sum problem

167. Sum of two numbers II - Input an ordered array (Easy)

  • analysis

    • Because the given array is ordered , We can use the idea of binary search to solve problems
      • Two hands at one end and one at the end . Judgment and target The relationship between . If you compare target Big , Then the tail pointer goes forward , Or the head pointer goes back
  • Code

    public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length-1;
        while (start < end) {
            if (numbers[start] + numbers[end] < target) {
                start++;
            } else if (numbers[start] + numbers[end] > target) {
                end--;
            } else {
                return new int[]{start + 1, end + 1};
            }
        }
        return null;
    }
    
  • Be careful : The subscript returned by the title is from 1 At the beginning


2.3 Merge two ordered arrays

88. Merge two ordered arrays (Easy)

  • Ideas

    • My thoughts
    • Because these two arrays are ordered , So you just need two pointers from the beginning at the same time , Who moves who , Place elements at the same time .
    • Because of the use of nums1 To save the merged data , So you need to save the elements first
    • Time O(m+n), Space O(m)
  • Code

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] backup = new int[m];
        System.arraycopy(nums1, 0, backup, 0, m);
        int p1 = 0;
        int p2 = 0;
        int i = 0;
        while (p1 < m && p2 < n) {
            if (backup[p1] <= nums2[p2]) {
                nums1[i] = backup[p1];
                p1++;
            } else {
                nums1[i] = nums2[p2];
                p2++;
            }
            i++;
        }
        //  Suppose one of them has finished copying , There are some arrays left in the data .
        // nums1 There is already p1+p2 Data , In total, we have to copy m+n Data , The remaining amount of data is m+n-p1-p2
        if (p1 < m) {
            System.arraycopy(backup, p1, nums1, p1+p2, m+n-p1-p2);
        }
        if (p2 < n) {
            System.arraycopy(nums2, p2, nums1, p1+p2, m+n-p1-p2);
        }
    }
    
  • The optimization space is O(1) New ideas , come from LeetCode official

    • Double pointer , because nums1 from m-1 There is no data from the beginning to the end , So we can take the following ideas
      • p1 Point to nums1 Of “ tail ”, This tail has only the subscript m-1 The location of
      • p2 Point to nums2 The tail of the
      • p Pointing to nums1 Last position of
      • Who's older, who copies , And then go ahead
  • Code

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        //  Be careful : What happens after the end of the loop ?
        if (p2 >= 0) {
            System.arraycopy(nums2, 0, nums1, 0,p2 + 1);
        }
    }
    
  • Be careful : What happens after the end of the loop ?

    • nums1 Run out of , be left over nums2, The remaining elements p2+1 individual , Then copy it
    • nums2 Run out of , be left over nums1, The rest of the elements p1+1 individual . Because we use nums1 As a new container , So there's no need to operate

2.4 Speed pointer

  • KEY
    • The key to solving problems with the speed pointer is to use fast and slow It's a long way to go

142. Circular list II(Medium)

  • analysis

    • Judge if there is a ring

      • fast One go 2 Step ,slow One go 1 Step , If there are rings , So after several moves fast It's sure to catch up with slow. It's not hard to understand , If there's a ring , that fast It's bound to go on forever , In addition to fast Walking ratio slow fast , that fast It's sure to catch up with slow
    • There is no ring problem solved , So here comes the question , How to find the entrance to the ring

    • Find the entrance to the ring

      • To borrow an official picture

        fig1

      • Given first fast The length of the walk :a+n(b+c)+b,slow The length of the walk :a+b

      • because fast In steps of slow Twice as many , therefore a+n(b+c)+b=2(a+b), After simplification, we have to :a=(n-1)(b+c)+c

      • That's easy ,slow To walk again c After that, you can get to the entrance of the ring . That is to say, start from scratch c And then you can get to the entrance of the ring , So you can find the entrance to the ring

  • Code

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
        return null;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while (fast != slow && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast == slow) {
            fast = head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }
    

2.5 The sliding window

  • KEY
    • There will be two pointers in the problem of sliding window type . One for the 「 extend 」 Of existing windows right The pointer , And a for 「 shrinkage 」 Window left The pointer . At any moment , There's only one pointer moving , And the other is still .

3. Longest substring without repeating characters (Medium)

  • analysis

    • The obvious thing is , If we traverse the string . from i Start , Find a substring without repeating characters . Suppose the ending position is t
    • that , When we slide the window , from i+1 To t This substring must be a substring without repeating characters .
    • therefore , When we keep moving i, Traversing the entire string , You can find the longest , Repeatless substrings
  • Code

    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int len = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i != 0) {
                set.remove(s.charAt(i));
            }
            while (right < s.length() && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
            }
            //  The length of the substring is  right - 1 - i + 1 = right - i
            len = Math.max(len, right - i);
        }
        return len;
    }
    
  • Be careful

    • right The position where the variable exists is actually the position of the first character following the current substring , therefore , The actual range of substrings is from i To right-1, So the length of the substring is right-i, namely set Of size()

* 76. Minimum cover substring (Hard)

  • analysis

    • Two pointers left and right Make up the window , Be sure to include T All characters in .
      • If not , Then expand the window , namely right Move right ; If you include , Then narrow the window , namely left Move to the right .
    • Maintain two variables at the same time . One is used to compare the length of records , A string used to record a window
    • How to judge whether the window contains T What about all the characters in ?
      • Use one map To record T The characters and numbers in ( Why record the quantity ? because T There may be duplicate characters in )
  • Code

    public String minWindow(String s, String t) {
        int length = 1000000;
        Map<Character, Integer> tmap = new HashMap<>();
        Map<Character, Integer> smap = new HashMap<>();
    
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (!tmap.containsKey(t.charAt(i))) {
                tmap.put(c, 1);
                smap.put(c, 0);
            } else {
                tmap.replace(c, tmap.get(c) + 1);
            }
        }
        String res = "";
        int left = 0, right = -1;
        while (right < s.length()) {
            right++;
            if (right == s.length()) {
                break;
            }
            char cr = s.charAt(right);
            if (smap.containsKey(cr)) {
                smap.replace(cr, smap.get(cr) + 1);
            }
            boolean flag = check(tmap, smap);
            while (flag && left <= right) {
                char cl = s.charAt(left);
                if (right - left + 1 < length) {
                    length = right - left + 1;
                    res = s.substring(left, right+1);
                }
                if (smap.containsKey(cl)) {
                    smap.replace(cl, smap.get(cl) - 1);
                }
                //  If we zoom out the window , It is not t The characters in , So again check There must be no problem , Or you have to start again check 了 
                flag = tmap.containsKey(cl) ? check(tmap, smap) : true;
                left++;
            }
        }
        return res;
    }
    
    public boolean check(Map<Character, Integer> tmap, Map<Character, Integer> wmap) {
        for (Character character : tmap.keySet()) {
            if (!wmap.containsKey(character) || wmap.get(character) < tmap.get(character)) {
                return false;
            }
        }
        return true;
    }
    
  • Be careful :

    • When left stay p1 It's about ,right stay p2 Location time . The substring represented by the window is from [p1,p2] The string of ( contain p2). therefore , For the substring operation of , need right+1, because Java The sub string in is the selection of front close and back open
  • Optimization point ( Dig a hole )

    • The code I gave was not optimized , According to the idea given by the official explanation , There's room for optimization

    • s It contains a lot of t Characters that don't appear in , So can we deal with it first s, Only care about those t The characters in , Ignore extra characters , Then slide the window

      ….


2.6 Based on practice

367. Effective complete square number (Easy)

  • Ideas

    • Search for square root by binary search ( come from LeetCode official )
    • The left boundary is 2, The right border is num/2
      • If left < right ,mid = (left + right) /2 Judge mid*mid and target The relationship between
      • If it is greater than , be right = mid - 1; If it is less than left = mid + 1
    • Be careful :int Type squared , It's very likely to spill over , So use long Prevent overflow
  • Code

    public boolean isPerfectSquare(int num) {
        if (num == 1) {
        return true;
        }
        long left = 2;
        long right = num / 2;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long t = mid * mid;
            if (t > num) {
                right = mid - 1;
            } else if (t < num) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
    

633. Sum of squares (Medium)

  • Ideas

    • Find the nearest square to this number , And then it's written from this to n. from n Start , Bisection looks for two square numbers that meet the criteria
  • Code

    public boolean judgeSquareSum(int c) {
        if (c <= 5) {
        return c != 3;
        }
        long mid = 0;
        long left = 2;
        long right = c / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            long t = mid * mid;
            if (t > c) {
                right = mid - 1;
            } else if (t < c) {
                left = mid + 1;
            } else {
                break;
            }
        }
    
        left = 0;
        right = mid;
        while (left <= right) {
            long sum = left*left + right*right;
            mid = left + left + (right - left) / 2;
            if (sum < c) {
                left++;
            } else if (sum > c) {
                right--;
            } else {
                return true;
            }
        }
        return false;
    }
    
  • Optimize

    • If you use the built-in square root function, you can greatly improve the time efficiency

680. Verify palindrome string Ⅱ(Easy)

  • Ideas

    • The judgment of palindrome string is a classic problem that can be solved by dichotomy
    • Start to judge from end to end . If equal , Then go on to the next position .
    • If it's not equal , There are two situations : Delete left Or delete the character right Where the character is
      • No matter where the character is deleted , It's time to make a new judgment , because [0,left) and (right, s.length()-1] The characters inside have been judged , The remaining [left, right] The ones in the interval have not been judged .
      • So just judge (left, right] or [left, right) The characters in the
    • Time complexity O(n)
  • Code

    public static boolean validPalindrome(String s) {
        if (s.length() <= 2) {
            return true;
        }
        int left = 0;
        int right = s.length() - 1;
        while (left <= right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                //  Delete left 
                boolean flag1 = true;
                boolean flag2 = true;
                int newLeft = left + 1;
                int newRight = right;
                while (newLeft <= newRight) {
                    if (s.charAt(newLeft) == s.charAt(newRight)) {
                        newLeft++;
                        newRight--;
                    } else {
                        flag1 = false;
                        break;
                    }
                }
                //  Delete the right side 
                newLeft = left;
                newRight = right - 1;
                while (newLeft <= newRight) {
                    if (s.charAt(newLeft) == s.charAt(newRight)) {
                        newLeft++;
                        newRight--;
                    } else {
                        flag2 = false;
                        break;
                    }
                }
                //  As long as one of the two sides can meet the conditions , I can go back true
                return flag1 || flag2;
            }
        }
        return true;
    }
    
  • Be careful :

    • If you delete the one on the left, it can't be palindrome , Then it is necessary to judge whether the palindrome on the right is deleted . If one of them is, then the conditions are satisfied

524. Delete the longest letters from the dictionary (Medium)

  • Ideas

    • How to judge whether a string can be obtained by deleting some characters from the given string ?
      • Judgment d Whether the string in is s The subsequence .
    • How to quickly determine whether a string is a subsequence of a string ?
      • Imitate the merge sort of two ordered arrays , The time complexity is O(n),n Is the length of the string to be judged
    • Time complexity O(MN), among ,M For the dictionary d The number of characters in .N Is the longest character length in the dictionary
  • Code

    public String findLongestWord(String s, List<String> d) {
        String res = "";
        //  From the dictionary in turn d Take out the string for matching comparison 
        for (String t : d) {
            int i = 0;
            int j = 0;
            while (i < t.length() && j < s.length()) {
                if (t.charAt(i) == s.charAt(j)) {
                    i++;
                    j++;
                } else {
                    j++;
                }
            }
            //  If t When you exit when you meet the criteria ,i = t.length(), j <= s.length()
            if (i == t.length() && j <= s.length() ) {
                if (t.length() > res.length()) {
                    //  When t Is longer than res When the length of the , You can assign values directly 
                    res = t;
                } else if (t.length() == res.length()) {
                    //  When t The length of ==res When the length of the , Need to sort lexicographically  
                    String[] array = {res, t};
                    Arrays.sort(array);
                    res = array[0];
                }
            }
         }
        return res;
    }
    
  • Be careful

    • The return is Dictionary order The one with the smaller serial number , So when you give the answer , To determine the dictionary order

2.7 Advanced practice

* 340. At most K Longest substring of different characters (Hard)

  • Ideas

    • Use HashMap Record the number of characters in the substring , Because a character in a substring can be repeated many times
    • The sliding window ,start = end = 0
      • When Map The number of character types in is less than or equal to K when , enlarge a window ; Greater than K Zoom out the window when
    • The qualified substring is [start, end]
  • Code

    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) {
            return 0;
        }
        if (k >= s.length()) {
            return s.length();
        }
    
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int start = 0;
        int end = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            //  Try to c Put in map in 
            map.put(c, end);
    
            if (map.size() <= k) {
                // c After putting in, the conditions are satisfied , Keep expanding the window 
                end++;
            } else {
                maxLen = Math.max(end - start, maxLen);
                // c The condition is not satisfied after putting it in , You need to shrink the window 
                while (start <= end) {
                    char t = s.charAt(start);
                    if (map.get(t) == start) {
                        map.remove(t);
                        break;
                    }
                    start++;
                }
                maxLen = Math.max(end - start, maxLen);
                start++;
            }
        }
        if (map.size() <= k) {
            maxLen = Math.max(end - start, maxLen);
        }
        return maxLen;
    }
    
  • Pay attention to the handling of some special cases

    • s = "a",k = 0,answer = 0
    • s = "a",k >= 1,answer = 1
    • s = ”aa“, k = 1,answer = 2

版权声明
本文为[PrimaBruceXu]所创,转载请带上原文链接,感谢

Scroll to Top