题目列表

  • 5. 最长回文子串[中心扩展，dp]
  • 8. 字符串转换整数 (atoi)
  • 151. 翻转字符串里的单词

  • 165. 比较版本号

    具体代码

    5. 最长回文子串

    中心扩展,注意长度为b - a - 1 20210528_213359.mp4```java class Solution { public String longestPalindrome(String s) {

    1.   int start = 0, maxLen = 0;
    2.   for(int i = 0; i < s.length(); i++){
    3.       int a = i - 1, b = i + 1;
    4.       while(a >= 0 && b < s.length() && s.charAt(a) == s.charAt(b)) {a--; b++;}
    5.       //a + 1 b - 1; => b - a - 1
    6.       if(b - a - 1 > maxLen){
    7.           start = a + 1;
    8.           maxLen = b - a - 1;
    9.       }
    10.       a = i; b = i + 1;
    11.       while(a >= 0 && b < s.length() && s.charAt(a) == s.charAt(b)) {a--; b++;}
    12.       if(b - a - 1 > maxLen){
    13.           start = a + 1;
    14.           maxLen = b - a - 1;
    15.       }
    16.   }
    17.   return s.substring(start, start + maxLen);

    } }

    **dp**
```java
class Solution {
  public String longestPalindrome(String s) {
      int start = 0, maxLen = 0;
      boolean[][] dp = new boolean[s.length()][s.length()];
      for(int i = s.length() - 1; i >= 0; i--){
          for(int j = i; j < s.length(); j++){
              if(i == j) dp[i][j] = true;
              else if(i + 1 == j) dp[i][j] = s.charAt(i) == s.charAt(j);
              else dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];

              if(dp[i][j] && j - i + 1 > maxLen){
                  start = i;
                  maxLen = j - i + 1;
              }
          }
      }
      return s.substring(start, start + maxLen);
  }
}

    8. 字符串转换整数 (atoi)

    class Solution {
  public int myAtoi(String s) {
      char[] str = s.toCharArray();
      int k = 0;
      while(k < str.length && str[k] == ' ') k++;
      if(k == str.length) return 0;
      int f = 1;
      if(str[k] == '-') {f = -1;k++;}
      else if(str[k] == '+'){k++;}
      //数值计算
      int res = 0;
      while(k < str.length && str[k] >= '0' && str[k] <= '9'){
          int x = str[k] - '0';
          //防止溢出处理
          if(f > 0 && res > (Integer.MAX_VALUE -x)/10) {return Integer.MAX_VALUE;}
          if(f < 0 && -res < (Integer.MIN_VALUE +x)/10) {return Integer.MIN_VALUE;}
          //****特判"-2147483648"
          //INT_MAX = 2^31 − 1 = 2147483647
          //INT_MIN = -2^31 = -2147483648
          //-2147483648 上面两个if都能通过，但是下面的res是看作正数计算的
          //2147483648超过了INT_MAX，所以-2147483648要特判
          if (-res * 10 - x == Integer.MIN_VALUE) return Integer.MIN_VALUE;
          res = res*10 + x;
          k++;
      }
      return res*f;
  }
}

    151. 翻转字符串里的单词

    class Solution {
  public void reverse(char[] str, int l, int r){
      while(l < r){
          char tmp = str[l];
          str[l] = str[r];
          str[r] = tmp;
          l++; r--;
      }
  }
  public String reverseWords(String s) {
      int len = s.length();
      char[] str = s.toCharArray();
      int end = len - 1;
      while(end >= 0 && str[end] == ' ') end--;
      int p = 0, q = 0;
      while(q <= end){
          int start = p;
          while(q <= end && str[q] == ' ') q++;
          while(q <= end && str[q] != ' ') str[p++] = str[q++];
          reverse(str, start, p - 1);
          if(q <= end) str[p++] = ' ';
      }
      reverse(str, 0, p - 1);
      return new String(str, 0, p);
  }
}

    165. 比较版本号

    class Solution {
  public int compareVersion(String v1, String v2) {
       for(int i = 0,j = 0;i < v1.length() || j < v2.length();){
          int a = i,b = j;
          while(a < v1.length() && v1.charAt(a) != '.') a ++;
          while(b < v2.length() && v2.charAt(b) != '.') b ++;
          int x = a == i ? 0 : Integer.valueOf(v1.substring(i,a));
          int y = b == j ? 0 : Integer.valueOf(v2.substring(j,b));
          if(x > y)return 1;
          if(x < y)return -1;
          i = a + 1;j = b + 1;
      }
      return 0;
  }
}