89. 格雷编码
难度中等141 收藏 分享 切换为英文 关注 反馈
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数* n*，打印其格雷编码序列。格雷编码序列必须以 0 开头。
输入：1
输出：[0,1]
0
1
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。
思路 由 1->2；
0
1
在最左边+0变成
00
01
和原来不变，将最左边从0变成1.
10
11，此时01与10是连续的数值但是其有两个位数不同。因此，在将第一位从0变成1，则并对称的向上取右边的数，则能满足格雷性质！
即，用2^(k-1) 倒序加上之前的格雷序列。
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> temp = new ArrayList();
temp.add(0);
temp.add(1);
for(int i=2;i<=n;i++){
int t = 1<<(i-1);
int j = temp.size()-1;
for(int k = j;k>=0;k--){
temp.add(temp.get(k)+t);
}
}
return temp;
}
}
940. 不同的子序列 II
给定一个字符串 S，计算 S 的不同非空子序列的个数。
因为结果可能很大，所以返回答案模**** 10^9 + 7.
输入："abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
思路：动态规划；
动态规划要点：
- 把空字符串加入子序列，最后再减去。dp[0] = 1;
- 如果新增的第k个字符a是已经出现过的，假设在第i次出现过，那么第i次新增时，会把a加在i-1的结果集当中，而第k个字符a又会新增在结果集当中，造成重复。需要把这一部分减去。
动态规划状态转移方程如下：
加入的第个k字符a如果在之前没有出现过，dp[k+1] = 2×dp[k];
如果出现过， dp[k+1] = 2×dp[k]- dp[i-1];其中i为a上一次出现位置的dp索引。
class Solution {
public int distinctSubseqII(String S) {
long MOD = (long) (1e9+7);
long[] dp = new long[S.length()+1];
int n = S.length();
dp[0] = 1;
HashMap<Character,Integer> map = new HashMap();
for(int i=0;i<S.length();i++){
if(!map.containsKey(S.charAt(i))){
dp[i+1] = dp[i]*2;
}else{
dp[i+1] = dp[i]*2 - dp[map.get(S.charAt(i))-1];
}
dp[i+1] %= MOD;
map.put(S.charAt(i),i+1);
}
if(dp[n]<0) dp[n]+=MOD;
return (int) ((dp[S.length()]-1));
}
}
546. 移除盒子
给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和
输入:
[1, 3, 2, 2, 2, 3, 4, 3, 1]
输出:
23
解释:
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (33=9 分)
----> [1, 3, 3, 3, 1] (11=1 分)
----> [1, 1] (33=9 分)
----> [] (22=4 分)
思路：本题较难，需要用三维dp来记录结果。
dp[l][r][k]，其中dp[l][r]是从l起到r终，k指的是与boxes[r]相同的有多少个解。
dfs(boxes,0,boxes.length-1,0)
动态转移方程如下:
两种情况： 1、将最后的k个r直接消去。dp[l][r][k] = dp[l][r-1][0] + (k+1)^2
2、 如果前面的颜色有和第r个相同的，考虑按照该index将其分割，并将r移动到index后面。那么会有：这种方式的意思就是先将第index到第r之间的递归消除，这样多了一个连续的颜色，再消除。
dfs(boxes,0,index,k+1) + dfs(boxes,i+1,r-1,0);
由于index可能有多个，遍历取max；
代码如下：
class Solution {
int[][][] dp = new int[101][101][101]; //题目告知boxes长度最大为100；
public int removeBoxes(int[] boxes) {
int res = dfs(boxes,0,boxes.length-1,0);
return res;
}
public int dfs(int[] boxes, int l, int r, int k){
if(l>r){
return 0;
}
if(dp[l][r][k]!=0){
return dp[l][r][k];
}
while(r>1&&boxes[r]==boxes[r-1]){
r = r-1;
k = k+1;
}
int max = 0;
max = Math.max(max,dfs(boxes,l,r-1,0)+(k+1)*(k+1));
for(int i=l;i<r;i++){
if(boxes[i]==boxes[r]){
max = Math.max(max,dfs(boxes,l,i,k+1)+dfs(boxes,i+1,r-1,0));
}
}
dp[l][r][k] = max;
return max;
}
}
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
思路： 本题很自然能想到栈；类似于操作数入栈；
以实例"3[a2[c]]"为例，首先将 3 [ a 2 [ c 入栈，碰到 ] 时，将出栈直到碰到 [ 后，将数字出栈。生成一个字符串 "cc"， 这里需要注意先入先出，如2[bc]，出栈后变成cbcb。需要反转。反转后重新入栈。
然后继续 碰到 ],继续将栈内元素出栈，直到碰到[，则有。3cca，同样注意反转后入栈。
最后得到栈为{accaccacc}。此时出栈后将顺序颠倒即可。
class Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack();
String result = "";
for(int i=0;i<s.length();i++){
if(s.charAt(i)!=']'){
stack.push(s.charAt(i));
}
else{
String temp = "";
while(stack.peek()!='['){
temp = String.valueOf(stack.pop()) + temp;
}
stack.pop();
String nums = "";
while(!stack.isEmpty()&&stack.peek()>='0'&&stack.peek()<='9'){
nums = String.valueOf(stack.pop()) + nums;
}
int num = Integer.parseInt(nums);
String res = "";
for(int j=0;j<num;j++){
res += temp;
}
result = res;
char[] support = res.toCharArray();
for(char ch:support){
stack.push(ch);
}
}
}
String aaa="";
while(!stack.isEmpty()) {
aaa=stack.pop()+aaa;
}
return aaa;
}
}
379. 电话目录管理系统
设计一个电话目录管理系统，让它支持以下功能：
get: 分配给用户一个未被使用的电话号码，获取失败请返回 -1
check: 检查指定的电话号码是否被使用
release: 释放掉一个电话号码，使其能够重新被分配
// 初始化电话目录，包括 3 个电话号码：0，1 和 2。
PhoneDirectory directory = new PhoneDirectory(3);
// 可以返回任意未分配的号码，这里我们假设它返回 0。
directory.get();
// 假设，函数返回 1。
directory.get();
// 号码 2 未分配，所以返回为 true。
directory.check(2);
// 返回 2，分配后，只剩一个号码未被分配。
directory.get();
// 此时，号码 2 已经被分配，所以返回 false。
directory.check(2);
// 释放号码 2，将该号码变回未分配状态。
directory.release(2);
// 号码 2 现在是未分配状态，所以返回 true。
directory.check(2);
思路： 用一个boolean数组表示，每当get时，找到数组中为true的值，更新为false；若找不到，返回-1；代码不难，在于找到合适的数据结构来表示。如果用hashMap，则需要维护index，并且release时索引需要改变，增大了难度。
class PhoneDirectory {
boolean[] sys;
int size = 0;
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
this.sys = sys;
this.size = maxNumbers;
sys = new boolean[size];
Arrays.fill(sys,true);
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
public int get() {
for(int i=0;i<size;i++){
if(sys[i]){
sys[i] = false;
return i;
}
}
return -1;
}
/** Check if a number is available or not. */
public boolean check(int number) {
return sys[number];
}
/** Recycle or release a number. */
public void release(int number) {
sys[number] = true;
}
}
/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* boolean param_2 = obj.check(number);
* obj.release(number);
*/
835. 图像重叠
给出两个图像 A 和 B ，A 和 B 为大小相同的二维正方形矩阵。（并且为二进制矩阵，只包含0和1）。
我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。之后，该转换的重叠是指两个图像都具有 1 的位置的数目。
（请注意，转换不包括向任何方向旋转。）
最大可能的重叠是什么？
输入：A = [[1,1,0],
[0,1,0],
[0,1,0]]
B = [[0,0,0],
[0,1,1],
[0,0,1]]
输出：3
解释: 将 A 向右移动一个单位，然后向下移动一个单位。
思路： 注意该题是求移动，不存在循环的情况。因此可以用一个temp数组表示移动后的矩阵。
移动后与另一个数组比较重叠区域。注意，A、B都可以移动。求更重叠更大的那个。
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int m = A.length;
int n = A[0].length;
int max = 0;
for(int right = 0;right<n;right++){
for(int down = 0;down<m;down++){
int count = 0;
int[][] temp = new int[2*m][2*n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int x = i+down;
int y = j+right;
temp[x][y] = A[i][j];
if(B[i][j]==1&&temp[i][j]==B[i][j]){
count ++;
}
}
}
max = Math.max(max,count);
count = 0;
temp = new int[2*m][2*n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int x = i+down;
int y = j+right;
temp[x][y] = B[i][j];
if(A[i][j]==1&&temp[i][j]==A[i][j]){
count ++;
}
}
}
max = Math.max(max,count);
}
}
return max;
}
}
186. 翻转字符串里的单词 II
给定一个字符串，逐个翻转字符串中的每个单词。
输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
思路： 原地翻转；
class Solution {
public void reverseWords(char[] s) {
int left = 0;
int right = s.length-1;
reverse(s,left,right);
for(int i=0;i<right;i++){
if(s[i]==' '){
reverse(s,left,i-1);
left = i+1;
}
}
reverse(s,left,right);
}
public void reverse(char[] s ,int left ,int right){
while(left<right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
271. 字符串的编码与解码
请你设计一个算法，可以将一个 字符串列表 编码成为一个 字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。
思路：编码 加字符串列表加起来，中间用非ASCII 码分割；
解码时，不用split函数，以防止分割码直接被去除。减少了[""]的情况。
public class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String str:strs){
sb.append(str);
sb.append(Character.toString((char)257));
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0) return res;
List<Character> t = new ArrayList();
System.out.println(s);
for(int i=0;i<s.length();i++){
if(s.charAt(i)!=Character.toString((char)257).charAt(0)){
t.add(s.charAt(i));
}else{
if(t.size()!=0){
char[] a = new char[t.size()];
for(int j=0;j<t.size();j++){
a[j] = t.get(j);
}
res.add(String.valueOf(a));
}else{
res.add("");
}
t= new ArrayList();
}
}
return res;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
672. 灯泡开关 Ⅱ
现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n]，这 4 个按钮的功能如下：
将所有灯泡的状态反转（即开变为关，关变为开）
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, ...)
输入: n = 1, m = 1.
输出: 2
说明: 状态为: [开], [关]
输入: n = 2, m = 1.
输出: 3
说明: 状态为: [开, 关], [关, 开], [关, 关]
输入: n = 3, m = 1.
输出: 4
说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].
思路：如果只有前奇数翻转和偶数翻转，奇数一定和灯泡1相同，偶数一定和灯泡2相同; 如果有3k+1翻转出现，由于两次翻转抵消。假设一次。 那么 1、4、7中的奇数一定与1相同。 判断1与3是否相等，如果不等，那么3k+1翻转出现了。 那么3k+1中的偶数，一定是与2相反，其余偶数一定与2相同。 3k+1中的奇数，一定与3相同，其余奇数，一定与1相同。
因此，只需要前三个灯泡的状态，就可以确定所有灯泡的状态。
假设四种翻转分别为A、B、C、D；
若翻转次数=1；return 1；
翻转次数为1，从A、B、C、D选一个，因此在n>=3时，结果为4；
若m=2；则翻转只能取到 “” 、A、B、C、AD、BD、CD七种， 因此，在n>=3时，结果为7；
若m>=3；翻转最多取到所有情况， “” 、A、B、C、D、AD、BD、CD八种，因此，在n>=3时，结果为8；
n等于1时，最多两种；
n等于2时，最多4种。
class Solution {
public int flipLights(int n, int m) {
if(n == 0 || m == 0){
return 1;
}
if(m == 1){
return n<3 ? n+m:4;
}
else if (m == 2 ){
return n<3 ? n*m:7;
}
else{
return n<3 ? 2*n:8;
}
}
}
