Lexi's Leetcode solutions

Archive for the ‘leetcode’ Category

几道典型two pointers一快一慢题。记住j要匀速的走,i指向最终想要的数组的最后一个元素(或者倒数第二个,或者第一个可以被change的。。因题而异)。做的挺焦躁的,记下来对比练习:

1. Remove Elements:一个数组,删掉所有出现的x,返回新长度。

  • 两个pointer,一个正常走,一个指向真正去掉x的数组的长度。
  • public int removeElement(int[] A, int elem) {
        int i = 0;
        for (int j = 0; j < A.length; j++) {
            if (A[j] != elem) { //should be used 
                A[i] = A[j];
                i++;
            }
        }
        return i;
    }

2. 一个排好序的数组,删掉所有重复,让新数组每个数字只出现一次,返回新数组长度。不许用额外空间。

  • i指向最后一个保证valid的元素
  • j指向当前exam的元素,所以从1开始;当A[j] == A[i]的时候,说明A[j]是个invalid的,所以接着走
  • 可以看出来j肯定走的比i快,所以不用担心i的出界问题
  • public int removeDuplicates(int[] A) {
        if (A.length == 0)
            return 0;
        int i = 0; //right most valid element
        for (int j = 1; j < A.length; j++) {
            if (A[j] != A[i]) { //when not equals to right most valid, means this is also valid, extend the valid array
                i++;
                A[i] = A[j];
            }
        }
        return i + 1; 
    }

3.每个数字最多出现两次,比如1, 1, 1, 2, 2, 3 => 1, 1, 2, 2, 3

  • 同样,是当前exam的元素和valid array的最后一个(其实这里是倒数第二个)元素比较,而不是A[j]和A[j – 1]比较。后者就要混乱很多。
  • public int removeDuplicates(int[] A) {
        if (A.length < 2)
            return A.length;
        int i = 1;
        for (int j = 2; j < A.length; j++) {
            if (A[j] == A[i - 1]) {
                continue;
            } else {
                i++;
                A[i] = A[j];
            }
         }
         return i + 1;
    }

4. 单链表,删除所有出现过两次或以上的元素,比如1->1->2->2->2 => null

  • 同样,i指向最后一个valid元素,j是当前exam的
  • 但是当A[i] == A[j]的时候,i要缩短,所以要keep一个prev pointer
  • j一定要每次都往后走,保证匀速,千万别i动了j却没动。就挂在这了。
  • public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, i = head, j = head.next;
        while (j != null) {
            if (i.val == j.val) {
                while (j != null && i.val == j.val) {
                    i.next = j.next; //remove j
                    j = j.next;
                }
                prev.next = i.next; //remove i
                i = prev.next;
                j = i == null ? null : i.next;
            } else {
                j = j.next;
                i = i.next;
                prev = prev.next;
            }
        }
        return dummy.next;
    }

这题完全没印象,后来发现是之前做用了string.indexOf这个函数cheat成功了。这也是two pointers一快一慢的练习题,挺难做的,需要重做。

  • i:当前unique substring的头
  • j:当前unique substring的尾
  • 注意最后可能忘记算最后一段的长度了(因为dup那个条件已经不存在)
public int lengthOfLongestSubstring(String s) {
    int i = 0, len = 0, n = s.length();
    char A[] = s.toCharArray();
    Set<Character> set = new HashSet<Character>();
    for (int j = 0; j < n; j++) {
        if (set.contains(A[j])) { //found dup
            len = Math.max(len, j - i);
            while (i < n && A[i] != A[j]) {
                set.remove(A[i]);
                i++;
            }
            i++;
        } else {
            set.add(A[j]);
        }
    }
    return Math.max(len, n - i);
}
  • d[i][j]表示从(0, 0)到(i, j)有几种走法,因为只能从上面来或从左边来,所以每次计算只需要d[i – 1][j]和d[i, j – 1],左上角的全都浪费了。
  • f[i]表示从(0,0)到(当前row, j)有几种走法,上面来的就是自己,左边来的已经算好了,所以 f[j] = f[j] + f[j – 1];
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    // one way DP, f[i] means from (0, 0) to (currRow, i) has how many ways
    int f[] = new int[n];
    f[0] = obstacleGrid[0][0] > 0 ? 0 : 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) { //comes from above or left 
            if (obstacleGrid[i][j] > 0) {
                f[j] = 0;
            } else {
                if (j == 0) //first col only from above
                    f[j] = f[j];
                else 
                    f[j] = f[j] + f[j - 1];
            }
        }
    }
    return f[n - 1];
}
Tags: ,

