算法

阅读原文 这里的算法基本全是经典,必知必会。个人认为,算法主要是学思维,学会思考的方式后再锻炼思维。没有基础凭空是很难想到题解的,即使你智商高也需要时间,因为很多技巧本来就是前人的积累,而我们思考的过程是在方法的基础上进一步思考、运用、从而体现自己的思维价值。这就像狼人杀,大家一开始都很菜,后来慢慢发明了许多技巧,逐渐掌握这些技巧后大家水平都越来越高…… 所以不用担心自己不会,可能更多是缺技巧基础。但是水平也会有上限,比如说智商可能就到那里,不过也没必要再向上突破了,解决工程问题足够用了
再说,算法就像打游戏,非常让人快乐

数组,哈希,原地,二分,多指针,快慢指针,头尾指针,pivot,swap,
贪心,分治,减治,DP,模拟,滑动窗口,字典树,DFS…… 我个人永远是,掌握100道题,熟练度足够了

查找


排序


文件索引



找出其中的两根柱子,使得它们与 x 轴共同构成的容器可以容纳最多的水
头尾指针移动记录cur最优解

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。

单调栈

【数学与位运算】
在一个长度为 n 的数组 nums 里,所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,重复了哪几个。请找出数组中任意一个重复的数字。(哈希) (原地数组)
RU5DMN/p2kAkwRs4g2JfaL+z64wukpSExJi7+9/OTKoN1i3cnExR9ruWT8NbN+LlEHm/EbhlKXRxG1xljiecQxMyWnFCbgJWqIzMguRxln+uJYfej3RDTKOd4dUUUT0844F16mrx+BY00/yXclaBP9Pf3sVfWndIkhVaih4IL8RhvptLeG2M5GnS2W+uEtnp7clZcAMYdpJi22Xo+Os3cNLC8dkaDJEskfcrAy23d7DGJnprrfhNjm7dwn2zyh6itnYNhaUqq+XX28mXLyuXGSHCVPYi8SXYqPmE4CQjbKgNfogMDZYdQmLbpcrHpVBzblzcuhzhvW75kp8vc6mwtsLPNZksYbH0VS/rC9xHK3TNmXw0p1Ba/spF5aTenJU2NdeZ3qfmpGyiZLy/34kVdPYgn3n8sJdPOqrITR5C5IG7YBIrdDqL5/4U8fcwi7xOcmReXxbWe9FW0mAXSCQGvfuPNvtHetufyp2Hknfe0nrJN6er6AzB7kfTIxtDXCjg5OCg2ef9AMbCEw4OwXVK2ZkxBfi9ewmYdYJd1XIjNrJ0gM6udRaXf0OjsDPawU9dLOaVrjBa6XR8thOKqvlu1XKe4vw4X2Hg/jb5vob/kKgWKSBrvcnKrM5q0ogcE5j6BfKyO/I7fiYdJJFJPX7O1tw7vDCTtREW44d+5xn4M/APklHvUvoe+qITZvnFSXXve4jPfzZ86AYEkyAuxeOW1z25jtPbIJlklXlEIztJhaWbQcGYzSoBcybP0m9yXcQvImTHKFxSiKINC4NN/mIHs/8L2JG+I9nbq/X3SkTk+kQEddEp5n95MCp0wuayUAVrAN7dgK9C+7kAfke1WBD3/Rs+7vnfx6fLZEhkQT94uwh6Djz7KbslPIi2o4yimnEJuybKh5V0/P0t8o9L9MsABVoYWTPHrxKoq07V8OAiPw2IrSNE+Gwk/hysHSGYnpdHpLu0XeC3epwPUyRBAN9sZHzE/QGWK6i37s5f10kjQucJZD/PGBSWUyF47bLdXg+v6HRT93odCrGDoRUu1OrEJFA/xIiUUoYZHkY7OwjbEGs00s2OAADHXwADz8LytqD+K+u8BlqpSSvkTmgXcVwRgKw57EEIqwAln2rwaF3bLP0VUlVvKhMKxAZVVvQKaK93dIWt1au/EgJhjkycJ4H5iP4ycjDnlNWAU/SRKXLRkgED9KqXSZkM+eEaglZJ/iGrKurSxTZwBWeI9tlIoiPh24dKE6dmEk7yAogX9HNScYlD1lT6fgmTXmu8wTc4fEAO6o847xU1PALj0xBO4MUrV3OXKJfvDOJfalNHiEWDTB6aiUx9

给出一个包含 0 .. N 中 N 个数的序列,找出0 .. N 中没有出现在序列中的那个数。
RU5DMHNriRufkGFVtJkJND6fKRyIMZBJeRDTlNKXpzyFnxLf5RzS0zg/TLBHwSulNJKu00r8F1esEOvZN9xXWOQsCWqaW2Y1+tnePMzRW2sAUBCpEDm0wbZ6FbD4rRDoz2IxRu0Bj1gkVolHMw/b59A3BBphCCu+Uu0z3kiRbwNeRIgBw2bOG/Qgwx6YwAT5RTfQZ7qo1z6QmpcdDUAXWfiJsdliblzFdXr2S9GkDEnZdU8MOc/dZsixSBOMDUsgbOnKWLHwBuVXVSe5SDUxeXcPrx7p4TCns6W3M6lIIG3So9L/

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。(哈希) (分治) (Boyer-Moore投票算法)
RU5DMLzAcHmBIUIOTobc6e+Jh23HmvEe8gOeR5cQbjyCCqXdR5zI/MBbbYYrxelG2k6TqtMcw2A+cVIEzyiKqVkqcKH/MySuHXm1HlQS/YvOZPK0nrbeR209UJ8lI7rJRQXkwK3r/ZwniY0bLKvQ4uJf/ya43Folkd3pGRQeeLyp8UrLEFw7kEr4fJYe3U1xqw1wblgaiBgGfmYuCePMvAe3LcG4ptsOrFMXgnlLAzRDmyuH6nnYQSyvAuhIWDX/wOzwaDytJmdyYiGUfzU38/7zswp7ofgvNAAUQEmVK8+tay71T8E4+nd38j1Wpy9W8ZkuyvrB2AwBvjQwWYWZK1WrkwUQhqsbTkxugLyrxKsBOGuaRMVqajz8wrx69wr8WNf2RlS/+LiEChfho0bBg6f1HeSrP6NL1B5ytgGL4rJsVBPD2B92tynA7J50Bq6JgxG+2REuwYuUmzPS2nE8VmNb9FMYiCLACXwRfyJpfLvawnFzve2/CQuj5bM4Sc/b86SkYHAWVe6m3o1YBc/J70PUzWbUoJJoXL5VKqGyynmX9cqerI0ONYo/9bBC8xFFXrK/BGMvpJZJSoSwrLUlJ2/q25bGCXABAERYNVFLxv4vC4DCVXXQfyCIXDNAlWZWHfCSfGaaulpBRnNqyXpUr0yCyLYAOOvOzjI7q1Eaqb9qi534QYwnkbmHjdlhxaInFBYVPQ==

给你一个整数数组 nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。(贪心) (分治)
RU5DMNkY703C/aHwfpAH78g9vHxDmArfCvqtHD7THpqjruqXCkacVE0qtYpdwYvsp7cE1ffSCWpIKamo3VYiOSiigVhSy2sWezk4hA+FsOZGKhDwtYbwDA++eIZ+3GQf3dH3OEwUUkRqx0Bch28cx2jwWgDQP8GdSiKssdN1hoV95AmbgoEzsLmt7UmsMYqQoYkgLSRUYiImuPY2UzIxL4cvGF/GC1U+jbZO6gMe8uauLqqH6G7n7ju/yKJKF06Eqd+WX6lbvdfdjjTlO1aY3rNa4RMGBLG7ahpPN+jH4d2K7/acOFYbY2VP3/AU0AjFoc/8uEYiaob/+KsMqYJt1Mh4oroLXjjbSp5m1E7F4GzZFpP9YEjf/UTf4+l42jlvMRbszghkw0fzwzBsMAcdg7jOJyUjIsu/WjhH5SxicuwGgVrhg0u7tNvnxRmfVov5kOho91pK5DjhRkg5gNc8UagD7LrKYL5ELjRH5q61jsXGLM4Fu00tR9sqBQROzOIrSauPgpa3J1tfs6F0p5Pci+EydNGsbzW09XzV719PMTpdoeWCg7TKWGlrq0z1ruMVBMDT2AuCdKQkFd8lTce9Focwb6veS6xSmxpMHqgYawowIr+wDQsXdr5aY15A0COFxZ7wS9gHxSrE49gTe2hWZeMBG0AYc6w15+m0geF7ktYiq2uygpnd7oi+6ytvTgjZ1q3ZQSCIScvCox1fosq1AdXZmFK1IV8cRjhtutMxz60ND/RU56Ivn+PXPYxE5oinLkxLDCZrgmAvolxo/GXdP/tkonRwrXdivr/KS2TCMTdXM/blwGAaNx5zim6CWRmbELjBI+uXy36zBF5SOq4/ohA7R02tpFLOdvUq3nanFA9X606zzpo51QakZbqSo9idxYyQu+MSzGbQYpKfIzagNmHvWnhAd+DFQXUy61X2C+9mNZz/Z4HCSojw1Yg/a1MW6VAwrGW0wXKOkznzC9EqnL91oxzHfzwbztURygdcndD6i6HB1nnaSu8YIA1C5rjFsWpSquXq5AauU+3A5pIV2TaBrGsrjbhq7dtjtjjwOFle79Qjv2U108/FlEB5bF/mvFejrLgPSTG03sdmlmACqxiH4X39xVuM704Q/jMvI1u7I5kZD1FpGQoDJHgdJtLQueLz7/gw9vrn5KuSyYMD0IFys9wa+27gSJcmiH79tAiaRd2u5+fTnSLOFEyOCJEuwVZ0jsMW6t1xb9Rhbb00rrlT3Y8j+9YX/oQkmHW8TUdEjKbr/LEvPzZRiXdBALoTSD8O41lhov15utVRiu/Xzohq0zWyaC8lSU8O9rPIcPMmaB1EOvUk77J7D5BEogb7aq3QfauSiJ1sKz09nvhBecqunp8q6CI2gFvFC3FdXK+lgVXDu27hbgyTfFX+u9TP2laQx7HGlgu7b/F/MyhjUnlMwCF1TMTi7kCcnubOB7VZTHxqb+XgfJcUb72KgXn/UImxOlBXhwm0jU0oyh3OoEVdQyWBHQs0msL5W+B3PUP7lQ9d84iCpUHDC7zym4j8mi7wBpyOX/5ToZ11QaMm2epCW4RKcPtOqtw04jPW4K5SCqoXOZqmW8nDctRY8qSDz5+4Xc0wAANVbIj2w9JqXPJubheUdXYKlhH1Jl7jvne0JSxrhqaB9+qsZwKJpb9KLNbdW6aMTi387eJha8w7/VLZLeP5O4gruXyLzd7Gijtg2w0adTgqWL+9VUw7/vbGo7S459jZs1FA/xyN/zpHgdweuHpOIwYxeOto33/SXNvpPWUKRxwlQeJhh8fDg/KLkWjMvtckzwcTTK7pl/Odm5ouNBIV0DVzpZ5HboyR7vlb7dNB3Kq2BbANsuEmwrF7KAQMjzaXGJJcQgZ6wFh2q3ICWQE=

