2022-07-24

[Zheaoli]

2022-07-24

[shaDowPark]

二叉搜索树中两个节点之和

wx: shadow

[gongpeione]

/*
 * @lc app=leetcode id=74 lang=javascript
 *
 * [74] Search a 2D Matrix
 * 剑指 Offer 04. 二维数组中的查找
 */

// @lc code=start
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let found = false;

    // start from the num at top right
    let row = 0;
    let col = matrix[0].length - 1;

    while(row < matrix.length && col >= 0) {
        const cur = matrix[row][col];

        if (cur === target) {
            found = true;
            break;
        }

        // if target greater than cur
        // then the target must from rows below
        if (target > cur) {
            row++;
        }
        // if target less than cur
        // then the target must from cols from the left
        if (target < cur) {
            col--;
        }
    }

    return found;
};
// @lc code=end

---

微信id: 弘树 来自 vscode 插件

[SaraadKun]

1184. 公交站间的距离

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        //顺时针统计start和destination之间的距离diff,同时统计全路径距离和sum,
        //start和destination逆时针距离为sum - diff, 取最小值即可
        int n = distance.length, sum = 0, diff = 0;
        //diff计数的标记
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            if (i == start || i == destination) {
                flag ^= true;
            }
            if (flag) {
                diff += distance[i];
            }
            sum += distance[i];
        } 
        return Math.min(diff, sum - diff);
    }
}

---

WeChat: Saraad

[SaraadKun]

433. 最小基因变化

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        //预处理数据,添加中间节点,建图+BFS,记录已访问过的节点,避免重复访问
        Map<String, List<String>> adj = new HashMap<>();
        //预处理bank建图,对每个单词,用'*'分别替换每一位的单词作为中间节点,将原单词与中间节点的边添加到邻接表中
        for (String gene : bank) {
            List<String> list = adj.getOrDefault(gene, new ArrayList<>());
            char[] chs = gene.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                char tmp = chs[i];
                chs[i] = '*';
                String ne = new String(chs);
                list.add(ne);
                List<String> nes = adj.getOrDefault(ne, new ArrayList<>());
                nes.add(gene);
                adj.put(ne, nes);
                chs[i] = tmp;
            }
            adj.put(gene, list);
        }
        //end不在图中,提前返回
        if (!adj.containsKey(end)) {
            return -1;
        }
        //使用map记录到达该节点的步数
        Map<String, Integer> map = new HashMap<>();
        Set<String> visited = new HashSet();
        Queue<String> q = new ArrayDeque<>();
        //将start相关中间节点入队
        char[] schs = start.toCharArray();
        for (int i = 0; i < schs.length; i++) {
            char tmp = schs[i];
            schs[i] = '*';
            String ne = new String(schs);
            if (adj.containsKey(ne)) {
                q.offer(ne);
                visited.add(ne);
                map.put(ne, 1);
            }
            schs[i] = tmp;
        }
        //BFS
        while (!q.isEmpty()) {
            String cur = q.poll();
            int step = map.get(cur);
            for (String ne: adj.get(cur)) {
                if (end.equals(ne)) {
                    return (step + 1) / 2;
                }
                if (!visited.contains(ne)) {
                    q.offer(ne);
                    visited.add(ne);
                    map.put(ne, step + 1);
                }
            }
        }
        return -1;
    }  
}

---

老题新做: 433 WeChat: Saraad

[restartgr]

14. 最长公共前缀

扫描每个子串，每次比较都截取最短的长度
var longestCommonPrefix = function(strs) {
    if(!strs.length){
        return ''
    }
    let res = strs[0]
    for(let i = 1; i<strs.length; i++){
        for(let j = 0; j <strs[i].length && j<res.length; j++){
            if(res[j] !== strs[i][j]) {
                res = res.substring(0,j)
                break;
            }
        }
        // 每次比较都截取strs[i].length长度的字符串
        res = res.substring(0,strs[i].length)
    }
    return res
};

---

Wechat: Jörmungandr

[dreamhunter2333]

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
/*
 * @lc app=leetcode.cn id=1184 lang=cpp
 *
 * [1184] 公交站间的距离
 */

// @lc code=start
class Solution
{
public:
    int distanceBetweenBusStops(vector<int> &distance, int start, int destination)
    {
        int res = 0;
        int all_distance = accumulate(distance.begin(), distance.end(), 0);
        if (start > destination)
            swap(start, destination);
        for (int i = start; i < destination; i++)
            res += distance[i];
        return min(res, all_distance - res);
    }
};
// @lc code=end

---

微信id: 而我撑伞 来自 vscode 插件