这个题一开始自己做死了,后来bf给讲用stack之后就一遍过了,代码也简单很多。思路

  1. 先用/来split string
  2. 然后看每一小段,若是”.”或者是“”(说明两个/连着),不入栈;若是”..”,pop;若是正常,push
  3. 最后再用string builder把”/”和栈中元素一个一个连起来。
public String simplifyPath(String path) {
    Stack<String> s = new Stack<String>();
    String[] split = path.split("/");
    for (String a : split) {
        if (!a.equals(".") && !a.isEmpty()) {
            if (a.equals("..")) {
                if (!s.isEmpty()) {
                    s.pop();
                }
            } else {
                s.push(a);
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!s.isEmpty()) {
        sb.insert(0, s.pop());
        sb.insert(0, "/");
    }
    return sb.length() == 0 ? "/" : sb.toString();
}

Hands down,这是我leetcode做的最难的题top 5。别的都是可以用算法说得通的,这题就是纯数学。我这辈子最怕的就是数学,要死要活。

几个要点:

  1. 找没用过的里面的第(k – 1) / (n – 1)!个数字,放第一位上
  2. k = (k – 1) % (n – 1)!,第一个数字确定了,剩下这些里面重新找第k个。
  3. n每次-1,比如第一位确定后有(n-1)!种后面数字的排法,第二位也确定了后面的数字排法就又少了一位(n – 1 – 1)!

还是不是很清楚,今晚睡觉接着想。

public String getPermutation(int n, int k) {
    boolean[] used = new boolean[n];
    // used[i] means the digit i + 1 is used, e.g. used[0] means digit '1' is used
    StringBuilder sb = new StringBuilder();
    int factorial = getFactorial(n - 1);
    int originalN = n;
    while (k > 0) {
        int index = (k - 1) / factorial;
        int count = 0;
        for (int i = 0; i < originalN; i++) {
            if (used[i] == false)
                count++;
            if (index == count - 1) {
                sb.append(i + 1);
                used[i] = true;
                break;
            }
        }
        n--;
        k = (k - 1) % factorial + 1;
        if (n == 0)
            break;
        factorial /= n;
    }
    return sb.toString();
}
private int getFactorial(int n) {
    if (n == 1 || n == 0)
        return 1;
    return n * getFactorial(n - 1);
}
Tags: ,

非常非常难,用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。

算法:

  1. 首先把每个substring是不是palindrome先二维dp的做出来,参见上一题的分析。其实这一步可以合在下一步里,但是下一步本身的logic就够难想了,所以这里分开来写。
  2. 一维dp(为神马是一维啊!!头一次看这样的一维啊!!一维dp却是两层循环啊卧槽!!!),d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
  3. 把d[i]先赋成最大值。
  4. i从后往前,然后j在每个i处从前往后。这样做就能保证在i处,i + 1…j – 1的所有两两combination(中间的小节substring)都已经算出来了,就能用了。如果str[i, j]是个palindrome,那么可以在j 和j + 1中间切一刀,这样的#就是d[j + 1] + 1([i..j], 一刀, [j + 1..本来有几刀])。这样切法可能就比之前算的d[i]小了,于是update。
public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) { // i is always <= j
        for (int j = i; j < n; j++) {
            boolean isPalindrome = s.charAt(i) == s.charAt(j) 
                && (j - i < 2 || isPalin[i + 1][j - 1]);
            isPalin[i][j] = isPalindrome;
        }
    }
    int[] d = new int[n];
    // initialize as cut between every letter
    for (int i = 0; i < n; i++) {
        d[i] = n - 1 - i;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (isPalin[i][j]) {
                if (j == n - 1)
                    d[i] = 0;
                else
                    d[i] = Math.min(d[i], d[j + 1] + 1);
            }
         }
    }
    return d[0];
}

