算法基础: esay level

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

function search(nums: number[], target: number): number {
    let max = nums.length - 1
    let min = 0
    while(max >= min) {
        if (nums[max] === target) {
            return max
        } 
        else if (target < nums[max]) {
            max --
        } else if (target > nums[min]){
            min ++
        }
    }
    return -1
};

两数之和

// first one
var twoSum = function(nums, target) {
    let j = 0
    for(let i = 0; i< nums.length; i ++) {
        let item = nums[i];
        let diff = target - item;
        j = nums.indexOf(diff)
        if(j > -1 && j != i) {
            return [i,j]
        }
    } 
};

// second
var twoSum = function(nums, target) {
    let map = new Map()
    for(let i = 0; i< nums.length; i ++) {
        if (map.has(nums[i])) {
          return [
            map.get(nums[i]), i
          ]
        } else {
          map.set(target - nums[i], i)
        }
    } 
};
twoSum([2,7,11,15], 17)

三数最接近之和

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length < 2) return false
    var res = []
    for(let i = 0; i < s.length; i ++) {
        res[i] = s[i]
    }
    var arr = []
    for (let i = 0; i < res.length; i ++) {
        let temp = arr[i]
        if (arr.includes(temp)) {
            arr.push(temp)
        } else {
            if(
                temp === arr.pop() || 
                temp.reverse() === arr.pop()
            ) {
                arr.pop()
            }
        }
    }
    return arr.length === 0
};

正确解读

var isValid = function(s) {
  s = s.split('')
  let len = s.length;
  if (s % 2) return false
  let map = new Map([
    [')', '('],
    [']', '['],
    ['}', '{']
  ])
  let stack = []
  for (let i of s) {
    if (map.get(i)) {
      if (
        stack[stack.length - 1] !== map.get(i)
      ) {
        return false
      } else {
        stack.pop()
      }
    } else {
      stack.push(i)
    }
  }
  return !stack.length
}

正整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首次尝试，好搓的解法

var mapSep = new Map([
	[4, 'IV'],
	[9, 'IX'],
	[40, 'XL'],
	[90, 'XC'],
	[400, 'CD'],
	[900, 'CM']    
])
var mapCom = new Map([
	[1, 'I'],
	[5, 'V'],
	[10, 'X'],
	[50, 'L'],
	[100, 'C'],
	[500, 'D'],
	[1000, 'M']   
])
function repeatNum (type, num) {
	return type.repeat(num)
}
var intToRoman = function(num) {
	const getOpt = (basis,spe = 0, num, max) => {
		console.log('basis', basis, spe, num)
		if(num === spe) return mapSep.get(num)
		var reset = Math.floor( num/basis )
		if (num % basis === 0) {
			return repeatNum(mapCom.get(basis), num / basis)
		} else if ( num > spe && num < max && spe !== 0) {
			return mapSep.get(spe) + countRest(num - spe)
		} else {
			return repeatNum(mapCom.get(basis), reset) + countRest(num - reset * basis)
		}
	}
	const countRest = (num) => {
		if(1 <= num && num < 5) {
			return getOpt(1, 4, num, 5)
		} else if (5 <= num && num < 10) {
			return getOpt(5, 9, num, 10)
		} else if (10 <= num && num  < 50) {
			return getOpt(10, 40, num, 50)
		} else if (50 <= num && num < 100) {
			return getOpt(50, 90, num, 100)
		}else if (100 <= num && num  < 500) {
			return getOpt(100, 400, num, 500)
		} else if (500 <= num && num  < 1000) {
			return getOpt(500, 900, num, 1000)
		} else if (1000 <= num && num  <= 3999) {
			return getOpt(1000, 0, num, 3999)
		}
	}
	return countRest(parseInt(num))
};
console.log('1994', intToRoman(1994))

正解

var intToRoman = function (num) {
    let keys = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1],
        values = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
    let res = "";
    for (let i = 0; i < keys.length; i++) {
        while (num >= keys[i]) {
            num = num - keys[i];
            res = res + values[i];
        }
    }
    return res;
};

驼峰转下划线

content-type

function transform(word) {
    return word.replace(/[-|@|_](\w)/, (m, val) => val.toUpperCase())
}
// test
transform('content-type')

下划线转驼峰

function revserTransform(word, mark = '-') {
  return word.replace(/([A-Z])/g, `${mark}$1`).replace(/(\w)+g/, mark).toLowerCase().slice(1)
}
// test
revserTransform('ContentType', '@') // content@type
// test
revserTransform('ContentType', '-') // content-type

验证回文

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

解法一: 迭代循环

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    if(typeof s != 'string') return s = s.toString()
    if(s.length < 2) return true
    var r = /[a-zA-Z0-9]/g;
    var arr = s.match(r) || [];
    let j = arr.length - 1
    for (let i = 0; i < j; i ++, j --) {
      if (arr[i].toLowerCase() != arr[j].toLowerCase()) {
        return false
      }
    }
    return true
};

利用正则表达式^以及replace优化下

