Recently preparing for the interview, I have brushed some simple and intermediate algorithm questions on Lintcode, and also mastered some common algorithms. Since I only know js grammar at present, I solved all the solutions by myself with JS, so I leave a hole here to remember, hoping to help beginners or fellow travelers like me.
The largest subarray
General Violence Algorithm — Easy to understand, complexity O(n^3)
/** * Given an array of integers, find a subarray with the maximum sum and return the maximum sum. * * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */
const maxSubArray = function(nums) {
var l = nums.length;
var ans = - 10000.; // Initialize the value
for (var i = 0; i < l; i++) {
for (var j = i; j < l; j++) {
let sum = 0;
for (var k = i; k < j; k++) {
sum += nums[k];
}
if(sum > ans) { ans = sum; }}}return ans;
}
/* Violence enumerates all subsets n^3 */
let num = [2 -.2.- 3.4.- 1.2.1.- 5.3]
console.log(maxSubArray(num));
Copy the codeGreedy algorithm — discard substring and negative substring, only keep positive substring O(n)
function maxSubArray1(nums) {
var l = nums.length;
var ans = - 10000.;
var sum = 0;
for (var i = 0; i < l; i++) {
sum += nums[i];
if (sum > ans) {
ans = sum;
}
if (sum < 0) {
sum = 0; // Substring sum is negative, discard}}return ans
}
Copy the codeFinding the main element
/** * Given an array of integers, find the main element whose occurrence is strictly greater than 1/k of the number of elements in the array. * * @param nums: A list of integers * @param k: An integer * @return: The majority number */
const majorityNumber = function(nums, k) {
var i, l = nums.length,
obj = {};
var temp = ~~(l * 1 / k); / / number in the middle
for (i = 0; i < l; i++) {
if (nums[i] in obj) {
obj[nums[i]] += 1;
} else {
obj[nums[i]] = 1;
}
// Because it is the only primary element
if (obj[nums[i]] > temp) {
returnnums[i]; }}}Copy the codeSearch two dimensional matrix
/** ** search for 2d matrix ** complexity O(log(n)) + O(log(m)) ** @param matrix: matrix, a list of lists of integers * @param target: An integer * @return: a boolean, indicate whether matrix contains target */
const searchMatrix = function(matrix, target) {
var row = 0;
if (matrix.length === 0) {
return false;
}
for (var i = 0; i < matrix.length; i++) {
let last = matrix[i].pop()
if (last < target) {
continue;
} else if (last === target) {
return true;
} else {
row = i;
break; }}for (var j = 0; j < matrix[row].length; j++) {
if (matrix[row][j] === target) {
return true;
} else {
continue; }}return false;
}
Copy the codeSearch the two-dimensional matrix II
/** * write an efficient algorithm to search for a value in an m×n matrix and return the number of occurrences of that value. * Integers in each line are sorted from left to right. * The integers in each column are sorted from top to bottom. * There are no duplicate integers in each row or column. * * @param matrix: A list of lists of integers * @param target: An integer you want to search in matrix * @return: An integer indicate the total occurrence of target in the given matrix */
const searchMatrix1 = function(matrix, target) {
var i, l = matrix.length,
num = 0;
for (i = 0; i < l; i++) {
var row = matrix[i];
var j, jl = row.length;
for (j = 0; j < jl; j++) {
if (row[j] === target) {
num += 1;
break; }}}return num;
}
Copy the codeFind the KTH largest number
** @param n: An integer * @param nums: An array * @return: the Kth largest element */
const kthLargestElement = function(n, nums) {
if (n === 1) {
return Math.max.apply(null, nums);
}
let i,
l = nums.length,
left = [],
right = [],
pivot = nums[~~(Math.random() * l)];
for (i = 0; i < l; i++) {
if (nums[i] > pivot) {
right.push(nums[i])
} else {
left.push(nums[i])
}
}
if (right.length > n) {
return kthLargestElement(n, right);
} else if (right.length === n) {
return Math.min.apply(null, right);
} else {
n = n - right.length;
returnkthLargestElement(n, left); }}console.log(kthLargestElement(10[1.2.3.4.5.6.8.9.10.7])); / / 1
console.log(kthLargestElement(4[9.3.2.4.8])); / / 3
Copy the code/** * Given an array of integers, find the main element whose occurrence is strictly greater than 1/k of the number of elements in the array. * * @param nums: A list of integers * @param k: An integer * @return: The majority number */
const majorityNumber = function(nums, k) {
var i, l = nums.length,
obj = {};
var temp = ~~(l * 1 / k); / / number in the middle
for (i = 0; i < l; i++) {
if (nums[i] in obj) {
obj[nums[i]] += 1;
} else {
obj[nums[i]] = 1;
}
// Because it is the only primary element
if (obj[nums[i]] > temp) {
returnnums[i]; }}}console.log(majorityNumber([3.1.2.3.2.3.3.4.4.4].3));
Copy the codeGreed problem:
Money change problem
Let’s say I have an unlimited number of coins of 20,10,5,1. Give the number of change needed, find the change scheme, requirements: use the least number of coins
Strategy: Select the maximum number of coins available each time
[20,10,5,1] n is the change number */
function greedyMoney(m, n) {
let result = [];
for (var i = 0; i < m.length; i++) {
while (n >= m[i] && n > 0) { result.push(m[i]) n = n - m[i]; }}return result;
}
Copy the codeCrossing the river by boat
There’s only one boat that can carry two people, and it’s going as fast as the slower of the two people, and then it’s going to take one person to row it back, and it’s going to take at least how long to get t people to the other side, and let’s say that t people’s speeds are in ascending order.
strategy
- The quickest and the quickest cross the river, and the quickest row back; The second slowest and slowest cross the river, and then the second fastest row back, the time required is: t[0]+2*t[1]+t[n-1].
- The fastest and slowest to cross the river, then the fastest to row back, the fastest and the second slowest to cross the river, then the fastest to row back, the time required is: 2*t[0]+t[n-2]+ T [n-1].
- Each run does not affect others, so it has a greedy substructure. Solution to the following
let array = [1.2.3.4.5.6.7.9.12.15] // 10 people, each person takes 1,2... n
function greedyBoat(arr) {
let total = 0; / / the total available
while (arr.length > 0) {
var l = arr.length;
// If there are 3 people left
if (l === 3) {
total += arr[0] + arr[1] + arr[2];
break;
}
// If there are 2 people left
if (l === 2) {
total += arr[1];
break;
}
// If there is 1 person left
if (l === 1) {
total += arr[0];
break;
}
// Cross the river once
total += Math.min.apply(null, [arr[l - 1] + 2 * arr[0] + arr[l - 2], arr[0] + 2 * arr[1] + arr[l - 1]])
// Remove the two digits at the end of the array
arr.length -= 2;
}
return total;
}
console.log(greedyBoat(array));
Copy the code