搜索到
88
篇与
的结果
-
-
力扣455分发饼干 这个题目属于很典型的贪心算法，贪心算法的具体可以见我下一篇博文，我将会有很详细的解释，我接下来先当着这道题目进行一个简单的解释假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。示例 1:输入: g = [1,2,3], s = [1,1]输出: 1解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。示例 2:输入: g = [1,2], s = [1,2,3]输出: 2解释: 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2。很简单的思想，我们如何先对g和s进行排序的话，那么我们就按照g的1 2 3 s的1 1 那么我们可以很轻松的推出来，g的第一个和s的第一个开始进行匹配需要注意的是 我们需要注意qsort的函数的使用方法void qsort(void base, size_t nitems, size_t size, int (compar)(const void , const void ));以上是qsort函数的内部参数，base：指向要排序的数组的起始地址的指针，它可以是任何类型的数组，因为它被声明为 void * 类型，这是一个通用指针类型，可以指向任意类型的数据。nitems：要排序的数组中的元素个数。size：数组中每个元素的大小，以字节为单位。这个参数很重要，因为 qsort 需要知道每个元素的实际大小，以便正确地对数组进行操作。compar：一个指向比较函数的指针，这个比较函数用于确定数组中元素的排序顺序。比较函数需要接受两个 const void * 类型的参数，并返回一个整数，用于表示两个元素的相对大小关系。第三个参数需要注意一下就是需要指明是如传入的比如接下来的写法就是从大到小的排序 int cmp(const voida,const voidb){return (int)b - (int)a}因为他返回的是一个负值那么默认会把b排到a前面，接下来就是上真正的代码了int cmp(const void*a,const void*b) { return *(int*)a - *(int*)b; } int findContentChildren(int* g, int gSize, int* s, int sSize) { qsort(g,gSize,sizeof(int),cmp); qsort(s,sSize,sizeof(int),cmp); int i = 0; int j = 0; for(j;j<sSize;j++){ if(i<gSize && g[i] <= s[j]){ i++; } } return i; }
-
力扣日常更新字符串中的第一个唯一的字符 这个题目还是日常的哈希算法，难度很低。还是分享一下把先上题目给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。示例 1：输入: s = "leetcode"输出: 0示例 2:输入: s = "loveleetcode"输出: 2示例 3:输入: s = "aabb"输出: -1还是老思路，把里面的数字排序放到一个新数组里面，然后进行循环遍历，如果等于1的话 就直接拿出来。思路有了。DEV启动！int firstUniqChar(char* s) { int c[128] = {0}; int i = 0; for(i;i<strlen(s);i++){ c[s[i]]++; } for(i = 0;i<strlen(s);i++){ if(c[s[i]] == 1){ return i; } } return -1; }
-
力扣409最长回文串 最长回文串一眼哈希算法，给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。示例 1:输入:s = "abccccdd"输出:7解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。示例 2:输入:s = "a"输出:1解释：可以构造的最长回文串是"a"，它的长度是 1。直接上代码int longestPalindrome(char* s) { int c[128] = {0},ret = 0; int i = 0; for(i = 0;i<strlen(s);i++){ c[s[i]]++; } for(i = 0;i<128;i++){ ret+=c[i] - c[i]%2; } return ret+(ret!=strlen(s)); }原理很简单，就是数学题目
-
力扣290单词规律 直接上题目给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。示例1:输入: pattern = "abba", s = "dog cat cat dog"输出: true示例 2:输入:pattern = "abba", s = "dog cat cat fish"输出: false示例 3:输入: pattern = "aaaa", s = "dog cat cat dog"输出: false很简单，和上一道题类似，但是上一个一维数组解决 但是这个得二维数组我先直接上代码bool wordPattern(char * pattern, char * s){ char a[301][3001]; char *p=strtok(s," "); int pos=0,len=strlen(pattern); while(p!=NULL) { sprintf(a[pos++],"%s",p); p=strtok(NULL," "); } if(len!=pos) return false; for(int i = 0 ; i < len; i++) for(int j = i + 1; j < len; j++) { int re = strcmp(a[i],a[j]); if((pattern[i] == pattern[j] && re != 0) || (pattern[i] != pattern[j] && re == 0) ) return false; } return true; } 道理和昨天的是一样的。当然也可以用哈希算法，我没有去写，但是思路还是很好理解的，我先贴上大佬的代码，后期去研究研究怎么写的struct Hash_Table{ int key;//键 char val[30];//把s中单个的字符串例如dog拷贝到这个哈希表中，这个30和提供的测试数据有关，测试过，数据中s中单个字符串不大于30 UT_hash_handle hh; }; bool wordPattern(char * pattern, char * s){ char** array = malloc(sizeof(char*)*300);//定义一个二维数组（二级指针），其数组是一级指针，也就是一维数组，指向s中单独的字符串，例如dog，1 <= pattern.length <= 300，所以为包含300个一级指针类型的二级指针开辟内存，当然也有可能s中字符串的个数大于pattern.length，还是跟提供测试数据有关，300通过的了测试 int count = 0;//记录s包含的以空格分隔的字符串的个数，例如dog cat则cout=2 array[count] = strtok(s," ");//字符串分隔函数的用法就是如此 for(count = 0; array[count]!=NULL;){//字符串分隔函数的用法就是如此 array[++count] = strtok(NULL," ");//字符串分隔函数的用法就是如此 }//自此，array内包含cout个字符串，指向每个字符串的指针对应于array[i] if(count != strlen(pattern)){//判断pattern字符个数和s中以空格分隔的字符串个数是否相等 return false;//例如pattern = "ab", s = "dog cat cat", 2!=3，直接返回false } struct Hash_Table* table1 = NULL;//记录pattern到s的映射 struct Hash_Table* table2 = NULL;//记录s到pattern的映射 struct Hash_Table* temp = NULL;//用于存储数据加入哈希表 int patternnumber[300] = {0};//把pattern中的单个字符转换为int型，好处理 for(int i=0; i<strlen(pattern); i++){ patternnumber[i] = pattern[i]-'a';//把pattern中的单个字符转换为int型，好处理 HASH_FIND_INT(table1,&(patternnumber[i]),temp);//查找patternnumber[i])是否在哈希表table1出现，返回结果在temp中 if(temp == NULL){//如果不存在 temp = malloc(sizeof(struct Hash_Table));//为temp开辟内存 temp->key = patternnumber[i];//将数据存储到temp结构体中，patternnumber[i]为键 strcpy(temp->val,array[i]);//将s中的以空格分隔的字符串拷贝到结构体val中，作为值 HASH_ADD_INT(table1,key,temp);//key为键，也就是通过哈希函数把key转换为地址，将结构体存到该地址。完成添加add，前面key赋值的是patternnumber[i]，所以patternnumber[i]是用来查找的键，可以得到的是值val，即array[i] } else if(strcmp(temp->val,array[i])!=0) return false;//当查到不是第一次出现的元素，比较之前映射的array[i]和现在的array[i]，不一样直接false } for(int i=0; i<count; i++){//与哈希表1类似，只不过存储s到pattern的映射关系 HASH_FIND_STR(table2,array[i],temp); if(temp == NULL){ temp = malloc(sizeof(struct Hash_Table)); temp->key = patternnumber[i]; strcpy(temp->val,array[i]); HASH_ADD_STR(table2,val,temp);//注意这里的第二个参数键的名字是val，在哈希表table2中，我们是通过键(key)s的字符也就是array[i]中指向的字符，来得到val即pattenumber，所以下面if中要判断，当不是第一次出现的字符时，对应的之前的映射pattenumber和现在的pattenumber是否一样，不一样直接false } else if(temp->key!=patternnumber[i]) return false; } return true;//前面所有false情况排除，那就符合题意，返回true }这里需要注意的一点知识点就是，一个是用到了二维数组，还有一个就是用到了切割字符串的办法，strtok() 此时要传入要切割的函数以及哪个位置要进行切割，这点需要牢记。最后就是写逻辑判断的时候思路要清晰的哦
