2022-07-14

[Zheaoli]

2022-07-14

[restartgr]

59. 螺旋矩阵 II

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let startx = 0, starty = 0;   // 起始位置
    let loop = Math.floor(n/2);   // 旋转圈数
    let mid = Math.floor(n/2);    // 中间位置
    let offset = 1;    // 控制每一层填充元素个数
    let count = 1;     // 更新填充数字
    let res = new Array(n).fill(0).map(() => new Array(n).fill(0));

    while (loop--) {
         // 下面开始的四个for就是模拟转了一圈
        // 模拟填充上行从左到右(左闭右开)
        for (j = starty; j < n - offset; j++) {
            res[startx][j] = count++;
        }
        // 模拟填充右列从上到下(左闭右开)
        for (i = startx; i < n - offset; i++) {
            res[i][j] = count++;
        }
        // 模拟填充下行从右到左(左闭右开)
        for (; j > starty; j--) {
            res[i][j] = count++;
        }
        // 模拟填充左列从下到上(左闭右开)
        for (; i > startx; i--) {
            res[i][j] = count++;
        }

        // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
        startx++;
        starty++;

        // 更新offset
        offset += 1;
    }
    // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
    if (n % 2 === 1) {
        res[mid][mid] = count;
    }
    return res;
};

---

wechat: Jörmungandr

[SaraadKun]

745. 前缀和后缀搜索

class WordFilter {

    Trie preTrie = new Trie();
    Trie sufTrie = new Trie();

    //正反向构建两颗Trie,构建时按索引顺序添加,
    //查找时按前后缀分别查找两棵树,得到两个id集合,倒序遍历取第一个相同的id即为最大id
    public WordFilter(String[] words) {
        int n = words.length;
        for (int i = 0; i < n; i++) {
            char[] chs = words[i].toCharArray();
            preTrie.add(chs, i, true);
            sufTrie.add(chs, i, false);
        }
    }

    public int f(String pref, String suff) {
        List<Integer> idx1 = search(pref.toCharArray(), preTrie, true);
        List<Integer> idx2 = search(suff.toCharArray(), sufTrie, false);
        int n = idx1.size(), m = idx2.size();
        if (n == 0 || m == 0) {
            return -1;
        }
        int i = n - 1, j = m - 1;
        while (i >= 0 && j >= 0) {
            int num1 = idx1.get(i), num2 = idx2.get(j);
            if (num1 < num2) {
                j--;
            } else if (num1 > num2) {
                i--;
            } else {
                return num1;
            }
        }
        return -1;
    }

    private List<Integer> search(char[] chs, Trie cur, boolean dir) {
        int n = chs.length;
        for (int i = dir ? 0 : n - 1; i < n && i >= 0; i += dir ? 1 : -1){
            cur = cur.children[chs[i] - 'a'];
            if (cur == null) {
                return List.of();
            }
        }
        return cur.values;
    }

    static class Trie {

        Trie[] children = new Trie[26];
        boolean isEnd = false;
        List<Integer> values = new ArrayList<>();

        public void add(char[] chs, int index, boolean dir) {
            Trie cur = this;
            int n = chs.length;
            for (int i = dir ? 0 : n - 1; i < n && i >= 0; i += dir ? 1 : -1){
                int idx = chs[i] - 'a';
                if (cur.children[idx] == null) {
                    cur.children[idx] = new Trie();
                }
                cur = cur.children[idx];
                cur.values.add(index);
            }
            cur.isEnd = true;
            cur.values.add(index);
        }

    }

}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */

---

WeChat: Saraad

[restartgr]

707. 设计链表

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var MyLinkedList = function() {
    this.head = null
    this.size = 0
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
     if(index < 0 || index > this.size - 1){
        return -1
    }
    let step = index
    let cur = this.head
    while(step){
        cur = cur.next
        step -- 
    }
    return cur.val
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    const node = new ListNode(val)
    node.next = this.head
    this.head = node
    this.size ++
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    const node = new ListNode(val)
    if(!this.head){
        // 当head不存在时说明链表为空，效果和添加首相同
        this.addAtHead(val)
    } else{
        let cur = this.head
        while(cur.next){
            cur = cur.next
        }
        cur.next = node
        this.size ++
    }
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index<=0){
        this.addAtHead(val)
    } else if(index === this.size){
        this.addAtTail(val)
    } else if(index > this.size - 1){
        return null;
    } else {
        let cur = this.head
        let step = index
        while(step > 1){
            cur = cur.next
            step -- 
        } 
        const node = new ListNode(val)
        node.next = cur.next
        cur.next = node 
        this.size ++
    }
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    // index 可以从0 开始 
    if(index < 0 || index > this.size - 1){
         return null;
    } else{
        const dummy = new ListNode(null)
        dummy.next = this.head
        let cur = dummy
        let step = index
        while(step){
            cur = cur.next
            step -- 
        }
        if(index === 0){
            this.head = cur.next.next
        }
        cur.next = cur.next.next
        this.size --
    } 
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

