2022-07-18

[Zheaoli]

2022-07-18

[restartgr]

350. 两个数组的交集 II

哈希表
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    if(nums1.length<nums2.length){
        [nums1,nums2] = [nums2,nums1];
    }
    const len1 = nums1.length
    const len2 = nums2.length
    const map = {}
    const res = []
    for(let i = 0;i < len1;i++){
        if(!map[nums1[i]]){
            map[nums1[i]] = 1
        } else{
            map[nums1[i]] ++
        }
    }
    for(let j = 0;j<len2;j++){
        if(map[nums2[j]]){
            res.push(nums2[j])
            map[nums2[j]] --
        }
    }
    return res
};

---

Wechat: Jörmungandr

[restartgr]

202. 快乐数

依然是哈希表
无限重复 === 找环
/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    let map = { }
    const getSum = (n) =>{
        let sum = 0
        while(n){
            const count = n % 10
            sum += count * count
            n = Math.floor(n / 10)
        }
        return sum
    }
    while(true){
        if(map[n]){
            return false
        }
        if(n === 1){
            return true
        }
        map[n] = 1
        n = getSum(n)
    }
};

---

Wechat: Jörmungandr

[restartgr]

454. 四数相加 II

分成两组的哈希表
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function (nums1, nums2, nums3, nums4) {
  let res = 0;
  const map = {};
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      const sum = nums1[i] + nums2[j];
      if (map[sum]) {
        map[sum]++;
      } else {
        map[sum] = 1;
      }
    }
  }
  for (let t = 0; t < nums3.length; t++) {
    for (let s = 0; s < nums4.length; s++) {
      const sum = nums3[t] + nums4[s];
      if (map[0 - sum]) {
        res += map[0 - sum];
      }
    }
  }
  return res;
};

---

Wechat: Jörmungandr

[SaraadKun]

815. 公交路线

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        //预处理routes,key为公交站编号,value为公交车编号集合
        //BFS source入队,并将source对应的所有公交车所经过的公交站入队,
        //记录公交车使用情况,避免重复搜索.记录bfs轮次即为所需乘坐的公交车数量
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = routes.length;
        for (int i = 0; i < n; i++) {
            for (int j : routes[i]) {
                List<Integer> list = map.getOrDefault(j, new ArrayList<>());
                list.add(i);
                map.put(j, list);
            }
        }
        //记录访问过的公交车编号
        boolean[] visited = new boolean[n];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{source, 0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            //数组cur[0]为站点编号,cur[1]为搭乘过的公交车数量
            int station = cur[0], step = cur[1];
            if (station == target) {
                return step;
            }
            //找到所有途径当前站点公交车,将这些公交车所经过的站点全部入队,并标记公交车已处理过
            for (int bus : map.get(station)) {
                if (!visited[bus]) {
                    for (int ns : routes[bus]) {
                        q.offer(new int[]{ns, step + 1});
                    }
                }
                visited[bus] = true;
            }
        }
        return -1;
    }
}

---

WeChat: Saraad

[restartgr]

15. 三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a,b)=>a-b)
    const res = []
    for(let i = 0;i+2<nums.length;i++){
        // 去重
        if(nums[i] === nums[i-1]){
            continue
        }
        let slow = i + 1
        let fast = nums.length -1
        while(slow<fast){
            sum = nums[i]+nums[slow]+nums[fast]
            if(sum<0){
                slow ++
            } else if(sum>0){
                fast --
            } else{
                res.push([nums[i],nums[slow],nums[fast]])
                // 去重
                while(slow<fast && nums[slow] === nums[slow+1]){
                    slow ++
                }
                while(slow<fast && nums[fast] === nums[fast-1]){
                    fast --
                }
                // 移到下一位
                slow ++
                fast --
            }
        }
    }
    return res
};

---

Wechat: Jörmungandr

[restartgr]

18. 四数之和

只是外层加了个for循环
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  if (nums.length < 4) return [];
  const res = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i + 3 < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    for (let j = i + 1; j + 2 < nums.length; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue;
      }
      let l = j + 1;
      let r = nums.length - 1;
      while (l < r) {
        const sum = nums[i] + nums[j] + nums[l] + nums[r];
        if (sum < target) l++;
        else if (sum > target) r--;
        else {
          res.push([nums[i], nums[j], nums[l], nums[r]]);
          while (l < r && nums[l] === nums[l + 1]) {
            l++;
          }
          while (l < r && nums[r] === nums[r - 1]) {
            r--;
          }
          l++;
          r--;
        }
      }
    }
  }
  return res;
};

---

Wechat: Jörmungandr

[restartgr]

344. 反转字符串

非库函数写法
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  let left = 0;
  let right = s.length - 1;
  while (left <= right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
};

---

Wechat: Jörmungandr

[restartgr]

541. 反转字符串 II

涉及模拟的反转字符串
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const array = s.split('')
    const len = array.length
    for(let i = 0; i<len; i+=2*k){
        let l = i; r = i + k - 1 > len ? len : i + k - 1
        while(l<=r){
            [array[l],array[r]] =  [array[r],array[l]]
            l++
            r--
        }
    }
    return array.join('')
};

---

Wechat: Jörmungandr

[restartgr]

剑指 Offer 05. 替换空格

正则匹配
var replaceSpace = function(s) {
    return s.replace(/\s/g,"%20")
};

遍历法 
var replaceSpace = function(s) {
    return s.split(' ').join('%20')
};
指针法
/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    const array = s.split('')
    //  记录0的个数
    let count = 0
    for(let i = 0;i< array.length;i++){
        if(array[i] === ' '){
            count ++
        }
    }
    let left = array.length - 1;
    let right = array.length + count * 2 - 1;

    while(left >= 0) {
        if (array[left] === ' ') {
        array[right] = '0';
        array[right-1] = '2';
        array[right-2] = '%';
        right -=3
        left--;
        } else {
            array[right--] = array[left--];
        }
    }
    return array.join('')
};

---

Wechat: Jörmungandr