剑指 Offer II 005. 单词长度的最大乘积

这一题一看就是，通过一个hash表来进行存储，进一步，我们使用一个i32来进行存储，其中低26位足够表示26个字母了，因为每一个元素中字母不重复，因此可以这么干
判断是否存在重复元素，只需要取&即可

  1. /// 剑指 Offer II 005. 单词长度的最大乘积
  2. pub fn max_product(words: Vec<String>) -> i32 {
  3.     let mut each_word_dup = Vec::<i32>::new();
  4.     let mut res = 0;
  5.     words.iter().for_each(|ss| {
  6.         // 记录每一个string中的char的数据
  7.         let mut bits = 0;
  8.         ss.chars().for_each(|c| {
  9.             let offset = (c as usize) - ('a' as usize);
  10.             bits |= (1 << offset);                              // 老是把或写成与
  11.         });
  12.         each_word_dup.push(bits);
  13.     });
  14.     for i in 0..words.len() {
  15.         for j in (i + 1)..words.len() {
  16.             // 没有重复的时候才进行记录
  17.             if each_word_dup[i] & each_word_dup[j] == 0 {
  18.                 let temp = words[i].len() * words[j].len();
  19.                 res = res.max(temp as i32);
  20.             }
  21.         }
  22.     }
  24.     res
  25. }

注意，老是搞错&和|！！！！
优化思路可以是，使用hashMap，使得词频相同的，我们只保存最大长度的，减少一部分空间

坐座位问题

pdd的笔试题，题目大意是对于一个电影院有m个座位，当前有n个座位被坐了。假设座位顺序编号0..m，有一个座位已坐的数组used。如果某个人想查找一个座位，他的思路是，查询L..=R范围内，如果存在没有坐的座位的话就直接返回-1否则返回编号最小的空座位。这一题是比较简单的题，但是要优化时间比较麻烦，不能让用户每一次查询的时候，需要去遍历一次表，那么时间肯定不够：
这一题没完全做出来，因为给的范围很大，是long的范围，但是java不支持long index
使用一个数组标记脏座位，查询起始L与末尾R是否在两个脏区间内是O1的，因此只需要判断起始终止位置在什么区间中即可。即下图的query函数。

static class SearchLocation{
    private int[] locations;
    private int max;
    /// m为所有位置，used表示坐过的位置
    public SearchLocation(int m, int[] used) {
        Arrays.sort(used);
        locations = new int[m];
        int index = 1;
        for (int l : used) {
            if (l >= m) continue;
            if (l == 0) {
                locations[l] = index;
                continue;
            }
            if (locations[l-1] != 0) locations[l] = index;
            if (locations[l-1] == 0) {
                index ++;
                locations[l] = index;
            }
        }
        this.max = index;
        System.out.println(Arrays.toString(locations));
    }
    public void query(int start, int end) {
        if (start == end) {
            if (this.locations[start] == 0) System.out.println(start);
            else System.out.println(-1);
            return;
        }
        // 记录起始位置在location中的标记
        int s_ = locations[start];
        int e_ = locations[end];
        // 1. 如果位于同一个脏区间，返回-1
        if (s_ == e_ && s_ != 0) System.out.println(-1);
        // 2. 如果位于两个干净位置
        else if (s_ == e_ && s_ == 0) System.out.println(start);
        // 3. 如果起始位置不在脏区间
        else if (s_ == 0) System.out.println(start);
        // 4. 如果end不在脏区间或者两个都在脏区间（不同）,找到第一个干净位置
        else {
            for (int i = start; i <= end; i ++)
                if (locations[i] == 0) {
                    System.out.println(i);
                    return;
                }
        }
    }
}