对《程序员面试金典（第5版）》的笔记(2)

第28页

第108页

package A20180922;
import org.junit.Test;
import java.util.Arrays;
public class Solution {

    private static boolean findElement(int[][] matrix, int ele) {
        int row = 0, col = matrix.length - 1;
        while (row < matrix.length && col > 0) {
            if (matrix[row][col] == ele)
                return true;
            else if (matrix[row][col] > ele)
                col--;
            else
                row++;
        }
        return false;
    }
   @Test
    public void test1() {
        String str = "abcdefg";
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i) - 'a';
            checker |= (1 << val);
            System.out.println(Integer.toBinaryString(checker));
        }
        // Integer.toHexString(1);
    }
   public boolean isUniqueChars2(String str) {
        if (str == null) return true;
        if (str.length() > 256) return false;
        boolean[] charSet = new boolean[256];
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i);
            if (charSet[val])
                return false;
            charSet[val] = true;
        }
        return true;
    }
   public boolean isUniqueChars(String str) {
        if (str == null) return true;
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i);
            if ((val & (1 << val)) > 0)
                return false;
            checker |= (1 << val);
        }
        return true;
    }
   // brutal force 排序后遍历
    @Test
    public void reverse() {
        String str = "abcdefghi";
        // StringBuilder sb = new StringBuilder();
        // sb.append(str).reverse().toString();
        char[] chars = str.toCharArray();
        int l = 0, r = chars.length - 1;
        while (l <= r) {
            char tmp = chars[l];
            chars[l++] = chars[r];
            chars[r--] = tmp;
        }
        String str2 = new String(chars);
        System.out.println(str2);
    }
   public boolean permutation(String s, String t) {
        if (s.length() != t.length()) return false;
        return sortString(s).equals(sortString(t));
    }
   private String sortString(String t) {
        char[] chars = t.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
   public boolean permutation2(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] cntArr = new int[256];//视编码而定
        for (char c : s.toCharArray()) {
            cntArr[c]++;
        }
        for (char c : t.toCharArray()) {
            if (--cntArr[c] < 0)
                return false;
        }
        return true;
    }
   public void replaceSpaces(char[] str, int length) {
        int spaces = 0;
        for (char c : str) {
            if (c == ' ')
                spaces++;
        }
        int newLength = length + 2 * spaces;
        str[newLength] = '\0';
        for (int i = length - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[newLength - 1] = '0';
                str[newLength - 2] = '2';
                str[newLength - 3] = '%';
                newLength = newLength - 2;
            } else {
                str[newLength - 1] = str[i];
                newLength--;
            }
        }
    }
   public String cpmpressString(String s) {
        int size = countCompression(s);
        if (s.length() <= size)
            return s;
        StringBuilder sb = new StringBuilder();
        char c = s.charAt(0);
        int cnt = 1;
        for (int i = 1; i < s.length(); i++) {
            if (c == s.charAt(i)) {
                cnt++;
            } else {
                sb.append(c);
                sb.append(cnt);
                c = s.charAt(i);
                cnt = 1;
            }
        }
        sb.append(c);
        sb.append(cnt);
        return sb.toString();
   }
   private int countCompression(String s) {
        if (s == null || s.isEmpty()) return 0;
        char last = s.charAt(0);
        int size = 0, cnt = 0;
        for (int i = 1; i < s.length(); i++) {
            if (last == s.charAt(i))
                cnt++;
            else {
                last = s.charAt(i);
                size += 1 + String.valueOf(cnt).length();
                cnt = 1;
            }
        }
        size += 1 + String.valueOf(cnt).length();
        return size;
    }
   String compressAlternate(String str) {
        int size = countCompression(str);
        if (size >= str.length())
            return str;
        char[] array = new char[size];
        int index = 0;
        char last = str.charAt(0);
        int count = 0;
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) == last)
                count++;
            else {
                index = setChar(array, last, index, count);
                last = str.charAt(i);
                count = 1;
            }
        }
        index = setChar(array, last, index, count);
        return String.valueOf(array);
    }
   private int setChar(char[] array, char last, int index, int count) {
        array[index] = last;
        index++;
        char[] cnt = String.valueOf(count).toCharArray();
        for (char x : cnt) {
            array[index] = x;
            index++;
        }
        return index;
    }
   public boolean isRotation(String s1, String s2) {
        int len = s1.length();
        if (len == s2.length() && len > 0) {
            String s1s1 = s1 + s2;
            return isSubString(s1s1, s2);
        }
        return false;
    }
   public boolean isSubString(String s1, String s2) {
        return true;
    }
   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;
                }
            }
        }
    }
}