寒假CS每日打卡 Feb.8th

演算法部分

1.Acwing 入門組每日一題
題目：不高興的津津

津津上初中了，
媽媽認為津津應該更加用功學習，所以津津除了上學之外，還要參加媽媽為她報名的各科復習班，
另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴，
但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興，
假設津津不會因為其它事不高興，并且她的不高興不會持續到第二天，
請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興，

輸入格式
輸入檔案包括七行資料，分別表示周一到周日的日程安排，
每行包括兩個小于10的非負整數，用空格隔開，分別表示津津在學校上課的時間和媽媽安排她上課的時間，

輸出格式
輸出檔案包括一行，這一行只包含一個數字，
如果不會不高興則輸出0，如果會則輸出最不高興的是周幾（用1,?2,?3,?4,?5,?6,?7分別表示周一，周二，周三，周四，周五，周六，周日），
如果有兩天或兩天以上不高興的程度相當，則輸出時間最靠前的一天，

輸入樣例：
5 3
6 2
7 2
5 3
5 4
0 4
0 6
輸出樣例：
3

題解：
??現在入門組的題目越來越水了，

代碼：

#include <iostream>

using namespace std;

int main(){
    int ans = 0, val = -1, a, b;

    for(int i = 1; i <= 7; i ++){
        cin >> a >> b;
        a += b;
        if(a > 8 && a > val)
            val = a, ans = i;
    }
    cout << ans << endl;
    return 0;
}

2.Acwing 提高組每日一題
題目：魚塘釣魚

有 N 個魚塘排成一排，每個魚塘中有一定數量的魚，例如：N=5 時，如下表：

即：在第 1 個魚塘中釣魚第 1 分鐘內可釣到 10 條魚，第 2 分鐘內只能釣到 8 條魚，……，第 5 分鐘以后再也釣不到魚了，
從第 1 個魚塘到第 2 個魚塘需要 3 分鐘，從第 2 個魚塘到第 3 個魚塘需要 5 分鐘，……
給出一個截止時間 T，設計一個釣魚方案，從第 1 個魚塘出發，希望能釣到最多的魚，
假設能釣到魚的數量僅和已釣魚的次數有關，且每次釣魚的時間都是整數分鐘，

輸入格式
共 5 行，分別表示：
第 1 行為 N；
第 2 行為第 1 分鐘各個魚塘能釣到的魚的數量，每個資料之間用一空格隔開；
第 3 行為每過 1 分鐘各個魚塘釣魚數的減少量，每個資料之間用一空格隔開；
第 4 行為當前魚塘到下一個相鄰魚塘需要的時間；
第 5 行為截止時間 T，

輸出格式
一個整數（不超過231?1），表示你的方案能釣到的最多的魚，

資料范圍
1≤N≤100,
1≤T≤1000
輸入樣例：
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
輸出樣例：
76

題解：
??很值得做的一道題目，如果在魚塘之間移動不需要花費時間，那么這道題是不是就是一道貪心呢，先把每個池塘的每分鐘釣魚數量加入大根堆中，然后每次取得堆頂元素，累加答案，然后減去每釣一次減少的數量，之后再加入大根堆中，這樣子直到沒有釣魚時間，那么多了魚塘之間的走動費用，上述方法還有效嘛，是可以的，因為移動費用只會使用一次，可以在第i魚塘釣好了之后再跑到第i + 1個魚塘，我們可是使用列舉來解決，列舉在前 1 個魚塘、在前 2 個魚塘 …在前n個魚塘釣魚的情況，然后取這些情況的最大值，

代碼：

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 110;
int a[MAXN], b[MAXN], c[MAXN];
typedef pair<int, int> PII;

