数据结构与算法Week3——迷宫问题
迷宫问题本周学习了第三章——栈与队列，作业是一道算法题——迷宫问题，描述如图。
也就是说，要判断是否存在从起点到终点的通路。大体上有广度优先搜索和深度优先搜索两种选择。
由于这章学的是栈和队列，为了用到它们，助教希望我们写出非递归函数（难度确实比递归要高一些，所以后来说写成递归也行）。
递归的深度优先搜索众所周知，做算法题，越不让用什么，就偏偏用什么，写出来一定是最简单的🤣🤣🤣。所以我们可以首先从递归程序入手，尝试解决这个问题。
首先，显然，我们要读入数据并生成迷宫，记录坐标，不消多说。主要来看一下递归函数怎么写。其实就是dfs模板：当我们搜索到一个点时，如果它就是target，那么就找到了路，直接返回，并且终止搜索；否则，如果它的上下左右有路，就搜索它们（这里要加上判断条件防止越界），也就是递归。同时，每搜索一个点，就将它置为1，防止重复搜索(每个点只需搜索一遍)。
代码如下
1234567891011121314151617181920212223242526272829303132333435363738#include <iostream>#include ...
sort的自定义排序与lambda表达式
sort的自定义排序与lambda表达式今天在刷力扣讨论区时，看到一个问题，是关于C++sort()函数自定义排序的：知识点提问｜关于 C++ 的 sort 的自定义排序 - 力扣，正好也用过很多次了，就试着回答了一下，没想到被精选了😂😂，还得了150积分。
于是想了想，准备将那个回答完善一下，也放到这里来。
sort函数的介绍sort()函数位于<algorithm>头文件中，大概是最常用的泛型算法之一了。顾名思义，这是用来排序的函数。它的一般形式为sort(iterator first,iterator last)，将[first,last)中的元素按升序排列。由于容器支持的迭代器类型必须为随机访问迭代器，sort() 只支持array、vector、deque 这 3 个容器。
应该说，大部分情况下，选择sort()函数进行排序是简单且高效的。sort对普通的快速排序进行了优化，并结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。它的时间复杂度是O(N*log2N)。这比随便写一个O(N^2)的冒泡排序好太多了。也避免了手写快排的 ...
leetcode 670. 最大交换
题目描述leetcode670.最大交换
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
注意:
给定数字的范围是 [0, 108]
题解——脑筋急转弯——模拟选择排序思路考虑最优解：容易看出，尽量使最前面的数最大，是最好的结果。也就是说，如果后面的最大值比第一个数大，就将它和第一个数交换并返回答案；否则考虑第二个数……如果到最后发现已经是倒序排列了，就不做交换，直接返回。
其实，这不就是选择排序的过程嘛！依次找到最大的数、次大的数……并与第一个数、第二个数……交换。不同的是，我们最多只能执行一次交换。所以，我们套用选择排序的模板，如果执行了交换就直接返回。
值得注意的是，内层循环应当从后往前进行，这是因为在有两个最大值时，使用后面的更好。
代码12345678910111213141516171819class Solution {public: ...
leetcode 857. 雇佣 K 名工人的最低成本
题目描述leetcode857. 雇佣 K 名工人的最低成本
有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。
现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：
对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。
示例 1：
输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工 ...
leetcode 1592. 重新排列单词间的空格
题目描述leetcode1592. 重新排列单词间的空格
给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词 。
请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。如果不能重新平均分配所有空格，请 将多余的空格放置在字符串末尾 ，这也意味着返回的字符串应当与原 text 字符串的长度相等。
返回 重新排列空格后的字符串 。
示例 1：
输入：text = " this is a sentence "
输出："this is a sentence"
解释：总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间，相邻单词间空格数为：9 / (4-1) = 3 个。
示例 2：
输入：text = " practice makes perfect"
输出："practice makes perfect "
解释：总共有 7 个空格和 3 个单词 ...
leetcode 768. 最多能完成排序的块 II
题目描述leetcode768. 最多能完成排序的块 II
这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。
arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例 1:
输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。
示例 2:
输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
注意:
arr的长度在[1, 2000]之间。
arr[i]的大小在[0, 10**8]之间。
题解——一种很容易想 ...
leetcode 640. 求解方程
题目描述leetcode640. 求解方程
求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。
如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。
如果方程中只有一个解，要保证返回值 'x' 是一个整数。
示例 1：
输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"
示例 2:
输入: equation = "x=x"
输出: "Infinite solutions"
示例 3:
输入: equation = "2x=x"
输出: "x=0"
提示:
3 <= equation.length <= 1000
equation 只有一个 '='.
equation 方程由整数组成，其绝对值在 [ ...
leetcode 761. 特殊的二进制序列
题目描述leetcode761. 特殊的二进制序列
特殊的二进制序列是具有以下两个性质的二进制序列：
0 的数量与 1 的数量相等。
二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例 1:
输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。
说明:
S 的长度不超过 50。
S 保证为一个满足上述定义的特殊 的二进制序列。
题解——视作有效括号，逐层处理思路所谓特殊的二进制数列，其实就是有效的括号，将1视为 ...
刷题四月，用Knight为我的大一画上句号
2022.12.21更新：已经拿到蓝牌子辣，指路——总算在2022年拿到了心心念念的蓝牌子
刷题四月，用Knight为我的大一画上句号今天竞赛分数更新了，发现拿到了knight勋章，又恰好声望等级升到了L4，就想着来讨论区记录一下，谈一谈我这四个月的刷题经历。
关于我如题所述，我是一名准大二生，非计算机科班。我从大一才开始接触编程，编程课上过大一上的C程序设计，和大一下的面向对象编程基础(C++)，下学期还会学数据结构与算法，数据库与信息系统，虽然不是计算机相关专业，编程课倒也不少。
为什么我会来力扣刷题据我所知，leetcode上为找工作准备笔试和面试的人居多，你或许会感到疑惑，我既不是科班，也不想转码，还不找工作，来这里干什么😂。其实是因为这学期的C++课，老师允许我们做100道leetcode，不限难度，作为期末的大作业。因为没有想做的项目，所以就选择了它(其实也是大多数同学的选择)。就这样，我第一次认识到了leetcode。
我的刷题经历其实二月的时候就注册了账号，点开了第一道“简单题”——两数之和。并在两分钟后关闭了页面🤣。因为根本不知道它想让我写什么。那时还 ...
leetcode 899. 有序队列
题目描述leetcode899. 有序队列
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
示例 1：
输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
示例 2：
输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
提示：
1 <= k <= S.length <= 1000
s 只由小写字母组成。
题解——脑筋急转弯——直观证明思路当k==1时，相当于将一个环切开，使字典序最 ...
