高明网站开发绿蜻蜓建设管理有限公司网站

当前位置： 首页 > news >正文

高明网站开发,绿蜻蜓建设管理有限公司网站,建设银行官方门户网站,公司做网站推广需要多少钱目录 第一题 题目来源 题目内容 解决方法 方法一#xff1a;贪心 第二题 题目来源 题目内容 解决方法 方法一#xff1a;双指针 方法二#xff1a;KMP算法 方法三#xff1a;indexOf方法 方法四#xff1a;Boyer-Moore算法 方法五#xff1a;Rabin-Karp算法…目录 第一题 题目来源 题目内容 解决方法 方法一贪心 第二题 题目来源 题目内容 解决方法 方法一双指针 方法二KMP算法 方法三indexOf方法 方法四Boyer-Moore算法 方法五Rabin-Karp算法 第三题 题目来源 题目内容 解决方法 方法一递减法 方法二位运算和循环 方法三二分查找 第一题 题目来源

1. 将钱分给最多的儿童 - 力扣LeetCode 题目内容 解决方法 方法一贪心 class Solution {public int distMoney(int money, int children) {// 如果可分配的钱小于儿童的个数则无法均分返回-1if (money children) {return -1;}// 减去每个儿童至少分配的1美元后剩余的钱money - children;// 计算剩下的钱最多可以再均分给多少个儿童即money / 7与儿童个数中的较小值int cnt Math.min(money / 7, children);// 已经分配了cnt个儿童money - cnt * 7;children - cnt;// 如果剩余的儿童个数为0且剩余的钱大于0或者剩余的儿童个数为1且剩余的钱为3// 表示不满足要求需要减少已分配的儿童个数if ((children 0 money 0) || (children 1 money 3)) {cnt–;}// 返回已分配的儿童个数return cnt;} }这段代码是使用贪心思路实现的计算分配钱币给儿童的最多个数。 如果总钱数小于儿童个数无法进行分配返回-1。将每个儿童至少获得1美元后将剩余的钱数money减去儿童个数。计算可以获得7美元的儿童个数最多为儿童个数和money/7的较小值。将7美元的儿童个数乘以7减去money得到剩余要分配的钱数。剩余的儿童个数等于总儿童个数减去7美元的儿童个数。如果剩余的儿童个数为0且还有剩余的钱则将7美元的儿童个数减1。返回最终的儿童个数。 复杂度分析 时间复杂度为O(1)因为无论输入的数值大小如何都只需要执行固定数量的操作。具体而言算法中只有一些简单的数学运算和比较没有使用循环或递归等可变的迭代结构。空间复杂度也为O(1)因为算法中没有使用额外的数据结构来存储数据只是使用了几个变量来保存中间结果。 LeetCode运行结果 第二题 题目来源
2. 找出字符串中第一个匹配项的下标 - 力扣LeetCode 题目内容 解决方法 方法一双指针 首先判断 needle 是否为空字符串如果是则直接返回 0。然后判断 haystack 的长度是否小于 needle 的长度如果是则不可能匹配返回 -1。接着使用两个指针 i 和 j 分别指向 haystack 和 needle 的起始位置通过一个循环遍历 haystack 字符串。在循环中使用 j 来遍历 needle 字符串如果匹配失败则退出当前循环将 i 后移一个位置。如果在遍历 j 结束时j 的值等于 needle 的长度 n说明找到了匹配项返回 i 的值即可。如果循环结束后仍然没有找到匹配项则返回 -1。 class Solution {public int strStr(String haystack, String needle) {int m haystack.length();int n needle.length();// 如果 needle 为空字符串则返回 0if (n 0) {return 0;}// 如果 haystack 长度小于 needle 长度则不可能匹配返回 -1if (m n) {return -1;}for (int i 0; i m - n; i) {int j;// 在 haystack 中从当前位置开始与 needle 进行匹配for (j 0; j n; j) {if (haystack.charAt(i j) ! needle.charAt(j)) {break;}}// 如果 j 的值等于 needle 的长度则说明找到了匹配项返回匹配项的下标if (j n) {return i;}}// 没有找到匹配项返回 -1return -1;} }复杂度分析 时间复杂度在最坏情况下需要遍历 haystack 的每个字符并且在每个位置进行 needle 的匹配。因此时间复杂度为 O((m-n1) * n)其中 m 是 haystack 的长度n 是 needle 的长度。注意这里的 (m-n1) 是遍历的次数每次遍历都需要比较 n 个字符。空间复杂度代码中只使用了常数个变量因此空间复杂度为 O(1)。 需要注意的是虽然上述代码的时间复杂度与 needle 的长度 n 相关但由于 n 的取值范围很小1 n 104因此该算法在实际情况中通常会表现良好。 LeetCode运行结果 方法二KMP算法 当使用KMP算法来实现字符串匹配时需要先构建Next数组然后利用Next数组进行匹配。 class Solution { public int strStr(String haystack, String needle) {if (needle.isEmpty()) {return 0;}int[] next getNext(needle);int i 0, j 0, m haystack.length(), n needle.length();while (i m) {if (haystack.charAt(i) needle.charAt(j)) {i;j;if (j n) {return i - j;}} else if (j 0) {j next[j - 1];} else {i;}}return -1;}private static int[] getNext(String pattern) {int[] next new int[pattern.length()];int i 1, j 0, n pattern.length();while (i n) {if (pattern.charAt(i) pattern.charAt(j)) {j;next[i] j;i;} else if (j 0) {j next[j - 1];} else {next[i] 0;i;}}return next;} } 以上代码中strStr方法用于进行字符串匹配返回第一个匹配位置的索引若不存在匹配则返回-1。getNext方法用于构建模式串即 needle的Next数组。 复杂度分析 KMP算法的时间复杂度为O(mn)其中m为原串的长度n为模式串的长度。 getNext方法的时间复杂度是O(n)因为需要依次计算Next数组中每一个元素的值。strStr方法的时间复杂度是O(m)因为需要依次遍历原串中的每一个字符。在最坏情况下即当原串中不存在匹配子串时strStr方法的时间复杂度为O(m-n1)即O(m)。 综上所述KMP算法的时间复杂度为O(mn)。空间复杂度为O(n)即Next数组的长度。 需要注意的是KMP算法虽然能够提高字符串匹配的效率但也有一定的局限性。当模式串过长时构建Next数组的时间可能会变得很慢从而影响整个算法的性能。 LeetCode运行结果 方法三indexOf方法 可以使用Java中的indexOf方法来实现。indexOf方法用于查找子字符串在父字符串中第一次出现的位置。 class Solution {public int strStr(String haystack, String needle) {return haystack.indexOf(needle);} }在上述代码中strStr方法接受两个参数haystack和needle并调用indexOf方法在haystack字符串中查找needle字符串的第一次出现位置。如果找到了匹配项则返回对应的下标否则返回-1。  复杂度分析 时间复杂度该算法使用Java中的indexOf方法其时间复杂度为O((n-m1)m)其中n为haystack字符串的长度m为needle字符串的长度。具体来说在最坏情况下需要遍历haystack的每个字符并检查是否与needle相等因此时间复杂度为O((n-m1)m)。空间复杂度该算法的空间复杂度为O(1)因为只使用了常数级别的额外空间。 需要注意的是尽管indexOf方法的时间复杂度为O((n-m1)m)但在实际应用中它通常比手动实现的算法更高效。这是因为indexOf方法在底层经过了优化使用了一些技巧来加速字符串匹配。因此在大多数情况下使用现有的API是更好的选择。当然如果需要特定的定制功能或特别高效的性能可能需要考虑实现自己的匹配算法。 LeetCode运行结果 方法四Boyer-Moore算法 Boyer-Moore算法利用了两个启发式规则来跳过尽可能多的字符以达到快速匹配的目的。这两个规则是坏字符规则Bad Character Rule和好后缀规则Good Suffix Rule。 class Solution { public int strStr(String haystack, String needle) {int n haystack.length();int m needle.length();if (m 0) {return 0;}int[] badChar new int[256];Arrays.fill(badChar, -1);for (int i 0; i m; i) {badChar[needle.charAt(i)] i;}int s 0;while (s n - m) {int j m - 1;while (j 0 needle.charAt(j) haystack.charAt(s j)) {j–;}if (j 0) {return s;} else {s Math.max(1, j - badChar[haystack.charAt(s j)]);}}return -1; }}在该代码中我们首先对needle字符串进行预处理得到坏字符表badChar其中badChar[c]表示字符c在needle中最靠右出现的位置如果字符c不在needle中则为-1。 然后我们从0开始枚举haystack中长度为m的子串s并比较s与needle是否相等。如果相等则返回当前起始位置否则我们利用坏字符表来计算s需要移动的距离。 具体来说我们将字串s中最靠右的坏字符与s中的对应字符对齐然后向右移动j - badChar[haystack.charAt(s j)]个字符其中j - badChar[haystack.charAt(s j)]表示坏字符在needle中最靠右出现的位置与它在s中出现的位置之差。如果坏字符不在子串s中则我们可以将s直接向右移动一个位置。 复杂度分析 Boyer-Moore算法的时间复杂度为O(nm)其中n是haystack字符串的长度m是needle字符串的长度。在主循环中我们通过比较needle和子串s的最后一个字符来判断是否匹配。如果不匹配我们利用坏字符表badChar来计算需要移动的距离。在最坏情况下每次比较都有一个字符不匹配那么主循环的迭代次数为O(n/m)。而在每次比较中通过坏字符表找到需要移动的距离的时间复杂度为O(m)。所以总体的时间复杂度为O(n/m * m) O(n)。空间复杂度方面除了输入字符串之外我们只使用了一个大小为256的数组badChar来存储坏字符表因此空间复杂度为O(1)。 值得注意的是Boyer-Moore算法的性能在处理大文本时更加明显因为它利用了预处理表格来跳过尽可能多的字符减少了比较的次数。 总结起来Boyer-Moore算法是一种高效的字符串匹配算法适用于处理大文本的情况时间复杂度为O(nm)空间复杂度为O(1)。 LeetCode运行结果 方法五Rabin-Karp算法 Rabin-Karp算法的基本思想是通过计算字符串的hash值来进行快速匹配。具体步骤如下 1、首先判断特殊情况如果needle为空字符串则返回0如果haystack的长度小于needle的长度则返回-1。 2、接下来计算needle和haystack的初始hash值。这里使用了一个质数31作为base并将每个字符映射为对应的整数值。 初始化needleHash和currHash为0用于存储hash值。初始化power为1用于在滑动窗口时快速计算hash值。 3、然后使用一个循环遍历needle的每个字符计算needleHash和currHash并更新power的值。 4、然后在一个循环中通过滑动窗口的方式在haystack上逐个移动子串并比较hash值是否相等和子串是否与needle相同。 如果当前hash值相等并且子串与needle相同则返回子串在haystack中的起始位置。如果当前hash值不相等通过重新计算hash值的方式继续滑动窗口。 5、如果循环结束后仍未找到匹配返回-1表示未找到。 class Solution { public int strStr(String haystack, String needle) {int n haystack.length();int m needle.length();if (m 0) {return 0;}if (n m) {return -1;}int prime 31;long needleHash 0;long currHash 0;long power 1;for (int i 0; i m; i) {needleHash needleHash * prime (needle.charAt(i) - a);currHash currHash * prime (haystack.charAt(i) - a);power * prime;}for (int i 0; i n - m; i) {if (currHash needleHash haystack.substring(i, i m).equals(needle)) {return i;}if (i n - m) {currHash currHash * prime - (haystack.charAt(i) - a) * power (haystack.charAt(i m) - a);}}return -1; }} 复杂度分析 哈希值计算计算模式串和文本串中第一个子串的哈希值需要遍历模式串和子串的字符。因此哈希值计算的时间复杂度为O(m)其中m为模式串的长度。哈希值比较在每次哈希值匹配的情况下需要比较模式串和当前子串是否相等。最坏情况下需要比较所有字符时间复杂度为O(m)。滑动窗口滑动窗口的操作需要在文本串上移动移动n - m 1次其中n是文本串的长度m是模式串的长度。每次滑动窗口需要进行哈希值计算和哈希值比较操作时间复杂度为O(1)。 综上所述Rabin-Karp算法的总体时间复杂度为O((n-m1) * m)其中n是文本串的长度m是模式串的长度。在最坏情况下即当哈希值匹配每次都发生冲突时时间复杂度可能达到O(nm)。 需要注意的是选择合适的哈希函数和哈希值比较算法对算法的性能有影响。另外Rabin-Karp算法需要额外的空间来存储哈希值空间复杂度为O(m)。 LeetCode运行结果 第三题 题目来源
3. 两数相除 - 力扣LeetCode 题目内容 解决方法 方法一递减法 首先处理特殊情况。如果被除数为0则返回0如果除数为1则返回被除数本身。接下来处理除数为-1的情况。如果被除数大于Integer.MIN_VALUE说明除法结果不会溢出直接返回被除数的相反数否则返回Integer.MAX_VALUE避免溢出。处理正负号。通过判断被除数和除数的符号确定最终结果的符号。将被除数和除数都转为正数进行计算。使用循环逐步减去除数每次循环都将除数翻倍同时记录除数的倍数即为商。循环结束后根据步骤3中记录的符号返回正确的商。最后检查商是否溢出。如果超过了Integer.MAX_VALUE则返回Integer.MAX_VALUE。 class Solution { public int divide(int dividend, int divisor) {// 处理边界条件if (dividend 0) { // 被除数为0return 0;}if (divisor 1) { // 除数为1return dividend;}if (divisor -1) { // 除数为-1if (dividend Integer.MIN_VALUE) { // 检查是否溢出return -dividend;} else {return Integer.MAX_VALUE;}}// 处理正负号boolean isNegative (dividend 0 divisor 0) || (dividend 0 divisor 0);// 将被除数和除数都转为正数进行计算long dividendAbs Math.abs((long) dividend);long divisorAbs Math.abs((long) divisor);int quotient 0;while (dividendAbs divisorAbs) {long temp divisorAbs;int multiple 1; // 除数的倍数while (dividendAbs (temp 1)) {temp 1;multiple 1;}dividendAbs - temp;quotient multiple;}if (isNegative) {quotient -quotient;}// 检查是否溢出if (quotient Integer.MAX_VALUE) {return Integer.MAX_VALUE;} else {return quotient;} }} 复杂度分析 处理边界条件的操作是O(1)它们只需要执行一次。处理正负号的操作是O(1)它只需要进行一次比较和赋值操作。将被除数和除数转为正数的操作是O(1)它只需要调用Math.abs()方法一次。主要的计算过程是通过一个while循环实现的。在每次循环中除数会翻倍因此总共进行的迭代次数不会超过log(N)其中N是被除数与除数的差值的大小。在每次循环中判断被除数与除数的大小关系、减去除数、更新商等操作都是O(1)的。 综上所述代码的时间复杂度主要由循环的迭代次数决定即O(logN)。其中N是被除数与除数的差值的大小。空间复杂度方面代码只使用了有限的变量存储中间结果所以是O(1)的。 需要注意的是由于代码使用了long类型来处理可能的溢出情况因此在某些情况下时间复杂度可能会略微增加具体取决于具体的输入值。但整体上该算法的时间复杂度仍然是O(logN)的。 LeetCode运行结果 方法二位运算和循环 思路是使用位运算和循环来实现整数相除的操作。 首先我们先处理一些特殊情况。如果除数为0或者被除数为最小值且除数为-1防止溢出那么返回Integer.MAX_VALUE作为结果。然后我们判断结果的符号。如果被除数和除数的符号不同那么商的符号为负否则为正。接下来我们将被除数和除数都转为正数进行计算防止溢出。使用long类型的变量来保存转换后的值。然后我们通过循环来不断减去除数直到被除数小于除数为止。在每次循环中我们使用位运算将除数扩大两倍左移一位并记录扩大的倍数。当被除数小于等于扩大后的除数时我们将被除数减去扩大后的除数并将倍数累加到结果中。最后根据之前判断的符号确定结果的正负并返回结果。 class Solution { public int divide(int dividend, int divisor) {// 判断特殊情况除数为0、被除数为最小值且除数为-1防止溢出if (divisor 0 || (dividend Integer.MIN_VALUE divisor -1)) {return Integer.MAX_VALUE;}// 判断结果的符号boolean negative (dividend 0) ^ (divisor 0);// 将被除数和除数都转为负数进行计算防止溢出long dvd Math.abs((long) dividend);long dvs Math.abs((long) divisor);int result 0;while (dvd dvs) {long temp dvs;long multiple 1;while (dvd (temp 1)) {temp 1;multiple 1;}dvd - temp;result multiple;}// 根据符号确定结果的正负if (negative) {return -result;} else {return result;} }} 复杂度分析 时间复杂度主要集中在两个循环中。外层循环中每次被除数减去扩大的除数直到被除数小于除数为止所需的迭代次数最多为被除数和除数的差值的二进制位数。内层循环中通过位运算将除数不断左移直到大于被除数的一半。因此总体时间复杂度为O(log(max(dividend, divisor)))。空间复杂度算法只使用了常数级别的额外空间主要是用于存储一些变量和结果。因此空间复杂度为O(1)。 需要注意的是在处理边界情况时判断除数是否为0以及被除数为最小值且除数为-1等操作都是常数级别的操作并不会改变算法的时间和空间复杂度。 综上所述该算法的时间复杂度为O(log(max(dividend, divisor)))空间复杂度为O(1)。 LeetCode运行结果 方法三二分查找 使用了二分查找的思想通过不断将搜索范围缩小来逼近商的值直到找到最接近的商。 具体实现步骤如下 对特殊情况进行处理当被除数为 Integer.MIN_VALUE 且除数为 -1 时由于计算过程中会出现溢出因此要返回 Integer.MAX_VALUE。将被除数和除数转换为长整型避免计算过程中出现溢出。确定搜索的上下界左边界为 0右边界为被除数。进行二分查找在每次查找过程中先计算中间值 mid然后判断 mid * dvs 是否小于等于 dvd如果是则将 res 更新为 mid同时将左边界 left 更新为 mid 1以继续向右侧搜索否则说明 mid * dvs 大于 dvd需要向左侧搜索将右边界 right 更新为 mid - 1。当左右边界相遇时二分查找结束返回 res 作为商的结果。根据被除数和除数的符号可以通过异或运算来确定商的符号。 class Solution { public int divide(int dividend, int divisor) {// 特殊情况处理if (dividend Integer.MIN_VALUE divisor -1) {return Integer.MAX_VALUE;}// 将被除数和除数转换为长整型long dvd Math.abs((long) dividend);long dvs Math.abs((long) divisor);// 确定搜索的上下界long left 0, right dvd;int res 0;// 二分查找while (left right) {long mid (left right) / 2;if (mid * dvs dvd) {res (int) mid;left mid 1;} else {right mid - 1;}}// 根据符号返回结果return ((dividend 0) ^ (divisor 0)) ? -res : res; }} 复杂度分析 时间复杂度使用二分查找的思路每次查找可以将搜索范围缩小为原来的一半因此时间复杂度为 O(logN)其中 N 是被除数除以除数的结果。空间复杂度该方法只定义了几个基本类型变量所以空间复杂度是常数级别的即 O(1)。 LeetCode运行结果