一个月刷完cc150

1.3 URLify
Problem:
Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string. (Note: If implementing in Java, please use a character array so that you can perform this operation in place.)
Example:
Input: "Mr John Smith ", 13 Output: "Mr%20John%20Smith”

Analysis:
If we edit the string from end and work backwards, we can move characters without worrying about overwriting.

Code:
public void urlify(char[] str, int strLen){
  int whitespaces = 0;
  for (char c : str){
    if (c == ' ') whitespaces++;
  }
  int length = strLen + 2*whitespaces;
  str[length] = '\0';
  for (int i = strLen, j = length-1; i >= 0; i--) {
    if (str[i] == ' ') {
      str[j] = '0';
      str[j-1] = '2';
      str[j-2] = '%';
      j -= 3;
    }
    else {
      str[j] = str[i];
      j--;
    }
  }
}

1.4 Palindrome Permutation
Problem:Given a string, write a function to check if it is a permutation of a palin-drome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.
Example:
Input: Tact Coa
Output: True (permutations: "taco cat", "atco eta", etc.)

Analysis:
If no more than 1 character’s count is even, all other characters’ count is odd, then can form a palindrome.

Code:
public boolean palindromePerm(String s){
  char[] counts = new char[256];
  int even = 0;
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    counts[c]++;
  }
  for (int n : counts) {
    if (n != 0 && n % 2 == 0) even++;
  }
  return even <= 1;

}

1.5 One Away
Problem:
There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
Example:
pale, ple -> true pales, pale -> true pale, bale -> true pale, bake -> false

Analysis:
Insert and Delete are similar, because it's the situation where the difference of two strings is 1. Also check for Replace where the lengths are the same. If edit is more than 2, return false.

Code:
public boolean oneEdit(String s1, String s2){
  if (Math.abs(s1.length() - s2.length()) > 1) return false;
  boolean edited = false;
  int i = 0, j = 0;
  while (i < s1.length() && j < s2.length()){
    if (s1.charAt(i) != s2.charAt(j)) {
      if (edited) return false;
      edited = true;
      if (s1.length() > s2.length()) {
        i++;
      }
      else if (s1.length() < s2.length()) {
        j++;
      }
    }
      else {
        i++;
        j++;
      }
  }
  return true;
}

WarriorZ 发表于 2019-6-4 01:46
I finished CC189 in last winter break. But when I received some interviews and prepare for it I fin ...

cc150 and cc189,which one do you recommend, or both? or which one first? Thanks

louisgogogogo 发表于 2019/06/06 23:14:28


cc150 and cc189,which one do you recommend, or both? or which one first? Thanks

150是老版，189是新版，新版多了39道题所以叫cc189。不知道新版有没有中文版，反正我当时看的是英文版。150是有中文版的。你英文阅读没障碍就看新版的吧。

看个人啦。我个人认为还不如直接刷leetcode和学习高人的解法效果来得好。当然，当作学习资料去学习也还是不错的

1.6 String Compression

Public string compress(String s){
        if (s == null || s.length() <= 2) return s;
        StringBuilder ans = new StringBuilder();
        char last = s.charAt(0);
        int count = 1;
        for (int I = 1; I < s.length(); I++){
                if(s.charAt(i) == last){
                        I++;
                        count++;
                } else {
                        ans.append(last).append(count);
                        last = s.charAt(i);
                        count = 1;
                }
        }
        ans.append(last).append(count);
        return ans.length() < s.length()? Ans: s;
}



Public String compress(String s){
        if(s == null || s.length() <= 2) return s;
        int len = compressLen(s);
        if (len >= s.length()) return s;
        char[] ans = new char[len];
        int I = 0;
        char last = s.charAt(0);
        int count = 1;
        for (int j = 1; j < s.length(); j++){
                if (s.charAt(j) == last){
                        count++;
                } else {
                        ans[i++] = last;
                        for(char c : String.valueOf(count).toCharArray()){
                                ans[i++] = c;
                        }
                        last = s.charAt(j);
                        count = 1;
                }
        }
        ans[i++] = last;
        for(char c : String.valueOf(count).toCharArray()){
                ans[i++] = c;
        }
        return String.valueOf(ans);
}

Public int compressLen(String s){
        int len = 0;
        char last = s.charAt(0);
        int count = 1;
        for(int I = 1; I < s.length(); I++){
                if (s.charAt(i) == last){
                        count++;
                } else {
                        len += 1 + String.valueOf(count).length();
                        count = 1;
                        last = s.charAt(i);
                }
        }
        len += 1 + String.valueOf(count).length();
        return len;
}

1.8 Zero Matrix
Problem:
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

Analysis:
We can use character arrays to store columns and rows that are marked as zero.

Code:
public void zeroMatrix(int[][] matrix){
  boolean[] row = new boolean[matrix.length];
  boolean[] col = new boolean[matrix[0].length];
  for (int i = 0; i < row.length; i++){
    if (row[i]) continue;
    for (int j = 0; j < col.length; j++){
      if (col[j]) continue;
      if (matrix[i][j] == 0) {
        row[i] = true;
        col[j] = true;
      }
    }
  }
  for (int i = 0; i < row.length; i++){
    for (int j = 0; j < col.length; j++){
      if (row[i] || col[j]) {
        matrix[i][j] = 0;
      }
    }
  }
}

1.9 String Rotation
Problem:
Assumeyou have a method isSubstringwhich checks if one word is a substring of another. Given two strings, sl and s2, write code to check if s2 is a rotation of sl using only one call to isSubstring (e.g.,"waterbottle" is a rotation of"erbottlewat”).

Analysis:
For rotated string xy to yx, the yx will always be a substring of xyxy.

Code:
Public boolean isRotation(String s1, String s2){
    If (s1.length() != s2.length()) return false;
    Return isSubstring(s2, s1 + s1);
}

1.7 Rotate Matrix
Problem:
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Analysis:
The 90 degree rotation can be done by move elements clockwise layer by layer.

Code:
public void matrixRotation(int[][] matrix){
  for (int layer = 0; layer < matrix.length/2; layer++){
    for (int i = layer; i < matrix.length - layer - 1; i++) {
      int offset = i - layer, start = layer, end = matrix.length - layer - 1;
      int tmp = matrix[layer][i];
      matrix[layer][i] = matrix[end-offset][layer];
      matrix[end-offset][layer] = matrix[end][end-offset];
      matrix[end][end-offset] = matrix[i][end];
      matrix[i][end] = tmp;
    }
  }
}