两个字符串是否可重组相等


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/** 1.0
* 两个字符串是否可重组相等
* 很好理解,对字符串 s 和 t 进行重排序,然后比较是否一致,返回结果。
* Created by wubin on 2017/3/12.
*/
public boolean permutation(String s, String t){
if (s.length() != t.length()) return false;
return sort(s).equals(sort(t));
}
public String sort(String str){
char[] chars = str.toCharArray();
java.util.Arrays.sort(chars);
return new String(chars);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/** 1.1
* 两个字符串是否可重组相等
* 追求效率的
* Created by wubin on 2017/3/12.
*/
public boolean permutationEffective(String s, String t){
if (s.length() != t.length()) return false;
int[] letters = new int[256];
char[] sChars = s.toCharArray();
for (char cs: sChars){
letters[cs]++;
}
for (int i = 0; i < t.length(); i++) {
int val= t.charAt(i);
if(--letters[val]<0){
return false;
}
}
return true;
}

替换空格为 %20


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/** 2.0
* 替换空格为 %20
* Created by wubin on 2017/3/12.
*/
public static char[] replaceSpaces(char[] chars, int length){
int spacesCount = 0;
int newLength = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ' '){
spacesCount++;
}
}
newLength = chars.length + (spacesCount * 2);
char[] str = new char[newLength];
for (int i = chars.length -1; i >= 0 ; i--) {
if(chars[i] != ' '){
str[newLength - 1] = chars[i];
newLength--;
}else {
newLength = newLength - 3;
str[newLength] = '%';
str[newLength+1] = '2';
str[newLength+2] = '0';
}
}
return str;
}

压缩字符串


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/** 3.0
* 压缩字符串 如aaaaaccccaaa 为 a5c4a3
* Created by wubin on 2017/3/12.
*/
public String compressBad(String str){
String newStr = "";
char last= str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last){
count++;
}else {
newStr += last + "" + count;
last = str.charAt(i);
count = 1;
}
}
return newStr + last + count;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/** 3.1
* 压缩字符串 如aaaaaccccaaa 为 a5c4a3
* 更好的做法是用StringBuffer
* Created by wubin on 2017/3/12.
*/
public String compressBetter(String str){
StringBuffer newStr = new StringBuffer();
char last= str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last){
count++;
}else {
newStr.append(last);
newStr.append(count);
last = str.charAt(i);
count = 1;
}
}
newStr.append(last);
newStr.append(count);
return newStr.toString();
}

旋转二维数组


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/** 4.0
* 旋转二维数组 其实就是 swap()
* Created by wubin on 2017/3/12.
*/
public void rotate(int[][] matrix, int n){
for (int layer = 0; layer < n / 2; ++layer) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; ++i) {
int offset = i - first;
int top = matrix[first][i];
matrix[first][i] = matrix[last - offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = top;
}
}
}

将二维数组中有 0 的行和列都清为 0


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/** 5.0
* 将二维数组中有 0 的行和列都清为 0
* Created by wubin on 2017/3/12.
*/
public void setZeros(int[][] matrix){
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0){
row[i] = true;
column[j] = true;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (row[i] || column[j]){
matrix[i][j] = 0;
}
}
}
}

确定一个字符串的所有字符是否全部不同? 不允许使用其他数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**6.0
* 这是最渣的实现,时间复杂度为O(n^2)
* @param str
* @return
*/
public static boolean isDiffChars(String str){
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
for (int j = i+1; j < chars.length; j++) {
if (chars[i] == chars [j]){
return false;
}
}
}
return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**6.1
* 这是稍好的实现,时间复杂度为O(n),空间复杂度为 O(1)
* @param str
* @return
*/
public static boolean isDiffCharsTwo(String str){
if (str.length() > 256) return false;
boolean[] asii = new boolean[256];
for (int i = 0; i < 256; i++) {
asii[i] = false;
}
for (int i = 0; i < str.length(); i++) {
int charVal = str.charAt(i);
if (asii[charVal]){
return false;
}
asii[charVal] = true;
}
return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**6.2
* 这是位的实现,时间复杂度为O(n),空间只需要用1/8
* @param str
* @return
* 核心就是 每一个 char会对应 11111...的一位(通过checker |= (1<<val)实现),如果出现重复的话,100与 111的与运算就会 >0 然后就重复了(checker & (1 << val)
*/
public static boolean idUnqueChars(String str){
if (str.length() > 256 ) return false;
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0){
return false;
}
checker |= (1 << val);
}
return true;
}

二进制相加,都为String,返回String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**7.0
* 主要逻辑涉及3点: 1. 确保a比b长 短的补0 2. 相加时 两个位 + 进位 初始进位为0,保持一致
* 3. 注意最后可能有进位,比a要长一个位
* @param a
* @param b
* @return String
*/
public static String addBinary(String a, String b) {
if (a.length() < b.length()){
String temp = a;
a = b;
b = temp;
}
int[] result = new int[a.length()];
char[] achars = a.toCharArray();
char[] bchars = new char[a.length()];
for (int i = 0; i < a.length(); i++) {
if (i < a.length() - b.length()){
bchars[i] = '0';
}else{
bchars[i] = b.charAt(i - a.length() + b.length());
}
}
int[] ains = parseCharsToInts(achars);
int[] bins = parseCharsToInts(bchars);
int res = 0;
for (int i = ains.length - 1; i >= 0; i--) {
result[i] = ains[i] ^ bins[i] ^ res;
res = getResult(ains[i],bins[i],res);
}
StringBuffer sb = new StringBuffer();
if (res == 1){
sb.append(res);
}
for (int i = 0; i < result.length; i++) {
sb.append(result[i]);
}
return sb.toString();
}
public static int getResult(int a, int b, int c){
if ( a + b + c >= 2){
return 1;
}else{
return 0;
}
}
public static int[] parseCharsToInts(char[] chars){
int[] ins = new int[chars.length];
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '0'){
ins[i] = 0;
}else if (chars[i] == '1'){
ins[i] = 1;
}
}
return ins;
}