1410. HTML Entity Parser

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

• Quotation Mark: the entity is " and symbol character is ".
• Single Quote Mark: the entity is ' and symbol character is '.
• Ampersand: the entity is & and symbol character is &.
• Greater Than Sign: the entity is > and symbol character is >.
• Less Than Sign: the entity is < and symbol character is <.
• Slash: the entity is ⁄ and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "& is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the & entity by &

Example 2:

Input: text = "and I quote: "...""
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x > y && x < y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com⁄problemset⁄all"
Output: "leetcode.com/problemset/all"

Constraints:

• 1 <= text.length <= 10^5
• The string may contain any possible characters out of all the 256 ASCII characters.

给定一个HTML字符串，要求把其中的特殊符号转换为其原来的表示。

简单题，遍历字符串，找到以&开头，以;结尾的子串，根据情况把它转换为原来的字符即可。请注意，有可能该子串不属于文中6种情况中的任何一种，此时不需要转义，直接原样拷贝。代码如下：

class Solution {
public:
	string entityParser(string text) {
		int n = text.size(), i = 0;
		string ans = "";
		while (i < n) {
			while (i < n&&text[i] != '&') {
				ans.push_back(text[i]);
				++i;
			}
			if (i >= n)break;
			int j = i + 1;
			while (j < n&&text[j] != ';')++j;
			string mark = text.substr(i, j - i + 1);
			if (mark == "&quot;")ans.push_back('\"');
			else if (mark == "&apos;")ans.push_back('\'');
			else if (mark == "&amp;")ans.push_back('&');
			else if (mark == "&gt;")ans.push_back('>');
			else if (mark == "&lt;")ans.push_back('<');
			else if (mark == "&frasl;")ans.push_back('/');
			else ans += mark;
			i = j + 1;
		}
		return ans;
	}
};

本代码提交AC，用时460MS。

844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

给定两个字符串，其中包含小写字母和#，#表示删除前一个字符。问这两个字符串的最终结果是否一致。

这道题如果不考虑Follow up的话很简单，新建一个string，看到字母就push_back，看到#就pop_back，最后看剩余字符串是否相等即可。

但是Follow up要求只使用O(1)的空间，这就需要思考一下了。思路是这样的，从后往前处理两个字符串，统计#的数目，模拟删除过程，直到无法删除找到一个能被留在最终字符串中的字母，比较S和T的这个字符是否相等。完整代码如下：

class Solution {
public:
	bool backspaceCompare(string S, string T) {
		int i = S.size() - 1, j = T.size() - 1;
		while (i >= 0 || j >= 0) {
			int skipS = 0, skipT = 0;
			while (i >= 0) {
				if (S[i] == '#') {
					++skipS;
					--i;
				}
				else if (skipS > 0) {
					--skipS;
					--i;
				}
				else {
					break;
				}
			}

			while (j >= 0) {
				if (T[j] == '#') {
					++skipT;
					--j;
				}
				else if (skipT > 0) {
					--skipT;
					--j;
				}
				else {
					break;
				}
			}

			if ((i >= 0) != (j >= 0))return false;
			if (i >= 0 && S[i] != T[j])return false;
			--i;
			--j;
		}
		return true;
	}
};

本代码提交AC，用时0MS。

876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

• The number of nodes in the given list will be between 1 and 100.

给定一个单向链表，要求找到其中间节点。

简单题，快慢指针，快指针的速度是慢指针的2倍，则当快指针走到末尾时，慢指针正好指向中间位置。代码如下：

class Solution {
public:
	ListNode* middleNode(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *fast = head, *slow = head;
		while (fast->next) {
			fast = fast->next->next;
			slow = slow->next;
			if (fast == NULL)break;
		}
		return slow;
	}
};

本代码提交AC，用时0MS。