做算法题有个挺有意思的规律题目越简单越能看出思路的差距。暴力解法往往很快就能写出来但想出更优雅的解法可能需要多琢磨一会儿。下面这三道题都是 LeetCode 上的简单题我把自己第一次做时的思路和后来学到的更好写法整理了一下。题一存在重复元素题目给一个整数数组判断里面有没有重复的数字。我最先想到的写法看到有没有重复第一反应肯定是拿每个数跟后面的数都比一遍#include stdbool.h bool containsDuplicate(int nums[], int numsSize) { for (int i 0; i numsSize; i) { for (int j i 1; j numsSize; j) { if (nums[i] nums[j]) { return true; } } } return false; }这代码写起来很顺但问题也很明显两层循环时间复杂度是O(n²)。数组稍长一点LeetCode 就会报超时。更好的思路排个序再看其实有个特别简单的转化如果数组是有序的相同的数字一定会挨在一起。那我们先排序然后只需要扫一遍看看相邻的两个数相不相等就行了。为了代码好懂这里用冒泡排序纯数组下标操作不涉及指针#include stdbool.h bool containsDuplicate(int nums[], int numsSize) { // 冒泡排序 for (int i 0; i numsSize - 1; i) { for (int j 0; j numsSize - 1 - i; j) { if (nums[j] nums[j 1]) { int temp nums[j]; nums[j] nums[j 1]; nums[j 1] temp; } } } // 排序后检查相邻元素 for (int i 0; i numsSize - 1; i) { if (nums[i] nums[i 1]) { return true; } } return false; }关键点排序把时间复杂度降到了O(n log n)虽然教学代码里写的是冒泡实际工程中换成快速排序就行后面的扫描是O(n)。整体比暴力解法快太多了。题二罗马数字转整数题目给一个罗马数字字符串转成对应的整数。我最先想到的写法一开始我直接把六种减法特例全写成了if-else比如看到I就判断后面是不是V或X是的话就减 1否则加 1int romanToInt(char s[]) { int result 0; int len 0; while (s[len] ! \0) len; for (int i 0; i len; i) { if (s[i] I) { if (i 1 len (s[i1] V || s[i1] X)) { result - 1; } else { result 1; } } else if (s[i] X) { if (i 1 len (s[i1] L || s[i1] C)) { result - 10; } else { result 10; } } // ... 后面还有 C、V、L、D、M 的一大堆判断 // 代码太长这里省略了 } return result; }这代码能跑但写起来特别繁琐而且逻辑分散。万一规则再多几条代码还会继续膨胀。更好的思路其实规律只有一条仔细观察会发现罗马数字的减法规则可以归纳成一句话如果当前字符的值 右边字符的值当前字符做减法否则做加法。比如IVI(1) V(5)所以 I 减VIV(5) I(1)所以 V 加。利用这个规律我们建一个字符到数值的映射表然后从左到右扫一遍就行int romanToInt(char s[]) { int map[256] {0}; map[I] 1; map[V] 5; map[X] 10; map[L] 50; map[C] 100; map[D] 500; map[M] 1000; int result 0; int len 0; while (s[len] ! \0) len; for (int i 0; i len; i) { int current map[(unsigned char)s[i]]; int next (i 1 len) ? map[(unsigned char)s[i 1]] : 0; if (current next) { result - current; } else { result current; } } return result; }关键点把一堆特例压缩成了一个统一的判断条件代码简洁了很多。时间复杂度O(n)空间复杂度O(1)已经是这道题的最优解。题三最长公共前缀题目给一个字符串数组找出所有字符串的最长公共前缀。我最先想到的写法我当时的做法是先求第 0 个和第 1 个字符串的公共前缀再用这个结果和第 2 个字符串求公共前缀依此类推。// 辅助函数求两个字符串的公共前缀长度 int commonPrefix(char a[], char b[]) { int i 0; while (a[i] ! \0 b[i] ! \0 a[i] b[i]) { i; } return i; } char* longestCommonPrefix(char** strs, int strsSize) { if (strsSize 0) return ; int minLen commonPrefix(strs[0], strs[1]); for (int i 2; i strsSize; i) { int len commonPrefix(strs[0], strs[i]); if (len minLen) minLen len; } strs[0][minLen] \0; return strs[0]; }这个思路没问题但写起来比较繁琐需要额外的辅助函数而且每次两两比较时前面的字符会被反复扫描。更好的思路纵向扫描换个角度看问题公共前缀其实就是所有字符串在相同位置上的字符都一样。那我们可以一列一列地检查而不是一个字符串一个字符串地比较。char* longestCommonPrefix(char** strs, int strsSize) { if (strsSize 0) return ; int col 0; // 当前检查第几列 while (1) { char c strs[0][col]; // 拿第一个字符串的第 col 个字符当基准 if (c \0) break; // 第一个字符串到头了 int match 1; for (int row 1; row strsSize; row) { if (strs[row][col] ! c) { match 0; break; } } if (!match) break; // 这一列有不匹配的前缀到此为止 col; } strs[0][col] \0; // 截断剩下的就是最长公共前缀 return strs[0]; }关键点把字符串之间的比较转化成了矩阵按列的检查。一旦发现某一列不匹配立刻停止不需要再往后看。代码更紧凑而且避免了重复比较。