动态规划之简单(0-1)背包问题 动态规划的经典题目背包问题，今天尝试解答了一下，现总结如下。 题目描述给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？ 举个简单的例子，输入如下： N = 3, W = 4 wt = [2, 1, 3] val = [4, 2, 3]...

字符串转换整数 (atoi)题目描述 原题地址：https://leetcode-cn.com/problems/string-to-integer-atoi 请你来实现一个 atoi 函数，使其能将字符串转换成整数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下： 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数...

有效的数独题目 题目地址：https://leetcode-cn.com/problems/valid-sudoku/submissions/ 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 上图是一个部...

零钱兑换题目 题目地址：https://leetcode-cn.com/problems/coin-change 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例1： 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = ...

存在重复元素 leetcode中，存在重复元素相关的题目 题目1题目描述 题目地址：https://leetcode-cn.com/problems/contains-duplicate/ 给定一个整数数组，判断是否存在重复元素。 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。 示例 1: 输入: [1,2,3,1] 输出: t...

只出现一次的数字 leetcode中，只出现一次的数字相关的题目 题目1 题目地址：https://leetcode-cn.com/problems/single-number 题目描述给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 示例 1: 输入: [2,...

买卖股票的最佳时机 leetcode中，买卖股票相关的题目 I 题题目 题目地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能...

题目 题目地址：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/ 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例1： 给定数组 nums = ...

题目 题目地址：https://leetcode-cn.com/problems/keys-and-rooms/ 有N个房间，开始时你位于0号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上，对于每个房间i都有一个钥匙列表 rooms[i]，每个钥匙rooms[i][j]由[0,1，...，N-1]中的一个整数表示，其中N =...

题目 题目地址：https://leetcode-cn.com/problems/01-matrix/ 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例 1: 输入: 0 0 0 0 1 0 0 0 0输出: 0 0 0 0 1 0 0 0 0示例 2: 输入: 0 0 0 0 1 0 1 1 1输出： 0 0 0 0 1 0 1...