编程知识 cdmana.com

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

      

    • 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

---