Leetcode题解——717/844

出其东门

发布于 2019-07-19 11:22:40

3720

发布于 2019-07-19 11:22:40

文章被收录于专栏：01二进制01二进制

717. 1比特与2比特字符

题目

https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/

题解

由于10， 11两个编码都是以1开头的，这意味着只要是以1开头的后面一个数必定是根这个1一起的字符编码。利用这一点：

用一个指针从前向后走，遇到1就走两步，遇到0就走一步，看最后是不是走到n-1的位置，说明最后的0只能是单独存在的，否则走到n的位置就说明这个0是跟前面的1一起的。

代码

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
            int i = 0;
            for (i = 0; i < bits.length - 1; ) {
                if (bits[i] == 0) {
                    i++;
                } else
                    i += 2;
            }
            System.out.println(i);
            return i == bits.length - 1;
        }
}

844. 比较含退格的字符串

题目

https://leetcode-cn.com/problems/backspace-string-compare/

题解

解法1

将字符串变成字符数组后放入ArrayList中，遍历元素，如果出现'#'，删除其前一个元素后再将其本身也删除，等遍历完成后，将最后的ArrayList变成一个字符串返回再进行比较即可。

解法2

采用栈的思想，遍历字符串，如果当前字符不是'#'则入栈，如果遇到了'#'就将前一个元素入栈，最后将栈内元素生成字符串返回进行比较即可

代码

解法1

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        System.out.println(main.backspaceCompare("ab#c", "ad#c"));
    }

    public boolean backspaceCompare(String S, String T) {
        return newString(S).equals(newString(T));
    }

    private String newString(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != '#')
                stack.push(c);
            else {
                if (!stack.isEmpty())
                    stack.pop();
            }
        }
        while (!stack.isEmpty())
            sb.append(stack.pop());
        return sb.toString();
    }
}

解法2

import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        System.out.println(main.backspaceCompare("ab#c", "ad#c"));
    }

    public boolean backspaceCompare(String S, String T) {
        return newString(S).equals(newString(T));
    }

   public String newString(String s) {
       List<Character> characters = new ArrayList<>();
       for (char c : s.toCharArray()) {
           characters.add(c);
       }

       StringBuilder sb = new StringBuilder();
       int i = 0;
       while (i < characters.size()) {
           if (characters.get(i) == '#') {
               if (i - 1 >= 0) {
                   characters.remove(i - 1);
                   i--;
               }
               characters.remove(i);
           } else {
               i++;
           }
       }
       for (char c : characters) {
           sb.append(c);
       }
       return sb.toString();
   }
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-07-06，如有侵权请联系 cloudcommunity@tencent.com 删除

https