游客gsugatesykzaq_社区达人页_阿里云开发者社区

1.验证回文串（125-易）给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。ps：我们将空字符串定义为有效的回文串。示例 :输入: "A man, a plan, a canal: Panama" 输出: true思路分析：法1：比较常规的做法就是使用双指针，这里注意忽略字母的大小写，即 A == a ，对于其他非法字符直接跳过，但只考虑字母和数字字符。法2：这里分享另一个思路。将字符建立映射关系，具体是把 '0' 到 '9' 映射到 1 到 10，'a' 到 'z' 映射到 11 到 36 ，'A' 到 'Z' 也映射到 11 到 36 。然后把所有数字和字母用一个 char 数组存起来，没存的字符就默认映射到 0 了。这样只需要判断字符串中每个字母映射过去的数字是否相等，如果是acsii值为 0， 就意味着它是非法字符，对应映射位置为空。代码实现:// 双指针 public boolean isPalindrome(String s) { s = s.toLowerCase(); if (s == null && s.length() == 0) { return true; } int l = 0, r = s.length() - 1; char[] cs = s.toCharArray(); while (l < r) { // 剔除非法字符（即找到有效的对比） while (!isAlphanumeric(cs[l]) && l < r) l++; while (!isAlphanumeric(cs[r]) && l < r) r--; if (cs[l] != cs[r]) { return false; } l++; r--; } return true; } // 合法字符：字母和数字 private boolean isAlphanumeric(char c) { if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9') { return true; } return false; }// 解法2：映射+双指针 private char[] charMap = new char[256]; public boolean isPalindrome(String s) { // 建立映射('1~10', '11~36') for (int i = 0; i < 10; i++) { charMap[i + '0'] = (char) (1 + i); } for (int i = 0; i < 26; i++) { charMap[i + 'A'] = charMap[i + 'a'] = (char) (11 + i); } char[] cs = s.toCharArray(); int l = 0, r = cs.length - 1; char sl, sr; while (l < r) { sl = charMap[cs[l]]; sr = charMap[cs[r]]; // 检查映射是否为空 if (sl != 0 && sr != 0) { if (sl != sr) { return false; } l++; r--; } else { if (sl == 0) { l++; } else { r--; } } } return true; }2.验证回文串ii（680-易）给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例:输入: "abca" 输出: True 解释: 你可以删除c字符。思路分析：基于双指针实现，最多删除一个元素，也可以不做删除操作。那么我们就对删除一个元素进行分析，即出现某次不对称时，删除一个元素，继续进行比较，这里我们通过调用isPalindrome函数判断字符串区间是否回文。代码实现：class Solution { public boolean validPalindrome(String s) { char[] cs = s.toCharArray(); int i = 0, j = cs.length - 1; while (i < j && cs[i] == cs[j]) { i++; j--; } if (isPalindrome(cs, i, j - 1)) { return true; } if (isPalindrome(cs, i + 1, j)) { return true; } return false; } public boolean isPalindrome(char[] cs, int i, int j) { while (i < j) { if (cs[i] != cs[j]) { return false; } i++; j--; } return true; } }3.最短回文串(214-难)题目描述：给定一个字符串 s，你可以通过在字符串前面添加字符（即添加前缀）将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。示例 :输入: "abcd" 输出: "dcbabcd"思路分析：本题可以用双指针实现，但这里用字符串匹配感觉比较合适。本案例关键就是求出从开头开始(前缀)的最长回文串!!!参考这里思路1：对原字符串进行反转匹配，举例：abbacd 原s: abbacd, 长度记为 n 逆r: dcabba, 长度记为 n 判断 s[0,n) 和 r[0,n) abbacd != dcabba 判断 s[0,n - 1) 和 r[1,n) abbac != cabba 判断 s[0,n - 2) 和 r[2,n) abba == abba 从开头开始的最长回文串也就找到了, 接下来只需要将末尾不是回文串的部分倒置加到原字符串开头即可，但过于暴力！思路2：对思路1字符串匹配进行优化，我们知道字符串匹配算法还有KMP算法。如果我们把思路1中的例子 abbacd dcabba看成一个字符串，中间加上一个分隔符 #（避免计算公共前后缀出错），abbacd#dcabba。左右部分可以对应拼接字符串的前缀和后缀，即寻找前缀和后缀相等的子串。我们如果求出了 abbacd#dcabba 的 next 数组，因为我们构造的字符串后缀就是原字符串的倒置，前缀后缀相等时，也就意味着当前前缀是一个回文串，而 next 数组是寻求最长的前缀，我们也就找到了开头开始的最长回文串。思路3：马拉车算法，待补充...代码实现：解法1：反转字符串public String shortestPalindrome(String s) { String r = new StringBuilder(s).reverse().toString(); int n = s.length(); int i = 0; for (; i < n; i++) { if (s.substring(0, n - i).equals(r.substring(i))) { break; } } return r.substring(0, i) + s; }解法2：KMPpublic String shortestPalindrome(String s) { String ss = s + "#" + new StringBuilder(s).reverse(); int max = getLastNext(ss); return new StringBuilder(s.substring(max)).reverse() + s; } // 获取next数组（即当前位置之前存放的最大匹配长度）的最后一个值 private int getLastNext(String s) { int n = s.length(); char[] chs = s.toCharArray(); int[] next = new int[n + 1]; // 初始化 next[0] = -1; next[1] = 0; int k = 0; // 最大匹配(前后缀相等)长度 int i = 2; // 当前最后一个位置 while (i <= n) { if (k == -1 || chs[i - 1] == chs[k]) { next[i] = k + 1; k++; i++; } else { k = next[k]; } } return next[n]; }4.构造最长的回文串（409-易）给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。示例 :输入:"abccccdd" 输出:7 解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。思路分析：法1：本题要求通过输入构造最长回文串的长度，故可以统计每次字符出现的次数，最后考虑奇数情况完成字符串构造。法2：这里可以对数组长度和统计方法进行优化，这里只需要统计偶数（奇数 - 1）出现的个数，见解法2，参考这里：）代码实现：class Solution { // 统计每个字符出现的次数 public int longestPalindrome(String s) { int[] cnts = new int[256]; char[] cs = s.toCharArray(); for (char c : cs) { cnts[c]++; } int len = 0; for (int cnt : cnts) { // 只考虑偶数部分 len += (cnt / 2) * 2; } if (len < s.length()) { len++; } return len; } // 优化（题意优化空间和统计逻辑） public int longestPalindrome(String s) { int[] cnts = new int[58]; char[] cs = s.toCharArray(); for (char c : cs) { cnts[c - 'A']++; } int len = 0; for (int cnt : cnts) { len += cnt - (cnt & 1); } return len < s.length() ? len + 1 : len; } }ps：这里为什么申请58个位置，不应该是52吗？这里你要看一下ASCII码表，可以参考这里，大写字母ASCII值从64-90；小写字母的ASCII值从97-122，中间间隔6个字符，so。5.回文子串（647-中）给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。示例:输入: "aaa" 输出: 6 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".思路分析：遍历字符串中的每个字符，尝试从字符串的每个位置进行字符串扩展，向左右两边扩展每个位置（即定义两个变量更新左右边界），并统计回文子串的数量。ps：但这里要注意奇偶，即每次固定字符个数，两种扩展情况！示例： z x x c 注：扩展时固定一个字符有4个，固定两个字符有2个，共6个 a b a 注：扩展时固定一个字符有4个，固定两个字符有0个，共4个代码实现：class Solution { private int count = 0; public int countSubstrings(String s) { char[] cs = s.toCharArray(); int n = cs.length; for (int i = 0; i < n; i++) { extendSubString(cs, i, i); extendSubString(cs, i, i + 1); } return count; } // 向两侧扩展字符串 private void extendSubString(char[] cs, int left, int right) { while (left >= 0 && right < cs.length && cs[left] == cs[right]) { left--; right++; count++; } } }6.最长的回文子串（5-中）给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 ：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。思路分析：思路1：和上题中回文子串思路相同，遍历字符串，从不同位置开始扩展字符串（获取扩展子串的长度），但要注意奇偶两种情况！定义两个变量 start 和 end ，当最大长度发生变化进行更新这两个边界。思路2：动态规划，同时也需要更新当前最大回文串的长度和左右边界。dp[i][j] 表示 s[i, j] 是否是回文串状态转移方程：cs[i] == cs[j] 并且区间[i + 1, j - 1]是回文串或者只剩下i，j两个元素，区间[i, j]是一定是回文串，否则不是。思路3：马拉车算法，待补充...代码实现：class Solution { // 中心扩展法 public String longestPalindrome(String s) { char[] cs = s.toCharArray(); int len = cs.length; if (len < 2) { return s; } int start = 0; int end = 0; for (int i = 0; i < len; i++) { int len1 = extendSubString(cs, i, i); int len2 = extendSubString(cs, i, i + 1); int max = Math.max(len1, len2); if (max > end - start) { // 对于（如a b b a），i代表左b位置 start = i - (max - 1) / 2; end = i + max / 2; } } return s.substring(start, end + 1); } private int extendSubString(char[] cs, int left, int right) { while (left >= 0 && right < cs.length && cs[left] == cs[right]) { left--; right++; } return right - left - 1; } // 动态规划 public String longestPalindrome(String s) { char[] cs = s.toCharArray(); int len = s.length(); boolean[][] dp = new boolean[len][len]; int start = 0; int end = 0; int maxLen = 0; for (int j = 0; j < len; j++) { for (int i = 0; i < j; i++) { if (cs[i] == cs[j] && (dp[i + 1][j - 1] || j - i < 3)) { dp[i][j] = true; if (j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; end = j; } } } } return s.substring(start, end + 1); } }7.最长回文子序列（516-中）给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。子序列，指某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。示例 :输入:"bbbab" 输出:4 注：一个可能的最长回文子序列为 "bbbb"。思路分析：注意：一旦涉及到子序列/最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。dp 数组的定义是：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]。一般求什么设什么。状态转移方程：如果我们想求dp[i][j]，假设你知道了子问题 dp[i + 1][j - 1] 的结果（s[i+1..j-1] 中最长回文子序列的长度），可以算出 dp[i][j]的值（s[i..j] 中，最长回文子序列的长度），关键：我们只需要判断新加入的两个元素的大小，若相等加入，若不相等，即不能同时加入，我们需要取两个元素加入的最大值即可。if (s[i] == s[j]) // 它俩一定在最长回文子序列中 dp[i][j] = dp[i + 1][j - 1] + 2; else // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？ dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);动态规划流程：base case：只有一个元素，显然最长回文子序列长度是 1，也就是 dp[i][j] = 1 (i == j)；当i > j 时， 不存在最长子序列，即长度初始化0；上述代码和图示已经确定一个基本位置的依赖关系，目标位置dp[0][n - 1]为了保证每次计算 dp[i][j]，左下右方向的位置已经被计算出来，只能斜着遍历或者反着遍历代码实现：class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); char[] cs = s.toCharArray(); int[][] dp = new int[n][n]; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (cs[i] == cs[j]) { // 相等直接加入 dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]); } } } return dp[0][n - 1]; } }8.分割回文串（131-中）给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。举例：输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]思路分析：法1：暴力递归：将大问题分解为小问题（回文串），利用小问题的结果解决当前大问题。上述案例分析:输入：aab 先考虑在第 1 个位置切割，a | ab 这样我们只需要知道 ab 的所有结果，然后在所有结果的头部把 a 加入 ab 的所有结果就是 [a b] 每个结果头部加入 a，就是 [a a b] 再考虑在第 2 个位置切割，aa | b 这样我们只需要知道 b 的所有结果，然后在所有结果的头部把 aa 加入 b 的所有结果就是 [b] 每个结果头部加入 aa,就是 [aa b] 再考虑在第 3 个位置切割，aab | 因为 aab 不是回文串，所有直接跳过最后所有的结果就是所有的加起来 [a a b] [aa b]法2：动态规划：每次判断一个字符串是否是回文串的时候，我们都会调用 isPalindrome 判断。这就会造成一个问题，比如字符串 abbbba，期间我们肯定会判断 bbbb 是不是回文串，也会判断 abbbba 是不是回文串。判断 abbbba 是不是回文串的时候，在 isPalindrome 中依旧会判断中间的 bbbb 部分。而其实如果我们已经知道了 bbbb 是回文串，只需要判断 abbbba 的开头和末尾字符是否相等即可。所以我们为了避免一些重复判断，可以用动态规划的方法，把所有字符是否是回文串提前存起来，空间换时间的思想。对于字符串 s。用 dp[i][j] 表示 s[i，j] 是否是回文串，然后有状态转移方程 dp[i][j] = s[i] == s[j] && dp[i+1][j-1] 。我们只需要两层 for 循环，从每个下标开始，考虑所有长度的子串即可。因为要保证 dp[i + 1][j - 1] 中 i + 1 <= j - 1：i + 1 <= j - 1 j = i + len - 1 化简得 len >= 3所以为了保证正确，多加了 len < 3 的条件。也就意味着长度是 1 和 2 的时候，我们只需要判断 s[i] == s[j]。然后把 dp 传入到递归函数中即可。法3：回溯算法：根据动态确定每个下标和长度的字符串是否为回文串。满足条件的话，依次进行更新：选择，递归，撤销选择。可以传入回溯算法作为参数，套用回溯算法模板。代码实现：public List<List<String>> partition(String s) { return partitionHelper(s, 0); } private List<List<String>> partitionHelper(String s, int start) { // 递归出口：分割位置start == s.length() if (start == s.length()) { List<List<String>> ans = new ArrayList<>(); List<String> list = new ArrayList<>(); ans.add(list); return ans; } List<List<String>> ans = new ArrayList<>(); for (int i = start; i < s.length(); i++) { if (isPalindrome(s.substring(start, i + 1))) { String left = s.substring(start, i + 1); for (List<String> l : partitionHelper(s, i + 1)) { // 每个结果头部加上回文子串left l.add(0, left); ans.add(l); } } } return ans; } private boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (s.charAt(i++) != s.charAt(j--)) return false; } return true; }解法2：动态规划（空间换时间）public List<List<String>> partition(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; char[] ch = s.toCharArray(); for (int len = 1; len <= n; len++) { //所有长度 for (int i = 0; i <= n - len; i++) { //每个下标 int j = i + len - 1; dp[i][j] = ch[i] == ch[j] && (len < 3 || dp[i + 1][j - 1]); } } return partitionHelper(s, 0, dp); } private List<List<String>> partitionHelper(String s, int start, boolean[][] dp) { if (start == s.length()) { List<String> list = new ArrayList<>(); List<List<String>> ans = new ArrayList<>(); ans.add(list); return ans; } List<List<String>> ans = new ArrayList<>(); for (int i = start; i < s.length(); i++) { if (dp[start][i]) { // 看s[start...i]是否回文 String left = s.substring(start, i + 1); for (List<String> l : partitionHelper(s, i + 1, dp)) { l.add(0, left); ans.add(l); } } } return ans; }解法3：回溯算法private List<List<String>> ans = new ArrayList<>(); public List<List<String>> partition(String s) { int n = s.length(); // 长度和起始位置确定是否为回文（动态规划） boolean[][] dp = new boolean[n][n]; for (int len = 1; len <= n; len++) { for (int i = 0; i <= n - len; i++) { dp[i][i + len - 1] = s.charAt(i) == s.charAt(i + len - 1) && (len < 3 || dp[i + 1][i + len - 2]); } } partitionHelper(s, 0, dp, new ArrayList<>()); return ans; } private void partitionHelper(String s, int start, boolean[][] dp, List<String> temp) { if (start == s.length()) { ans.add(new ArrayList<>(temp)); } for (int i = start; i < s.length(); i++) { if (dp[start][i]) { String left = s.substring(start, i + 1); temp.add(left); partitionHelper(s, i + 1, dp, temp); temp.remove(temp.size() - 1); // 撤销选择 } } }9.分割回文串ii（132-难）给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。示例：输入: "aab" 输出: 1 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。思路分析：本题涉及最少分割次数，显然是一个动态规划问题。确定回文串参考8的动态规划解法。分析如下：dp[i]：以下标i作为结尾的最少的分割次数；确定递推关系：不失一般性，我们考虑j (j < i)字符（分割点）的分割方案。确定动态规划的状态转移方程：假设[0, i]已经是回文了，则dp[i] = 0。否则需要考虑j位置，判断[j + 1, i]是否为回文子串，如果是，那么以i作为结尾的最少分割次数为dp[i] = min(dp[i], dp[j] + 1)；那么待解决的问题就是如何判断[j + 1, i]是回文子串，若字符串长度较大，那么双指针时间复杂度过高（与647不同）这里可以使用动态规划求回文子串。子串[j, i]是回文子串必须同时满足下面两个条件：[j + 1, i - 1] 是回文子串或j -i <= 1；s.charAt(i) == s.charAt(j)，当长度小于等于2只需满足此项。从根据依赖关系从左下角至右上角依次填表，确定子串是否回文。代码实现：public int minCut(String s) { int n = s.length(); boolean[][] isPalindrome = new boolean[n][n]; for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || isPalindrome[i + 1][j - 1])) { isPalindrome[i][j] = true; } } } // 初始化dp数组 int[] dp = new int[n]; for (int i = 0; i < n; ++i) dp[i] = i; for (int i = 1; i < n; ++i) { if (isPalindrome[0][i]) { dp[i] = 0; continue; } for (int j = 0; j < i; ++j) { if (isPalindrome[j + 1][i]) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n - 1]; }

