Leetcode 752 Open the Lock

题目原文

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
The lock initially starts at '0000', a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

Note:

1. The length of deadends will be in the range [1, 500].
2. target will not be in the list deadends.
3. Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

题意分析

转自 ： here

从初始状态“0000”开始转动，每次只能将其中一位转动一格，可正转可反转，同时deadends中有多个状态，如果转到该状态则不能继续，也即必不可转到目标结果。求问转到目标结果的最小次数。

解法分析

本题需要找到一个最小次数，通常需要运用BFS，在BFS中加入剪枝，并且对于到过的状态建立unordered_set，通过上述方法减少遍历次数。C++代码如下：

class Solution {
public:
   /* static bool isEnd(string a,vector<string>& deadends){
        for(auto k:deadends){
            if(a==k)
                return 1;
        }
        return 0;
    }*/
    int openLock(vector<string>& deadends, string target) {
        queue<string> myQue;
        unordered_set<string> dde(deadends.begin(),deadends.end());
        if(dde.count("0000"))
            return -1;
        myQue.push("0000");
        int queSize=1;
        int layer=0;
        int i,j;
        string temp,temp1;
        unordered_set<string> mySet;
        mySet.insert("0000");
        while(!myQue.empty()){
            layer++;
            queSize=myQue.size();
            for(i=0;i<queSize;i++){
                temp=myQue.front();
                for(j=0;j<4;j++){
                    temp1=temp;//add
                    if(temp1[j]=='9')
                        temp1[j]='0';
                    else
                        temp1[j]+=1;
                    if(temp1==target)
                        return layer;
                    if(!dde.count(temp1)&&!mySet.count(temp1)){            
                            myQue.push(temp1);
                            mySet.insert(temp1);                            
                    }
                    temp1=temp;//sub
                    if(temp1[j]=='0')
                        temp1[j]='9';
                    else
                        temp1[j]-=1;
                    if(temp1==target)
                        return layer;
                    if(!dde.count(temp1)&&!mySet.count(temp1)){
                            myQue.push(temp1);
                            mySet.insert(temp1);                   
                    }
                }
                myQue.pop(); 
            }
        }
        return -1;  
    }
};

上述代码不超时的关键除了剪枝和记录去过的状态以外，还在于检测一个状态是否deadend的方法，如果采用每次都遍历deadend一遍的方法则会超时，如果将deadend做成一个unordered_set，则可以是查询复杂度从O(n)降到O(1)。

Leetcode 718 Maximum Length of Repeated Subarray

题目原文

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

转自 ： here

题意分析

给定两个长度不一定相等的整型数组，找出他们间相同子数组的最大长度。

解法分析

此题采用动态规划方法，关键是找到最优子结构，首先我想到的是用bothLen[i][j]表示以A[i],B[j]结尾的数组的相同子数组的最长长度，但是这样做不能得到最优子结构，因此用bothLen[i][j]表示以A[i],B[j]结尾的相同子数组的长度，bothLen[i][j]=(A[i]==B[j])?bothLen[i-1][j-1]+1:0，C++代码如下：

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<vector<int>> bothLen(A.size()+1,vector<int>(B.size()+1));
        int maxLen=0;
        for(int i=1;i<=A.size();i++){
            for(int j=1;j<=B.size();j++){
                bothLen[i][j]=(A[i-1]==B[j-1])?bothLen[i-1][j-1]+1:0;
                maxLen=max(bothLen[i][j],maxLen);
            }     
        }
        return maxLen;  
    }
};

为了减少空间消耗，可以将二维vector转化为一维，但是j的遍历方向需要改变。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<int> bothLen(B.size()+1,0);
        int maxLen=0;
        for(int i=1;i<=A.size();i++){
            for(int j=B.size();j>0;j--){
                bothLen[j]=(A[i-1]==B[j-1])?bothLen[j-1]+1:0;
                maxLen=max(bothLen[j],maxLen);
            }     
        }
        return maxLen;  
    }
};

这里bothLen[j]表示了bothLen[j][i],bothLen[j-1]表示了bothLen[j-1][i-1]，为了达到这个效果j需要从大往小变，以免覆盖i-1时的值。因此对于一维数组的递归式，如a[i]=a[i-1]+1，这种可以用一个变量表示，而a[i]=a[i-1]+a[i-2]，可以用两个变量表示，二维如a[i][j]=a[i][j-1]可以用a[i]表示，而本题这种需要通过改变j的遍历方向减少所需空间。当然也可以将将二维a[i][j]变为a[2][j],第一维大小固定为2.

[LeetCode] Game of Life 生命游戏

 solve it in-place

from here

每一个位置有两种状态，1为活细胞，0为死细胞；现在我们可以丰富每一个位置上的信息，让它能表示四种状态：

状态0： 死细胞转为死细胞

状态1： 活细胞转为活细胞

状态2： 活细胞转为死细胞

状态3： 死细胞转为活细胞

