博客主页 | 时游

个人Demo项目

内含各种功能演示，例如三维可视化、二维绘图

待添加

待添加项目

待添加

书籍详细描述

待添加

待添加项目

1021.删除最外层的括号

/*
 * @lc app=leetcode.cn id=1021 lang=typescript
 *
 * [1021] 删除最外层的括号
 */

// @lc code=start
function removeOuterParentheses(s: string): string {
	let stack = [];
	let final: string[] = [];
	let l = 0,
		r = 0;
	while (r < s.length) {
		if (s[r] == "(") {
			stack.push(1);
		} else {
			stack.pop();
		}

		if (stack.length == 0) {
			// 结束
			final.push(s.slice(l + 1, r));
			l = r + 1;
		}
		r++;
	}

	console.log(final);

	return final.join("");
}

console.log(removeOuterParentheses("(()())(())"));

// @lc code=end

时游小于 1 分钟

108.将有序数组转换为二叉搜索树

/*
 * @lc app=leetcode.cn id=108 lang=typescript
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * 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)
 *     }
 * }
 */

/**
 * 二叉搜索树：左子树所有节点都小于该节点，右子树都大于该节点
 *
 *
 *
 * */

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 sortedArrayToBST(nums: number[]): TreeNode | null {
	if (!nums.length) return null;
	return useRecursion(nums, 0, nums.length - 1);
}

function useRecursion(nums: number[], l: number, r: number): TreeNode | null {
	if (l > r) {
		return null;
	}
	let mid = l + +Math.floor((r - l) / 2);
	let middle = nums[mid]; // 向下取整
    
	const node = new TreeNode(middle);

	node.left = useRecursion(nums, l, mid - 1);
	node.right = useRecursion(nums, mid + 1, r);

	return node;
}

console.log(sortedArrayToBST([-10, -3, 0, 5, 9])); // 数据一定是升序的数组

// @lc code=end

时游小于 1 分钟

1099.小于-k-的两数之和

/*
 * @lc app=leetcode.cn id=1099 lang=typescript
 *
 * [1099] 小于 K 的两数之和
 */

// @lc code=start

/* 暴力循环法，复杂度很高 */
// function twoSumLessThanK(nums: number[], k: number): number {
// 	let max = -1;
// 	nums.map((num, index) => {
// 		let diff = k - num;
// 		nums.slice(index + 1).map(num2 => {
// 			if (num2 < diff) {
// 				if (num + num2 > max) {
// 					max = num + num2;
// 				}
// 			}
// 		});
// 	});
// 	return max; // -1表示不存在
// }

/* 双指针 */
function twoSumLessThanK(nums: number[], k: number): number {
	// 排序，从小到大
	nums = nums.sort((a, b) => a - b);
	let l = 0,
		r = nums.length - 1;
	let result = -1;
	while (l < r) {
		let currentSum = nums[l] + nums[r];
		if (currentSum >= k) {
			r--;
		} else {
			if (currentSum > result) {
				result = currentSum;
			}
			l++;
		}
	}
	return result;
}

let nums = [
		358, 898, 450, 732, 672, 672, 256, 542, 320, 573, 423, 543, 591, 280,
		399, 923, 920, 254, 135, 952, 115, 536, 143, 896, 411, 722, 815, 635,
		353, 486, 127, 146, 974, 495, 229, 21, 733, 918, 314, 670, 671, 537,
		533, 716, 140, 599, 758, 777, 185, 549,
	],
	k = 1800;

console.log(twoSumLessThanK(nums, k));

// @lc code=end

时游小于 1 分钟

11.盛最多水的容器

/*
 * @lc app=leetcode.cn id=11 lang=typescript
 *
 * [11] 盛最多水的容器
 */

// @lc code=start
// 时间复杂度O(n^2)，空间复杂度O(n)
// function maxArea(height: number[]): number {
// 	let max = 0;
// 	for (let i = 0; i < height.length; i++) {
// 		for (let j = i + 1; j < height.length; j++) {
// 			let area = (j-i)*Math.min(height[i],height[j])
// 			if(area>max){
// 			    max = area
// 			}
// 		}
// 	}
// 	return max;
// }

function maxArea(height: number[]): number {
	let l = 0,
		r = height.length - 1;
	let max = 0;
	while (l < r) {
		let area = (r - l) * Math.min(height[l], height[r]);
		max = Math.max(max, area);

		if (height[l] > height[r]) {
			r--;
		} else {
			l++;
		}
	}
	return max;
}
// @lc code=end

时游小于 1 分钟

1133.最大唯一数

/*
 * @lc app=leetcode.cn id=1133 lang=typescript
 *
 * [1133] 最大唯一数
 */

// @lc code=start

// 复杂度过高，不建议
// function largestUniqueNumber(nums: number[]): number {
// 	let hasRepet: number[] = [];
// 	nums.map((item, index) => {
// 		if (nums.slice(index + 1, nums.length).includes(item)) {
// 			hasRepet.push(item);
// 		}
// 	});
// 	// 剔除有重复的数字
// 	nums = nums.sort((a, b) => b - a).filter(item => !hasRepet.includes(item));

// 	return nums.length ? nums[0] : -1;
// }

interface NumberMap {
	[index: number]: number | null;
}
function largestUniqueNumber(nums: number[]): number {
	let map: NumberMap = {};
	nums.map(num => {
		if (map[num]) {
			map[num]++;
		} else {
			map[num] = 1;
		}
	});
	let max = -1;
	Object.keys(map).map(key => {
		let number = Number(key);
		if (map[number] == 1) {
			if (number > max) {
				max = number;
			}
		}
	});

	return max;
}

