当前位置:   article > 正文

算法day25

算法day25

第一题

394. 字符串解码

        解法:模拟栈的完成上述的操作;

分析:

下面以如图的字符串来分析;

        首先定义一个数字栈用来存放数字,同时定义一个容器stringbuffer栈,里面用来存放字符串;

        1、遇到数字:将这个数字进栈操作到数字栈中;

        2、遇到‘【’符号,将【符号后面的字符串提取出来,放入到字符串栈中;

        3、遇到‘】’:首先将此时字符串栈顶的字符串拿出来,进行解析,根据数字栈栈顶的数字来重复刚取出来的字符串,最后将解析好的字符串放在字符串栈顶;

        4、遇到单独的字符:将这个单独的字符串直接放在字符串栈顶字符的后面;

小细节:如果遇到的数字是非单位数,我们要能够完整的获取到这个多位数的数字;

        综上所述,代码如下:

  1. class Solution {
  2. public String decodeString(String s) {
  3. Stack<StringBuffer> st = new Stack<>();
  4. st.push(new StringBuffer());//先放一个空串
  5. Stack<Integer> nums = new Stack<>();
  6. int i = 0,n = s.length();
  7. char[] s1 = s.toCharArray();
  8. while(i < n){
  9. //遇到数字
  10. if(s1[i] >= '0' && s1[i] <= '9' ){
  11. int tmp = 0;
  12. while(i < n && s1[i] >= '0' && s1[i] <= '9' ){
  13. tmp = tmp * 10 + (s1[i] - '0');
  14. i++;
  15. }
  16. nums.push(tmp);
  17. }
  18. else if(s1[i] == '['){
  19. i++;//把后面的字符串提取出来
  20. StringBuffer tmp = new StringBuffer();
  21. while(i < n && s1[i] >= 'a' && s1[i] <= 'z' ){
  22. tmp.append(s1[i]);
  23. i++;
  24. }
  25. st.push(tmp);
  26. }
  27. else if(s1[i] == ']'){
  28. //解析字符串
  29. StringBuffer tmp = st.pop();
  30. int num = nums.pop();
  31. while(num-- != 0){
  32. st.peek().append(tmp);
  33. }
  34. i++;
  35. }
  36. else{
  37. StringBuffer tmp = new StringBuffer();
  38. while(i < n && s1[i] >= 'a' && s1[i] <= 'z' ){
  39. tmp.append(s1[i]);
  40. i++;
  41. }
  42. st.peek().append(tmp);
  43. }
  44. }
  45. return st.peek().toString();
  46. }
  47. }

        

第二题        

解法:模拟栈的基本运行逻辑

步骤:

1、让元素一直进栈操作

2、定义指针来指向popped数组的0号位置元素,在进栈后判断栈顶元素是否和出栈元素的指针所指的元素相同,如果相同,则进行出栈操作;如果不同则指针位置向后移动一个位置,接着进行入栈操作;

        综上所述,代码如下:

  1. class Solution {
  2. public boolean validateStackSequences(int[] pushed, int[] popped) {
  3. Stack<Integer> st = new Stack<>();
  4. int i = 0,n = popped.length;
  5. for(int x : pushed){
  6. st.push(x);
  7. while(!st.isEmpty() && st.peek() == popped[i]){
  8. st.pop();
  9. i++;
  10. }
  11. }
  12. return i == n;
  13. }
  14. }

ps:本次的内容就到这里了,如果对你有所帮助的话,就请一键三连哦!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/707153
推荐阅读
相关标签
  

闽ICP备14008679号