1.best-time-to-buy-and-sell-stoc
问题描述：假设你有一个数组，其中第i个元素是某只股票在第i天的价格。
如果你最多只能完成一笔交易(即买一股和卖一股股票)，设计一个算法来求最大利润。
解题思路：我的想法是
1.对于每一个结点求出能获益的最大利润，即i点后的最大值减去i点的值
2.在上述最大之中取最大
2.best-time-to-buy-and-sell-stoc ii
问题描述：假设你有一个数组，其中第i个元素表示某只股票在第i天的价格。
设计一个算法来寻找最大的利润。你可以完成任意数量的交易(例如，多次购买和出售股票的一股)。但是，你不能同时进行多个交易(即，你必须在再次购买之前卖出之前买的股票)。
解题思路：一开始我的思维不够灵活，把问题想得复杂了想先把第i天买入第j天卖出所获利润的表格算出来，从prices[i]最小值点必然买入或最大值点必然卖出的角度思考，贪心都不行，要动态规划才可能求出。网上看了别人的思路，才发现原来问题这样简单：
- 只要第二天的价格高于第一天，就进行交易。(这样的话就默认可以同一天内先卖出再买进)
写出来代码比第一题还要短。
3.best-time-to-buy-and-sell-stoc iii
问题描述：假设你有一个数组，其中第i个元素是某只股票在第i天的价格。
设计一个算法来求最大的利润。你最多可以进行两次交易。
注意:你不能同时进行多个交易(即，你必须在再次购买之前出售之前买的股票)。
解题思路：一开始被问题难住了，看了讨论之后又整理了思路。为不采用盲目包里搜索的方式，尽可能做有效的查找。因第一次交易本身对第二次交易有影响，所以“可进行两次交易”的求解方法不是传统分治法的分割，第二次交易要在第一次的基础上进行。而想要在一趟遍历中求出两次交易的最优利润，需要有一个整体的评价标准，每进行下一步操作都假设上一步操作已经完成，而此刻总资产已经可以算出。
（我觉得这实际上是动态规划的思想，此问题中k = 2，常见的动态规划问题k = n）
于是我们可设第一次买入后的总资产 buy1[i] = -prices[i]
第一次卖出后获得的利润为 sell1 = max(sell1, buy1 + prices[i])
第二次买入 buy2 = max(sell1, sell1 - prices[i])
第二次卖出 sell2 = max(sell2, buy2 + prices[i])
public int maxProfit(int[] prices) {
int buy1 = -65535, sell1 = 0, buy2 = -65535, sell2 = 0;
for(int i = 0; i < prices.length; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);//保证第一次买卖后资产最多
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);//保证第二次买卖后资产最多
}
return sell2;
}4.spiral-matrix
问题描述：给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
例如，给出以下矩阵：
[[ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]
你应该返回[1,2,3,6,9,8,7,4,5]。
解题思路：
每次循环做一层（由外向内），需解决两个问题：每一层内部该怎么做？（最后剩下的）单独行/列怎样处理？
整体分为两步：
1.每一次循环做一层分为上下左右四条边
2.遇到一层不够完整一圈（结束条件）
public ArrayList<Integer> spiralOrder(int[][] matrix) {
int k, i, j, m, n;
ArrayList<Integer> reslist = new ArrayList<>();
m = matrix.length;
if(m==0)
return reslist;
n = matrix[0].length;
//每一次循环做一层：从外向里
int step = (int) Math.min(Math.ceil((double)m/2),Math.ceil((double)n/2));
for(k = 0; k<step; k++){
//判断结束
if((n-2*k)==1 || (m-2*k)==1) {
for(i = k; i<m-k; i++) {
for(j = k; j<n-k; j++)
reslist.add(matrix[i][j]);
}
return reslist;
}
//part1：上边
for(i = k; i<n-k; i++)
reslist.add(matrix[k][i]);
//part2：右边
for(i = k+1; i<m-k; i++)
reslist.add(matrix[i][n-k-1]);
//part3：下边
for(i = n-k-2; i>=k; i--)
reslist.add(matrix[m-k-1][i]);
//part4：左边
for(i = m-k-2; i>k; i--)
reslist.add(matrix[i][k]);
}
//所有层刚好都是完整一圈
return reslist;
}5.spiral-matrix ii
问题描述：给定一个整数n，将数字1到n^2按螺旋的顺序填入n×n的矩阵
例如：给出的n=3，你应该返回如下矩阵：
[[ 1, 2, 3 ],[ 8, 9, 4 ],[ 7, 6, 5 ]]
解题思路：还是上一题的思想，将add改为数组赋值语句，好像比上一题还要简单。
public int[][] generateMatrix(int n){
int k, i, j;
int[][] res = new int[n][n];
//每一次循环做一层：从外向里
int step = (int) Math.ceil((double)n/2);
int num = 1;
for(k = 0; k<step; k++){
//part1：上边
for(i = k; i<n-k; i++){
res[k][i] = num;
num++;
}
//part2：右边
for(i = k+1; i<n-k; i++) {
res[i][n-k-1] = num;
num++;
}
//part3：下边
for(i = n-k-2; i>=k; i--) {
res[n-k-1][i] = num;
num++;
}
//part4：左边
for(i = n-k-2; i>k; i--) {
res[i][k] = num;
num++;
}
}
return res;
}6.first-missing-positive
问题描述：给出一个无序的整数型数组，求不在给定数组里的最小的正整数.例如：
给出的数组为[1,2,0] 返回3,
给出的数组为[3,4,-1,1] 返回2.
你需要给出时间复杂度在O(n)之内并且空间复杂度为常数级的算法
解题思路：看到题目描述就觉得肯定很简单，没怎么仔细想就开始代码。结果写完的程序稀巴烂，像是筛子总是漏掉各种样例，啪啪打脸。
由题目要求，只能遍历常数次数组，需要在一层循环内完成搜索或者排序操作。我的思路是：遍历一遍数组采用交换的策略将元素归位，最终使得：小于A.length的元素K都归位于A[k-1]。那么如下问题就来了：
- 大于A.length的元素怎样处理才不会影响下一步
- 如果入到要交换的两个元素恰好相等，处理以保证不循环
- 如果要交换的元素a恰好已归位（与本身交换），处理以保证不循环
- 如果要交换后到a位置的元素自然归位，处理以保证不循环
有这么多补丁要打，我觉得只能说明一开始解决问题的逻辑就很垃圾。于是我看了通过的其他人的代码，也是交换的思想，但是出发点不同，他是像冒泡排序一样每一次都将第i位置的元素归位，但实际上完成了k次交换，0=<k<=n,虽然代码能够通过，但我觉得这并不是严格意义上的O(n)复杂度，最好O(n),最坏O(n^2),平均O(nlogn)。
public class Solution {
public int firstMissingPositive(int[] A) {
int n=A.length;
for(int i=0;i<n;i++){
while(A[i]>0&&A[i]<=n&&A[A[i]-1]!=A[i]){
swap(A,i,A[i]-1);
}
}
for(int i=0;i<n;i++){
if(A[i]-1!=i){
return i+1;
}
}
return n+1;
}
public void swap(int[] A,int i,int j){
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}代码反思：即使觉得再简单的问题最开始也要想清楚步骤，用几层循环来完成，精确到是用for 还是 while,对于后续写程序处理具体细节真的很重要。有时用while()需要打很多补丁而for来写就会简洁清晰，反之亦然。
发现一个清晰代码满足O(n)的题目要求，贴在下面供自己学习，代码来自用户：湖人总冠军LA
链接：https://www.nowcoder.com/questionTerminal/ea7ca311264d4c579a1ef6c1f7f69138
来源：牛客网
import java.util.ArrayList;
public class Solution {
/*解题思路：先将数组存入Arraylist中，因为这样遍历数组中的任何一个元素的时间变成O(1),即以空间换取时间。
步骤：（1）遍历数组，找到最大值max，并将数组存入Arraylist中,时间复杂度为O(n)
（2）遍历从正整数1到最大值max之间的数，并判断Arraylist中是否包含该数。若不包含该数字，则该数字就是第一个缺失的正整数；
若循环走到底，即Arraylist包含了1到max之间所有数，则第一个缺失数字就是max后一个数字，即max+1.时间复杂度为O(n)*/
public int firstMissingPositive(int[] A) {
if(A.length == 0)
return 1;
ArrayList<Integer> list = new ArrayList<>();
int max = 0;
//步骤（1）
for(int i = 0;i < A.length;i ++){
list.add(A[i]);
if(A[i] > max){
max = A[i];
}
}
//步骤（2）
for(int i = 1;i <= max;i ++){
if(!list.contains(i))
return i;
}
return max + 1;
}
}7.search-a-2d-matrix
问题描述：请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
例如：对于下面的矩阵：
[↵ [1, 3, 5, 7],↵ [10, 11, 16, 20],↵ [23, 30, 34, 50]↵]
要搜索的目标值为3，返回true；
解题思路：实现功能很简单只需要遍历一次矩阵，就能找出来，而题目的用意就是减少搜索的次数，尽可能查找最少的数组元素。整体需要两层嵌套循环实现，第一层循环判断该在矩阵的哪一行搜索元素，第二层循环进行搜索，第二层循环只会执行一次，达到减少搜索次数的目的。
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
boolean res = false;
int m = matrix.length, n = matrix[0].length;
if(target<matrix[0][0]) return res;
for(int i = 0; i<m; i++){
if(target>matrix[i][n-1])
continue;
for(int j = 0; j<n; j++){
if(target==matrix[i][j])
return true;
}
}
return res;
}
}代码反思：如果有很多补丁需要打的情况，需要从逻辑出发进行优化而不是哪漏补哪。
8.convert-sorted-array-to-binary-search-tree
问题描述：给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）
解题思路：做了链表部分的convert-sorted-list-to-binary-search-tree紧接着就锁了这道题，思路完全相同，只是对数据结构的处理方式有不同，链表只需给出子链的头结点，数组需要标记起止位置；也因此，在递归过程中的终止条件不同。
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if(num.length == 0) return null;
return buildBST(num, 0, num.length-1);
}
public TreeNode buildBST(int[] num,int left,int right){
if(left==right)
return new TreeNode(num[left]);
if(left>right)
return null;
//想要中间（或偏后）的结点
int mid = (right+left)/2+(left+right)%2;
TreeNode root = new TreeNode(num[mid]);
root.left = buildBST(num, left, mid-1);
root.right = buildBST(num, mid+1, right);
return root;
}
}9.merge-sorted-array
问题描述：给出两个有序的整数数组A和B，请将数组B合并到数组A中，变成一个有序的数组
注意：可以假设A数组有足够的空间存放B数组的元素，A和B中初始的元素数目分别为m和n
解题思路：把A copy到C，然后再合并到A.不过题如果这么做毫无思维容量在里边，今天有点急也没仔细想，想敷衍了事。
public class Solution {
public void merge(int A[], int m, int B[], int n) {
int a = 0, b = 0, i;
int[] C = new int[m];
for(i = 0; i<m; i++){
C[i] = A[i];
}
//合并BC 到A
for(i = 0; i<m+n; i++){
//bigger one place in A
if(n==0) break;
if(m!=0 && a!=m &&(b==n || C[a]<B[b])){
A[i] = C[a];
a++;
}
else{
A[i] = B[b];
b++;
}
}
}
}代码反思：看了别人的解，都没有像我这种不动脑做题选手！大家都是从后往前处理，不需要另开空间。
这位 JacobGo！ 大神又一次让我醍醐灌顶，我决定要追随大神的步伐，努力上进
/*
* 最优解：从后往前处理,不需要开辟额外空间
* Runtime: 0 ms.Your runtime beats 45.38 % of java submissions.
*/
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, index = m + n - 1;
while (i >= 0 && j >= 0)
nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
while (j >= 0)
nums1[index--] = nums2[j--];
}
京公网安备 11010502036488号