https://leetcode-cn.com/tag/array/
题目汇总
106. 从中序与后序遍历序列构造二叉树中等
118. 杨辉三角简单
119. 杨辉三角 II简单
120. 三角形最小路径和中等
121. 买卖股票的最佳时机简单
122. 买卖股票的最佳时机 II简单
123. 买卖股票的最佳时机 III困难※※
126. 单词接龙 II困难※※※
128. 最长连续序列困难
152. 乘积最大子数组中等※
106. 从中序与后序遍历序列构造二叉树中等
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出中序遍历 inorder = [9,3,15,20,7]，后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
与 105. 从前序与中序遍历序列构造二叉树类似
思路：递归
根据中序遍历和后序遍历可以确定二叉树，具体过程为：
根据后序序列最后一个结点确定根结点
根据根结点在中序序列中的位置分割出左右两个子序列
对左子树和右子树分别递归使用同样的方法继续分解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :13 ms
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length == 0 || inorder.length == 0)
return null;
TreeNode root = new TreeNode(postorder[postorder.length-1]);
for(int i=0;i<inorder.length;i++){
if(inorder[i]==postorder[postorder.length-1]){
root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
root.right = buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),
Arrays.copyOfRange(postorder,i,postorder.length-1));
break;
}
}
return root;
}
}
118. 杨辉三角简单
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
思路：
递推公式 array[i][j] = array[i-1][j-1] + array[i-1][j]
class Solution {//执行用时 :1 ms
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int[][] array = new int[numRows][numRows];
if(numRows == 0)
return res;
for(int i=0;i<numRows;i++){
List<Integer> sub = new ArrayList<>();
for(int j = 0;j <= i;j++){
if(j == 0 || j == i){
array[i][j] = 1;
}else{
array[i][j] = array[i-1][j-1] + array[i-1][j];
}
sub.add(array[i][j]);
}
res.add(sub);
}
return res;
}
}
119. 杨辉三角 II简单
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
输入: 3
输出: [1,3,3,1]
思路：与上题类似
class Solution {
public List<Integer> getRow(int rowIndex) {//执行用时 :1 ms
Integer[] array = new Integer[rowIndex+1];
// 将数组所有元素填充1
for(int i=0;i<=rowIndex;i++){
array[i] = 1;
}
for(int i=0;i<=rowIndex;i++){
for(int j = i;j >= 0;j--){
if(j == 0 || j == i){
array[j] = 1;
}else{
array[j] += array[j-1];
}
}
}
return Arrays.asList(array);//把数组转换成集合
}
}
120. 三角形最小路径和中等
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
自顶向下的最小路径和为11（即，2 + 3+ 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
思路：动态规划
自底向上，从倒数第二行开始计算每个数字到下一个节点的最小值并加上当前节点值存入当前节点，最后顶点中存储的就是最终的最短路径结果。
class Solution {//执行用时 :3 ms
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0)
return 0;
int[][] dp = new int[triangle.size()+1][triangle.size()+1];
for(int i=triangle.size()-1;i>=0;i--){
List<Integer> list = triangle.get(i);
for(int j=0;j<list.size();j++){
dp[i][j] = Math.min(dp[i+1][j] , dp[i+1][j+1])+list.get(j);
}
}
return dp[0][0];
}
}
121. 买卖股票的最佳时机简单
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路：
找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。
class Solution {
public int maxProfit(int[] prices) {//执行用时 :1 ms
if(prices == null || prices.length <= 1)
return 0;
int max = 0;//最大利润
int min = prices[0];//历史最低价格
for(int i=0;i<prices.length;i++){
if(prices[i]<min){
min = prices[i];
}
else if(prices[i]-min>max){
max = prices[i] - min;
}
}
return max;
}
}
122. 买卖股票的最佳时机 II简单
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
思路：贪心算法（局部最优的选择）
第 i 天与第 i - 1 的价格进行比较，如果差值为正数，就记入总利润，这样的过程和交易的最后结果是等价的。
class Solution {
public int maxProfit(int[] prices) {//执行用时 :1 ms
if(prices == null || prices.length <= 1)
return 0;
int profit = 0;
for(int i=1;i<prices.length;i++){
int temp = prices[i] - prices[i-1];
if(temp > 0)
profit += temp;
}
return profit;
}
}
123. 买卖股票的最佳时机 III困难※※
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
思路：动态规划
用一个状态转移方程秒杀了 6 道股票买卖问题，看了很久才看懂
出处：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/关键就在于列举出所有可能的「状态」，然后想想怎么穷举更新这些「状态」。一般用一个多维 dp 数组储存这些状态，从 base case 开始向后推进，推进到最后的状态，就是我们想要的答案。
class Solution {
public int maxProfit(int[] prices) {//执行用时 :6 ms, 在所有 Java 提交中击败了51.40%
if (prices.length == 0)
return 0;
int max_k = 2;
int[][][] dp = new int[prices.length][max_k + 1][2];
for (int i = 0; i < prices.length; i++){
for (int k = max_k; k >= 1; k--) {
if (i - 1 == -1) {
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
return dp[prices.length - 1][max_k][0];
}
}
126. 单词接龙 II困难※※※
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord到 endWord的最短转换序列。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord是非空的，且二者不相同。
示例 1:
输入:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
思路：回溯
知道是回溯，但是代码写不对，看精选解题吧
https://leetcode-cn.com/problems/word-ladder-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-3/
128. 最长连续序列困难
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是[1, 2, 3, 4]。它的长度为 4。
思路：哈希表
class Solution {
public int longestConsecutive(int[] nums) {//执行用时 :6 ms,73.67%
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num-1)) {//当前数字-1不在哈希表里的数字，作为连续序列的第一个数字去找对应的最长序列
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum+1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
152. 乘积最大子数组中等※
给你一个整数数组
nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路：动态规划
遍历数组时计算当前最大值，不断更新
令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
当负数出现时则imax与imin进行交换再进行下一步计算
来自精选解题自己好几次都提交失败了，膜拜大佬！！！
class Solution {
public int maxProduct(int[] nums) {
if(nums == null || nums.length <= 0)
return 0;
if(nums.length == 1)
return nums[0];
int result = Integer.MIN_VALUE;
int max = 1;
int min = 1;
for(int i=0;i<nums.length;i++){
if(nums[i] < 0){
int temp = max;
max = min;
min = temp;
}
max = Math.max(max * nums[i], nums[i]);
min = Math.min(min * nums[i], nums[i]);
result = Math.max(max, result);
}
return result;
}
}
网友评论