算法日常练习3

2021年9月28日练习。

LintCode 1300

事实上，当\(n \leq 3\)时，总是能赢；\(n \geq 4\)时，只要\(n\)是4的倍数一定输，其他情况我一定赢，因此只要返回 (n%4!=0) 即可。

class Solution {
public:
    /**
     * @param n: an integer
     * @return: whether you can win the game given the number of stones in the heap
     */
    bool canWinBash(int n) {
        return (n%4!=0);//在c++中自动将非零的数转换为true
    }
};

LintCode 1609

快慢指针基本题目。

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

class Solution {
public:
    /**
     * @param head: the head node
     * @return: the middle node
     */
    ListNode * middleNode(ListNode * head) {
        if(!head || !head->next){
            return head;
        }
        else{
            ListNode* f=head,*s=head;
            while(f&&f->next){
                f = f->next->next;
                s=s->next;
            }
            return s;
        }
    }
};

北京北站的故事

题目描述

北京北站现有\(n\)节车厢从A方向驶入，并按进站顺序依次编号，站长要求这些车厢按照指定的顺序从B 向使出。Qingyong从《交通运输概论》课程学习到，完成站长的任务需要借助中转站（记为C方向）。假设C可以停放任意数量的车厢，但是C末端封闭，因此，驶入C站的车厢必须按照相反的顺序驶出。Qingyong进一步限定允许的操作如下：

让A方向最前面的车厢从B方向驶出车站；
让A方向最前面的车厢驶入中转站C；
让中转站 C 中最后驶入的车厢从 B 方向驶出车站。

请帮助Qingyong判断能否让车厢按照站长给定的顺序驶出北京北站。

输入数据

输入共包括两行。

第一行为一个正整数\(n\)，代表车厢总数，\(n < 100000\)。

第二行有\(n\)个正整数，代表站长要求的车厢驶出车站顺序。

输出数据

Yes 或者 No。

样例输入

1 2	5 4 5 3 2 1

样例输出

Yes

实际上这个题目考察如何用栈调整队列中元素的顺序。

设置两个变量 in_num 与 out_num 分别代表当前处于队首的车辆编号以及当前需要出队的车辆编号：

当 in_num == out_num 时， in_num++；
当 in_num > out_num 时，需要将所有在\([\text{in_num} > \text{out_num - 1}]\)区间范围内的车辆编号全部入栈，然后更新 in_num 为 out_num + 1；
否则，需要在栈中取栈顶元素，若栈非空且栈顶元素等于 out_num ，则将栈顶元素出栈；否则不能满足要求。

#include <iostream>
#include <stack>
using namespace std;
int main() {
	int n;
	cin >> n;
	stack<int> s;
	int in_num = 1, out_num;
	for (int i = 0; i < n; i++) {
		cin >> out_num;
		if (in_num == out_num) {
			in_num++;
		}
		else if(out_num > in_num){
			for(int j = in_num; j < out_num; j++){
				s.push(j);
			}
			in_num = out_num + 1;
		}
		else {
			if (!s.empty() && s.top() == out_num) {
				s.pop();
			}
			else {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

割绳子

题目描述

现有\(N\)条绳子，它们的长度分别为\(L_1,L_2,\dots,L_n\)，如果从它们中切割出\(K\)条长度相同的绳子，问这\(K\)条绳子每条最长能有多长？

输入格式

输入共有两行。

第一行包含两个正整数\(N\)和\(K\)，用一个空格分隔。

第二行包含\(N\)个数，依次表示\(N\)条绳子的长度，两数间用一个空格分隔。每条绳子长度的小数不超过两位。

题目数据满足\(1 \leq N \leq 1000,1 \leq K \leq 1000，1 \leq L_i \leq 10000\)。

输出格式

仅包含一个数，表示所得\(K\)断绳子的最大长度，输出四舍五入保留小数点后两位。

题目分析

注意精度问题和搜索效率即可，使用二分查找就可以解决本题目。

#include <vector>
#include <iostream>
using namespace std;
bool valid(vector<int>&length, int mid, int k) {
	for (int i = 0; i < length.size(); i++) {
		k -= length[i] / mid;
	}
	return k <= 0;
}

int main() {
	int n, k;
	cin >> n >> k;
    vector<int> length(n);
	int max_len = 0;
	for (int i = 0; i < n; i++) {
		double temp;
		cin >> temp;
		length[i] = temp * 100;
		max_len = max(max_len, length[i]);
	}
	int l = 1, r = max_len;
	int ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (valid(length, mid, k)) {
			ans = max(mid, ans);
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	cout << fixed << setprecision(2) << ans / 100.0 << endl;
	return 0;
}