发表了文章 2022-05-18

十大常见排序算法（代码实现、复杂度分析与应用场景）

常见排序算法可以分为两大类：非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。如：快速排序、归并排序、堆排序、冒泡排序等。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。如：计数排序、基数排序、桶排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。常见算法的复杂度分析参考这里：所谓稳定性是指待排序的序列中有两元素相等,排序之后它们的先后顺序不变.假如为A1,A2.它们的索引分别为1,2.则排序之后A1,A2的索引仍然是1和2.（相同的记录在排序前后相对次序不发生改变，那么就是稳定的排序）对于不稳定的排序算法 ，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是， 排序算法是否为稳定的是由具体算法决定的 ，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a[j]>=a[j+1]，则两个相等的记录就会交换位置。稳定性的意义：1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。稳定排序算法：冒泡排序、插入排序、归并排序、（计数排序、桶排序与基数排序）不稳定排序算法：希尔排序、选择排序、堆排序与快速排序复杂度分析：数据结构和算法本身解决的是“快”和“省”的问题，衡量算法执行效率的指标就包括复杂度复杂度分析包括时间复杂度和空间复杂度分析，时间复杂度是指算法执行的时间与数据规模的关系，空间复杂度是指算法占用的空间与数据规模的关系为什么进行复杂度分析？如何分析？为什么分析复杂度：通过测试、统计、监控，可以的得到算法执行的时间和占用的内存大小，但是测试结果非常依赖测试环境，测试结果受数据规模的影响很大；我们需要一个不依赖测试环境和数据规模就可以粗略估算算法执行效率的方法大O时间复杂度表示法：表示代码执行时间随数据规模增长的变化趋势，又称渐进时间复杂度。大O空间复杂度表示法：表示代码执行所占的内存空间随数据规模增长的变化趋势，又称渐进空间复杂度 ps：给出随着增长规模的下界，具体流程：https://www.cnblogs.com/zxhyJack/p/10596735.html大O复杂度表示法算法的执行效率，粗略地讲就是算法的执行时间。下面的代码是求1，2，3...n累加的和。cal(int n) { int sum = 0; int i = 1; for (; i <= n; ++i) { sum += i; // 两步操作 } return sum; }从CPU的角度，这段代码的操作是，读数据 -> 运算 -> 写数据，如果每一个操作都是unit_time，第二行和第三行是一个unit_time，而第四行和第五行的for循环是2n个unit_time，加上return操作。时间复杂度就是2n+3，一般计算的时候会把常量省略，所以这个程序的时间复杂度就是n。所以就可以推断出，所以代码的执行时间T(n)与每行代码的的执行次数成正比。引出重要概念：所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比，即T(n) = O(f(n))复杂度分析法则单段代码，看循环的次数。多段代码，看代码循环量级。嵌套代码求乘积，比如递归和多重循环。多个规模求加法，方法中并行的两个循环。常用的复杂度级别多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长&#