黃韋智

我妹今天出發去史丹佛資工碩士,很了不起呢!
/**
* @param {number[]} w
*/
var Solution = function(w) {
this.arr = [];
let sum = 0;
for(let i = 0; i < w.length; i++) {
sum += w[i];
this.arr.push(sum);
}
};
/**
* @return {number}
*/
Solution.prototype.pickIndex = function() {
let target = Math.random() * this.arr[this.arr.length-1];
let low = 0;
let high = this.arr.length - 1;
while (low < high) {
let mid = Math.floor((low + high)/2)
if (this.arr[mid] <= target)
low = mid + 1;
else
high = mid;
}
return high;
};

題目中例子2,權重為[1, 3],表示有兩個點,權重分別為1和3,那麼就是說一個點的出現概率是四分之一,另一個出現的概率是四分之三。由於我們的Math.random()函數是等概率的隨機,那麼我們如何才能有權重的隨機呢? 我們可以使用一個trick,由於權重是1和3,相加為4,那麼我們現在假設有4個點,然後隨機等概率取一個點,隨機到第一個點後就表示原來的第一個點,隨機到後三個點就表示原來的第二個點,這樣就可以保證有權重的隨機。那麼我們就可以建立權重數組的累加和數組,比如若權重數組為[1, 3, 2] 的話,那麼累加和數組為[1, 4, 6],整個的權重和為6,Math.random() * this.arr[this.arr.length-1],可以隨機出範圍[0, 5] 內的數,隨機到0 則為第一個點,隨機到1,2,3 則為第二個點,隨機到4,5 則為第三個點,所以我們隨機出一個數字target後,然後再累加和數組中查找第一個大於隨機數target的數字,使用二分查找法可以找到第一個大於隨機數target的數字的坐標,即為所求。

參考:https://www.cnblogs.com/grandyang/p/9784690.html

--

--

希望能夠好天氣~準備爬南湖了
var pathSum = function(root, sum) {
if (!root) return 0
return (
pathSumStart(root, sum) +
pathSum(root.left, sum) +
pathSum(root.right, sum)
)
};
const pathSumStart = (root, sum) => {
if (!root) return 0;
const self = root.val === sum ? 1 : 0;
return (
self +
pathSumStart(root.left, sum - root.val) +
pathSumStart(root.right, sum - root.val)
)
}

如果子 node.val 等於 sum 減 root.val 就符合目標 sum,例如 現在 root.val = 5,sum = 8,當子 node.val = 5 即符合題目需求。因此只要將每一個 node 當作 root,幾算延伸出去的 path 是否符合 sum 即可

--

--

滑板真低難,練起來要好多時間(摔好多次)
var getDirections = function(root, startValue, destValue) {
const startPath = [];
const destPath = [];
find(root, startValue, startPath);
find(root, destValue, destPath);


// find the root
while (startPath.length && destPath.length && startPath.at(-1) === destPath.at(-1)) {
startPath.pop();
destPath.pop();
}

// L -> U
return startPath.map(() => "U").join("") + destPath.reverse().join("");
};
function find(root, d, path) {
if(!root) return false;

if(root.val === d) return true;

if(root.left && find(root.left, d, path)) {
path.push("L")
return true
}

if(root.right && find(root.right, d, path)) {
path.push("R")
return true
}

return false
}

--

--

今天學習了拉花,真的超困難!
var longestUnivaluePath = function(root) {
if (!root) return 0;
return Math.max(
longestPassPath(root.left, root.val) + longestPassPath(root.right, root.val),
longestUnivaluePath(root.left),
longestUnivaluePath(root.right)
)
};
const longestPassPath = (root, val) => {
if (!root || root.val !== val) return 0;
const left = longestPassPath(root.left, val);
const right = longestPassPath(root.right, val);
return 1 + Math.max(left, right)
};

題目意思是判斷最長相同的 node,因此只要分別判斷中間跟左右以及左右子樹等三種狀態。

--

--

黃韋智

黃韋智

自學寫程式,目前爲 React 前端工程師。熱愛旅遊,將近 30 個國家,足跡遍佈亞洲與歐洲。生命與街舞已經離不開,歡迎訂閱 Youtube 頻道:https://www.youtube.com/channel/UCEU-bEDl7R-iGyLVZFae33g