参考CS-Notes

算法思想相关

1.双指针

  1. 167.有序数组的Two Sum

    1. class Solution {
    2.  public int[] twoSum(int[] numbers, int target) {
    3.      int l = 0;
    4.      int r = numbers.length-1;
    5.      while(true) {
    6.          if(numbers[l]+numbers[r] < target) {
    7.              l++;
    8.          } else if (numbers[l]+numbers[r] > target) {
    9.              r--;
    10.          } else {
    11.              break;
    12.          }
    13.      }
    14.      return new int [] {l+1,r+1};
    15.  }
    16. }

  2. 633.两数平方和

    1. class Solution {
    2.  public boolean judgeSquareSum(int c) {
    3.      int i = 0;
    4.      int j = (int) Math.sqrt(c);
    5.      int res = 0;
    6.      boolean flag = false;
    7.      while (i <= j) {
    8.          res = i*i + j*j;
    9.          if (res == c) {
    10.              flag = true;
    11.              break;
    12.          } else if (res < c) {
    13.              i ++;
    14.          } else {
    15.              j --;
    16.          }
    17.      }
    18.      return flag;
    19.  }
    20. }

  3. 345.反转字符串中的元音字母

    1. class Solution {
    2.  public String reverseVowels(String s) {
    3.      if(s == null) return null;
    4.      int i = 0;
    5.      int j = s.length()-1;
    6.      HashSet<Character> vowels = new HashSet<> (
    7.              Arrays.asList('a','e','i','o','u','A','E','I','O','U')
    8.      );
    9.      char result[] = s.toCharArray();
    10.      while(i<=j) {
    11.          while (i<j && !vowels.contains(result[i])) {
    12.              i++;
    13.          }
    14.          while(i<j && !vowels.contains(result[j])) {
    15.              j--;
    16.          }
    17.          char tmp = result[i];
    18.          result[i] = result[j];
    19.          result[j] = tmp;
    20.          i++;
    21.          j--;
    22.      }
    23.      return new String(result);
    24.  }
    25. }

  4. 680. 验证回文字符串 Ⅱ

    1. class Solution {
    2.  public boolean isHW(String s,int i,int j) {
    3.      while(i<j) {
    4.          if(s.charAt(i) != s.charAt(j)) {
    5.              return false;
    6.          }
    7.          i ++;
    8.          j --;
    9.      }
    10.      return true;
    11.  }
    12.  public boolean validPalindrome(String s) {
    13.      int i = 0;
    14.      int j = s.length()-1;
    15.      boolean flag = true;
    16.      while(i<j) {
    17.          if(s.charAt(i) != s.charAt(j)) {
    18.              return isHW(s,i+1, j) || isHW(s, i, j-1);
    19.          }
    20.          i++;
    21.          j--;
    22.      }
    23.      return true;
    24.  }
    25. }

  5. 88.合并两个有序数组

    1. class Solution {
    2.  public void merge(int[] nums1, int m, int[] nums2, int n) {
    3.      int i = m-1;
    4.      int j = n-1;
    5.      int ij = m+n-1;
    6.      while(i>=0 || j>=0) {
    7.          if(i<0) {
    8.              nums1[ij--] = nums2[j--];
    9.          } else if(j<0){
    10.              nums1[ij--] = nums1[i--];
    11.          } else {
    12.              if(nums1[i] > nums2[j]) {
    13.                  nums1[ij--] = nums1[i--];
    14.              } else {
    15.                  nums1[ij--] = nums2[j--];
    16.              }
    17.          }
    18.      }
    19.  }
    20. }

  6. 141.环形链表

    1. public class Solution {
    2.  public boolean hasCycle(ListNode head) {
    3.      if(head == null || head.next == null) return false;
    4.      ListNode rb = head.next;
    5.      ListNode tt = head;
    6.      while (rb != tt) {
    7.          if(rb == null || rb.next == null) return false;
    8.          rb = rb.next.next;
    9.          tt = tt.next;
    10.      }
    11.      return true;
    12.  }
    13. }

  7. 524.通过删除字母匹配到字典里最长单词

    1. class Solution {
    2.  private boolean isSub(String s,String d) {
    3.      int i=0;
    4.      int j=0;
    5.      while (i<s.length() && j<d.length()) {
    6.          if(s.charAt(i++) == d.charAt(j)) {
    7.              j ++;
    8.          }
    9.      }
    10.      return j == d.length();
    11.  }
    12.  public String findLongestWord(String s, List<String> d) {
    13.      String result = "";
    14.      int maxLen = 0;
    15.      for (String x : d) {
    16.          if(isSub(s, x)) {
    17.              if(maxLen < x.length()) {
    18.                  maxLen = x.length();
    19.                  result = x;
    20.              } else if(maxLen == x.length() && result.compareTo(x) > 0) {
    21.                  result = x;
    22.              }
    23.          }
    24.      }
    25.      return result;
    26.  }
    27. }

双指针的题，一般都要从两个端点同步遍历数据，通过协调两个指针的移动与否来满足题目要求。