[LeetCode] 394. Decode String

2024-09-06 05:18

文章标签 leetcode string decode 394

本文主要是介绍[LeetCode] 394. Decode String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/queue-reconstruction-by-height/description/

#题目
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路

第一版 python

先将 peoples 排序，排序的先 ele[0] 由大到小排序，若 ele[0] 相等那么比较 ele[1]由小到大排序。

people 从大到小排序，放入 res中。
其对原res是没有影响，只需要选好新ele 插入的位置，这里只需要根据 ele[1]的下标插入即可，该下标显示了新 ele 在res前有多少个元素，大于等于新ele。

Code

import functools
class Solution:def reconstructQueue(self, people):""":type people: List[List[int]]:rtype: List[List[int]]"""people = sorted(people,key=functools.cmp_to_key(lambda x0, x1: x1[0] - x0[0]  or (x0[0] == x1[0] and x0[1] - x1[1])))res = []for ele in people:res.insert(ele[1], ele)return res

第二版 java

非递归 stack

使用了字符串 stack 记录外层字符串与数组stack 当前字符串

构思时，就考虑一层，不要考虑过多。

class Solution {public String decodeString(String s) {Stack<String> strStack = new Stack();Stack<Integer> numStack = new Stack();char[] charArr = s.toCharArray();String curStr = "";for(int i = 0 ; i < charArr.length ; i++){if(charArr[i] >= '0' && charArr[i] <= '9'){int num = 0;while(charArr[i] >= '0' && charArr[i] <= '9'){num = num *10 + (charArr[i] - '0');i++;}i--;numStack.push(num);}else if(charArr[i] == '['){strStack.push(curStr);curStr = "";}else if(charArr[i] == ']'){StringBuilder originalStr = new StringBuilder(strStack.pop());int curNum = numStack.pop();while(curNum-->0){originalStr.append(curStr);}curStr = originalStr.toString();}else{curStr += charArr[i] ;}}return curStr;}
}

递归方式

class Solution {int pos = 0;public String decodeString(String s) {int num = 0 ;StringBuilder curStr = new StringBuilder();for(; pos < s.length();pos++){char c = s.charAt(pos);if(c>= '0' && c<='9'){num = num  *10 + (c - '0');}else if(c == '['){++pos;String rStr =  decodeString(s);while(num-->0)curStr.append(rStr);num = 0;}else if(c == ']'){return curStr.toString();}else{curStr.append(c);}}return curStr.toString();}
}