casyup.me@outlook.com

0%

read/DecodedStringatIndex

Posted on

Decoded String at Index

这个题不是很好做 :(

my solution

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
class Solution {
public:
    string decodeAtIndex(string S, int K) {
        S.append("1");
        stack<array<int, 3>> s; // { current position, current lenth, physical position }
        long long cp = 0; // current position, it could bigger than int :(
        int pp = 0; // physical position
        while (cp < K) {
            int b = pp;
            while (S[pp] > '9') { ++pp; }
            // S[pp] will be a number
            s.push( array<int, 3>{(int)cp, pp - b, b} );
            cp += pp - b;
            cp += (S[pp] - '1') * cp;
            ++pp;
        }
        
        --K;
        while (!s.empty()) {
            auto arr = s.top();
            int b = arr[0];
            int len = b + arr[1];
            while (b <= K) {
                if (b + arr[1] > K) {
                    return { S[arr[2] - (b - K)] };
                }
                
                b += len;
                if (b > K) {
                    K = arr[0] - (b - K);
                    break;
                }
            }
            
            s.pop();
        }
        
        return {};  // should nerver be executed
    }
};

是用栈记录了位置, 然后通过计算的形式得到应有的位置.

不太好弄的是坐标的计算. 以及物理坐标和解码后坐标的理解 = =. 真的花了不少时间… 很惭愧（；´д｀）ゞ

仔细说一下细节吧. (难得有心情 (。・∀・)ノ)

1
S.append("1");

这是为了后面做准备的, 因为我的循环中假设了循环的截至位置为数字.

但是输入队列的循环截至可以不是数字, 而是字符. 如果要做这个判断的话, 需要一个分支. 很明显, 即会降低性能, 也会加深代码难度. 所以我就手动加了一个数字, 这个数字并不会影响最后的结果(因为再 constraints 里面已经保证了)

1
2
3
stack<array<int, 3>> s; // { current position, current lenth, physical position }
long long cp = 0; // current position, it could bigger than int :(
int pp = 0; // physical position

我存储了三个整数, 分别是 当前位置(解码后), 当前位置开始字符串长度, 当前物理位置(解码前)

其中前两个用于计算, 最后的用于找到对应的字符. 相对来说, 内存消耗还算比较少, 取决于字符串的长度. 但是因为题目的要求, 这肯定不会太大.

1
2
3
4
5
6
7
8
9
while (cp < K) {
	int b = pp;
	while (S[pp] > '9') { ++pp; }
	// S[pp] will be a number
	s.push( array<int, 3>{(int)cp, pp - b, b} );
	cp += pp - b;
	cp += (S[pp] - '1') * cp;
	++pp;
}

循环外部条件为是否到了 K 位置的节点. 内部条件为是否 > ‘9’. (还算挺简洁的)

S[pp] 在我加了约束后, 再结合题目的已知条件, 将会在一个数字那里停下, 所以直接用就行.

然后将其入栈. 计算下一步的位置 (这里的下一步位置是个缺陷, 因为在比较极端的情况下会溢出. 我想不出什么不加深难度, 不损耗性能的情况下规避这个问题. 最后选择了加大类型. 这可能会带来潜在的计算损耗. 但是因为不会太难, 因为现在 CPU 都支持 64 位计算. 所以应该不是什么问题).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
--K;
while (!s.empty()) {
	auto arr = s.top();
	int b = arr[0];
	int len = b + arr[1];
	while (b <= K) {
		if (b + arr[1] > K) {
			return { S[arr[2] - (b - K)] };
		}

		b += len;
		if (b > K) {
			K = arr[0] - (b - K);
			break;
		}
	}

	s.pop();
}

这是最后一个循环, 外部条件为栈是否为空. 内部条件为是否超出了所需计算的位置.

计算位置有两种可能性, 一种是在当前增加的范围内. 一种是继承自之前的字符. 第一种即刻返回即可. 而第二种需要重新计算 K. 这个计算可能会造成嵌套, 好的情况下能直接找到位置, 从而在数个空循环后找到.

还算可以, 循环的内容并不难, 计算也不多. 即使不是当前能即可返回的, 计算出来的 K 也应该可以避开一些无需的循环.

我能想到的, 最直接, 最好的方法可能就是公式了. 一种数学的方法. 这可能存在. 但我现在无心探究 (￣、￣)

the best solution

emm… 就 Submissions 而言. 它代码太长了, 而且是在用了递归的情况下, 实在不是一个好的学习案例.

Discuss 中倒是有一些可以学习的. 

1
2
3
4
5
6
7
8
9
10
11
string decodeAtIndex(string S, int K) {
	long N = 0, i;
	for (i = 0; N < K; ++i)
		N = isdigit(S[i]) ? N * (S[i] - '0') : N + 1;
	while (i--)
		if (isdigit(S[i]))
			N /= S[i] - '0', K %= N;
		else if (K % N-- == 0)
			return string(1, S[i]);
	return "lee215";
}

是的, 老夫的直觉是正确的. 是存在一种计算可以很简洁地计算出来. (因为是存在规律的).

emm… 很好!

足够简洁, 也很高效. 非常不错的算法.

那么反思一下自己. 还是缺失能够直接看透问题本质, 那种最直接, 最切入主题的方式. 练习还是不够, 思考还是不够深.