给定一个整数数组,找到和为 0 的子数组,返回满足要求的子数组的起始位置和结束位置。(哈希) (两个区间之和)
RU5DMN+BZfE6ApDsVrXUIGId12CF16/y9MrelSriNotKqNBLxJQBgr6lwSbQMpeMLnGuiq4CGjk5ngh6ttwKmvZyig2B5SY9+45/1SlU0vcMmprDy9aBQZW2DLCGtk5Z48Niq7KVZwptGfnmGolL/UXGfx15lTjmM123PCHDXwIerdwtI2AsN5dJ9Kz0gYKK9GJKc9JzUwaKCVq7OM2l3QNhNfznTWAr82oi62wwdtt5LKIPQKMro+DYPzpP0VxCGGRGACN0hyU/dDAdfX7zG54u/hB4OxBiE7YaoIqgeC2vRbb8cY6x8g6rgedAmLIT+XIOYjnqSj86OsQ1o/f1YCkr52YKcMidXfauz5LrxJNDsE1WjI+XUvBWlPZI234CPqBqvTNtaXIW2LSspP0fLOwank0cNPnkF+TJBq9mjlEIQn9wWnv7SEAVSd3GNwFV/TRKfhj8+k9scVJOwQ29PYX+dmyw0jqhzhwtM5A363McSgCTNdtFFRfyryNJbUhizr75jbe3NsnQsXdMVxytDAZ/aqMkUTmUSZmQJyjSCi+0Utgf3d+1LZdhBK4jjmXDA79ymrcjHYdU9audS6brhBmf+c7P1O+SZ1DevLUBT5WTWe+cDfUTO5WDmisX+CDbMDAwgRr1gfLa8qhSQ4xmhvN8ueePmfI3MHerWVSQF7tyl6etsTpxyV1b9U5YEI8aKAQ3mwnVSkZROFSacT/eV0WxqrhYmNZIM7Uo4nnTCgE8eFsJ03fJMk0ZiWhpqI8nwM+yKRFNUhixBRaBVXI7217uSnAKPyrCc7nFOhn2cfO1q8hqLZC/A95xYenA5rzeWIMCmNL10f/mHjYEGyWMD7auW11c0VTakYSbIGLUThTl4sO6cxCVTElN6zNnjL0+LdhmdLAtcahWbqk3otlG8xHGyCC64NfaDozs+9RVA/uu6EeFcfGU++aHDERID9iqq320oUAgH9Z15PUnGJPu1pzLzG0=
给定一个正整数数组 n 和一个数值区间,返回和在给定区间范围内的子数组数量。(多指针) (二分查找/滑动窗口)
RU5DMPq3v01y0XJFuMiH0Y6I2UjHRjUpV7u3UjCYXIvw+tluunZ1f9pQr2+udKPtX2j2nRucsgyznmPxkEDurjLgXKD/le9vdFQxsE3Q2vI2lrWDNqZ/l4+nItE3ZciAZQ5SV7UxLjplytSWwrj8bhPAeHTyYvnZkzWfmSrTL3YwPpi/eBXX0WDwgmgNZyUwfth7BCHIJWrRzTdqqA5pJZ3GzFBDcJ/kwmtqdfZss73UgzTmVamGT4ksH2CqtPIpBqEMYVgDRulioxCNxgmtV8wV3KXvVNeA6EJ9gWlNkAdUU/lp0lIYdwHJ/F3kR1SuY8BrjAFqAflR7P3NoBXFufajtN0vkV6r8zIMJKMDXi9M3fa844bkNwPiM2xfmEzsdn+fFAquvFjunHlRBWs9YZmzWgy5IIeDF1MbK+OjF73NZOn9vkH/py2U78Y8/kKP0J0/hNqZdnzOsv/OmLLjEB4VmUXkYJ4ebzwl/+Xi1ozfmuSdL1tuuyAojRhNaHeG+iRRDaW3ZKhad2FoicTCmTzHTw6fSWXgm3anP0ZCnrdTpEPnXlwBDHe14EVfPMNo6Y/FcsWnh1OHJt0zGI0TpT0v8LfQFC2tiMGPMs/P2tPsi0zR5pFbfr4sSK2yNTRqLkriZOBDphdRcZF4fXpeqoa748H4NKT1r5ZQHtyyz5YoDa0FtDbl3DAa4RY6Vr8GTWnbTEOlXCyHAqJDMoGD8RyNmkYyN+rikuhL+AnVuDfix2WuUm4MI5q+mgT9w7hbOM8udhT916N8p/iLf+PcQlBW5sXMeGqjaZSDEMWGMm/OPgc6PLhseUsoLF0DbG+e/my3/UlAZi1ayGpBshESVCgM02sBq7cPBaxm/y+HEniARnEzC1c+uPJBDZR2jNRxRnjUqATw4nPKPeQs8zPTZIvjPAqHe23Og3zmJqj7PdUrvjk+14Y2B7JQAVCgoStoT6Thrg8I64XIvyUZBPscMn/5pGtNZJEDIEh7U7Z/KF0AAYgNclGsuIGBsYkYtNFV2aeJmBSkqN3sTjkx8OPp0otvd2J26XaMFmwgbbW35dAZHnfPZEia7f11gkXXU54O6K1mGBwBL9iLTUPuZ/DFZUsIyRi0/1+Q5IUDQVoDSV/TD+sowHBo0huC6GAZIi2vagZ1RFxetC60/Fi0DgW0cx6nbuBLKNPfpyRQFQtB5JKSODp0o/BM0+SThulOnYQgymyZ5bJyNciObVlujGBzeYiX+O3KsbtDlSw2uyXqYgHQR3UPOA5VSjNFIdOJVpCyAWbpHCu1bGcOK4BOXaCeIebgFFac0R6TbSJaBlzSe85KVzqFTtRBgvehfTwOkmRywRYn627Amk+1svp6eYZXjdWeZDO19xCAFuUm2CqDXSPVnG3IpsetNIKFmfLFRQYF6d+tXcuH5ariFGRXJPaKXrHrXTc5fuqzUMsfWN5YFnVCGclfcZHac1mjuljlwMpxGV2UgaxtOVn1qqd42q/GehLQDXv0ZaP4a7vthxjFq3gilvfLRWhMs/J8gJ8bYS/oja1Ksg==
扩展III:给定一个数值范围,求元素数值均在该范围内的子数组数量
顺序遍历即可,统计各段在数值范围内的最长子数组,然后数量就是An/n

给定一个含有n个正整数的数组和一个正整数target,找出该数组中满足其和≥target的长度最小的 连续子数组。(二分) (滑动窗口)
RU5DMFV5Xb4yh8XrMoqfXQ3+NLnBA/yGnTs3vusN/6MwGHd+rbxOGp2OJlt7GnL27l1RY1Wxa+dIvzs8s3H262UNfaaTpbAxFVFd8EdZ+lO6xLKb48m2jOf2i2PZpcP06UKo67VT94datpx36BuO3AhaXxOWSnh6s8cYwI3+GvgRWLcE0Ms0jTts13ZxRh2Ea9b8MPS1jbtmTEYyfWWgDFA0Ah3QsvxuyPkcIkdF0DtH6K+Mfwozh+/MYZZVzvxnufUm6Ao8ul4IVPlK1q82C+F4NtoIjbsCyLJZI/ICaN+NhUpOVYqUf4H+k0+yZjxJx/TwxCQUHMXOKGE7SduERkySOv2hd9xaC0+N8DaiY1FJzyLEyUcfhRsJyLlSSZADPJByZ+GDh0i/6kGEPVf75mI2lNIwMvunFVcUICXv27g6hvqGosAQTV3IS3DkjiQKbVThv0m48iHppMs3tsyJVfMy3qpzb5uW0h62UuHHwurPROkutc8mJNEYEFagePlQXxDAnEEPlJavENPvBRa+90/V5hAPKBuDbKQ1eIE7igC4G0J+