var isPalindrome = function(s) {
    if(typeof s != 'string') return s = s.toString()
    if(s.length < 2) return true
    var r = /[^a-zA-Z0-9]/ig;
    var arr = s.replace(r, '').toLowerCase()
    let j = arr.length - 1
    for (let i = 0; i < j; i ++, j --) {
      if (arr[i] != arr[j]) {
        return false
      }
    }
    return true
};

解法二: String.prototype.reverse()

var isPalindrome = function(s) {
    if(typeof s != 'string') return s = s.toString()
    if(s.length < 2) return true
    var r = /[^a-zA-Z0-9]/ig;
    s = s.replace(r, '').toLowerCase()
    return s == s.split('').reverse().join('')
};

最长回文子串

首次尝试，以失败告终，正解在下面

思路也是从中心点开始往俩边扩展，唯一不足的就是当遇到中心点是’aabbaa’这种偶数性的字符串没有很好的考虑到。漏掉了这种类型

var longestPalindrome = function(s) {
    if (s && s.length < 2) {return s}
    s = s.split('');
    if (s.length >= 2 && s.every((e) => e === s[0])) return s.join('')
    var target = s[1]
    var res = [s[0]]
    var str = ''
    for (let i = 1; i < s.length; i ++) {
        target = s[i]
        var left = s.slice(0, i)
        var right = s.slice(i + 1)
        while(right[0] && left[left.length - 1] && left[left.length - 1] == right[0]) {
          str = left.pop() + target + right.shift()
          res.push(str)
          target = str
        }
        while(target === left[left.length - 1]) {
          str = left.pop() + target
          res.push(str)
          target = str
        }
        while(target === right[0]) {
          str = target + right.shift()
          res.push(str)
          target = str
        }
    }
    var max = res[0]
    res.forEach((e) => {
        var tempLength = e.length
        if (max.length < tempLength) {
            max = e
        }
    })
    return max
};

https://leetcode-cn.com/problems/longest-palindromic-substring/
inner [“c”] bb [“d”]

正解

var longestPalindrome = function(s) {
    if(!s || s.length < 2){
        return s;
    }
    let start = 0,end = 0;
    let n = s.length;
    // 中心扩展法
    let centerExpend = (left,right) => {
        while(left >= 0 && right < n && s[left] == s[right]){
            left--;
            right++;
        }
        return right - left - 1;
    }
    for(let i = 0;i < n;i++) {
        let len1 = centerExpend(i, i);
        let len2 = centerExpend(i, i+1);
        // 两种组合取最大回文串的长度
        let maxLen = Math.max(len1, len2);
        if(maxLen > end - start){
          // 更新最大回文串的首尾字符索引
          // start = i - ((maxLen - 1) >> 1);
          // end = i + (maxLen >> 1);
          start = i - Math.floor((len - 1) / 2);
          end = i + Math.floor(len / 2);
        }
    }
    return s.substring(start,end+1);
};

作者：Alexer-660
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/5-zui-chang-hui-wen-zi-chuan-by-alexer-660/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

全排列

输入： [1,2,3]
输出： [
[1,2,3],
[1,3,2],
…
]
题解：

var permute = nums => {
  var len = nums.length
  if (nums.length < 2) return nums
  var res = []
  var path = []
  var backTrack = (path, nums) => {
    if (path.length === nums.length) {
      res.push(path)
    }
    for (let num of nums) {
      if (!path.includes(num)) {
        path.push(num)
        backTrack(path.slice(), nums)
        path.pop()
      }
    }
  }
  backTrack(path, nums)
  return res
}
permute([1,2,3,4])

计算容器的面积

• 暴力解法 O(n^2)

  var maxArea = function(height) {
      var max = 0
      for(let i = 0; i < height.length - 1;i ++) {
          for (let j = i+ 1; j < height.length; j ++) {
              max = Math.max(max, Math.min(height[i], height[j]) * (j - i))
          }
      }
      return max
  };

• 双指针解法

  var maxArea = function(height) {
      var max = 0
      var left = 0
      var right = height.length - 1
      while(left < right) {
        max = Math.max(max, Math.min(height[right], height[left]) * (right - left))
        if (height[right] > height[left]) {
          left ++
        } else {
          right -- 
        }
      }
      return max
  };

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数

function moveZeroes(nums: number[]): void {
    var len = nums.length
    while(len --) {
      var index = nums.indexOf(0)
      if (index > -1) {
        nums.splice(index, 1)
        nums.push(0)
      }
    }
};

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

function lengthOfLongestSubstring(s: string): number {
    var max = 0
    var res = []
    var sArr = s.split('')
    for (let i = 0; i < sArr.length; i ++) {
        var temp = sArr[i]
        var index = res.indexOf(temp)
        res.push(temp)
        if (index > -1) {
            res.splice(0, index + 1)
        } 
        max = Math.max(max, res.length)
    }
    return max
};

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

function maxSubArray(nums) {
    var sum = 0
    var ans = nums[0]
    for (let num of nums) {
        if (sum > 0) {
            sum = sum + num
        } else {
            sum = num;
        }
        ans = Math.max(sum, ans)
    }
    return ans
};
// test
var nums = [-2,1,-3, 4,-1,2,1,-5,4]
maxSubArray(nums)

参考

• js算法集合