Bit Manipulation

Find the Difference

/*
 * Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.
 */
public class Lc389 {
    /*
     * 思路：置换
     * 
     * 由于t比仅多一位，则将t的最后为假定成不同的字符，然后t和s做差.
     */
    public static char findTheDifference(String s, String t) {
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();

        // abcd
        // abcde
        int res = t.charAt(s.length());
        for (int i = 0; i < charS.length; i++) {
            res -= (int) charS[i];
            res += (int) charT[i];
        }

        return (char) res;
    }

    public static void main(String[] args) {
        String s = "abcd";
        String t = "abcde";
        System.out.println(findTheDifference(s, t));
    }
}

Single Number

import java.util.Arrays;

/*
 * 
 * iven a non-empty array of integers, every element appears twice except for one. Find that single one.
 *
 *

 *Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
 */
public class Lc136 {
    public static int singleNumber(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        /*
         * 三种情况 1 22 33 11 2 33 11 22 3
         */
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] != nums[i + 1] && i == 0) {
                return nums[0];
            }
            if (nums[i] != nums[i + 1] && nums[i + 1] != nums[i + 2]) {
                return nums[i + 1];
            }
        }

        return nums[nums.length - 1];
    }

    public static void main(String[] args) {
        int[] nums = { 4, 1, 2, 1, 2 };
        System.out.println(singleNumber(nums));
    }
}

Maximum Product of Word Lengths

/*
 * Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
 *    给与一个字符串数组，找到俩个单词长度乘积的最大值，要求，单词不共享相同字母，你可以认为所有的单词都是小写字母，如果没有这样的俩个三次存在则返回0；
 */
public class Lc318 {
    /*
     * 思路：在计算机中int由32位，小写的字母一个26个可以让后26为对应26个字母，对应位置由该字母则为1，反之则为0；
     * 
     * 对一个单词进行左移以及或操作知道一个单词所有字母都处理完成。一次类推
     * 
     * 比较俩个单词的对应数字进行与操作，（都为则1）如果为0，即俩个单词没有一个字母重复则进行计算
     * 
     * 注意：俩个单词必须完全不相同，没有一个字母重复才可以。
     */
    public static int maxProduct(String[] words) {
        int[] mask = new int[words.length];
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');
            }
            // 这里，最大遍历的位置为i-1
            for (int j = 0; j < i; j++) {
                if ((mask[i] & mask[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String words[] = { "abcd", "cde" };
        System.out.println(maxProduct(words));
    }
}