最近看青之蘆葦,為足球有更深入的了解
var largestNumber = function(nums) {
// 如果 array 為 [0, 0] 則不用排序回傳 0
if (nums.join("") * 1 === 0 ) {
return '0';
}
function quickSort(arr) {
// 如果 array 為空陣列或只有一個元素,直接返回,不需排序。
if (arr.length <=1 ) {
return arr;
}
let pivot = arr[arr.length -1]; // 將陣列元素最後一項設為基準值
let left = []; // 用來儲存比基準值大的元素
let right = []; // 用來儲存比基準值小的元素
for(let i = 0; i < arr.length - 1; i++) {
// 設定 i < arr.length - 1 是因為陣列最後一項被我們設為 pivot 因此不需考慮
if (`${arr[i]}${pivot}` > `${pivot}${arr[i]}`) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), pivot, ...quickSort(right)]
}
return quickSort(nums).join('');
};

利用 Quick Sort ,例如 9, 23 判斷標準為 923 > 239,所以 9 要放到 left array

--

--

希望中國人平安
var sortColors = function(nums) {
let zeroIndex = 0
let twoIndex = nums.length - 1
for (let i = 0; i <= twoIndex; i++) {
if (nums[i] === 0) {
[nums[i],nums[zeroIndex]] = [nums[zeroIndex], nums[i]]
zeroIndex ++
} else if(nums[i] === 2) {
[nums[i],nums[twoIndex]] = [nums[twoIndex], nums[i]]
twoIndex --
i--
}
}
};

利用 zeroIndex 和 twoIndex 兩個指針判斷下一個數字要放到前面還是後面,迴圈指針 i 等於第一個 twoIndex 停止,若 nums[i] === 2 i 需要再次判斷,可能被交換的 twoIndex 為 2 ,則需要再被放到最後

--

--

我妹今天出發去史丹佛資工碩士,很了不起呢!
/**
* @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 即可

--

--

黃韋智

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