LeetCode Notes 022

Decode String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example:

1
2
3
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* @param {string} s
* @return {string}
*/
let decodeString = function(s) {
let nums = []; // 保存数字
let ss = []; // 保存需要 repeat 的字符串
let str = ''; // 当前字符串
let ans = '';

for (let i = 0, len = s.length; i < len; i++) {
let item = s[i];

if (/[0-9]/.test(item)) {
if (i === 0 || /[0-9]/.test(s[i - 1])) {
str += item;
} else {
// s => 2[2[b]]
if (str || s[i - 1] === '[') {
if (nums.length)
ss.push(str);
else
ans += str;
}

str = item;
}
} else if (item === '[') {
nums.push(+str);
str = '';
} else if (item === ']') {
str && ss.push(str);

let count = nums.pop();
let a = ss.pop();
let tmp = a.repeat(count);

if (ss.length) { // 当前有 ss[] 栈
let last = ss.pop();
ss.push(last + tmp);
} else
ans += tmp;

str = '';
} else {
str += item;
}
}

return ans + str;
};

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
if (!s.length) return 0;
if (s[0] === '0') return 0;

var len = s.length
, dp = [];

for (var i = 0; i < len; i++) {
dp[i] = [];
if (i === 0) {
dp[i][0] = 1;
dp[i][1] = 1;
} else {
dp[i][0] = dp[i - 1][1],
dp[i][1] = 0;

if (s[i] !== '0')
dp[i][1] += dp[i - 1][1];

if (s[i - 1] !== '0') {
var num = Number(s[i - 1] + s[i]);
if (num >= 1 && num <= 26)
dp[i][1] += dp[i - 1][0];
}
}
}

return dp[len - 1][1];
};

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 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) {
node.val = node.next.val;
var tmp = node.next;
node.next = node.next.next;
tmp = null;
};

Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

  1. All letters in this word are capitals, like “USA”.
  2. All letters in this word are not capitals, like “leetcode”.
  3. Only the first letter in this word is capital if it has more than one letter, like “Google”.

Otherwise, we define that this word doesn’t use capitals in a right way.

Example 1:

1
2
Input: "USA"
Output: True

Example 2:

1
2
Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

1
2
3
4
5
6
7
8
/**
* @param {string} word
* @return {boolean}
*/
var detectCapitalUse = function(word) {
let p = /^([a-z]+|[A-Z]+|[A-Z]{1}[a-z]+)$/;
return p.test(word);
};
文章作者: Monad Kai
文章链接: onlookerliu.github.io/2018/04/02/LeetCode-Notes-022/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Code@浮生记
支付宝打赏
微信打赏