leecode318

Posted on Edited on In ,

第一题 leecode318

先想写一个比较字符串

不知所谓的一些写法问题很大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var comWords = function (words1, words2) {
    let len = 0, tag1 = 0, tag2 = 0;
    if (words1.length > words2.length) {
        len = words1.length
        tag1 = words1//大
        tag2 = words2
    } else {
        len = words2.length
        tag2 = words1
        tag1 = words2 // 大
    }

    const set = new Set()
    for (let i = 0; i < tag1.len; i++) {
        set.add(tag1[i])
    }
    for (let j = 0; j < tag2.len; j++)
        if (set.has(tag2[j])){
            return 0
        }
    return 1
}

修改后

1
2
3
4
5
6
7
8
9
10
11
var comWords = function (words1, words2) {
    const set = new Set(words1);

    for (let i = 0; i < words2.length; i++) {
        if (set.has(words2[i])) {
            return 0;
        }
    }
    
    return 1;
}

然后写一个暴力的两两组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxProduct = function (words) {
    max = 0
  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (comWords(words[i], words[j])) {//以后看见这种写法,都应该优化掉
        break;
      }else {
        if(words[i].length * words[j].length > max){
          max = words[i].length * words[j].length;
        }
      }
    }
  }
  return max;
};

出问题了，输出答案有问题

1、原因：break会直接结束循环，所以输出的都是连着一起的两个值

修改后：

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
/**
 * @param {string[]} words
 * @return {number}
 */
var comWords = function (words1, words2) {
    /*
      @Description: 不相同返回1
      */
    const set = new Set(words1);
    // console.log(set);
  
    for (let j = 0; j < words2.length; j++) {
      if (set.has(words2[j])) {
        return 0;
      }
    }
    return 1;
  };  

var maxProduct = function (words) {
    max = 0
  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (comWords(words[i], words[j])) {//不相同再进行运算比较
        if(words[i].length * words[j].length > max){
          max = words[i].length * words[j].length;
          console.log(words[i], words[j]);
        }
      }
    }
  }
  return max;
};

这样执行是通过了，但提交后说超出时间限制（暴力过头了😓）

看题解有位运算

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
var maxProduct = function(words) {
    const map = new Map();
    const length = words.length;
    for (let i = 0; i < length; i++) {
        let mask = 0;
        const word = words[i];
        const wordLength = word.length;
        for (let j = 0; j < wordLength; j++) {
            mask |= 1 << (word[j].charCodeAt() - 'a'.charCodeAt());
        }
        if (wordLength > (map.get(mask) || 0)) {
            map.set(mask, wordLength);
        }
    }
    let maxProd = 0;
    const maskSet = Array.from(map.keys());
    for (const mask1 of maskSet) {
        const wordLength1 = map.get(mask1);
        for (const mask2 of maskSet) {
            if ((mask1 & mask2) === 0) {
                const wordLength2 = map.get(mask2);
                maxProd = Math.max(maxProd, wordLength1 * wordLength2);
            }
        }
    }
    return maxProd;
};