网站模版安装教程,深圳建设网站哪家好,建筑工程集团有限公司,广州建站Leetcode Test
447 回旋镖的数量(1.8)
给定平面上 n 对 互不相同 的点 points #xff0c;其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 #xff0c;其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等#xff08;需要考虑元组的顺序#xff09;。 …Leetcode Test
447 回旋镖的数量(1.8)
给定平面上 n 对 互不相同 的点 points 其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等需要考虑元组的顺序。
返回平面上所有回旋镖的数量。
提示
n points.length1 n 500points[i].length 2-104 xi, yi 104所有点都 互不相同
【枚举法】
class Solution {
public:int numberOfBoomerangs(vectorvectorint points) {int ans 0;unordered_mapint, int cnt;for (auto p1 : points) {cnt.clear();for (auto p2 : points) {int d2 (p1[0] - p2[0]) * (p1[0] - p2[0]) (p1[1] - p2[1]) * (p1[1] - p2[1]);ans cnt[d2] * 2;}}return ans;}
};2707 字符串中的额外字符(1.9)
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s 使剩下的字符 最少 。
提示
1 s.length 501 dictionary.length 501 dictionary[i].length 50dictionary[i] 和 s 只包含小写英文字母。dictionary 中的单词互不相同。
【动态规划】
class Solution {
public:int minExtraChar(string s, vectorstring dictionary) {int n s.size();vectorint d(n 1, INT_MAX);unordered_mapstring, int mp;for (auto s : dictionary) {mp[s];}d[0] 0;for (int i 1; i n; i) {d[i] d[i - 1] 1;for (int j i - 1; j 0; j--) {if (mp.count(s.substr(j, i - j))) {d[i] min(d[i], d[j]);}}}return d[n];}
};2696 删除字串后的字符串最小长度(1.10)
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作在每一步操作中你可以从 s 中删除 任一个 AB 或 CD 子字符串。
通过执行操作删除所有 AB 和 CD 子串返回可获得的最终字符串的 最小 可能长度。
注意删除子串后重新连接出的字符串可能会产生新的 AB 或 CD 子串。
提示
1 s.length 100s 仅由大写英文字母组成
【栈】
int minLength(char *s){int n strlen(s), m 0;char *stack (char *)malloc(sizeof(char) * n);for (int i 0; i n; i) {stack[m] s[i];if (m 2 (stack[m - 2] A stack[m - 1] B ||stack[m - 2] C stack[m - 1] D)) {m - 2;}}free(stack);return m;
}2645 构造有效数字串的最少插入数(1.11)
给你一个字符串 word 你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 “abc” 串联多次得到则认为该字符串 有效 。
提示
1 word.length 50word 仅由字母 “a”、“b” 和 “c” 组成。
【计算组数】如果有一次下降例如ba则代表b和a肯定不是一个组里面的需要插入字母变成2个组
int addMinimum(char * word){int nstrlen(word);int cnt1;for(int i1;in;i){if(word[i]word[i-1]){cnt;}}return cnt*3-n;
}【动态规划】 d p [ 0 ] 0 dp[0]0 dp[0]0 d [ i ] d [ i − 1 ] 2 w o r d [ i ] 单独存在于一组 a b c 中 d[i]d[i-1]2word[i]单独存在于一组abc中 d[i]d[i−1]2word[i]单独存在于一组abc中 d [ i ] d [ i − 1 ] − 1 w o r d [ i ] 可以和 w o r d [ i − 1 ] 在同一组 a b c 中 d[i]d[i-1]-1word[i]可以和word[i-1]在同一组abc中 d[i]d[i−1]−1word[i]可以和word[i−1]在同一组abc中
int addMinimum(char * word) {int n strlen(word);int d[n 1];memset(d, 0, sizeof(d));for (int i 1; i n; i) {d[i] d[i - 1] 2;if (i 1 word[i - 1] word[i - 2]) {d[i] d[i - 1] - 1;}}return d[n];
}2085 统计出现过一次的公共字符串(1.12)
给你两个字符串数组 words1 和 words2 请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。
提示
1 words1.length, words2.length 10001 words1[i].length, words2[j].length 30words1[i] 和 words2[j] 都只包含小写英文字母。
【hash】
class Solution {
public:int countWords(vectorstring words1, vectorstring words2) {unordered_mapstring,intf1,f2;for(auto w:words1){f1[w];}for(auto w:words2){f2[w];}int cnt0;for(auto [w,num]:f1){if(num1 f2[w]1){cnt;}}return cnt;}
};2182 构造限制重复的字符串(1.13)
给你一个字符串 s 和一个整数 repeatLimit 用 s 中的字符构造一个新字符串 repeatLimitedString 使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同那么较长的字符串字典序更大。
提示
1 repeatLimit s.length 105s 由小写英文字母组成
【贪心 双指针 hash计数】
char* repeatLimitedString(char* s, int repeatLimit) {int *cnt(int*)malloc(sizeof(int)*26);for(int i0;i26;i){cnt[i]0;}int nstrlen(s);for(int i0;in;i){cnt[s[i]-a];}char *ret(char*)malloc(sizeof(char)*(n1));char *pret;memset(ret,0,sizeof(char)*(n1));int m0;for(int i25,j24; i0 j0; ){//当前字符用完if(cnt[i]0){m0;i--;}//当前字符未超过limitelse if(m repeatLimit){cnt[i]--;*(p)ai;m;}//当前字符超过限制查找其他可填入字符else if(ji || cnt[j]0){j--;}//当前字符超过limit填入其他字符else{cnt[j]--;*(p)aj;m0;}}return ret;
}83 删除排序链表中的重复元素(1.14)
给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。
提示
链表中节点数目在范围 [0, 300] 内-100 Node.val 100题目数据保证链表已经按升序 排列
【模拟】
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* deleteDuplicates(struct ListNode* head) {if(head NULL) return head;struct ListNode* thead;while(t-next ! NULL){if(t-next-val t-val){t-nextt-next-next;}else{tt-next;}}return head;
}
