Explore

Luyện thuật toán

Hiếu Trần Ngọc

Buổi 1: Longest Palindromic Substring ( tìm chuổi con đối xứng có độ dài dài nhất)

requirement:

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"

Output: "bb"

Example 3:

Input: s = "a"

Output: "a"

Example 4:

Input: s = "ac"

Output: "a"

Solutions:

Hiếu

- liệt kê tất cả các chuổi con có độ dài lớn hơn hoặc bằng 2,

- kiểm tra tính đối xứng của chuổi con đó

- xử lý các trường hợp đặc biệt

/**

* @param {string} s

* @return {string}

var longestPalindrome = function(s) {

if (s.length < 2) {

return s[0]

}

let result = ''

for (let i = 0; i < s.length; i++) {

for (let j = i + 2; j <= s.length; j ++) {

const subStr = s.substring(i, j)

if (check(subStr) && result.length < subStr.length) {

result = subStr

}

if (result ==='') {

return s[0]

}

return result

};

function check(s) {

if (s.length < 2) {

return true

}

const haftLength = Math.floor(s.length/2)

for (let i = 0 ; i < haftLength; i++) {

const j = s.length - 1 - i

if (s[i] !== s[j]) {

return false

}

return true

}

Buổi 2: 3 Sum closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1

Output: 2

Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1

Output: 0

Solution:

var threeSumClosest = function(nums, target) {

let sum = 0

let min = 0

let result = 0

const num = nums.sort( (a,b) => a -b)

for(let i = 0; i < num.length && i < 3; i++){

sum += num[i];

}

if(num.length <= 3 || sum == target){

return sum

}

min = sum - target

result = sum

for(let i = 0; i< num.length -2; i++){

let j = i + 1;

let k = num.length - 1

while(j < k){

sum = num[i] + num[j] + num[k]

if(sum == target ){

return sum

}

if(Math.abs(min) > Math.abs(sum - target)){

min = sum - target

result = sum

}

if(sum < target){

j++

}else{

k = k - 1

}

return result

};

Buổi 3: Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

⁠

Example 1:

Input: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""

Output: []

Example 3:

Input: digits = "2"

Output: ["a","b","c"]

Solutions:

const numPad = {

'2': ['a', 'b', 'c'],

'3': ['d', 'e', 'f'],

'4': ['g', 'h', 'i'],

'5': ['j', 'k', 'l'],

'6': ['m', 'n', 'o'],

'7': ['p', 'q', 'r', 's'],

'8': ['t', 'u', 'v'],

'9': ['w', 'x', 'y', 'z']

}

var letterCombinations = function(digits) {

const splitDigist = digits.split('')

const result = []

getString('', splitDigist, splitDigist.length, result)

return result

};

function getString(str, digits, length, result) {

if (str.length === length ) {

if (str !== '') {

result.push(str)

}

return

}

const tempDegists = [...digits]

const digist = tempDegists.shift()

numPad[digist].forEach(each => {

const tempStr = str + each

getString(tempStr, tempDegists, length, result)

})

}

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.