大家好,又见面了,我是你们的朋友全栈君。
最近在准备秋招,做过了大大小小的公司的面试题,发现除了基础知识外,算法还是挺重要的。特意整理了一些常见的算法题,添加了自己的理解并实现。
除此之外,建议大家还可以刷刷《剑指offer》(但我还没刷完?,任重道远呐)。此外,左神在牛客网上也有算法课程,听了基础班的感觉还不错,起码让我这个算法小白也能快速地理解了很多问题,知识付费的时代,这个真的是良心课程了。就我个人而言的话,平时为了解决一个算法问题,需要花很多时间去看帖子、看讲解,但很难真正转化为自己的思想(主要问题就是没有动手练),大家可以根据自己的需求,进行算法的学习。
话不多说,下面来看题。
目录
16.将数字12345678转化成RMB形式:12,345,678
function isPrime(num){
if (num === 2 || num === 3) {
return true;
};
if (num % 2 === 0) {
return false;
};
let divisor = 3,limit = Math.sqrt(num);
while(limit >= divisor){
if (num % divisor === 0) {
return false;
}
else {
divisor += 2;
}
}
return true;
}
console.log(isPrime(30)); // false
function fibonacci(n){
if (n <= 0) {
return 0;
}
if (n == 0) {
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
但是递归会有严重的效率问题。比如想要求得f(10),首先需要求f(9)和f(8)。同样,想求f(9),首先需要f(8)和f(7)…这样就有很多重复值,计算量也很大。
function fibonacci(n){
let ori = [0,1];
if (n < 2) {
return ori[n];
};
let fiboOne = 1,fiboTwo = 0,fiboSum = 0;
for (let i = 2; i < n; i++) {
fiboSum = fiboOne + fiboTwo;
fiboTwo = fiboOne;
fiboOne = fiboSum;
}
return fiboSum;
}
console.log(fibonacci(5));
function greatestCommonDivisor(a, b){
let divisor = 2,res = 1;
if (a < 2 || b < 2) {
return 1;
};
while(a >= divisor && b >= divisor){
if (a%divisor === 0 && b%divisor === 0) {
res = divisor;
}
divisor++;
}
return res;
};
console.log(greatestCommonDivisor(8, 4)); // 4
console.log(greatestCommonDivisor(69, 169)); // 1
function greatestCommonDivisor(a,b){
if (b === 0) {
return a;
} else {
return greatestCommonDivisor(b,a%b);
}
};
function removeDuplicate(arr){
if (arr === null || arr.length < 2) {
return arr;
};
let res = [],exits = [];
for(let i = 0; i < arr.length; i++){
let j = arr[i];
while( !exits[j] ){
res.push(arr[i]);
exits[j] = true;
}
}
return res;
}
console.log(removeDuplicate([1,3,3,3,1,5,6,7,8,1])) // [1,3,5,6,7,8]
这一题的解法和上一题类似。
function removeDuplicateChar(str){
if (!str || str.length < 2 || typeof str != "string") {
return;
};
let charArr = [],res = [];
for(let i = 0; i < str.length; i++){
let c = str[i];
if(charArr[c]){
charArr[c]++;
}
else{
charArr[c] = 1;
}
}
for(let j in charArr){
if (charArr[j] === 1) {
res.push(j);
}
}
return res.join("");
}
console.log(removeDuplicateChar("Learn more javascript dude"));
// Lnmojvsciptu
function mergeSortedArr(a,b){
if (!a || !b) {
return;
};
let aEle = a[0],bEle = b[0],i = 1,j = 1,res = [];
while(aEle || bEle){
if ((aEle && !bEle) || aEle <= bEle) {
res.push(aEle);
aEle = a[i++];
}
else{
res.push(bEle);
bEle = b[j++];
}
}
return res;
}
console.log(mergeSortedArr([2,5,6,9], [1,2,3,29])) // [1,2,2,3,5,6,9,29]
function reverse(str){
let resStr = "";
for(let i = str.length-1; i >= 0; i--){
resStr += str[i];
}
return resStr;
}
console.log(reverse("ABCDEFG"));
function reverse2(str){
if (!str || str.length < 2 || typeof str != "string") {
return str;
};
let res = [];
for(let i = str.length-1; i >= 0; i--){
res.push(str[i]);
}
return res.join("");
}
console.log(reverse2("Hello"));
String.prototype.reverse3 = function(){
if (!this || this.length < 2) {
return;
};
let res = [];
for(let i = this.length-1; i >= 0; i--){
res.push(this[i]);
}
return res.join("");
}
console.log("abcdefg".reverse3());
例如:将“I am the good boy”反转变为 “I ma eht doog yob”。
提示:使用数组和字符串方法。
function reverseInPlace(str){
return str.split(' ').reverse().join(' ').split('').reverse().join('');
}
console.log(reverseInPlace('I am the good boy'));
function isPalindrome(str){
if (!str || str.length < 2) {
return;
}
for(let i = 0; i < str.length/2; i++){
if (str[i] !== str[str.length-1-i]) {
return false;
}
}
return true;
}
console.log(isPalindrome("madama"))
eg:在一个未排序的数组中找出是否有任意两数之和等于给定的数。
给出一个数组[6,4,3,2,1,7]和一个数9,判断数组里是否有任意两数之和为9。
这个题解得很巧妙,
function sumFind(arr,num){
if (!arr || arr.length < 2) {
return;
};
let differ = {};
for(let i = 0; i < arr.length; i++){
let subStract = num - arr[i];
if (differ[subStract]) {
return true;
}
else{
differ[arr[i]] = true;
}
}
return false;
}
console.log(sumFind([6,4,3,2,1,7], 9)); // true
如:get-element-by-id 转为 getElementById
let str = 'get-element-by-id';
let arr = str.split('-');
for(let i=1; i<arr.length; i++){
arr[i] = arr[i].charAt(0).toUpperCase() + arr[i].substring(1);
}
console.log(arr.join('')); // getElementById
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入: [“flower”,”flow”,”flight”] 输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”] 输出: “”
function longestCommonPrefix(arr) {
if(arr.length === 0){ // 简单逻辑判断
return "";
} else if(arr.length === 1){
return arr[0];
}
let res = "",temp = "";
for(let i = 0; i < arr[0].length; i++){ // 以数组第一个元素为标准
res += arr[0][i];
for(let j = 1; j < arr.length; j++){ // 如果后面所有元素都以该前缀开头,则前缀++
if(arr[j].indexOf(res) !== 0){
return temp // 否则返回 temp
}
}
temp = res;
}
return res;
}
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置,编程计算最少加油次数。并证明算法能产生一个最优解。 要求:
输入:第一行有2个正整数n和k,表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 个整数,表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地,汽车已加满油。第k+1 个加油站表示目的地。
输出:输出编程计算出的最少加油次数。如果无法到达目的地,则输出”NoSolution”。
function greedy(n, k, arr){ // n:加满可以行驶的公里数; k:加油站数量; arr:每个加油站之间的距离数组
if (n == 0 || k == 0 || arr.length == 0 || arr[0] > n) {
return "No Solution!"; // arr[0] > n :如果第一个加油站距离太远,也无法到达
};
let res = 0, distance = 0; // res:加油次数;distance:已行驶距离
for(let i = 0; i <= k; i++){
distance += arr[i];
if (distance > n) { // 已行驶距离 > 加满可以行驶的公里数
if(arr[i] > n){ // 如果目前加油站和前一个加油站的距离 > 加满可以行驶的公里数,则无法到达
return "No Solution!";
};
// 可以在上一个加油站加油,行驶到目前的加油站i:
distance = arr[i];
res++; // 加油次数+1
}
}
return res;
}
let arr = [1,2,3,4,5,1,6,6];
console.log(greedy(7,7,arr)) // 4
String.prototype.trim1 = function(){
// return this.replace(/\s*/g,""); // 清除所有空格
return this.replace(/(^\s*)|(\s*$)/g,""); // 清除字符串前后的空格
};
console.log(" hello word ".trim1()) // "hello word"
一个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右 四个位置相连,如果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?
可以看我之前的讲解。Javascript实现岛问题
思路:将字符串切割成数组再反转,遍历数组,加入辅助数组,当数组长度为3的倍数,再向辅助数组加入 “,”。
function RMB(str){
let arr = str.split("").reverse();
let res = [];
for(let i = 0; i < arr.length; i++){
res.push(arr[i]);
if ((i + 1) % 3 === 0) {
res.push(",");
}
}
return res.reverse().join("");
}
console.log(RMB("12345678"))
function delSrt(str){
let res = [], nowStr;
for(let i = 0; i < str.length; i ++){
if (str.charAt(i) != nowStr) {
res.push(str.charAt(i));
nowStr = str.charAt(i);
}
}
return res.join("");
}
console.log(delSrt("aabcc11"))
一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(数组,里面是一个个具体的项目),你来安排宣讲的日程,要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。
步骤:
function getMostCount(obj){
if (!obj || obj.length < 1) {
return;
};
obj.sort(sortEndTime);
let res = 1, now = obj[0].end;
for(let i = 1; i < obj.length; i++){
if (now < obj[i].start) {
res++;
now = obj[i].end;
}
}
return res;
}
// 自定义排序法
function sortEndTime(obj1,obj2){
return obj1.end - obj2.end;
}
var obj = [
{start:6,end:8},
{start:7,end:9},
{start:11,end:12},
{start:10,end:14},
{start:16,end:18},
{start:17.5,end:21},
{start:15,end:17},
{start:22,end:23}
];
console.log("最大场次:" + getMostCount(obj));
把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
思路:
function hanoiProcess(n,from,to,help){
if (n < 1) {
return;
}
if (n == 1) { // 最后一个从from移到to
console.log("Move 1 from " + from + " to " + to);
} else{
hanoiProcess(n-1, from, help, to); // 前n-1个从from移到help上,可以借助to
console.log("Move "+ n +" from " + from + " to " + to);
hanoiProcess(n-1, help, to, from); // 再把n-1个从help移到to,可以借助from
}
}
hanoiProcess(3, "左", "右", "中");
结果:
Move 1 from 左 to 右 Move 2 from 左 to 中 Move 1 from 右 to 中 Move 3 from 左 to 右 Move 1 from 中 to 左 Move 2 from 中 to 右 Move 1 from 左 to 右
母牛每年生一只母牛,新出生的母牛成长三年后也能每年生一只母牛,假设不会死。求N年后,母牛的数量。
思路:
function cow(n){
if (n < 1) {
return;
};
let count = 0;
if (n > 4) {
count = cow(n-1) + cow(n-3);
} else{
count = n;
}
return count;
}
let n = 7;
console.log(n + " 年后,牛的数量是: " + cow(n))
// 7 年后,牛的数量是: 13
一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的金条,不管切成长度多大的两半,都要花费20个铜板。一群人想整分整块金条,怎么分最省铜板?例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 10+20+30=60。金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50,花费60。再把长度50的金条分成20和30, 花费50。一共花费110铜板。但是如果先把长度60的金条分成30和30,花费60。再把长度30 金条分成10和20,花费30。一共花费90铜板。 输入一个数组,返回分割的最小代价。
这个也可以看我之前的博文介绍。js实现切割金条问题
如果有更好的解法,感谢大佬赐教!我的解法太普通了,有时间再改进下。
算法问题先写到这,如果还有更多的面试题,也可以和我交流交流,相互学习呀!
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/148451.html原文链接:https://javaforall.cn