小牛博客

题目链接：LeetCode 179. 最大数 ¶一、题解 题目大意： 给定一组非负整数，我们可以任意组合，使其得到的结果最大！ 思路： 这个题目，我的想法是分析每个数的最高位以及每一位的大小情况，包括0的特殊处理，后来发现这样处理似乎非常复杂！ 正确做法： 我们可以把每个数看为一个整体，通过交换相邻两个数的位置，即可得到是否需要交换！ 类似排序！ 因此这样处理就很简单了，只需要定义一个排序函数处理相邻两个数的大小情况，排完序，自然就是一个最大值的情况了！ 对于前导0的处理？ 能出现前导0的情况一定是给定的数中只有0。 若不只有0，则0和其他数交换的过程中，会发现，0这个数一定会和其他数进行交换放到后方，因为其他数放到前方一定比放到后方要大！因此不可能出现前导0的情况！ 因此如果最终结果第一位为0，则该序列都是0，直接返回即可！ 时间复杂度： O(nlogn) 空间复杂度： O(n) ¶二、AC代码 参考代码： 12345678910111213class Solution {public: string largestNumber(vector<int>& ...

题目链接：AcWing 62. 丑数 ¶一、题解 题目大意： 只包含2，3，5质因子的数，称之为丑数，求第 n 个丑数的值！ 思路： 假设有一个序列是丑数序列，我们将其中2的倍数，3的倍数，5的倍数抽取出来得到三个序列！ 那么原序列的取值一定是1和这三个序列的并集！ 因此丑数序列的每一个取值一定可以由这三个序列得到！ 我们使用三个指针分别指向三个序列的开始，那么下一项的取值一定是三个序列中最小的一个，取完值后对应指针后移即可！ 那三个序列的取值一定可以由已知的丑数序列通过乘2，乘3，乘5得到！ 不好理解的地方在于三个指针的移动？ 三个指针都处在已得到序列之前的某个位置，只有该位置的数乘以对应的2，3，5才可以且该结果在三个结果中最小，该指针才会后移！ 三个指针是否会越界？ 自然不会，由于丑数序列下标每次必增加1，而三个序列的指针却不一定增加1，因此一定不会越界！ 注意： 由于三个序列可能会有重复，即可能同时是几个数的倍数！因此我们遇到相同时，指针一定要同时后移！ 时间复杂度： O(n) 空间复杂度： O(n) ¶二、AC代码 参考代码： 123456789101112131415 ...

¶一、MyBatis简介 MyBatis，和数据库进行交互的持久化层框架（SQL映射框架） 官方文档也很详细：点击这里！ MyBatis特点： MyBatis将重要的步骤抽取出来可以人工定制，其他步骤自动化 重要步骤都是写在配置文件中(好维护) 完全解决数据库的优化问题 MyBatis底层就是对原生JDBC的一个简单封装 既将java编码与sq|抽取了出来,还不会失去自动化功能;半自动的持久化层框架 实现原理图示： 复杂场景可以实现手动！半自动 ¶二、MyBatis搭建 ¶1、数据库建表和对应JavaBean（略） ¶2、pom.xml导包 导入MyBatis、数据库驱动、以及log4j依赖！ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" ...

题目连接：AcWing 69. 数组中数值和下标相等的元素 ¶一、题解 题目大意： 一个单调递增序列，有一些数是和下标匹配的，找出任意一个该数！ 思路： 很明显，还是二分，关键点，二分的核心：需要找到二段性是啥！ 从目标答案该数向左向右分析，可以得到： 该数左边，每个数都比下标要小 该数右边，每个数都比下标要大或相等 因此可以通过二分找到第二段第一个满足条件的即可，即第一个下标和数值匹配的数即可！ **时间复杂度： **O(logn) **空间复杂度： **O(1) ¶二、AC代码 参考代码： 12345678910111213class Solution {public: int getNumberSameAsIndex(vector<int>& nums) { int l = 0, r = nums.size() - 1; while(l < r){ int mid = l + r >> 1; if(nums[mid] >= mid) r = mid; ...

题目链接：LeetCode 154. 寻找旋转排序数组中的最小值 II ¶一、题解 题目大意： 将一个递增序列（可能有重复元素）进行旋转，所谓旋转一次，就是将最后一个数和第一个数交换！要求旋转后的数组找到其最小值！ 思路： 仍然是二分，虽然本题的序列不是递增或递减，但是二分的本质是看是否有二段性！ 序列旋转过后一等会得到两个单调递增序列，由于有重复元素，因此旋转过后的第一段开始和第二段结束可能会有相等的部分！ 由于我们要找最小值，和重复元素无关，我们可以将第二段的重复元素先全部删掉！ 当然，全部删掉后若只剩下第一段，则直接返回第一点第一个点，即 nums[0] 这样第二段终点一定小于第一段起点！ 这样就有了二段性： 第一段都大于等于nums[0] 第二段都小于nums[0] 最终的答案当然就是第二段的第一个满足条件的点！ 时间复杂度： O(n)，若整段都是同样的数则会之间扫描一遍，因此达不到logn 空间复杂度： O(1) 、 ¶二、AC代码 参考代码： 123456789101112131415class Solution {public: int findMin( ...

题目连接：AcWing 68. 0到n-1中缺失的数字 ¶一、题解 题目大意： 0 到 n - 1 的数依次升序排列，其中有某个数不在该序列中！要求找出该数！ 思路： 很明显，是一道二分题目！ 但是最关键的是要找到如何二分，即这道题的二段性，也就是前一段满足一个条件而后一段满足另一个条件！ 还是很容易找到一个规律： 目标数的左边，都是下标和数值相等的 目标数的右边，都是下标和数值不相等的 因此我们可以利用二段性，二分出第一段最后一点，或者是第二段的第一个点！ 本题的答案当然就是第二段的第一个点，即第一个下标和数值不相等的点！ 还可以做一下特判，如果该序列的最后一个数 nums[n - 1] 与下标 n - 1 相同，直接返回 n！ 时间复杂度： O(logn) 空间复杂度： O(1) ¶二、AC代码 参考代码： 123456789101112131415class Solution {public: int getMissingNumber(vector<int>& nums) { if(nums.empty()) return 0; ...

¶一、SpringMvc概述 ¶1、SpringMvc概述 一种轻量级的、基于 MVC 的 Web 层应用框架。偏前端而不是基于业务逻辑层。Spring框架的一个后续产品！ MVC：新的软件架构模式 M: Model，模型，封装和映射数据(javaBean) V: View，视图，界面显示工作（.jsp) C: Controller，控制器，控制整个网站的跳转逻辑(Servlet) 概述： Spring 为展现层提供的基于 MVC 设计理念的优秀的 Web 框架，是目前最主流的MVC 框架之一 Spring3.0 后全面超越 Struts2，成为最优秀的 MVC 框架。 Spring MVC 通过一套 MVC 注解，让 POJO 成为处理请求的控制器，而无须实现任何接口。 支持 REST 风格的 URL 请求。 采用了松散耦合可插拔组件结构，比其他 MVC 框架更具扩展性和灵活性。 ¶2、SpringMvc实现思想 看下图可知，SpringMvc将所有请求都交由Front Controller来进行控制处理！SpringMvc的核心部分就是前端控制器！ ¶3、第一个Spr ...

题目链接：LeetCode 781. 森林中的兔子 ¶一、题解 一道有趣的数学问题，类似脑筋急转弯！ 题目大意： 通过每个兔子报的数（表示和自己一样颜色的兔子数），计算得到最少有多少只兔子！ 思路： 先将报的数相同的进行一下统计 设报的数为 x，报 x 数的兔子有 sum 只！ sum % (x + 1) == 0：则最少需要sum / (x + 1)种颜色，且sum只兔子都进行了回答 否则：最少需要sum / (x + 1) + 1 种颜色，共有(sum / (x + 1) + 1) * (x + 1) 只兔子回答了 ¶二、AC代码 参考代码： 1234567891011121314class Solution {public: int numRabbits(vector<int>& answers) { unordered_map<int, int> hash; for(auto x : answers) hash[x] ++; int res = 0; for(auto i ...

题目链接：AcWing 1222. 密码脱落 ¶一、题解 题目大意： 给定一个字符串，求其最长回文子序列，返回其最少脱落的字母数！ 思路： 转态表示：由于是回文，因此我们使用区间来处理，使用f[i][j]表示区间 i 到 j 的回文子序列集合。属性为：最大值！ 状态计算： 都选：在a[i] == a[j]的情况下有解：f[i + 1][j - 1] + 2 a[i]选a[j]不选：f[i][j - 1]，a[i]不一定可以匹配，包含第四种情况 a[i]不选a[j]选：f[i + 1][j]，a[j]不一定可以匹配，包含第四种情况 都不选：f[i + 1][j - 1] 最终答案： n - f[0][n - 1] 因此： 只需要计算前三种情况即可，第四种情况已经被包含！ 注意： 当长度为1的时候特殊处理f[i][j] = 1，防止越界！ ¶二、AC代码 参考代码： 1234567891011121314151617181920212223242526#include <iostream>#include <algorithm>using namespace ...

题目链接：LeetCode 1143. 最长公共子序列 ¶一、题解 最长公共子序列，经典的线性DP问题！ 思路： 状态表示：两个字符串，使用二维数组f[i][j]表示字符串a的前i个和字符串b的前j个子串的集合！属性为：计算最大值！ 状态计算： 都选，在二者相同情况下有解：f[i - 1][j - 1] + 1 a[i]选b[j]不选：f[i][j - 1]，a[i]不一定可以匹配，包含第四种情况 a[i]不选b[j]选：f[i - 1][j]，b[j]不一定可以匹配，包含第四种情况 都不选：f[i - 1][j - 1] 最终答案： f[n][m] 因此： 只计算前三种情况最大值即可，第四种已经被包含在内！ 注意： 下标问题，f[i][j]对应字符串下标为i - 1, j - 1 ¶二、AC代码 参考代码： 12345678910111213class Solution {public: int longestCommonSubsequence(string a, string b) { int n = a.size(), m = b.size(); ...

题目链接：AcWing 1381. 阶乘 ¶一、题解 数学思想： 0是如何产生的？ 当然是有2和5相乘得到的！那么，只要我们将2和5都除掉，那不就没有0了！ 具体思路： 遍历过程中，将每个数的因子2和5计数并除掉 结果每次只保留个位数即可 由于因子2和因子5的个数不一定相等，所以再进行一次乘2运算 因子2的个数一定比因子5的多，因此最终一定是2被除了多次，我们只要再将其乘回来即可！乘的次数为a - b ¶二、AC代码 12345678910111213141516171819#include <iostream>using namespace std;int n;int main(){ cin >> n; int a = 0, b = 0, res = 1; for(int i = 1; i <= n; i ++){ int x = i; while(x % 2 == 0) x /= 2, a ++; while(x % 5 == 0) x /= 5, b ++; res = ...

题目链接：LeetCode 1006. 笨阶乘 ¶一、题解 ¶解法一： 思路： 找规律！ n * (n - 1) / (n - 2) + (n - 3) - (n - 4) * (n - 5) / (n - 6) + (n - 7) - (n - 8).... 对于乘除法：n(n - 1)/(n - 2)，多项式进行一下除法可知道结果为n + 1 + 2 / (n - 2)，因此在n > 4的情况下，最终结果为n + 1，在n <= 4的情况下，则直接算即可！ n > 4的情况下： 第一组三项为n + 1，同理，下一组三项的乘除法结果为n - 3，可以发现正好和第四项抵消！ 结论：除了前三个，连续的四个数结果都为0。 所以有四种情况，根据模4结果处理！ 因此最终为： n > 4 时： n % 4 == 0：最终结果为n + 1 + 5 - 4 * 3 / 2 + 1 n % 4 == 1：最终结果为n + 1 + 2 - 1 n % 4 == 2：最终结果为n + 1 + 3 - 2 * 1 n % 4 == 3：最终结果为n + 1 + 4 - 3 ...