题目描述
给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
实现 Solution class:
- Solution(int[] nums) 使用整数数组 nums 初始化对象
- int[] reset() 重设数组到它的初始状态并返回
- int[] shuffle() 返回数组随机打乱后的结果
解题思路
遍历数组，交换当前数和random生成的一个数，知道数组遍历完成。注意，Random是伪随机，同一个对象对于一个random对象。
198. 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。解题思路
同样的是动态规划，首先找出转移方程。题目给出的限制条件是不能连续拿相邻两个房间的钱，即当前最大的钱为i-2时的钱加上当前房间的钱或者第i-1个房间的钱，当前房间拿钱。即dp[i] =max(dp[i-2]+nums[i],dp[i-1]) 。之后就是考虑边界条件了，即i=0 和i=1时的取值。
53. 最大子序和
题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入:nums = [1]
输出:1
示例:3：提示：
1 <= nums.length <= 3 * 104-105 <= nums[i] <= 105
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解题思路
动态规划解题步骤：
- 确定状态
- 找到转移方程
- 确定初始以及边界条件
- 计算结果
看起来很简单，但是就是死活无法找到转移方程。没办法，只能去评论区偷一手。得到转移方程 dp[i]=num[i]+max(dp[i-1],0); 接下来就水到渠成了，边界条件就是dp[0] = nums[0] 作为初始值开始循环计算统计最大dp[i] 即可。
121.买卖股票的最佳时机
描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解题思路
存在类似的题目有做过类似的题目，122. 买卖股票的最佳时机 II，与现在的题目不同点在于该题可多次出售，此题只能出售一次。只要记住最大最小值即可一次遍历得到最大利益（从新选择最小值后最大值要复位）。
70. 爬楼梯
描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
解题思路
经典动态规划题目,找出状态转移方程f(n) = f(n-1) +f(n-2)即可解题.