题面：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
demo-project\14-大厂面试题Leetcode\01-最长公共前缀.ts
export function longestCommonPrefix(strs: string[]): string {
const n = strs.length
if (n <= 0) return ''
let prefix = strs[0]
for (let i = 1; i < n; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.slice(0, prefix.length - 1)
}
if (prefix.length === 0) {
return ''
}
}
return prefix
}
// 测试
console.log('公共前缀:', longestCommonPrefix(["flower","flow","flight"]))
console.log('公共前缀:', longestCommonPrefix(["abc","abd","aaa", "axx"]))
console.log('公共前缀:', longestCommonPrefix(["abc","abd","aaa", "tyh"]))题面：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
思路：使用双指针，是效率最高的一种做法。
right指针的作用，是从头扫描到尾部；left指针默认指向 0 的位置，在发现 right 指针出现了重复的字符时，向左移。
demo-project\14-大厂面试题Leetcode\02-无重复字符的最长子串.ts
function lengthOfLongestSubstring(s: string): number {
const n = s.length
// 1.定义需要用到的变量
const map = new Map<string, number>()
let maxLength = 0
let left = 0
for (let right = 0; right < n; right++) {
const rightChar = s[right]
// 保留最新的索引之前，判断之前这个字符，是否已经出现过
if (map.has(rightChar) && map.get(rightChar)! >= left) {
left = map.get(rightChar)! + 1
}
map.set(rightChar, right)
const currLength = right - left + 1
maxLength = Math.max(currLength, maxLength)
}
return maxLength
}
console.log(lengthOfLongestSubstring("abcabcbb"))题面：给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序，与原始字符串相同，则该字符串称为回文字符串。
思路：考虑两种情况：
- 以一个元素为中心的回文子串；
- 不是以一个元素为中心的回文子串。
demo-project\14-大厂面试题Leetcode\03-最长回文子串.ts
function longestPalindrome(s: string): string {
const n = s.length
if (n <= 1) return s
let start = 0, end = 0
for (let i = 0; i < n; i++) {
const len1 = centerExpand(s, i, i)
const len2 = centerExpand(s, i, i + 1)
const maxLen = Math.max(len1, len2)
if (maxLen > end - start) {
start = i - Math.floor((maxLen - 1) / 2)
end = i + Math.floor(maxLen / 2)
}
}
return s.substring(start, end + 1)
};
function centerExpand(s: string, left: number, right: number): number {
const n = s.length
while (left >= 0 && right < n && s[left] === s[right]) {
left--
right++
}
return right - left - 1
}
// 测试
console.log(longestPalindrome("cbbd"))递归和栈结构，通常都可以相互转化。
题面：给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表，应该同样使用 TreeNode，其中 right 子指针，指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表，应该与二叉树先序遍历顺序相同。
demo-project\14-大厂面试题Leetcode\04-二叉树展开为链表.ts
// 二叉树
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
function flatten(root: TreeNode | null): void {
// 边界判断
if (!root) return
// 栈结构
const stack = [root]
let prev: TreeNode | null = null
while (stack.length) {
const curr = stack.pop()!
if (prev) {
prev.right = curr
prev.left = null
}
// 将左右两个节点，压入到栈中
if (curr.right) stack.push(curr.right)
if (curr.left) stack.push(curr.left)
prev = curr
}
};题面：给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为 '+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是向零截断。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位整数表示。
demo-project\14-大厂面试题Leetcode\05-逆波兰表达式.ts
function evalRPN(tokens: string[]): number {
const stack: number[] = []
// 遍历所有的 tokens
for (const token of tokens) {
switch (token) {
case '+':
const a = stack.pop()!
const b = stack.pop()!
stack.push(b + a)
break;
case '-':
const c = stack.pop()!
const d = stack.pop()!
stack.push(d - c)
break;
case '*':
const e = stack.pop()!
const f = stack.pop()!
stack.push(f * e)
break;
case '/':
const g = stack.pop()!
const h = stack.pop()!
stack.push(Math.trunc(h / g))
break;
default:
stack.push(Number(token))
break;
}
}
return stack.pop()!
};
// 测试
console.log(evalRPN(["2","1","+","3","*"]))V8 引擎运行 JS 代码，进行词法分析后，会生成 tokens 数组。
编译器底层，基本都是“逆波兰表达式”。
Math.trunc()，将数字的小数部分去掉，只保留整数部分。