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;
}
}
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();
}
}