给定一个整数数组 n,请找出该数组中的最长上升连续子序列(最长上升连续子序列可以定义为从右到左或从左到右的序列)。(模拟/DP) (局部解)
RU5DMALN4furXEPNcpt06xcWTF3dCJSjPs9nR7gdBro5fC8sONICOXTTqcI2/LLOoFNg1rE0viAePvv7Zg8ZhGrfyg3oxOuQCbTYMVnFyrkVlWIuxLoPbJ15YanuQsAnEEKeppVJgvuiXNDdIqzSGvtNN9gjhnTu549i13YfkB/QiIYPRHG92ioei3r3CKk5Ua1Pbyxy0e7Zx68MF0RJYkROyEXN6HDlXB0Oa76vQNc2FfrdN0PJBKgMYsttvxyTdqoyCpjrE0ccvSAW4xnNvJ68hlJRfAZ2sGNmY0OSMpwp5fY+OX3nntaZgsOOG1t4KvYad9jfUsQMl1OHHwmGgTutQxAP5LuICuKua9ZU3v6XwJgT5PpcMUjyCr1p5GeDqdC9pJOVXV58+G70j1eodnmVtLNKGiVwT9Tnr+1RAx8x1zthsqrP4VXOfH7Y4BS4iRyYMvpszgGxdZiLzHvdElF7yR5NeY+Hnrr2ZDKpai51YxR2WpwtUKc0Gyqtfug5CDDW356pw7KqhK5yJsTyOi0E5fK0k/y8ei8oJbr8H5II/PSzqpBQGygtbhnCXvMjf+Me9KJfnAEIdd5eTQyZp9Umvls6oAyc2EWa9IJQMdlsIxWKeqhQ6yEKwLxUKmkWoswsuOXsAPxrfc0BGNSHIJ3s/O4an1IYIJirVkFIAiIelQ5tsJiTd4LHNhcDYEHVMW33X4SACwjdYhnm3DQT1YTqMIgplYhu81BJ/+GDbwGZB6e2O2mQVZ58N0WxcvZXs12H72sG6UWsFQUQRxPGujcp8NtoSgQIlkE5vt2aawN3+xiJ+sfFpwq8/Yts66Yk9MBfS7QBRvP47qVJh64/2Ig2rJVWon126eKNERUwLnqSd0b1K6/QU61j+Ts0LQlmwt1e7MIiJDQUHT+GdjYbfAY6DRAPSekuGGqhbKCLoCXHFoHvKI8E1wgtabmF2FnINSXJcMAiSX2RnK0wIdj1MjkuZgXzwD221OnDeDfyltXl3snUJnoSXj5hbLwrzpiosyg3JOxOCnp/89c24/Py7QxeQ+XwGKyeCib62wCGZdMI8Bz6kWqH6djby/cDqLSkzDuvkWXfR+mzreqKGmrDDuukYL2zosWOpBwG/7SOvuw77zRftADvx7HJnGh7ZaUzrYzHzjywbR7xohy14zj3KxA/K2KNPDJCBfkM927g6B9+YdpPfBNISzSXdS8PReVZICUUev4U5zYun2p4oJ+z/RGgMao7kC5WbGRE9pxVeGvDDz38OwZz1HF2IA+e9Ttr0I2tadDSdj2yASFjolHyI/PhE1bEv1s+9qfpyYITppDFAbjveHls+RFbyv0OkNBwz6xMdcm4kaPdF8pfTev8BhBPy1pZ5aGvOmROT5MCj04ULfP+LvJHjzkSAO+DvZpv+NuuFo9UqLzUg9OreBRrZFhb2T9r6bJwX547/YLZJ2dcQ7Er4f8V1Oqni49+XyhhvXNXItMSq/d2qAH88XEGZjJ6zol9y88kCbwpKanSks8mjQx9zzkD01Kj9L8Z2u8ib7jTxlKgNRD2v8waZzVVkA34x/Q9mUbuN/0V06OdfjP6eound74D8SsgKq+flX6+cUgFEx4hhcP66V7/eGqY/gA73BGm5WTj+IxgqfoXaAF+jD4uwr5hPLN+d0pmdEmqUdoW1rZoNrsTM7GxPIzF98wMRTvGbnWPzrdrUfAT3NAKYsjI8kbjkXiS+yJrz+8oqZkLshxSJi5yT7LU1pu5znhAicY3BZCSDL0Qa2SGkiMjiNkrBDINXZj54oufP5jWOS8ABczH24uS+e7VHjyEac73zKAuqS6FjnQp22I7867OHED1MvuWh7P/mcTojZFlQlRPdiZbVJVx7/5aJmtFm0aoA2b+VN4/+uuVVwxPAqLNiTOy
dp[i] = dp[i-1] + 1,可以用两个变量分别记录上升和下降序列
这题还可以更进一步,如果排序的话,结合二分法,可以优化到nlogn

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2),你需要找到其中最小的元素,要求O(logn)。
RU5DMPE3ox/+CQN5kLSO1tQTmTf7dELyH7C6M6OVr4Ol8SmT78XrqPJx9I+8qh5SKL8nzYNOrd1eHlp45tzrnJ1cSTPLz7/+Z/n9tpibRIzOXhXgaAY1hjM9Ouct9jxYVbdlA9JBpvz78vZNApq+Qms0J/GW9lO2uWNuW28ZDkwJjs15Y4ZZu9irLTqtwiHCPYhBEYJd17hhlBQLGNEPJqRrpm+KHM7+uMW5jqLgPmsE4+JP4x+UscNahHGnEKI2AlLFX5zPAAxikzWCu2UZONhxTzdT9Mgl2bZjVS0UVkcOvtbumBXzhaawkdIFv0iEh1lxBZjarWX1gz1iKsco0wl78qg0mGjmdLSWK3uiEJsX3/ubHNijhQdmwYbpuJJz44wKjXGVL8UZ1B2jf2EUoOoGEhlROWhVjn+CJC5m9gT93ho2jxWysLR1D3/vk4v1dcRChRHMOeXyr8G6zD0lxIgdt09pmt5pnJAfC76OW1pu9Us4iW/CICgU1j6dxAfhmFqxhf5ooDlC3wwFNOmHeHn7ksabCTRSQ0KAvTrS7gVnRLTmfwhb2CXLim77F/YHIxyIJa7THaVuWnPxpXUjMb3EbH8=

实现 addNum() 和 findMedian()。
RU5DMPBwN8Tenos0iTfxZwqKfFjutkGxIHbTAly7g06TS4PaFQcl9PE3mnT++/j/Y2bgnXw9vEAkFfLbKdWSFlCafhpc64yA2DvC3srZSJtrjQDRMrdYwv0aakX3AjWUJXtjr+ylEFWX+/3NqYeqC6WFfChp0relcFPZiKEsVWHmAnTu7U6cqLLjWS/xMJ7tQ4hicCw4m1TVItRozvpJFQb4/pcff/CJaFvWCOeslDSVPpK6fcn0Xic8wEG5n8BGOo3wF9kksAYqiJZLpr3+BVPb9TSS9LpYrR+j6q7sXbkxvbVyV4dUXJPN3iK+56An5OGXV5WFA+TvAEN7xlOVRkdKufmB5IEhYqgrbySoR+JQA4UYxNYjszENRHkO7QCtChCUImq851tYvc7O/st4c9O+WSxkdMxnY2viia31KmJBrVgQUyzkGZZHTAa9Tj55d2R3G45hnGX69TTaOFfH8MFTuWwcd0hB1MCDInwpVIyOKG5sk3xsqAptuveCxK/6JlD3f+qVUpW8IRhnjcYoYnKFebN6nmIz0p7Mk8hZAcx8x+278c6Vct+Q4H2BweXTPwmbUHSyogWfML9Iv5XuVV56hGaNEYYRKbyh1F+D03hGzsuhULtbKBohxv3ecSNfTlaAur4iuddMV/eKIT5Og0EBi/tk+687t4dk6XYooFiZADz2E4ZYH7YlbqDvyf2lOR13N4dDng1gKU3BE9G+gHJJdBqrhLE3Jz/2HMWedmtOktkCOjd6/fEfM90OqBUwbnfEovGPF8x15bYB0cvS1HRiYJawH+ldtDmd3pzYeqv9rRjpOg9nzjP6sSt01W5C0TVuCK9x2hmU8eYYEff027odyB7e8vW4461Uosmzy+Ibb3/2Sl6Pb8Es3uzsJ3/w/oyxNoFACJw5pjldb4rfwgzQtypZdOkqd49+X5wp223s1wTkS6dZeANECp/NV3Gk77zQcp3xUsY+BqzT4DDiryUOQZc=

给出 2n+1个数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。要求时间O(n),空间O(1)
RU5DMOQwjwd06UVYX83/gKEoEz132W8lKLYZ9fDTpJDFKjwGTt4qSHCP6Ly/3+CoRQhBirGgC+Y9WH/8qJMrQrwK0K+YcPsh6iXGGAL6RnKWz5jGgAy9ndfXnVXNtjSAyxqSkrPg1T1jSg8VE4fnply/icRzkNHQm52AnY5LqDZIXvaELpihuzDe3OEFuOOinzvc3wSW75VZTlW7l5RqAh/o6G1e24XUTLuXgVkgi+h7B7sKYB4pgiI1+yxCh/k6Y9YWqhUbAzJO/oBcCNfSP4P3s9Ft3Eqm2HKFAmM+oOU+F5KwnLrXd9Lu869x/Vt9asAng/sQO7jYY+0ylR4DjGa/SePdVxIeyMPLY7u1pHRnk7f5wXY202D3dMy/uH4R1FrV1BFi/jT0zL1sGi3qIBm5wvyZLXBBNhTn48TcY+QZ9Jf9HmZfHDxi9R+Q7VqjtlvzPQKRuGWD0cUmhdfeXfVBepUrKQqBdWEDs6tnUBRa6z8VrDDPCimmzyTZaCNAExm/2dj1BwjE09HWAxTFuhJ5RAKKotZyM6O/5WKCtI5UV0p8dEYfu7GQJ6XkMig9b+ts8pXHLosYR0VR3IRvK16Uka6gXMLGCh0Hb8DV6mYVJaBCyC0Jm+SePlV+idAHjAFhuw==

给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。(排序) (双指针)
RU5DMDRzCbu+AgXIk57NzYT2avlXmno4EJgBge9vXhosnSLW8jHyqDlUg360MaLBdSW2gM6k6P6PIhqCm2qR0KT+uXYEynaYmt1Z/iLZyfTwRiRILdNQTWg7InTCgIHK90wHVxBeCNndctkNSfWEPD0CvibqBGGxORtajytA7caSjm+mFybYvVO4pP48FHMsX7ZA0bwnUGePmYx+2KCOnDUOLL+m8Vk9kEAUTkzm/+EC9/xDMxN/ITLgAypK1eHBppiscOszHm0tC4ggUCRu95lU5+eEnU3Id8yfXi8Jo6EfkjAjfUzrxv7mI6fCLus7h08InWeUbndk3UZ0oCxUgKJ7o6vwH7XDDsQZVhnl9hHhLd+xlBQLEigI9zQqxpK/xlsxTWJU43CE8cZjwuPvUTMUqQnDNi+Cwy6ZrQIdP5EGcPMfM+WKLLjAvNsPERnGfaDwCx3mVmBhP00f65pep3efRfOwG4yIX4roqwQ3ZFGHYpB2khMWmhVThtj5qaFMzmIM2+k+fMU9ots79YamF7Wc8I/zXiNfKdYNwny0Yqi3JwvBvcuv5wW2CsbGxVGINz9RuSRYKR4RuNYPwy/kwdh1GFeg+TacMmBFJ3l1Vkur7WR6p0zi2ZQweGVperMlmLEwXj9JfVCAix6/WS7mwxPrYnPJHcFQu8lZWhX8L7ohiUhmKcGoy/waW3MFJEOosGuASDdynkHk34cih58FxEiAHJEmVjuqL+aY/rhMMLaQJ4SyYikaM2y9DYb8Kh8+Fh5tDuaegDfaxwGnn//LFh+YrkmHG/qfLD1e9xQD/zRjgz4GxRFzV11XggrKygDlASjWEhQy27lyMgcJnUx4vfjsqrW0cQxxnmFZ/CXOl7F5mxWVB/T9KfDCZwLFhLmeb9kyiaQql2rMT3im7xaKHLD2BzCbwMbg2QEEibs5HTPYWbOvjDgXEOOwv/BetVFcfA54YauSyKnVQQuNrDFwzswmF7haO2do/bkofr/kVwIKvdwf0mUWjjcTc7noPZ/0u1cAicaJsnGhmIjcwEhov99v9rLGhQ18/Y1ugBsF0Ln+y+rf

