elric-pp / blog Goto Github PK
View Code? Open in Web Editor NEWblog
blog
常用元字符
元字符 | 说明 |
---|---|
. | 匹配除换行符以外的任意字符 |
\w | 匹配字母或数字或下划线或汉字 |
\s | 匹配任意得空白符 |
\d | 匹配数字 |
\b | 匹配单词的开始或结束 |
^ | 匹配字符串的开始 |
$ | 匹配字符串的结束 |
常用的限定符
语法 | 说明 |
---|---|
* |
重复零次或更多次 |
+ |
重复一次或更多次 |
? |
重复零次或者一次 |
{n} |
重复n次 |
{n, } |
重复n次或更多次 |
{n, m} |
重复n到m次 |
使用一组方括号来制定字符范围, 如 [aeiou]
匹配任何一个英文元音字母
分支条件指几种规则,如果满足其中任意一种规则都应该当成匹配, 具体方法是用|
把不同规则分开
将多个字符用()
包起来, 用来指定子表达式(也叫做分组), 你可以对子表达式做一些操作
常用分组语法
分类 | 语法 | 说明 |
---|---|---|
捕获 | (exp) |
匹配exp, 并捕获文本到自动命名的组里 |
(?<name>exp) |
匹配exp,并捕获文本到名称为name的组里, 也可以写成(?'name'exp) | |
(?:exp) |
匹配exp,不捕获匹配的文本, 也不给此分组分配组号 | |
零宽断言 | (?=exp) |
匹配exp前面的位置 |
(?<=exp) |
匹配exp后面的位置 | |
(?!exp) |
匹配后面跟的不是exp的位置 | |
(?<!exp) |
匹配前面不是exp的位置 | |
注释 | (?#comment) | 这种类型的分组不对正则表达式的处理产生任何影响,只提供注释供阅读 |
常用的反义代码
语法 | 说明 |
---|---|
\W |
匹配不是字母, 数字, 下划线, 汉字的字符 |
\S |
匹配任意不是空白符的字符 |
\D |
匹配任意非数字的字符 |
\B |
匹配不是单词开头或结束的位置 |
`[^x] | |
[^aeiou] |
匹配除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(第四到第五个字符)。
懒惰限定符
语法 | 说明 |
---|---|
*? |
重复任意次, 但尽可能少重复 |
+? |
重复一次或者更多次, 但尽可能少重复 |
?? |
重复0次或1次, 但尽可能少重复 |
{n} |
重复n次以上, 但尽可能少重复 |
{n,m} |
重复n到m次, 但尽可能少重复 |
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:
- You must do this in-place without making a copy of the array.
- 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++;
}
}
};
/**
* 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;
}
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;
};
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;
};
};
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;
};
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;
};
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;
};
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 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;
};
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;
};
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;
};
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.