elric-pp / blog Goto Github PK

正则表达式学习笔记

目录

1. 元字符
2. 字符转义
3. 重复
4. 字符类
5. 分支条件
6. 反义
7. 分组
8. 后向引用
9. 零宽断言
10. 注释
11. 贪婪与懒惰
12. 处理选项
13. 平衡组/递归匹配
14. 补充

元字符

常用元字符

重复

常用的限定符

字符类

使用一组方括号来制定字符范围, 如 [aeiou] 匹配任何一个英文元音字母

分支条件

分支条件指几种规则,如果满足其中任意一种规则都应该当成匹配, 具体方法是用| 把不同规则分开

分组

将多个字符用()包起来, 用来指定子表达式(也叫做分组), 你可以对子表达式做一些操作

常用分组语法

反义

常用的反义代码

后向引用

根据分组组号对分组进行引用

零宽断言

(?=exp) 断言自身的出现的位置的后面能匹配表达式exp

\b\w+(?=ing\b) 匹配以ing结尾的单词的前面部分(不包括ing), reading --> read

(?<=exp) 断言自身出现的位置的前面能匹配表达式exp

(?<=\bre)\w+\b 匹配以re开头的单词的后半部分(不包括re), reading --> ading

负向零宽断言

(?!exp) 断言此位置的前面不能匹配表达式exp, \d{3}(?!\d) 匹配三位数字, 后面不能是数字

(?<!exp) 断言此位置的前面不能匹配表达式exp, (?<![a-z])\d{7} 匹配前面不是小写字母的七位数字

贪婪和懒惰

当正则表达式中包含能接受重复的限定符时，通常的行为是（在使整个表达式能得到匹配的前提下）匹配尽可能多的字符。以这个表达式为例：a.*b，它将会匹配最长的以a开始，以b结束的字符串。如果用它来搜索aabab的话，它会匹配整个字符串aabab。这被称为贪婪匹配。

有时，我们更需要懒惰匹配，也就是匹配尽可能少的字符。前面给出的限定符都可以被转化为懒惰匹配模式，只要在它后面加上一个问号?。这样.*?就意味着匹配任意数量的重复，但是在能使整个匹配成功的前提下使用最少的重复。

a.*?b匹配最短的，以a开始，以b结束的字符串。如果把它应用于aabab的话，它会匹配aab（第一到第三个字符）和ab（第四到第五个字符）。

懒惰限定符

参考资料

deerchao的blog

目录

1. moveZeroes
2. Convert Sorted Array to Binary Search Tree
3. Remove Duplicates from Sorted Array
4. First Bad Version
5. Valid Anagram
6. Maximum Depth of Binary Tree
7. Delete Node in a Linked List
8. Same Tree
9. Invert Binary Tree
10. Lowest Common Ancestor of a Binary Search Tree
11. Number of 1 Bits

moveZeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example,

given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
  for (var i = 0, k = 0; k < nums.length; k++) {
     if (nums[i] === 0) {
        nums.push(nums.splice(i,1)[0])
        continue;
     } else {
       i++;
     }
  }
};

Convert Sorted Array to Binary Search Tree

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    return Buildtree(nums, 0, nums.length-1)
};


function Buildtree(nums, start, end) {
  if( start=== end) return new TreeNode(nums[start]);
  if (start > end) return null;
  var mid = Math.floor((start + end) / 2);
  var node = new TreeNode(nums[mid]);
  node.left = Buildtree(nums, start, mid-1);
  node.right = Buildtree(nums, mid+1, end)
  return node;
}

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,

Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var k = 1;
    for (var i = 1; i < nums.length; ++i) {
        if(nums[i] !== nums[i-1]) {
            nums[k++] = nums[i]
        }
    }
    return k;
};

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

 /**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        var left = 0;
        var right = n;
        while (right-left !== 1) {
            var mid = parseInt((left + right) / 2);
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    };
};

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,

s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

  /**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    s = s.split("").sort().join("");
    t = t.split("").sort().join("");
    return s === t;
};

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  return root ? Math.max(maxDepth(root.left), maxDepth(root.right))+1 : 0;
};

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    var nextNode = node.next;
    node.val = nextNode.val;
    node.next = nextNode.next;
};

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p===null && q===null) return true;
    if (p===null || q===null ) return false;
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); 
};

Invert Binary Tree

Invert a binary tree.

       4
     /   \
    2     7
   / \   / \
  1  3  6   9

to

         4
       /   \
      7     2
     / \   / \
    9  6  3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null ) return root;
    var tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
};

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

       _______6______
      /              \
   ___2__          ___8__
  /      \        /      \
  0      _4_     7        9
        /   \
        3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (p.val>root.val && q.val>root.val)
       return lowestCommonAncestor(root.right, p, q);

    if (p.val<root.val && q.val<root.val)
       return lowestCommonAncestor(root.left, p, q);

    return root;
};

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    var count = 0;
    n = n.toString(2);
    for (var i = 0; i < n.length; i++) {
        if(n[i] === "1") count++;
    }
    return count;
};