面试题随笔-21/4/4

大数打印

// 大数打印
public int[] printNumbers(int n) {
  int len = (int) Math.pow(10, n);
  int[] res = new int[len - 1];

  for (int i = 0; i < len; i++) {
    res[i - 1] = i;
  }

  return res;
}


public int[] printNumbers2(int n) {
  int len = 0;
  while (n > 0) {
    n--;
    len = len * 10 + 9;
  }

  int[] res = new int[len];
  for (int i = 1; i < len + 1; i++) {
    res[i - 1] = i;
  }
  return res;
}

public void printNumbers3(int n){
  // 声明字符数组，用来存放一个大数
  char[] number = new char[n];
  Arrays.fill(number, '0');
  while (!incrementNumber(number)) {
    saveNumber(number); // 存储数值
  }
}


private boolean incrementNumber(char[] number) {

  // 循环体退出标识
  boolean isBreak = false;

  //进位标识
  int carryFlag = 0;
  int l = number.length;

  for (int i = l - 1; i >= 0; i--) {
    //取第i位的数字转化位int
    int nSum = number[i] - '0' + carryFlag;
    if (i == l - 1) {
      //最低位加1
      ++nSum;
    }

    if (nSum >= 10) {
      if (i == 0) {
        isBreak = true;
      } else {
        //进位之后减10，并把进位标识设置为1
        nSum -= 10;
        carryFlag = 1;
        number[i] = (char) ('0' + nSum);
      }
    } else {
      number[i] = (char) (nSum + '0');
      break;
    }
  }

  return isBreak;
}

private void saveNumber(char[] number) {

  boolean isBegin0 = true;

  for (char c : number) {
    if (isBegin0 && c != '0') {
      isBegin0 = false;
    }
    if (!isBegin0) {
      System.out.print(c);
    }
  }

  System.out.println();
}

验证回文串

// 验证是否是回文串
public boolean isPalindrome(String s) {
  s = s.toLowerCase().replaceAll("[^0-9a-z]", "");

  char[] c = s.toCharArray();
  int i = 0, j = c.length - 1;

  while (i < j) {
    if (c[i] != c[j]) {
      return false;
    }
    i++;
    j--;
  }

  return true;
}

public boolean isPalindrome2(String s) {
  s = s.toLowerCase();
  char[] c = s.toCharArray();
  int i = 0;
  int j = s.length() - 1;

  while (i < j) {
    if (!((c[i] >= '0' && c[i] <= '9') || (c[i] >= 'a' && c[i] <= 'z'))) {
      i++;
      continue;
    }

    if (!((c[j] >= '0' && c[j] <= '9') || (c[j] >= 'a' && c[j] <= 'z'))) {
      j--;
      continue;
    }

    if (c[i] != c[j]) {
      return false;
    }
    i++;
    j--;
  }

  return true;
}

kmp

// 暴力匹配
public int BFSearch(String haystack, String needle) {

  char[] h1 = haystack.toCharArray();
  char[] n1 = needle.toCharArray();

  int l1 = h1.length;
  int l2 = n1.length;

  int i = 0, j = 0;
  while (i < l1 && j < l2) {
    if (h1[i] == h1[j]) {
      i++;
      j++;
    } else {
      i -= j - 1;
      j = 0;
    }
  }

  if (j == l2) {
    return i - j;
  }

  return -1;
}

// kmp匹配
public int KmpSearch(String haystack, String needle, int[] next) {
  char[] h1 = haystack.toCharArray();
  char[] n1 = needle.toCharArray();

  int l1 = h1.length;
  int l2 = n1.length;
  int i = 0, j = 0;

  while (i < l1 && j < l2) {
    if (j == -1 || h1[i] == n1[j]) {
      i++;
      j++;
    }else {
      j = next[j];
    }
  }

  if (j == l2) {
    return i - j;
  }
  return -1;
}

旋转字符串

// 旋转字符串
public boolean rotateString(String A, String B) {
  if (A.equals("") && B.equals("")) {
    return true;
  }

  int len = A.length();
  for (int i = 0; i < len; i++) {
    String first = A.substring(0, 1);
    String last = A.substring(1, len);
    A = last + first;
    if (A.equals(B)) {
      return true;
    }
  }
  return false;
}