---

wechat: Jörmungandr

[restartgr]

206. 反转链表

1. 递归法
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverse = (pre,cur) =>{
    if(!cur){
        return pre
    }
    let next = cur.next
    cur.next = pre
    pre = cur
    cur = next
    return reverse(pre,cur)
}
var reverseList = function(head) {
    return reverse(null,head)
};

2. 迭代法
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
   let pre = null
   let cur = head
   while(cur){
       let next = cur.next
       cur.next = pre
       pre = cur
       cur = next
   }
   return pre
};

---

wechat: Jörmungandr

[restartgr]

24. 两两交换链表中的节点

1. 递归
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head ||　!head.next){
        return head
    }
    const next = head.next
    head.next = swapPairs(next.next)
    next.next = head
    return next
};

2. 迭代
var swapPairs = function(head) {
   const dummy = new ListNode()
   dummy.next = head
   let cur = dummy
   while(cur.next && cur.next.next){
       const temp = cur.next // 1
       const temp2 = cur.next.next //2
       temp.next = temp2.next
       temp2.next = temp
       cur.next = temp2
       cur = cur.next.next // 每次移两位
   }
   return dummy.next    
};

---

wechat: Jörmungandr

[restartgr]

19. 删除链表的倒数第 N 个结点

移位快慢指针
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode()
    dummy.next  = head
    let fast = dummy
    let slow = dummy
    while(n>0&&fast.next){
        fast = fast.next
        n--
    }
    while(fast.next){
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return dummy.next
};
```.
--- 
wechat: Jörmungandr

[restartgr]

面试题 02.07. 链表相交

1. 快慢指针法
把两个链表移动到同一个长度一起遍历，如果相交必有相同节点
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    // 根据题意，如果两个相交，一定后面有重复链表 那么让两个在一个起跑线开始遍历即可
    let lenA = 0
    let lenB = 0
    let curA = headA
    let curB = headB
    // 算出A的长度
    while(curA){
        curA = curA.next
        lenA ++
    }
    // 算出A的长度
    while(curB){
        curB = curB.next
        lenB ++
    }
    // 统一放在headA处理
    if(lenB>lenA){
        [lenB,lenA] = [lenA,lenB];
        [headA,headB] = [headB,headA];
    }
    let gap = lenA - lenB
    let currentA = headA
    let currentB = headB
    // 移到同一个位置
    while(gap){
        currentA = currentA.next
        gap --
    }
    while(currentA){
        if(currentA === currentB){
            return currentA
        }
        currentA = currentA.next
        currentB = currentB.next
    }
    return null
};

2. 巧妙方法
A遍历完遍历B，B遍历完遍历A，如果两个相交必能相遇到同一个点，否则都是null

skipA+cross+skipB =  skipB+cross+skipA
var getIntersectionNode = function(headA, headB) {
  let curA = headA
  let curB = headB
  while(curA !== curB){
      curA = curA === null ? headB:curA.next
      curB = curB === null ? headA:curB.next
  }
  return curA
};

---

wechat: Jörmungandr

[restartgr]

142. 环形链表 II

快慢指针法
快指针一次走两步，慢指针一次走一步，如果两者在某点相遇则存在环，此时从头节点距离为环外距离a，环内距离b和剩下环长度c 
2(a+b) = a+ n(b+c)+b => a = c +(n-1)(b+c) 
所以a = n圈环长度 + c , a + b = 环长度的n倍，而此时慢指针的长度据头的长度刚好是a+b。
此时从头节点开始起一个新指针和慢指针一起一步一动，最终会在入环点相遇（头指针走A到入环点，慢指针走N圈环长度 - b，刚好走完一个环到入环点）

var detectCycle = function(head) {
   let slow = head
   let fast = head
   while(fast &&fast.next){
       fast = fast.next.next
       slow = slow.next
       // 存在环形相交    
       if(fast === slow){
           let temp = head
           while(slow !== temp){
               temp = temp.next
               slow = slow.next   
           }
           return slow
       }
   }
   return null
};

---

wechat: Jörmungandr