想想看有没有办法分解为更小的数之和问题
RU5DMJ1xEuhSNuqoKszeo7UWq27IGRdOyn01pTHDu33pb3VzvNc9iohFVNK6VnzUMADNDlEjayFyMeIkz2EtyIpiy4kfMrUi7NgvYdDn7NRpiZZLKn1MnxreaN9XtEX3yyj9PbA9jno60ZbnG5u88L7P6HpVhmkXHX0K8BkP1BZoMVXZnLF5hC1ztdRpXkF/jZCZ8XmH+sxUCUwcZ6Du2jCfXEYfIlBm3u/nXdOCxGCJmnU+hPEUk941566m5UYb27SfCGpe4bFX3AkriNqGlTiKYdnWeZ8MbeQGgN9UpuwjtLEQ6jxGuswMhH3ghRkv0KncMEpokoK5JAVHWlMoZe8c3MZ3KI3Pqf2XAgeMFeTgn8DN0K3ayXffgNPM6flkjA+3XApRV+AsSZHgUgCD4KIYVK3yonZB+ug60dHCahFSdyYswo3ZQAp74g+5RzCK1NezOVxEkRjWhTogz+FJY4oHrV2MskVBjno0xxkPekbyrvPP/o80Spd7xzLkg9LoYgi1h3udocG5fDMLfP3CznjqJTEeHSVJL03bPW8JBR57Aoyh2lOu0wdAvCNpqDmxj9CWdA+6R2PuPfVPppS7Tb6PUvnNy94HnoAYoizI/93DqSLdbGA4wpMe+UqZAQF/gK1lBXScUi4hm9LDVOL5LoXSgiFIj6PLgNMrJldtlqwqiOAhaMK8juGQLbn6m5YTiJwKkDPvyoc31YhXb0XqYOEntfXmA0oMLpHyCA3L5rKn3UKAXS9qHHuiyDoIWRYSxJpLxD65ehLuraZqPthxoDRsMTYD3dWIUW+1fFZuf1cEr143Ma+bDjTYeT0OXkkjf/SE1geeKiuD6dAE1ubYd31NGqJtt9kKZjyOd950STdwZE4IOs5Oe3n9FYUFrPpj2AR91vUm6iO5DyujIWLkBWJZ+PSKYnHMc0rZ4mrC4qjXm76qPTgwQnqcb2AgQnkddlEZNFZQEnGhZ63El3k2TtbBkl0Kjkc1gSzB29bZxGdxqP+UlMCnkB+EfsU7XJ3qsZrRM3az1DeVwhJrRl7nJYzyQPWoSOoTPRdpQPeAN4//irhwQDkae63uEakoXbcVcz+v20oqRDENmBHdEY8haApRbyfUpPFd/mYLTbwcPrVvFFSxR4c5uvWv+Nvs1/ENhFgjpA==

这题是经典的二分查找,但是实际上我们往往会直接用牛顿迭代法公式计算:x i+1 = xi – f(xi) / f'(xi),推到此问题就是
斜率公式
def sqrt(a):
x0 = a
while x0*x0 > x:
x0 = (x0 + a/x0) / 2 // 公式
return int(x0)

字符串转整数,经典健壮性考察题
RU5DMIl3gprJqk+VvpoJnZ3OL5xMr8NAkfHqPATdNttFl2Fg9v4JPP2qNiJj3ukLoJfbUFxxb+cl0QeRi8B+7xwHvI/q4sQpKoqYqs7OLUOT9HgOkXJ7ICyL9Uu3czmRbz2U6ABZ8m9tVV0NSCpry97HiGBP5gXxua+HfiiUhAn6GxZYiaBiwxQVCW1vSCS+rkvDG1xZNsPfqZ49oM1pWikmqdTUVzwB7R02CfMIkxFh+11D7okORK6zhnVQXeVc5PpND9s7Br7WfxW8Lo4lmqvvccsh52YgoCjWtyIAZE76U89H/H7KL/qw2UeTef00fZccLwhJj1sgvfEPHXZsKEh2MMffD1hbEY5izANf4laevQv1

经典位运算题,用于熟悉加法器原理,也就是二进制不进位+进位运算(异或运算+与运算)
RU5DMIFaK7XyYeXKW1tmqPSQZvG1D0g6dmtqjT0aMzn2DMW387zD66Fn+t/BLZhatfGbXu4YhiVvwdUQ8QMaIUxoiVK5APFOadPVZKphX7Z7X7Pe458zpEqi+afQaABfX6BFSMu6Fz09m+4XWmmuPwO3vGpnKT1zTj9feMnQ1aRBBgAxc9qR+SWsE9pYcQQLXLhgdvGchTsGtkgfMh1rlIGe7EKouMlhWpFL0Q9Vi+FWeWQdOoxnca1QzrM+VIZQz+bDlV7EtHn4VP9PBJ8ybL7C5bA0B9HJ1ej4ycRt3Hznj4FQs+RiGq219RIrD/lZmrS0ChxlkdiHhFvR530QPOwz8ybXHUv/iVS5MGdkGP4iws0d/NBgVnmTgwrZV9LIsXSP1wtIjuPSblP262Ki2sm4RtCgssx52wOLz/cx3bBNEgBcvhcfXLzp82Epn+UE6fgvX+XrvVjPmvbStIvK2OjEmLSsUB0DCiF+Kjgz3Vg9ZPZ8uOI+8bwWYXfHP62g4ZDmsRpmfIkuPKnTO26K/Y9VzN/Oxszbm8dgyc0GFWCQbKNsktcyHbT44bnD+/hfZ79rWdfGOwJVbFYXTuO2XZVuA9BNRHLZe9qAoWup9VRh5xDxhig3qRVP/GapxbfLT8P2A0KjRGQsLxxtbiuB54bcK8sQNLF5vEVd9N/dYXmO/yXw/lpWalqCl+0BSLlFbfLJf6RE5tQeKHdEh0unv7BI391gDsYtiLjqSYDjPmgMdB8hLoiieC9HELUI5GtJuzvoZuD9UTRzdN588ZN6MFQQD4m/gbu8ufnVPpMRgDRnJHrqVQCevzDCe5TbASy1RHiflPYAbSwIN1IAK3q+lJmUGnQaHetdtFe9S96gL+mk2fHXHAPe2lPdpCT4vAgQ/E/CFfxu5RSciX4ktjb4jAGmufMswNc3quYrfXqiyDSnEvYvPyfszPUBoSlGlG0Tb5PPgETpljBmqhVfaMcEONLFR5Vtd6ACWydAsaIFoXBobZvLdAZK9jYJNtEOxAxwPc62mNC3J6xG2BaZcXq4RZxOmOKulrBBwsdRsGnj7+PpB1ynOghgzNab3DbXgbLSCtCOPZpc64KE7Y7XPUzxn2HlK8WfqGnhapM4e3HVXIxoPyfsVqGwmrgvNnyF5zR5bIl4PkiaGxYVl6POcIhEw9qJEg+K81mxGuh/v+Loqm8b+p5mk5oKYD9rjmMgnXSRJTRSxZ0m3MTOmOYCR2RDWStXlt6QPPern55cfFdNDWGYOW3q3dH4vVOdNdom7W8utznFmCa4GqoPHZL2NyWQSvnW2US5F9miYzoip+DGt4s+/mZRcLEFv7Sx4CuFQ8rYNT9T3gCqOPxuVLVmdGaUKbW8xS8UnSMyqpFmk7v9t8GGWTIzSOwSrcrfHjoQM/kFUEUPf+LGc3hHux7IhJr9FHe/uSoppsAFzGaNiNk0SP8FdxN0435lKYW4KgIi4M5z14RXLsX1U1wpb/l22oMmiARaYwhNMmt+NFatv6PgSs+XmxhX

while(b!=0):
sum = a ^ b
carry = (a & b) << 1
a=sum, b=carry
return a
事实上,电路中的加法器就是这个原理,XOR计算和AND计算
其他经典:
判断一个数是否是2的n次方: n&(n-1)=0 则是2的n次方,因为2的n次方不会有1
二进制数中有多少个1:while(n): n&=n-1; 每次相与清除一位1,循环的次数就是1的个数

【字符串】
给你一个字符串A,一个字符串B。返回A中涵盖B所有字符的最小子串 (双指针)
RU5DMH3ujBGTGwDjfXUt6ddysemoMUxCAqtiTResRV3hfOqDI18kp/b+Ulv3TzxLR5xHvSJXX9zlzVDu293DMmCG3hir8jjHqLKSf0SYXHkCAb0s9f47P3fCzN2kGmhf1gJmjdmk1iKEasBI/aKEp2ZbxFctPYVSvEebUXAwWCR89v1BuoBwnJdVp5aPGB9PwDfGFL+WxbadWwOlgKFndYCFXajgIKEkho8l/I0urcGsWfpTlkUhcra9ADa6Pl41gVgmInYlujiBEpBtZAO4ZgXRLEWvDFiIO94/zRtEaKt83B2JkwYVzTzDC4a02jr6uNirBhpDtdjt+ZUo6aQokVQ1lXhfC5fvl/rnCU1fJlThsBRHODg/gCls9hXNG0gJ+dAPulLlb40hAnTDdUZP514K1AFyVfxIDPtKN3AHW/mih6fs1tcVhskWaWedBFN+jVXfSIl+wqbhvA4pllXfoRRRyZRcIjpDLdSn2P7zigoOysTwzVmltiRflRSz3lVXWIuRwHVa9oj/FzLHMI8ZPNkPV2ZGFeF/PjdZmlaABdnUVuWrOivIa8c58eiE5DC8GtNQAP9UjjXCqrjCYXf8z4pFXVprkBiPjnu82hqU/wSCfBUj

给出两个字符串,找到最长公共子串,并返回其长度。(表示所有的子串可以用 substr[i]+length j)
RU5DMETGnXNnInohvOtfOsIguZBTXOdxNGvW2jFBurh7dNiKiAxyKR0fg6ux2gPnHD/ttJOCDGlaiuOrzCaRf+i0y13lteSHNuwW9kcfoQF2Ruu6SQ93vnIzokNQXZf2JU8wEKPDHJwX6zoJ+sY4oyZem78gYdP8cJeLPQ18EJuK8V7MQblMnt+Wfx7GRADUnJPR1E/thtzu83+uuqHENjRGsJSr9R9tI7yo2Jomru73myhXDepJCqGfWn/A/1tZHxEa7Ia865/ynxtyNDKATCDYjURLPYmWhjK5JGgOJNrgXetUlhpObQH0VsLXJKIdY/DQyP5Z0u1wYL3MSVAwXmWFLXnhiPYUlJOklpGtheJM+lndmXQgx5ngWrC0jYUHasWiD74exaDDpIo127b67wmzwQe00ZjSqPxc5Ox44fSndPLV3aGmFlz1v6y8vqCoI5ApKbSzqwv95IjAX76tm7LVEJVgVlsOVO29VOWhLyvsqY/gT9MW9Ln68t+z+Fb8ZzludECCHEIC9oNrjk+kTIhQ/yuBeIxbpkxKJaqY3B7TRDI9GufWYZc8mBo61lVUkdVLC/lql00HMoztX/q1kYzFMgg=