public boolean rotateString2(String A, String B) {
  return A.length() == B.length() && (A + A).contains(B);
}

public boolean rotateString3(String a, String b) {

  char[] A = a.toCharArray();
  char[] B = b.toCharArray();

  int n = A.length;
  if (n != B.length) return false;
  if (n == 0) return true;

  int[] next = new int[n];
  next[0] = -1;
  int i = 0, j = -1;

  while (i < n - 1) {
    if (j == -1 || B[i] == B[j]) {
      ++i;
      ++j;
      next[i] = j;
    } else {
      j = next[j];
    }
  }

  i = 0;
  j = 0;
  a = a + a;
  A = a.toCharArray();
  while(i < 2 * n && j < n) {
    if (j == -1 || A[i] == B[j]) {
      ++i;
      ++j;
    } else {
      j = next[j];
    }
  }

  if(j >= n) return true;

  return false;
}

最后一个单词的长度

// 最后一个单词的长度
public int lengthOfLastWord(String s) {
  if (s == null || s.length() == 0) {
    return 0;
  }

  int count = 0;

  for (int i = s.length() - 1; i >= 0; i--) {
    if (s.charAt(i) == ' ') {
      if(count==0) continue;
      break;
    }
    count++;
  }

  return count;
}

public int lengthOfLastWord2(String s) {
  s = s.trim();
  int start = s.lastIndexOf(" ") + 1;
  return s.substring(start).length();
}

public int lengthOfLastWord3(String s) {
  String[] words = s.split("  ");
  if (words.length < 1) {
    return 0;
  }

  return words[words.length - 1].length();
}

public String trim(String s) {

  char[] value = s.toCharArray();

  int len = value.length;
  int st = 0;

  char[] val = value;

  while ((st < len) && val[st] <= ' ') {
    st++;
  }

  while ((st < len) && (val[len - 1] <= ' ')) {
    len--;
  }

  return ((st > 0) || (len < value.length)) ? s.substring(st, len) : s;
}

最大深度与DFS

// 最大深度与dfs
public int maxDepth(TreeNode root) {
  if (root == null) {
    return 0;
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

// 非递归DFS
private List<TreeNode> traversal(TreeNode root) {
  List<TreeNode> res = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  stack.add(root);

  while (!stack.empty()) {
    TreeNode node = stack.peek();
    res.add(node);
    stack.pop();

    if (node.right != null) {
      stack.push(node.right);
    }
    if (node.left != null) {
      stack.push(node.left);
    }
  }

  return res;
}

层次遍历

private static Map<Integer, List<Integer>> res = new HashMap<Integer, List<Integer>>();

public void levelOrder(TreeNode root) {
  dfs(root, 0);
}

private void dfs(TreeNode root, int level) {

  if (root == null) {
    return;
  }

  if (res.size() == level) {
    List<Integer> tmp = new ArrayList<Integer>();
    tmp.add(root.value);
    res.put(level, tmp);
  } else {
    res.get(level).add(root.value);
  }

  dfs(root.left, level + 1);
  dfs(root.right, level + 1);
}

public Map<Integer, List<Integer>> levelOrder2(TreeNode root) {

  Map<Integer, List<Integer>> result = new HashMap<Integer, List<Integer>>();

  if (root == null) {
    return result;
  }

  // 定义一个队列
  Queue<TreeNode> queue = new LinkedList<TreeNode>();
  queue.add(root);
  int level = 0;

  while (queue.size() > 0) {

    ArrayList<Integer> tmp = new ArrayList<Integer>();
    result.put(level, tmp);

    int level_length = queue.size();
    for (int i = 0; i < level_length; i++) {
      TreeNode node = queue.poll();
      tmp.add(node.value);

      if (node.left != null) {
        queue.add(node.left);
      }
      if (node.right != null) {
        queue.add(node.right);
      }
    }
    level++;
  }

  return result;
}

二叉搜索树的验证

// 二叉搜索树的验证
public boolean isValidBST(TreeNode root) {
  if (root == null) {
    return true;
  }

  return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isBST(TreeNode root, int min, int max) {
  if (root == null) {
    return true;
  }

  if (min >= root.value || max <= root.value) {
    return false;
  }

  return isBST(root.left, min, root.value) && isBST(root.right, root.value, max);
}