Contents

ARST打卡第147周[147/521]

Algorithm

lc553_最优除法

除的结果最大化 = 被除数最大化 + 除数最小化

作为被除数,就前一个大于后一个数,就不要想除 作为除数,就前一个小于后一个数,就多相除

动规吧, 看下答案

发现还有我观察到的规律的直接总结,哭了—动规生疏了,脑子也不灵活了,多训练吧,加油

链接:https://leetcode-cn.com/problems/optimal-division/solution/zui-you-chu-fa-by-leetcode-solution-lf4c/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Node {
    double maxVal, minVal;
    string minStr, maxStr;
    Node() {
        this->minVal = 10000.0;
        this->maxVal = 0.0;
    }
};

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        vector<vector<Node>> dp(n, vector<Node>(n));

        for (int i = 0; i < n; i++) {
            dp[i][i].minVal = nums[i];
            dp[i][i].maxVal = nums[i];
            dp[i][i].minStr = to_string(nums[i]);
            dp[i][i].maxStr = to_string(nums[i]);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j + i < n; j++) {
                for (int k = j; k < j + i; k++) {
                    if (dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal) {
                        dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal;
                        if (k + 1 == j + i) {
                            dp[j][j + i].maxStr = dp[j][k].maxStr + "/" + dp[k + 1][j + i].minStr;
                        } else {
                            dp[j][j + i].maxStr = dp[j][k].maxStr + "/(" + dp[k + 1][j + i].minStr + ")";
                        }
                    }
                    if (dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal) {
                        dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal;
                        if (k + 1 == j + i) {
                            dp[j][j + i].minStr = dp[j][k].minStr + "/" + dp[k + 1][j + i].maxStr; 
                        } else {
                            dp[j][j + i].minStr = dp[j][k].minStr + "/(" + dp[k + 1][j + i].maxStr + ")"; 
                        }
                    }
                }
            }
        }
        return dp[0][n - 1].maxStr;
    }
};

推理总结

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();        
        if (n == 1) {
            return to_string(nums[0]);
        }
        if (n == 2) {
            return to_string(nums[0]) + "/" + to_string(nums[1]);
        }
        string res = to_string(nums[0]) + "/(" + to_string(nums[1]);
        for (int i = 2; i < n; i++) {
            res.append("/" + to_string(nums[i]));
        }
        res.append(")");
        return res;
    }
};

Review

【TED演讲】如何为自己说话

不断学习,扩展自己的实力最重要

我们每个人都是有一个接受范围的,我们时而强势自我,时而懦弱不争。我们的这个域到底是如何界定的?事实上,这个范围并非固定不变,而是会随着语境变化而变化。那时那刻,你的实力在决定着你可接受范围的边界。

重点是,我们的实力小时,我们的行动就变得局限,比如畏手畏脚地做事、需要解决眼前问题但无能为力……这时处于“弱势两难”的境地,如果我们沉默不敢站出来为自己说话则会被忽视、问题得不到解决,如果我们说出来又会受到相应的惩罚(自不量力而失去机会等)。

如何扩大我们的可接受范围,增加我们的实力?两个重要的影响因素。一是你在自己眼中是实力者,这时你会感到更加自信、不会害怕,就会扩大自己的域;二是你在他人眼中是实力者,他们给予了你更大的可接受范围。

具体做法:①为他人声张时,我们就能发掘自己的声音,就像“熊妈妈效应”;②为自己讲话时换位思考,站在对方角度去想对方的需求,更容易产生自己真正想要的结果;③展现自己的灵活力,沟通时抛出选择题更能得到对方的yes;④向他人寻求建议获得盟友,当一个谦恭的咨询者,可以解决“自我推销两难”困境(不推荐则没影响力,推荐则不讨喜),因为就自己的成就征求意见在他人眼中会变得能干且讨喜;⑤掌握专业知识,提高可信度,发掘自身的热情。

Tips

TAILQ 队列之一二事

Share-TAILQ中一两个函数理解

总体结构

https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/算法/TAILQ/TAILQ_structure.png

必须熟悉这个结构,才好理解下面的队列操作,否则会完全不理解

删除一个元素

这个函数挺有趣的,就是*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); 比较难理解

这里其实就是因为*(elm)->field.tqe_prev 就是 ``*(elm)->field.tqe_prev`的next

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#define	TAILQ_REMOVE(head, elm, field) do {				\
	QMD_SAVELINK(oldnext, (elm)->field.tqe_next);			\
	QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);			\
	QMD_TAILQ_CHECK_NEXT(elm, field);				\
	QMD_TAILQ_CHECK_PREV(elm, field);				\
	if ((TAILQ_NEXT((elm), field)) != NULL)				\
		TAILQ_NEXT((elm), field)->field.tqe_prev =		\
		    (elm)->field.tqe_prev;				\
	else {								\
		(head)->tqh_last = (elm)->field.tqe_prev;		\
		QMD_TRACE_HEAD(head);					\
	}								\
	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
	TRASHIT(*oldnext);						\
	TRASHIT(*oldprev);						\
	QMD_TRACE_ELEM(&(elm)->field);					\
} while (0)
插入队尾

*(head)->tqh_last = (elm); 这里是把原来的队尾的next指针赋值为 新队尾 (head)->tqh_last = &TAILQ_NEXT((elm), field); 这里是把last 指针赋值为 新队尾的next的起始地址

1
2
3
4
5
6
7
8
9
#define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
	QMD_TAILQ_CHECK_TAIL(head, field);				\
	TAILQ_NEXT((elm), field) = NULL;				\
	(elm)->field.tqe_prev = (head)->tqh_last;			\
	*(head)->tqh_last = (elm);					\
	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
	QMD_TRACE_HEAD(head);						\
	QMD_TRACE_ELEM(&(elm)->field);					\
} while (0)