子序列与子串的区别是,子串必须是连续的,而子序列可以是不连续的,因此要考虑更多情况...
RU5DMD7y2CiPhExtwiNIeSYRQXGOpWs/RxpBrML67yCCwSJSF6dcm6iv5cg/guZW08cl+9orumg/8YgFijZNzedGXzLKh0lfeerfa035bTB3Z/4fEDXk9UP02/u1rFshrG3Jzdn2aBGHwNFM2RyML+XlmLFHpk06CkIb1NaQorx6zWFqC4fdcWX7yviX8guOJrfHZgzQv6xie2iW+HQQkR1X2kOnpysb0g/myF1l6ZCjYcler+PI/Hb4gaosz3pPYgkiXjW9XxLac50MhKuGRS+Uddm0/KGIGile5G4ApCxRL+UGBoyoor/7w0Ue6M1527z2KlOv74edBH6i7SAGzxhl9IMrgBFswYQYWzJ6/emc9fo9GLs1KPZdj+0cLndvIm85yFKd79ylJTCjTI2LGGwLzVUGW3VOXrHLnxMXloG1UzTNqAv35QWXND4M5ya+VST0JFl4CZNbeex1BDPCnUNKrqbo3MtockvJUp6Vrpy+KP1Yrzg98DHZXgVG0GbOG73HuDzJezMDQk+ru6bgpmfFAJyfmZcVtimQNY3zEtmp0XzrBA/DP0GlI6i468xfw8+SyZ5TbOol0BkjN/N3K0spWCxXJn/4L2zhAdIaFNJDLefZ2DPIB3vFQ8A7y26xFVz6iIN/oUl+CMOSYLgeYZQXfP91Vnxpm+jMofsmEIrbRNAubPnknlNsNkws2sKdxazEtdJYow9gTjg+CaVnF7+kvLVahD+oWrd1Jv4iEjmRL/vcoBHfQQqSDl/vMoam1SVWEAU+TcZpxb/qxsfeuSjnWhcB/EALmhxvfgNqADW8ep7kZfs2dksBXGNn+F6cc4kNwxFQR3PtSPBY3Vli34ywF94d6UWmeyI+6k25tbFrmtbk91wTV2y6G+qvZBvN3rQjvSZwhNjISkkvUCmmQ0fvcpBCT0HeNKkU/9g6Cxw3mEP9sL2Z1o2KS1hj+1+l8cVT/uiy0Z1R2VIoak8p0BnfRzFYypqXKIToOaTMEkCnf7++TvICkq8D4qW/sLYXRSY1HU/8mFXVhDv0S3X5bt36CA0uhajaFX6Kh7EzOM+E5xWbyStZqVEclQK6Og/lw6JJALXLLDCwozmZXpbVCH0Ro69oIucjkunMoKSqoYEwZ8wL

RU5DMDlE6FHCjyAADTD+het3q6++2CgCeuIdfYNLDmXZluxdTyiXdL0j3jffC99PvwsyFVGrTUSVS4Q7qw3AvWINNShdrDFOwv6/A7+yfOmZqUngXsWf6S7+RI2J3yx2Gzeyz680qjNJSF9ztMe1kMMeObO19x65wvDUWkxJSEylhld0+ICgaDUg0kHtoRBOHCGZeI77gzjZl6v8evwWnHY/lNfqqIvSvt20+gOXIlVa26agdHQ0vPLU0H2C+zOshup1O3p3PsT4LLzYXpPdqQkC/roZASSV8SlGOJxZdakhPXTKzIwCzS15yGUyHKAkk6J0j+K2/SArGZipvhupqvANtCUO34kFjZ8zM0GnNsNF8tAlbExesHC8xxHsWea7JwRfPhomyxacYwdH5Mpms+dTSc4CMhK8TEox1SLG5CD+KgHH/caykK7+C49zPr/N/7f3o09yBgb6108dwpk7PCtnVZaQz9bOArPJ35WodWafQdKr1TE8V0M9vhAWY/OvJmVobNylD8USCrmRMtQtaZmIx+W0NxEDCmnBG9Tcpt4HbWbEKd/FkzstjiQHjlrCVOjXl8co/P7x5irSGdK9bJjV2KP879DwTq7gEci3VRHDK0nDi1vj7RVQ6JjSZOTfpIiJeVrACM9kUN/vPhf4ZdqPgxwX+lP6DnXBBkf25W2ELbKju6qbkMk9JHzp/H+qfqQ+H2PYgHFbIzTOvQfmoAEH/ErHjql5A4vGu71gMwXERlnMJa9Hs2Zzqqu+Dk4tMQZUtdtrBf1DylvUDt1myXAW5y33sbRSpyxjYE3wxxAgUZM4y/uQq0N3INp1STgHeGJM+kWUT4GTWfLiBFA6K1Y/G2vgA56kEaobVISQJr5jD8i4WO3xr7qUcsh56BXUzAN3mL64P1bDWKWk/VpbogtKL6FfIinX69OR2mE63F22qE3EOFBajFgzD2AbGmZY7WjHpYsWgXX8HV/AdskzmCb/YcoR4AGC8h66Bt6iyWCAz3Q/rxO7irm39cvDL0KKhrHO4O2RhFe0pzya8ldRN4xcDFEbGV8RVSOixBB7bBZL+8tY+k3rhGpdM32e06mJKTVozdLCXzdszJGLFjJsE+olBmvKWytqE7jLVe1djumXLWyRXsKNwvybDtYgmB6TmvmWloyjXszuflv35xaThh3YyTu6P45MAyWMvGVOGjz8U64K

给出一个字符串,求出它的最长回文子串,你可以假定只有一个满足条件的最长回文串。
RU5DMCY+v4FfJmW6mcIlL8SJUaq+2Vg+I8BFevSqpWtUFd/KF9jLBwSRKDzmgOvoDFMfxyBvSKdV01TL8cBBlL983PzsaE/2eF1fJfa9X0BYDtYYsZlAu6vNSZb0o97fCCLjoMa+UlUKT+KinxceDjNcpbUxFJ49uI/wCI/lXjf9WapMPKbn8a+gJMd0RbGVKSSbM6bDEKiRpe+thm0HgHOV+Gl4Qtlq1OoUM8BNwdIp9THhb3rMUtxq6+TDGlGCZIWwhUFvOGICuEx7zRNx69BbD4DmTIGzILfgckna/rLgrC8Bc11JvDm0TdngubVxRxC1CCJMQnnVxNj50axkXryOUoMojylr0cw48qvOtn8VWoozNEMMV0PemvNeAX3yLS8nU6oj7H6lTUVoe6VQwLXJhVAnpk/jkKdEUhDIQwJqQeZ5wR3F8zwO6VLJeHTucuiIsZfGqTMPRZqgFJ708V1SNmPPLzdkDVekJQq1rj8ODEvZyH/NMrPN94yeKQBWa8nFzyM9H8l1qOx+ps1txx7U6/IKVLepylhEXmigism6WnwnCyn/02hiosL3FUtGLMJsiSZYu/vV0uq5ue6AeOtFGoSqDoLmYpB58zlghGPg95JM5iFw1Ui9TM0prsv+QJFDnxHCSInoDSTilm7y8gOW2pL6B6GhBEFDx64J+k2K7yDCnWyQl0OhAFN5xsXPkjHXyB3KAcXgikzdqVS03xqk0QH6S5nIMPJzEtQDl+Q6TNpXDgQ/Fml6LP2JbZJ/jRX8uQFHOndONNrwV+oTwPsSogAum1UQNTdOjpLEPj4dE5oxVBDFil3liT8xikqZIvQcZwT/3zKATlu/nLAHKPSugiklNanfABxgu6DjFNHr3lX1S0dO/zO+Z2fAraQYPnyMC/Bq4jdgtZRxHhF1sDucBWqU8DmpZCHtdWTesc3qvYdhJASxPdmzISstNsY/hEOVgQ==

【数据结构】
给出一个可能包含重复数的整数组n,和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口,找到数组中每个窗口内的最大值。(模拟法)
RU5DML6TaLytyPTdJQliKlTgSqAIdEva+FRBfiNh8RtuP6qLJdVgT/LbMByfJGGKMlW5Pkoxol3ql/6eiLxGaO1sQvxVU1ntHrROn61PQETciiwrV0zWlVrJOHq+Twad4wG37FT5ng0cKDMJl+Vwm45pLlPICycpCMthFanL7xWls4JZ3eAlVhy5f21u8cQgzUQEM0xiGPXHHEarHWaJlsIvSzxjtg52bJdvoaIGxrTTrkkyDk6BXcIbLw1Rd9DqH6R2yirjTrK/3RfgOChb+Wd/hZs+XclLuDqPjPsKA38gCN66a4jU5/+vs2kgf7o3z09lHSMiqfcqHyw60GxbwCRU3cl+DygNoaxP7FkgSHroc1bATjnmcPuyUhwnh7KUYjs4MBmWPKVIMMyomMqkA140oZEEPjyjD8cK8cJFUQ+006MuQtMmkw4QMbJ2x5m0FdYQwuYt6/Iw85DAtC6SeIpQdSn/3UMdP2QNAjCNoL9r9Dgw72XBjmvONGKEvxdCsAd+ZE/0+PwpXyNp0Ij5MLuXLqY9GxJOYt/5AcbjRda+RuL0dl5aQmafevNel/ARkFHmEpszwN/RDUVcGoSjoqVzPJdBw/KxWG6VwByNoXwRS9t8UlI4JQlwaWONJMqK4IFbxYBBI7APrnniRrQa6Tq6ap5eFznRQ8ns4WxZA7S1/dhAnZ77/kZghho3YElHCWARwlaYuAKy2kdy6L068HnXPdfDxF8KvA5bjGZIeBKgh2ZbWSOKxaH0W8oA6N1Ol67UiazPsbQfhS3E3c1ilRe/dkFpqiN+rfhFsUUBvdBa0uLppEeeD14u0ENIcTO1M2rmjORHC5bxdF5UaLIDQKTFRzfGEqKpfykPgP/at+Siz6niEamKku/lq+OAXl85XaOcANhU8b6m5rLT0+lRPscpo7NEOCtPBHgVARu4d5PAGIm/e78u+H52aM2qd90T6hxMabz0+lC1cnq3rjDVXzDPYxVNOURI1FJS/kViOKiF5u8DECgRH0LtY8jS4ftJNb4GBuViiCaqlkxO56JYckqD7kijFVdi37d0CMY7SS4SGgDmEu2G8L7GrQ9ePsLhV+LjCFD88d6l8XuSQ3dU8GlCDYhzSZcVR7b0dIsIaBcBAG0lJWwlVU75RodWMnUEP2JkkWER3dW8268VVuUe7r597ntKjecFbyq+Y4Hxg4VlvX0DKJ0iWEAujjySCoT+158mZefrcARczUt79ZKMDcwRh059MQnoOI1ANsD2QOiO47jrfpaZEOQi2va91y2ySm9z4AyFlzlXaeIFNozwdd2Zxzo9WoeKJajhwkl3rMKpg7kPt/EpaKgsJkyS70bxhQoaGaVKnGT3ljgpVg+uUKB9sKg=