最后我们对所有状态对2取余，那么状态0和2就变成死细胞，状态1和3就是活细胞，这样可以获得一次转化的结果。

class Solution {
public:
    void gameOfLife(vector<vector<int> >& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
        int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int cnt = 0;
                for (int k = 0; k < 8; ++k) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2)) {
                        ++cnt;
                    }
                }
                if (board[i][j] && (cnt < 2 || cnt > 3)) board[i][j] = 2;
                else if (!board[i][j] && cnt == 3) board[i][j] = 3;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                board[i][j] %= 2;
            }
        }
    }
};

Leetcode 121 Best Time to Buy and Sell Stock

题目原文

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

转自：here

题意分析

本题是一个简单的求最优解问题，只能买卖一次股票，求最大收益，当卖的时候的价格比买的时候高，收益为0。

解法分析

本题采用动态规划方法求解。如果用暴力方法，显而易见算法复杂度为O(n^2)，所以一般用动态规划该方法复杂度变为o(n)，只有一个for循环，也就是通过遍历一次原序列就能得到解。首先分析最优子结构，令从左开始的一个子序列中最小元素为a，下一个元素为b，如果b比a小，则算上b后的序列的最小元素就是b，否则仍是a；如果b比a大，则求其差值，与Pro比较，如果差值大于pro，则修改pro的值，否则pro的值不变。这是一个简单的自底向上的动态规划问题。C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0||n==1)
            return 0;
        int pro=0,min=prices[0],i,temp;
        for(i=1;i<=n-1;i++){
            if(prices[i]>min){
                temp=prices[i]-min;
                if(temp>pro)
                    pro=temp;
            }
            else
                min=prices[i];
        }
        return pro;   
    }
};

由于只有一个for循环，所以复杂度为O(n)，注意对空输入和只有一个元素的输入的处理，都应输出0。

Another way, from here


这道题求进行一次交易能得到的最大利润。如果用brute force的解法就是对每组交易都看一下利润，取其中最大的，总用有n*(n-1)/2个可能交易，所以复杂度是O(n^2)。
很容易感觉出来这是动态规划的题目，其实跟Maximum Subarray非常类似，用“局部最优和全局最优解法”。思路是维护两个变量，一个是到目前为止最好的交易，另一个是在当前一天卖出的最佳交易（也就是局部最优）。递推式是local[i+1]=max(local[i]+prices[i+1]-price[i],0), global[i+1]=max(local[i+1],global[i])。这样一次扫描就可以得到结果，时间复杂度是O(n)。而空间只需要两个变量，即O(1)。代码如下：

public int maxProfit(int[] prices) {
    if(prices==null || prices.length==0)
        return 0;
    int local = 0;
    int global = 0;
    for(int i=0;i<prices.length-1;i++)
    {
        local = Math.max(local+prices[i+1]-prices[i],0);
        global = Math.max(local, global);
    }
    return global;
}

这种题目的解法非常经典，不过是比较简单的动态规划。这道题目还有两个变体，Best Time to Buy and Sell Stock II和Best Time to Buy and Sell Stock III，虽然题目要求比较像，但是思路却变化比较大，Best Time to Buy and Sell Stock II可以交易无穷多次，思路还是比较不一样，而Best Time to Buy and Sell Stock III则限定这道题交易两次，其实还可以general到限定交易k次，会在这道题目中仔细讲解，有兴趣的朋友可以看看哈。

Leetcode 122 Best Time to Buy and Sell Stock II

题目原文

Say you have an array for which the i^th element is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

转自：here

题意分析

本题与121题同为买卖问题，不同的是121只能买卖一次，而本题可以买卖多次，但每次买必须在卖过之后。121题采用简单的自底向上动态规划方法解，本题将采用贪心策略。

解法分析

本题是一个最优化问题，采用动态规划方法有点杀鸡焉用宰牛刀，本题我采用贪心策略。使用贪心策略要考虑两点，一是贪心选择，二是最优子结构。首先看贪心选择，这里贪心选择为一次贪心买卖。对于买入的时机，如果下一天的值更小，则选择下一天买，这样肯定能比在前一天买获得更多收益，如果后一天的值大于前一天买入值了，则开始考虑是否卖出，遍历剩下的天数，直到数值开始下降，在下降的前一天卖出，这样一次贪心的买卖完成，剩下的天数为子问题，具有最优子结构。C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i;
        auto n=prices.size();
        if(n==0||n==1)
            return 0;
        int maxPro=0;
        int buy=prices[0],sell;
        for(i=0;i<n;i++){
            buy=prices[i];
            if(prices[i+1]<=buy)
                buy=prices[i+1];  
            else{
                while((prices[i]<=prices[i+1])&&(i+1)<n)
                    i++;
                sell=prices[i];
                maxPro+=(sell-buy);
            }   
        }
        return maxPro;      
    }
};

算法复杂度为O(n)，用buy和sell来保存每次买卖的价格。