console.log(largestUniqueNumber([1, 2, 3, 3, 4, 4]));
// @lc code=end

时游小于 1 分钟

118.杨辉三角

/*
 * @lc app=leetcode.cn id=118 lang=typescript
 *
 * [118] 杨辉三角
 */

// @lc code=start
// 注意：递归方式生成杨辉三角在行数较大时可能会导致性能问题。因此，对于大型的杨辉三角，最好使用循环方式生成。
function generate(numRows: number): number[][] {
	let row: number[][] = [];
	for (let i = 0; i < numRows; i++) {
		row[i] = [];
		row[i][0] = 1;
		for (let j = 0; j < i; j++) {
			let count = row[i - 1][j - 1] + row[i - 1][j];
			row[i][j] = isNaN(count) ? 1 : count;
		}
		row[i][i] = 1;
	}
	return row;
}
// @lc code=end

时游小于 1 分钟

119.杨辉三角-ii

/*
 * @lc app=leetcode.cn id=119 lang=typescript
 *
 * [119] 杨辉三角 II
 */

// @lc code=start
function getRow(rowIndex: number): number[] {
	let res: number[][] = [];
	for (let i = 0; i < rowIndex + 1; i++) {
		res[i] = [];
		res[i][0] = 1;
		for (let j = 0; j < i; j++) {
			let count = res[i - 1][j - 1] + res[i - 1][j];
			res[i][j] = isNaN(count) ? 1 : count;
		}
		res[i][i] = 1;
	}
	return res[rowIndex];
}
// @lc code=end

时游小于 1 分钟

12.整数转罗马数字

/*
 * @lc app=leetcode.cn id=12 lang=typescript
 *
 * [12] 整数转罗马数字
 */

// @lc code=start
function intToRoman(num: number): string {
	const romanNumber = new Map<number, string>([
		[1000, "M"],
		[900, "CM"],
		[500, "D"],
		[400, "CD"],
		[100, "C"],
		[90, "XC"],
		[50, "L"],
		[40, "XL"],
		[10, "X"],
		[9, "IX"],
		[5, "V"],
		[4, "IV"],
		[1, "I"],
	]);

	let res: string = "";
	while (num > 0) {
		for (const [key, value] of romanNumber) {
			if (num >= key) {
				res += value;
				num -= key;
				break;
			}
		}
	}

    return res
}

console.log(intToRoman(789));


// @lc code=end

时游小于 1 分钟

121.买卖股票的最佳时机

/*
 * @lc app=leetcode.cn id=121 lang=typescript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start

// 数据量过大时，性能很差
// function maxProfit(prices: number[]): number {
// 	let maxs: number[] = [];
// 	prices.map((price, index) => {
// 		if (index !== prices.length - 1) {
// 			let arr = prices.slice(index, prices.length);
// 			let count: number[] = [];
// 			arr.map(cl => {
// 				count.push(cl - price);
// 			});
// 			maxs.push(Math.max(...count));
// 		}
// 	});

// 	let maxData = Math.max(...maxs);
// 	if (maxData <= 0) {
// 		return 0;
// 	} else {
// 		return maxData;
// 	}
// }

// function maxProfit(prices: number[]): number {
// 	let min = prices[0];
// 	let res = 0;
// 	prices.map(el => {
// 		if (el < min) {
// 			min = el;
// 		} else if (el - min > res) {
// 			res = el - min;
// 		}
// 	});
// 	return res;
// }

// function maxProfit(prices: number[]): number {
// 	let min = prices[0];
// 	let dp = Array.from({ length: prices.length }, () => 0);
// 	dp[0] = 0;
// 	for (let i = 1; i < prices.length; i++) {
// 		if (min > prices[i]) {
// 			min = prices[i];
// 		}
// 		dp[i] = Math.max(dp[i - 1], prices[i] - min);
// 	}
// 	return dp[dp.length - 1];
// }

function maxProfit(prices: number[]): number {
	let min = prices[0];
	let res = 0;
	for (let i = 1; i < prices.length; i++) {
		if (min > prices[i]) {
			min = prices[i];
		}
		res = Math.max(res, prices[i] - min);
	}
	return res;
}

console.log(maxProfit([7, 6, 4, 3, 1]));

// @lc code=end

时游小于 1 分钟

125.验证回文串

/*
 * @lc app=leetcode.cn id=125 lang=typescript
 *
 * [125] 验证回文串
 */

// @lc code=start
function isPalindrome(s: string): boolean {
	// 剔除非字母字符后转为小写
	s = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
	// 定义双指针
	let l = 0,
		r = s.length - 1;
	// 拆分为数组
	let arr = s.split("");
	let res = true;

	while (l < r) {
		if (arr[l] != arr[r]) {
			res = false;
			break;
		}
		l++;
		r--;
	}
	return res;
}

isPalindrome("0P");
// @lc code=end

时游小于 1 分钟

...

跳转到:

时游的个人博客

1021.删除最外层的括号

108.将有序数组转换为二叉搜索树

1099.小于-k-的两数之和

11.盛最多水的容器

1133.最大唯一数

118.杨辉三角

119.杨辉三角-ii

12.整数转罗马数字

121.买卖股票的最佳时机

125.验证回文串