这个题第二遍做code就写的挺完美的,高兴~~几个要点:

  • 直接乘会溢出,所以每次都要两个single digit相乘,最大81,不会溢出。
  • 比如385 * 97, 就是个位=5 * 7,十位=8 * 7 + 5 * 9 ,百位=3 * 7 + 8 * 9 …
    可以每一位用一个Int表示,存在一个int[]里面。
  • 这个数组最大长度是num1.len + num2.len,比如99 * 99,最大不会超过10000,所以4位就够了。
  • 这种个位在后面的,不好做(10的0次方,可惜对应位的数组index不是0而是n-1),
    所以干脆先把string reverse了代码就清晰好多。
  • 最后结果前面的0要清掉。
public String multiply(String num1, String num2) {
    num1 = new StringBuilder(num1).reverse().toString();
    num2 = new StringBuilder(num2).reverse().toString();
    // even 99 * 99 is < 10000, so maximaly 4 digits
    int[] d = new int[num1.length() + num2.length()];
    for (int i = 0; i < num1.length(); i++) {
        int a = num1.charAt(i) - '0';
        for (int j = 0; j < num2.length(); j++) {
            int b = num2.charAt(j) - '0';
            d[i + j] += a * b;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < d.length; i++) {
        int digit = d[i] % 10;
        int carry = d[i] / 10;
        sb.insert(0, digit);
        if (i < d.length - 1)
            d[i + 1] += carry;
        }
    //trim starting zeros
    while (sb.length() > 0 && sb.charAt(0) == '0') {
        sb.deleteCharAt(0);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}
Tags:

这个题挺吓人的,后来bf给讲明白了然后记得葫芦半片的,今天自己重新想了想,还是做出来了也通过了。不过是O(M * M * N的速度,没有网上说的O(M*N),忍了,反正也能pass oj.

算法:

  1. 先用dp求一个新矩阵,d[i][j]表示以(i, j)结尾有几个连续1(在当前row)。
  2. 然后遍历这个新矩阵,在每个cell,都看看“宽度是d[i][j]的矩阵最多能有多高?“,也就是往上expand到宽度变窄为止,往下expand到宽度变窄为止,然后总高度×当前宽度就是d[i][j]所属于的矩阵的最大面积。这就是个O(M * N) * O(M)。

当时给讲的时候觉得这怎么是人类能想出来的呢?然后bf说你把二维降成一维怎么做,不也是找以当前结束的1有多长吗。然后恍然大悟,这题还是有救的。题目本身写起来细节不多,不容易出bug,两遍就过了很开心~

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0)
        return 0;
    int res = 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] d = new int[m][n];
    for (int i = 0; i < m; i++) {
        d[i][0] = matrix[i][0] - '0';
        for (int j = 1; j < n; j++) {
            d[i][j] = matrix[i][j] == '1' ? d[i][j - 1] + 1 : 0;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = Math.max(res, expand(d, i, j));
        }
    }
    return res;
}
private int expand(int[][] d, int I, int J) {
    int height = 0;
    int width = d[I][J];
    //go up
    for (int i = I - 1; i >= 0; i--) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    //go down
    for (int i = I; i < d.length; i++) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    return width * height;
}

