Lexi's Leetcode solutions

Archive for September 2013

这个和regex的 .*不一样。这个是平时cd src*这种;?可以match任意一个字符,*可以match任意一个字符串,可以是空。

算法:下面这个算法超时,不过能写出来就不错了。每次两个字符串的第一个字母比较,若p的第一个字母是*,则一点点的chop s和p除了*剩下的recursive比较。p的那个*可以占用s的0个字符,1个字符,2个字符。。

一点优化:出现连续的*,取最右边那个就行。

public boolean isMatch(String s, String p) {
  if (s.length() == 0 && p.length() == 0)
    return true;
  if (p.length() == 0)
    return false;
  char c = p.charAt(0);
  if (s.length() != 0 && (c == '?' || c == s.charAt(0)))
    return isMatch(s.substring(1), p.substring(1));
  if (c == '*') {
    for (int i = 0; i <= s.length(); i++) { 
      // i is "* is taking up how many chars in s"
      String sLeft = "";
      if (s.length() != 0)
        sLeft = s.substring(i);
      if (isMatch(sLeft, p.substring(1)))
        return true;
     }
  }
  return false;
}
Tags:

这题正经做了一段时间;首先自己想的算法不好,不够数学;另外这个题的testcase很多情况,自己没想清楚,全是用oj来查出错误了。

数学的做法:每个zigzag(|/形状是n + n – 2的长度;除非n < 2, 则就是n本身的长度),这样可以直接在string上跳着取出应该append的index。这个有两种情况:

ABCDEFGHIJKL n = 4
-------------
A     G 
B   F H   L 
C E   I K  
D     J
  1. 第一行和最后一行每个zigzag段只要append一个就行了
  2. 中间那些行每次要append两个字母;

两个变量,想了半天。分别是“在当前段里的offset”和”在哪个zigzag段里“,但是要保证以”在那个段里“外层循环。

注意:想不明白边界条件的时候,不妨直接用if(边界在string range里),这样就能把所有出界全接住了。

public String convert(String s, int nRows) {
  if (s == null)
    return null;
  int len = nRows <= 1 ? nRows : (2 * nRows - 2);
  StringBuilder sb = new StringBuilder();
  for (int offset = 0; offset < nRows; offset++) {
    for (int zigIndex = 0; zigIndex * len < s.length(); zigIndex++) {
      int firstIndex = zigIndex * len + offset;
      if (firstIndex >= 0 && firstIndex < s.length())
        sb.append(s.charAt(firstIndex));
      if (offset > 0 && offset < nRows - 1) {
        int reverseIndex = (zigIndex + 1) * len - offset;
        if (reverseIndex >= 0 && reverseIndex < s.length())
          sb.append(s.charAt(reverseIndex));
      }
    }
  }
  return sb.toString();
}
Tags: , ,

比如{1, 2, 4, 5},3的supposed index就应该是2(把4的位置顶替了)。

facts:

  • because in the end, when p’s next is q, the mid will == p, and new left section will be [q, p](q is mid – 1 and p stays); new right section will be [q, p] (p is mid + 1 and q stays), which ever, we want to return the p because we didn’t find x!
  •  is there a possibility where in the end p’s next is not q? like p q somehow points to the same element, then it’s the same, we want to return p.
  • that’s all the possible combinations. There’s no way [p, somethinglese, q] in the end, that will always transform to scenario 1 or scenario 2.
int findSupposedIndex(int[] arr, int x, int p, int q) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
      return mid;
  else if (arr[mid] > x)
      return findSupposedIndex(arr, x, p, mid - 1);
  else
      return findSupposedIndex(arr, x, mid + 1, q);

Blog Stats

  • 221,510 hits
September 2013
M T W T F S S
 1
2345678
9101112131415
16171819202122
23242526272829
30