RU5DMDdyjap9Ib1fSeAnUq24p7F0f91CqC7BWQGM4YLdX/k99zl1EuU0bJUrdm7/90KZLSkdKErBfr2SDBexm4yfuPnYybsvMo6S0h7nb4aZfSNkRMlFH/MJYZuf3Xz+QFIadEMc1hXDS6ctcSpbr40a0Kw5unTRT7iadPPi6MgTj1QNRay87wPc6e4mRcKDprhPmUlPg84DO7oSfUZcqLpGXdJwfB1olGkouciXiybv50dyGrxsiLVeK+gWs6L0bLfBQfNBiRafcg+aBpV12t5+4NA2sZNjAAfqpQ+UnVWive/xX4fGhUjvA4QIzmTt2XhcL1SOgRvV39DV9PL+FmLV9v/CS140cL3ZqSJpJp7wL+iDOIXlxfA1emTfkww9ywIuYJ5t33TBt/SKSj/Pi8SYuX1Efd/wTl7lrESrN14sMZiFYEKLS/w2n3NAHZF0c2MjCXUlBA/fopYvVxhok9vNAlAPQt0ylRj0o/oVUUig4y2nExeinFHvdXnQz/HHNs3Gv/MTGT+dw9IiqN5D1K0cP44v5E0FS0360hDmy5+uGy25t7up194Qb/OvcgPYUCBoxUqAukth1e/Fy/Cmt8f+V6FWBrlnwmEZozfNdLTvYed2kCLuinC5jBvIkA9eg18SCzhlRVXu32XMfNXAITJlU7H1tCAEGsd7fwM8rZXwp32z1bR/tvzsMW4xQF5JsJ9HExD5oUi/InuaDkpMm7xIsEFVROXTwh8p3GxTW/Dr8OnE+xriOeFDdKhdX1wDpibI7fJuEytKtYzmBiLhlGz+5uohoTxQ4DIjwmAM7r4fljaxczVjEN94CG7yKleAibF3pCtVrJQClV1AlRSXfoiXlGIlCHvHtKKgS09KwZBlZzOy6I/6bf/oNdVHxyLb98eLLkoF6B36iTfk9RDZuEUzskmj9yMrYztrYvSL9lU4xVx50rwy1JDXam67nLvPXklGcT6tT+dO7ZXquJuP/Qsdbh6wFYALkYgXKl+TseqcZCZWWw4a7M4i0XHT4oUouKdI6dXBLVrmkCMQlLFdZ/269foZpg9MEPIW0umnAuHDkdahxXdP07p0BF3x2CKKBhBDJLNBdevv/G5ieg5Ld1pUPFs=

RU5DMJ6/v1CrYjqJo7Qr/MouZ2Nf9Tv8/JVbSQJXMcZBJnhVjrYpe4S9SoVIlya4OvBDpr4bq0I3zeKn91ZVddER1TEZuCv4gtHfblfm5uVWlQHzRDAgVC9QfF+xmUPcgqVhIHUDG2jZtCdRpR8S/++CKE4lTZofEgCpGCihAzSIIHwOc0NO+g6yNrWJZ+iseJxo/fBZk5p/VLYAFW57LOXCMdessst8SKthX4TwgdOvIQ1segb88D4xRxpQYCY2Xdha3TLc+9GAjA+viUsNTfZ/7Br+dG4fTo8EISXo2zJw1eRgaGiz5hZ4a2ZROXRBZVqPKuyJqFZrI3ZJNlYzH6B2mu4V8opPz4qZZZUxzM3SW+XDsWM3P9gnnH78jjtR+bcMZc8FOXzoVX5SU/7cmxF3hQCSRB2IpW1vRGqbucpjAr1jKGEJAaNDXmGsDIHa2nbFHoAyvAVLymRKkp8RXehAl8r176qjp0RlpoXnO/X4SgMmIxQkWQVDYCWB57dzLw0WVrFTaO4TfHHr7gqQJFS8F00/ZEiLUEyX7c73rDpfZeTS3HsCDO63P6i80S4XZ5ZJ2dDmGeJNbv84ZNgS9l7gKNgr8qo7TT7R4hkguyZ4HvtQXjK+imyblTCdtT+8GlmCJ5NIvwa3hCxX7+eWOWro/kVmvrG7flATUFTl5AqMqA/5z0PGuuPcv/GSgkZdyKDpBtnowyulwRBk3Oe5BQe0xWRMALT1DYpi2njM50GKogsrLkSIfZHp8miyZQOozhgitLig+IK/QU4VYhc/4u35VbLEGBwM+N3hE7qMErfkA7Hsg4+3kUlMw43qPgFwtaeTF5riYpCc3ILvW4brMx5yfTXHLvDKtpLn6hrOYoitCVDMu9H8nsUINn8ps1xVmgkdZWZ1RCo92SCC8pIQIEv+Z9lTXxCu9EKoUbVdvpaFLLhoogLdURgJSoFISsw/Z1Kk22k+098+HxKvB4GYx1ypjCZ97gfQ7gOrrFqkVmYfDbBzXemOkhDkTbj3VB/lv7OxpPaj3Mzq3wVOHnDwmay0NTStbaDAX2x+Wu+WMxfZtDPC/RNPSu1Ondb4kfSKnz7sT/88SzMCK0yWLVI9IO2uMh2v/Vig33xLc0rumyuPg4qbBHv/CrW1IYDiR9kI59TCBmuQQ2ysB0BqsDypk8q0oOBzMCXsuUaEzXNeKOGbgxQWhZOnPcG04gwRgQf2AgB0RQ==

【贪心,分治与动态规划】
假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易,设计一个算法来找出最大利润 (贪心)
RU5DMMO2tw2AXyw16zlLpRe+xLapb/k2wl47jlwySzBDBN0iL/CVYiPSKXAHDnKai3MrOnFlOaXM/aWRfJTY6hm9SU4jx926cOhF/SyWprT98YyZCdhEavxydSTcyC8+2095Gvw6dxPo+EJapaRfh3qVoDEWXm6Qk+YsV1iRZRs0G6i3sW4G6GGQyRPITC99e9V+owQNnRaykJmSGF85Xqii852enynbPLYz3KQiKEnDB2Rt0tKhUOVLVo2YHq9TokxDy3m/m7aDPjL+6fx4B1Fls1b+Na51K76ZIGRnmFRlT8jQUb7bKzFckGgccrhyb9OHLzUCgeUbDHjrF/NUJ0CIisWu0AoMlXhdb18LoyynCOCVJypr5fiYDl8udHMl3z2bKjpD4ZZ2qPzgYYnFyRbHth6VgJpLMiEn7Gzff98U0gD5vUvF5cvz0Km6qldUIu/ycg==

> 扩展I:可多次买卖(这个更简单了,只要今天比明天低,我就买,然后第二天就卖,否则就不买,和前一题一样简单)
RU5DMJqn6zcn4Ya+ZZfCKbPN0jR9rQqdJnfwqmrVAQZe+f49/PlElDSFEBw8MKNWHgAj4SXa9M4B/HENo2aAJy2K/Jqhz0r0wD0zR8rvSHY9fMJcPLTxYsUwlmHC6KQlsXJ8u9JdoJBPpEpYh78iFLvKgVD1yw9uHzXplHz7W6sD0DJQhcwQK+zFe8EMH/uoxEXriIs8Xy/ZvyhDmQgkkqe66dHls+NH/ytOYhFgmD5r6YcvtJRij+3MI+Hkz+x1HC8v5kS/4Ni1TL460SN7JCG0un54NXghOuKz8YwkZgRRzLuK

> 扩展II:只能买两次
RU5DMPlJcNyl8X9P3jdoYoc1+F3psXqjMRbpYmhHb54N8XxLPYzibK1aloNWZkmuM7FlPKWdCp1dGdK0OzduErdXJKMM3D0BFe6rANK4XheRCDAU7yo8GeHWLK8yuKKFPGAZH8xAxOFmc2b1wxFCI0fgym1EL7STnRjXNDQbN7CMBIIOKD/s9GxGtGSja3CwjOfrXvvefl05VbWKRSkJHxxlRpgTuTWiIgkJqMQgATFEnZ71+vyvv6CnsCxUrfOfiq0KC9Ui2wvovAlQJ5A3q/yJK3WorzAwRn1AwZ45q8A2KQdaA+d9zQKExZYLMgVZUM/cerwQ9gVSsW7wxXH14d1rtXGCbAnBsWmk9jJOu+aWEG3s0cXx5CtbWC/EUzCMFlVIzhLopCbU0PoZHshVvI2Oz+M=

给出一个股票n天的价格,你可以第一天买入1股,第二天又买入1股,然后第三第四天卖出2股……输出能够达到的最大利润值 (优先队列)
RU5DMILbFJHzWTbpHO/S6bCa8UczkwfUEQ3aMxKx36iuD88be5pgDRLz6tbJQhlnBwuF2S39d07fTMmayV8zVtEvBJWmrvlkwYPqUfWX6gwK2OpIJgZRft0m0K1fhtSPfXCCNSoO2/3FcvVJNOP/uKhh8QklOzPdlbmHlAv+R9x19O7hPF4koE7dgbtJfsVBhQ6XdFiI/vWfATi1GcI6sQHyfi2sj99lPMoVdPsi1H0J2GKtn3ZcvhK1C9ns9GXpfv+mNeEmGg3eHfLN++LNAzz/0RzXataw7F8OsH3oueX4jRXy4kvuC6I5wjHuS9kHqHOepHUC4uxRmTgSK4DGtlaVS6HYfyYwT3jyOl7Bwd+8yNq8s/DEwxTurv9Xes1iEaT/Wp84ir2sZq7G6NqOlUQ0KL3GPh4IPNqLGNB7uG0AKcGfhRmUXPKkyWfTzlklfr/m2XqqP1nk+gVTLt0m5RIH9ayOVnPi/8wtLbtIrlrSRsCOFfCBgAPFeg+24liScohisnijQxt+gfDFUDaOZ77KIXfDFt623lddkiJ1mrZQwJicORd6ZAdzIUarX7gBUlDbIHVIxz3FNb/9NJhQegfzhRNE9jxJyCM+hE72ywQDplez0GMwGhRPDdGXVOuAUxR9VsJTQ1gOZiAvlXtGQmfCvvizGa9ce4c67ouhKOqfFKYxw/6AE5SQNGJ5apKCNr+fhT7EWBFoRmhffu7XVu3qspH532jab4snno4KQOtZb2aJvDH5BBl5rgeabybgqOwQTcCayAfKGfU4paOYtIJ/wskMGc4Ddu7ceOVD3Nd8Xt2j01lAFDmyWeO+3yiw2/+BpnhbsihIZe/5fbc2hjJQMGRi0jXEJNicoYhGBU4bqdwMDdRhDZtwzr88R1rBJ+Y6ALanmXOGSMyze4wvpeRRmAJASNqhwlFqb5WDDrPH4ObkjFm1e2GhKPuoVUJjnUPs6qwU36LgyUmeqX3to3Mt4+Ig50p/aAxkYk/Sz0Ri+e+B5JaxqSLbcrFnNJZ4gb4rUg==
  • 用优先队列存储当前遇到过的价格 priority_queue
  • 每日的新价格 与历史最低价比较 if minheap.size() > 0 && k > minheap.top()
  • 若比最低价高,则弹出最低价,同时更新答案,即加上差值 result += k - minheap.pop(), minheap.push(k)
  • 压入当前价格 minheap.push(k)