int main(){
    int n, m, ans = 0;

    cin >> n;

    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = 1; i <= n; i ++)
        cin >> b[i];
    for(int i = 1; i < n; i ++)
        cin >> c[i], c[i] += c[i - 1];

    cin >> m;
	//從只在第1個魚塘釣魚遍歷到在所有n個魚塘都釣魚
    for(int i = 1; i <= n; i ++){
    	//預先減去走到魚塘的時間花費，剩下的時間就可以都用來釣魚
        int t = m - c[i - 1], res = 0;
        //按照每分鐘釣魚數量降序排列，因此隊首就是在當前分鐘能釣魚的最大數量
        priority_queue<PII> Q;
		//加入i個魚塘
        for(int j = 1; j <= i; j ++)
            Q.push({a[j], b[j]});    
		//當還有時間并且魚塘非空
        while(t > 0 && !Q.empty()){
        	//取得隊首
            PII tmp = Q.top();
            Q.pop();
            res += tmp.first;
            //釣魚數量每釣一次會遞減
            tmp.first -= tmp.second;
            if(tmp.first > 0)
                Q.push(tmp);
            //時間減 1
            -- t;
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
    return 0;
}

3.LeetCode 每日一題
題目：最長湍流子陣列

當 A 的子陣列 A[i], A[i+1], …, A[j] 滿足下列條件時，我們稱其為湍流子陣列：
若 i <= k < j，當 k 為奇數時， A[k] > A[k+1]，且當 k 為偶數時，A[k] < A[k+1]；
或 若 i <= k < j，當 k 為偶數時，A[k] > A[k+1] ，且當 k 為奇數時， A[k] < A[k+1]，
也就是說，如果比較符號在子陣列中的每個相鄰元素對之間翻轉，則該子陣列是湍流子陣列，
回傳 A 的最大湍流子陣列的長度，

示例 1：
輸入：[9,4,2,10,7,8,8,1,9]
輸出：5
解釋：(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2：
輸入：[4,8,12,16]
輸出：2

示例 3：
輸入：[100]
輸出：1

提示：
1 <= A.length <= 40000
0 <= A[i] <= 10^9

題解：
??DP，dp[i][0] 代表第i個位置下降能得到的最長長度，dp[i][1]代表第i個位置上升能得到的最長長度，狀態轉移很容易求得，

代碼：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size(), ans = 1;
        vector<vector<int>> dp(n, vector<int>(2, 1));

        for(int i = 1; i < n; i ++){
            if(arr[i] < arr[i - 1])
            	//當前位置下降就要求前面一個位置是上升的
                dp[i][0] = max(dp[i][0], dp[i - 1][1] + 1);
            else if(arr[i] > arr[i - 1])
            	//當前位置上升就要求前面一個位置是下降的
                dp[i][1] = max(dp[i][1], dp[i - 1][0] + 1);
            ans = max(ans, max(dp[i][0], dp[i][1]));
        }
        return ans;
    }
};

4.鏈表的中間結點
題目：

給定一個帶有頭結點 head 的非空單鏈表，回傳鏈表的中間結點，
如果有兩個中間結點，則回傳第二個中間結點，
鏈表里的數在1到100之間

樣例 1:
輸入：1->2->3->4->5->null
輸出：3->4->5->null

樣例 2:
輸入：1->2->3->4->5->6->null
輸出：4->5->6->null

題解：
??考察資料結構，使用巧妙的快慢指標來解決，快指標比慢指標每次多移動一個節點，當快指標移動到結尾時，慢指標剛好指向中間位置，

代碼：

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    ListNode * middleNode(ListNode * head) {
        ListNode *slow = head, *fast = head;
        
        while(true){
            if(fast && fast -> next)
                fast = fast -> next -> next;
            else
                break;
            slow = slow -> next;
        }
        
        return slow;
    }
};

書籍部分

None

PS.

1. 阿里云-天池 在線編程平臺較LeetCode來說簡單一點，體驗沒有LeetCode好，不過可以拿來練習，里面也有周賽等活動 鏈接：https://tianchi.aliyun.com/oj