括号题也不是只用stack才能做,这题是算长度,所以stack那种一match就俩一起pop了的方式就不适合了。求极值,一维dp最好使。

  • d[i]: 以i开头的最长valid parentheses有多长。
  • d[i] =
    • if  (str[i] == ‘)’),以右括号开头必定invalid,d[i] = 0
    • if (str[i] == ‘(‘),以左括号开头
      1. 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾,所以我们想catch((…))这种情况。j = i + 1 + d[i + 1],正好就是str[i]后面越过完整sequence的下一个,若是右括号,d[i] = 2 + d[i + 1]
      2. 除此之外,还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况,如((..))()()()。所以d[i]还要再加上j后面那一段的d[j + 1]

这个定义和最长公共字串那题的定义类似,都是“以某个固定位置开始/结束”。看两头的方式又像palindrome。从后往前的一维dp也不常见。挺好玩的,一下复习好多东西。

public int longestValidParentheses(String s) {
    if (s.length() == 0)
        return 0;
    int maxLen = 0;
    int[] d = new int[s.length()];
    // d[i] means substring starts with i has max valid lenth of d[i]
    d[s.length() - 1] = 0;
    for (int i = s.length() - 2; i >= 0; i--) {
        if (s.charAt(i) == ')')
            d[i] = 0;
        else {
            int j = (i + 1) + d[i + 1];
            if (j < s.length() && s.charAt(j) == ')') {
                d[i] = d[i + 1] + 2; //(()())的外包情况
                if (j + 1 < s.length())
                    d[i] += d[j + 1];//()()的后面还有的情况
            }
        }
        maxLen = Math.max(maxLen, d[i]);
    }
    return maxLen;
}

—————————-用stack的做法———————————–

  1. stack里面装的一直是“还没配好对的那些可怜的括号的index”
  2. 是'(‘的时候push
  3. 是’)’的时候,说明可能配对了;看stack top是不是左括号,不是的话,push当前右括号
  4. 是的话,pop那个配对的左括号,然后update res:i和top的(最后一个配不成对的)index相减,就是i属于的这一段的当前最长。如果一pop就整个栈空了,说明前面全配好对了,那res就是最大=i+1
public int longestValidParentheses(String s) {
    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    char[] arr = s.toCharArray();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
            stack.pop();
            if (stack.isEmpty())
                res = i + 1;
            else
                res = Math.max(res, i - stack.peek());
        } else {
            stack.push(i);
        }
    }
    return res;
}

这个题是非常常见的面试题,自己试着implement了两种方法,一个O(logn),一个O(n),但是写起来都不是很简洁。

O(n)的方法:binary search by start,找到一个要insert的位置(start1<start<=start2),取那个大的start2(因为它肯定会被start给replace掉,start1则不一定)。插入这个新interval,然后从头到尾检查overlap(两个参数无论谁前谁后都能用这个helper查出来),有就merge,不断吞噬overlap的。代码写起来有点长,不过思路非常清晰,不用考虑任何边界条件(什么a.start <= b.end…那些都烦死人了)。interview的时候可以写这种,因为binary search那段可能都不让你写。

还有一个trick是用iterator可以直接修改正在iterate的list,不会报modification exception,第一次用,很方便。

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    int insertPosition = insertByStart(intervals, newInterval.start, 0, intervals.size() - 1);
    intervals.add(insertPosition, newInterval);
    Iterator<Interval> it = intervals.iterator();
    Interval prev = it.next();
    while (it.hasNext()) {
        Interval curr = it.next();
        if (overlap(prev, curr)) {
            prev.start = Math.min(prev.start, curr.start);
            prev.end = Math.max(prev.end, curr.end);
            it.remove();
        } else {
            prev = curr;
        }
    }
    return intervals;
}
private int insertByStart(ArrayList<Interval> intervals, int x, int p, int q) {
    if (p > q)
        return p;
    int mid = (p + q) / 2;
    if (intervals.get(mid).start < x) {
        return insertByStart(intervals, x, mid + 1, q);
    } else {
        return insertByStart(intervals, x, p, mid - 1);
    }
}
private boolean overlap(Interval a, Interval b) {
    return within(a.start, b) || within(a.end, b) || within(b.start, a) || within(b.end, a);
}
private boolean within(int v, Interval b) {
    return v >= b.start && v <= b.end;
}

另一种方法是binary search,找出要start属于的位置,end属于的位置。但是很不好写,需要判断那些this.start >=that.end之类的,就更长了。回头看看能不能写简洁点。

Tags: , ,

Blog Stats

  • 222,235 hits
September 2021
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
27282930