给出一个非负整数数组,你最初定位在数组的第一个位置。 数组中的每个元素代表你在那个位置可以跳跃的最大长度。 判断你是否能到达数组的最后一个位置。
RU5DMFzKzgCmna9hGJG4LixhxomF+IQRFOGqan3jxH8m4xQEVu18aqDVnBtoF/2AfnftXhsEaUxglMeeymIZyff7BCvGNspdnFeV61ZD93QF3iG2Id+u+ZS0ln+wq48OI3fqLnGFY7KfQUbnM8wDoNb3TDSCgpjeog2fqzGEf5ETAPv7uBfA36d+oVUsZyjrh04MZTGmRTUasWTiIIG1x0xGz3X+iShqU5cXfyZUFL7O2W/GfDARZcV3Shq/bKC9eCdSXbG7s96NzSNPiYxC89vNvEvcrTl9E58DAewMmew/TVQ/Cc/cD4++sWNe8DGGwiuKrINEymndLqre7tDH9UC+Rb9/JxzW0uBeA0e2qgir7QyPyJQkU7eyTzRJFhQNdb/1TV4tZqMgSCYe6sigklrdygg=
> 扩展: 请用最少的跳跃次数到达终点
还是很简单,我到达一个点,就标记到这个点的最少跳跃次数 f(i),那么到终点就是 f(n)

给定一个数字列表,返回其所有可能的排列。如123, 132, 213... (穷举)
hint: 排列就是一个不断交互的过程... 也可以将其视为树遍历DFS的过程
RU5DMMpji7BeUpD8tFvVxSnLGJmLD+k5UcwYPQCcLmrd2D+QJbtvT9iVtWIwdGIpB3lvRNCLBoDIEumrYu7v1206yEoh7bq7kuP7DlsTF308PTX1WqBWUVHbOAEk1VH0eCZ25I8mpvS+Y7h6BXtTHax7SiQdWf4kczf+iIohYON0dxTI6K+QT4bL6BAfTvvBjKKPVCoLFnN/g4cXNnWZapOmjyYTJbIPHzK5HIWxtkaWFulAlvTtF8rmIqcZRumEJ+YIH/VdT9z4O5hI7gxiAR09f2yMWXyqgQdrkzhDvVnJDQGnwSIYuspkaLMVn4v2deN5LhMI+/cTxZ8MRIe3Me2J2Wy8jffg1v8bAxmAz/RjSFlUrFlyOvRl2xNlbuL4QccelhmJrib020qp7eDxw3xv4T6x42lPMNrRecXC8FSIji57NId6ht095dj145BazDB4NxkBJA1UBsafpj5DLJQDEcaPManfCiC/SNu1dtJkzV37Yd/QlTeOZ2z40q+omdK+CnhSzSSMyLBNRgKpaiUPT/YADjh4hvjCyuU1Pj4c291WlttqMhNbzKaMxCaJp7NXTlgGdp8kvvKO1+180Gv4rk7fP9CTfO7NWRwvqpS+uTwOFbgTEnQIBYGIH2rSAxBGIElHJBMLqaBv0fAFsWVPGNJh+XjUStPoPlb5tBIev0iaCceN0sOggw2o8YzTcIIQ74R6o4S0SMn3yiTuaY2bfTQeidQACDrjXaO4qwQOiXPs1ioaydALIKngcRgwF5cRpCCDGWuQuNoockU/ZTm2RR8yZhrKR/ft9uk9ergcpBeH05sUTTqxti6383/OSiQucdZcMdI+ptNyhNsVM/RdV5GXp4eNmm6l9nQfP57LDmOCPWCSZYllxhWgFLCulp4PMnd8vwaboonT4gSbdDXMuvX3l80+wClSr26AHLIbRiCvEAMU1Dh3s0wHVtvW8N5AuCDzJvXeoC4cnvDwlQ7LamENEjAC2N1RpZ5MByoKR3sqrG/xE7Tuxp33AnOrLTgRdXI9gWSriSX97Ar/cxm+T9YmYlKJAo/5aJ1n1Sdfmwv7BFPFvHNtujZ8AyknKcaNanMXiMvqBl7BdP0nzZfcE1Vqetk8mtDl/sYgeGoUlQ2XhygzHyw2aabsXGyaouxStZUXoTQWCnPLfdsI34wn5+DqYPnsp3KQHR14Gc/ubIExEexq2ykfOyo8IIi7p8IcefJ8supHq1y4OnfCLALHhpPD5fLa3S99kVmFn7WraQiGfDWQYj+DYAbFAAQhZxGVlG6MzXaW5dgR8TMuZ8WLN2qTm3mBFo4NfVHEtJ7v+TNsBnNLtQLxbRskBgrM+GVhlFHe2LpEU7HgvAj0CTTcbDzDw+XSLbeSJct/Ba/CFYEKgsjrMNiq3qmCfHWo6MriBe1MDzflu0A20GRbRZfoyA8ooZVm2KKY5HsT+mTwvbOV7dj6lH7Iy31dfbsMeE/OHco1awnEuWTbD8TN2i+rVtn6clCKvlVRHYcAR+TecYEiWIrZJ8C7e1OTL0m1kWJpdlbV3F/n1Xgc7h23X7Jblyql2w9jE2NsmBhDGrc7GUzb

// 排列/组合模板。适合解决要对元素排列求解的题
vector<vector<int>> 题目(vector<int> &nums) {
vector<vector<int>> res;
if (nums.empty())
return res;
// 有时需要对输入sort排序
递归(nums, res, 0);
return res;
}
/* 递归参数通常需要vector&引用和int begin*/
void 递归(vector<int> &nums, vector<vector<int>>& res, int begin)
{
// return终止条件,决定是否加入res。根据题目变通
if (begin+1 == nums.size())
{
res.push_back(nums);
return;
}
// 进行遍历-递归
for (int i = begin; i < nums.size(); ++i)
{
swap(nums[begin], nums[i]); // 递归前,如果是组合就要vector.push
递归(nums, res, begin + 1);
swap(nums[begin], nums[i]); // 引用传递所以要换回来,如果是组合就要vector.pop
}
}

如果不希望出现重复的数字,可以用一个hash表记录避重,或者一开始我们就把列表排序一下,这样重复数字只能有固定排列法

类似-全组合:a,b,c,ab,ac,bc,abc
其实,就是遍历时每遇到一个新字符,就将其与之前已有的组合组成新组合加入,这个思想其实就是组合的组成方式。相比上一题排列其实要简单很多
def subsets(self, nums):
nums.sort()
output = [[]]
for num in nums:
output.extend([subset + [num] for subset in output])
return output

在数组中的任意两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。给你一个数组,求出这个数组中逆序对的总数。
RU5DMP7iiJcuSbmBzrvpGXNp3AQ7RGBNOBurSGExRV/WL4k86A1mwcUlAayJz4Et5G54qnnXNfnGxK2cCRNR2xuvq8EoHE/0hGlXsc2L/lGmoaSlAi8IksL9HW+riy5FaEcBkxRAnnOjZPPGerjP170LWVHg/6HMr+PzQlEKX9ZFPWMloGRrzWgtHu82sJdKddWYOtksAKi3/Z6NpqWPGmyBZASh/gcq5q0NZ1PIf2uHdlCJ5NU5UNyeKB8JyQ+WRiIbH23+7bFY24sBt9VrxYrIOeHC7HanD8QD5mDg8XXopkLyx8NuQp57hdQ9txbRTOV0jdMERtOk4bGHLcN6aomRlk0BPb3gCmO9MtQqf9RGiXi9iOl+DMPc9QpzFqYwK2sONWcQ+K9F0y/Srr8cLtXsaV6yXMwKAZTKg7WkyfH/c8Q5zYiL6F0kvkwYg5l2/QnuzxUFCxTAXGH6SXJFgq1Ow7rN7wJlA9D8ILgC/SeS5pcqvnjrP120ihnnyTPBscrDEU/JRwSuD7jE7SMrWxSudSK/yoUTPYvStIZBP3drC1moiycOaULASx77Nbz0WlRQtNLMVlbF9wkoaUg+Rf7h7RgZPHeD0O5R2pW4N+aiUVdY9o/7RugQogQvVJ55f+WI49ZF5y7pWRu/zCGHl6cNo0UOLB+H0UmdVHGi+TTy9uhBaR6gpnAiD8jTg/2Sa/zRenJ6M04r2N/3rApBtOHqE+2+K5Wj3IG03RpqX9FOljIOmRFoabkSA/qYgk+rmz7W/LjVLqcJnPM95LxraQ5jlBtPQR9EIG0aaNSWPGMGjosUtSAe337WkMN0K3yrZ8YWzO2/rzUojL1hVPeAtWmRaTupP1Ve6o0jRLcXUnVaPHESTjFQ++NpmgvFTUZ164A11+hS2oR6W8vhGoKWJew3v0GNENq7E+gXBXLW/QeYhTy0SNpbWiLSfwwwjAQYjYa8UPnxOA8stt4a88zv3eYMAldxgBMFUZsvPiJC9v7oCpFG6Zno2WG0VmLScwITq2QWz/zHbOPCs2BEEvimZhVDQcxRiHrQwiAnL+ueqGbD0oWjm8TbqOLU/BQX+eSwn8BoOs0OKkpDh+ZHiryglLYRcsU=

编号为 0~n-1 的n个士兵围坐在一起形成一个圆圈,从编号为1的士兵开始依次报数,数到m的士兵会被杀死出列,之后的士兵再从1开始报数。直到最后剩下一士兵,求这个士兵的初始编号。
RU5DMF2V1DX0y2nq3UyFY/WIxRTpXJCSir8HGuzc1ieqdBsETZzvW2gY8kTzNrfgaJuQ9wk8y9NdUas7AdPIbvI8AjUx/30aE8nxColKrjwZ7VZLMyp12ucU/8MULExkGUH6gYnoN/5IX4eIEsUd4kwR7ZZZ/DuO9qfwnpJxb9CbaWBwH7wWo6BdyNlFFVxi7hj6a5hkMAhSeBr25EegwTg0KSZlepBl+R4/nhEZxd78SrRo784SrEkwGpYb7UIpINqrTj0GFV85pA+jGwckRskCYkc1E/JVvZieVw66sS5O5aMh66VBtwy+RBazk45nGS6IGkjZX7ROtyhkX+ogO9w2hXS0H+Eb8HYt5Cqpt4tK3vRrxboHOs3d2/FSxxcsmobpJ6uHusFKfl03hja+gFJaUFzp9SBAu2bjuqEjk7GJ6KghApT9X1l3KB+LTHUnUYXBj0gS3lX1k/5+uGZJfPnuDYCuCqExyoQLmyIZYkDujvMY0KaaK2NeM8gj7EGrdUSdhSTGFG24xSrOU6v6Yg0ffQat/yODR/4QdTzDE9kINucZ8K1XLEuH+vPnqiGcled6ogEH3vKeAd46PkM+81dkdstdIfUEgZYLcrPmimL8cI9Rbo3xSur1hQFwumuk9UlwSH/aUca4qvStJwNAlf8y4OzMp3gm8Zp4tMHA+cTwUzGPDTWsoTMJ/YELwyUuhYUDSuWFAzNKtJW/CnLL61l6CP1v9dkGlLksoULgLk5zM7YuTOZQdlLPscC/Y3PgoR4yXKaoWJx9Sj65NuYt3ZgNl7w=

int f(int n, m){
if(n==1) return n;
return (f(n-1, m) + m-1)%n + 1;
}
DP很适合解决 能通过局部解演变得到最终解 的问题,只要确定 要解决的目标动态转移方程,原本常规方式不易解决的问题都能迎刃而解

将长度为n的绳子剪成m段,这些长度的最大乘积是?如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
hint:拆解成子问题有最优解
RU5DMKpQGeYstI+bkqwilcndZfyqV/ekRVeMQlSfMMWd4eNFYRnM05PKkvTx34KqCFmQi7kgTixZ1MNV2gtQcVOr5TTGe8GLtT+HzWzHIXnbLICxTe19m0ahn0YBXLd2lBnxZCwSIe+XYPw07tA3kmsxwk3MQNfo/KVOdJA/ICs5jpyprhnt/f5lMw6xmiMYd1sI/1H5CuI64WvF+ucX4m6oiu0iO5MdK8IhQvBn9Nt8eH+UA2+sISOWd8QXIrCVNOwOK5CJFBSgAwR1ZqYCMf6EUH/gQO92ns0JoFLcAN4D4WwzYi1c9pWWNcVrpfSfcBwSWu65wSQ4Z8lqZdhVGAs2pguDug7WhAdb09FGLy5Amb4Frh74DtCjOiwUp5QW5m4SrIWKvBRnufdiEJe8UvvWF6IG1SPQnaHldjfq6Cz+GntcURXIZgua+cUDLeJsRVqfNolmt8ki//0hZpk1xFeibAKsx9Rd7YUFGbvjWiNs2ShP0BtGKTzh/M6VzmmhbxSety08vT57SlshmdQeO8QoZzZNF8Xzj8ammiCAxS7ozf0Y/b2w2M02d6loeW0y0uA1IJ+tIyUyh2RF41RUJObwNkux2qTNfI4ZFtqbOOI/rL7JYGWpJ22V3L+0CwV41anyZm1v1upbvbjlhTHGWOE7WE8Wq2EoLKZhNDtHEc5qoAdcUOM+KiRN6cNz0bbBDT7Pu15qICOOM1do3v309s3ooS92+A2wrocFqbXmsIrOUOioC4zElnlslOnJhHLsXqGKw625J/wk2yzaUq4CX8oeduaxgco9wQngc+X7UoXdg93264WZDoa005IMR1EDZuhGK9CmwYK4O/rKuaPYkXd8nMNcCSoBiVCXtQkYL+ARMHiggxNQgZNcDp3lXYNtRF37jA==

一个大小为 V 的背包,现在有n个物品,已知每个物品的大小 C[i] 和价值 W[i],问最多能装入背包的总价值是多大?

RU5DMCAke75pbV6H+aJxp0OyYS77BDpY5BNbJp3ug4hTZw/Eutd9EUAC+wyjKpR+fGrlJmh0wjyTEmGoXD2rspvSj7jpkC96Liqe9Xdk2P+2wqZm4r4vlqXTX0FN0/8PmseqPlQ3lnZo4XojT6cumMDK2HYgYDpVaWjmffhDkg0PNQUSkbla0+f3CU/GNgWZfM8BawYsXmvByCWglDt6UAZhPEfOk+TXlfwYwIANkwTcPHV3KjmjH1jprazEiHYmx6Yn1q8V8S2V0qJ2QldiAJR7WxGht1ZOT8oUt9SpmvnugvFpcm55ExThIAJ4BpPb7dLfycAoL4YOscgyxxMpG6My6Ca0M46H9blnX/Nqrvur4XB3D5R8RMmJ+Mjr2S3Yp1ntHiL1XgvxTSEErEHUZipeLJDbcvMzFLUm3EnudRirWLo/6idpZahVVX6NfdNto2341dTz58gf5iqKaHKo8UxQge6DFjEN5ZJtca1n6X1C4B/QyLDVFgFqNVzJQsJK1i2a3xHD/7avpnLY19Ff8NQGyTrMef7neXZbOr38XcWSQAit43Zx/wWs7DF9to2jYNiKrtYYapftj3yTo9IZR+ZC8tnQLDUSibif/eSGGAjI/YmlFFhEFwxdzdmmVuQjG32J9fzkNSjbQWTebxKcwOWsZSLtTwAZijdC4lf1m2WvQHNjeZLrCoGzi5/1QBAaXpv+5F3j3dxJrU1irFrHg+Rls48=
int backPackII(int V, vector<int> &C, vector<int> &W) {
int** f;
for(int i=1; i<=n; i++) // 加入各种物品(注意这里外层循环一定要是i,因为物品是不能重复加入的,所以放外层逐个迭代判断是否加入)
for(int v=1; v<=V; v++) // 计算不同容量下的局部最优解
if(v>=c[i]) // 背包容量够大,判断是否放入
f[i][v]=max(f[i-1][v], f[i-1][v-c[i]]+w[i]);
else // 背包容量不足,不能放入
f[i][v]=f[i-1][v];
return f[n][V];
}
其实我们也可以把第一维给优化掉,如 f[v] = max( f[v], f[v - C[i]] + W[i]) ,不过也还需要两层循环,只是物品数其实是不需要记的

给定一个只含非负整数的 m*n 网格,找到一条从左上角到右下角的可以使数字和最小的路径。
  1. O(n)。矩阵每个结点保存到该结点的最小路径和。f(i,j)=a[i][j]+min(f(i-1,j), f(i,j-1))
  2. 0,0点、最左列和最上行由于会下标越界,所以需要单独计算
  3. 这题要么开个大数组存储,要么写个二维vector,别用动态数组了

给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。
RU5DMALN4furXEPNcpt06xcWTF3dCJSjPs9nR7gdBro5fC8sONICOXTTqcI2/LLOoFNg1rE0viAePvv7Zg8ZhGrfyg3oxOuQCbTYMVnFyrkVlWIuxLoPbJ15YanuQsAnEEKeppVJgvuiXNDdIqzSGvtNN9gjhnTu549i13YfkB/QiIYPRHG92ioei3r3CKk5Ua1Pbyxy0e7Zx68MF0RJYkROyEXN6HDlXB0Oa76vQNc2FfrdN0PJBKgMYsttvxyTdqoyCpjrE0ccvSAW4xnNvJ68hlJRfAZ2sGNmY0OSMpwp5fY+OX3nntaZgsOOG1t4KvYad9jfUsQMl1OHHwmGgTutQxAP5LuICuKua9ZU3v6XwJgT5PpcMUjyCr1p5GeDqdC9pJOVXV58+G70j1eodnmVtLNKGiVwT9Tnr+1RAx8x1zthsqrP4VXOfH7Y4BS4iRyYMvpszgGxdZiLzHvdElF7yR5NeY+Hnrr2ZDKpai51YxR2WpwtUKc0Gyqtfug5CDDW356pw7KqhK5yJsTyOi0E5fK0k/y8ei8oJbr8H5II/PSzqpBQGygtbhnCXvMjf+Me9KJfnAEIdd5eTQyZp9Umvls6oAyc2EWa9IJQMdlsIxWKeqhQ6yEKwLxUKmkWoswsuOXsAPxrfc0BGNSHIJ3s/O4an1IYIJirVkFIAiIelQ5tsJiTd4LHNhcDYEHVMW33X4SACwjdYhnm3DQT1YTqMIgplYhu81BJ/+GDbwGZB6e2O2mQVZ58N0WxcvZXs12H72sG6UWsFQUQRxPGujcp8NtoSgQIlkE5vt2aawN3+xiJ+sfFpwq8/Yts66Yk9MBfS7QBRvP47qVJh64/2Ig2rJVWon126eKNERUwLnqSd0b1K6/QU61j+Ts0LQlmwt1e7MIiJDQUHT+GdjYbfAY6DRAPSekuGGqhbKCLoCXHFoHvKI8E1wgtabmF2FnINSXJcMAiSX2RnK0wIdj1MjkuZgXzwD221OnDeDfyltXl3snUJnoSXj5hbLwrzpiosyg3JOxOCnp/89c24/Py7QxeQ+XwGKyeCib62wCGZdMI8Bz6kWqH6djby/cDqLSkzDuvkWXfR+mzreqKGmrDDuukYL2zosWOpBwG/7SOvuw77zRftADvx7HJnGh7ZaUzrYzHzjywbR7xohy14zj3KxA/K2KNPDJCBfkM927g6B9+YdpPfBNISzSXdS8PReVZICUUev4U5zYun2p4oJ+z/RGgMao7kC5WbGRE9pxVeGvDDz38OwZz1HF2IA+e9Ttr0I2tadDSdj2yASFjolHyI/PhE1bEv1s+9qfpyYITppDFAbjveHls+RFbyv0OkNBwz6xMdcm4kaPdF8pfTev8BhBPy1pZ5aGvOmROT5MCj04ULfP+LvJHjzkSAO+DvZpv+NuuFo9UqLzUg9OreBRrZFhb2T9r6bJwX547/YLZJ2dcQ7Er4f8V1Oqni49+XyhhvXNXItMSq/d2qAH88XEGZjJ6zol9y88kCbwpKanSks8mjQx9zzkD01Kj9L8Z2u8ib7jTxlKgNRD2v8waZzVVkA34x/Q9mUbuN/0V06OdfjP6eound74D8SsgKq+flX6+cUgFEx4hhcP66V7/eGqY/gA73BGm5WTj+IxgqfoXaAF+jD4uwr5hPLN+d0pmdEmqUdoW1rZoNrsTM7GxPIzF98wMRTvGbnWPzrdrUfAT3NAKYsjI8kbjkXiS+yJrz+8oqZkLshxSJi5yT7LU1pu5znhAicY3BZCSDL0Qa2SGkiMjiNkrBDINXZj54oufP5jWOS8ABczH24uS+e7VHjyEac73zKAuqS6FjnQp22I7867OHED1MvuWh7P/mcTojZFlQlRPdiZbVJVx7/5aJmtFm0aoA2b+VN4/+uuVVwxPAqLNiTOy
这题还可以更进一步,如果排序的话,结合二分法,可以优化到nlogn

给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。

同样是DP,但是需要对比多个字符串的情况,都符合才能+1
因此我们需要二重循环立方程:

【其他,概率论,建模】
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
RU5DMPiTAToNoizK4WP/bZ0Sumz4NUh+AnEziqjKm5WzvHrMnrXZh26P9xcLxY4SQcU+QAxiRjZHbfNwZDR64g2rBZoGKlNxa3u9hN2FiLHFoNntYaKSNKzALgJYUqL2vvEfANNxzOA2jlOm5fpMQFpqrW01TDIijAjrJhZv4NCTvq7QsVtVwPwmKy36smxXnRs0Dp/Frcx7maQL+MSYrT5nsJ1OpgrbhNZb5vkVTex1vOdnU818tknfn1IeX4iHEW1M4MOow4tjjCO9OZoR9GIfiecJp2W32xXF3ENcVtsaAWbyf287s/gUugtAm9daoCgNtdV3MLWcxIq5/CKQ76dAzuz2Nq/MlYnycipwz7BalvhX
我们可以立DP公式,求n个骰子的点数和为x的概率为 f(n, x),那么 f(n, x) = sum(for i in range(6): f(n-1, x-i) * 1/6)
f(1,1)=1/6,越界则为0


一点番外周边,闲时调剂,也是给自己一点目标动力
Leetcode周赛-南外

线段树








comments powered by Disqus