力扣(LeetCode)刷题，简单题(第18期)
【摘要】 目录
第1题：好数对的数目
第2题：返回倒数第k个节点
第3题：将每个元素替换为右侧最大元素
第4题：删除最外层的括号
第5题：6和9组成的最大数
第6题：搜索插入位置
第7题：判定字符是否唯一
第8题：唯一摩尔斯密码词
第9题：统计有序矩阵中的负数
第10题：二叉搜索树的第k大节点
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看...
目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：好数对的数目
试题要求如下：
回答（C语言）：
-
int numIdenticalPairs(int* nums, int numsSize){
-
int hash[101];
-
int res = 0;
-
memset(hash, 0, 101 * sizeof(int));
-
-
for(int i = 0; i < numsSize; ++i) {
-
hash[nums[i]] += 1;
-
}
-
-
for(int i = 0; i < 101; ++i) {
-
if(hash[i] >= 2) {
-
res += hash[i] * (hash[i]-1) / 2;
-
}
-
}
-
return res;
-
}
运行效率如下所示：
第2题：返回倒数第k个节点
试题要求如下：
解答思路：
1、先让t向前走K步；
2、head和t同步前进，t到结尾，head到目标。
回答（C语言）：
-
/**
-
* Definition for singly-linked list.
-
* struct ListNode {
-
* int val;
-
* struct ListNode *next;
-
* };
-
*/
-
-
int kthToLast(struct ListNode* head, int k){
-
struct ListNode*t = head;
-
-
while (k--){
-
t = t->next;
-
}
-
-
while (t){
-
t = t->next;
-
head = head->next;
-
}
-
-
return head->val;
-
}
运行效率如下所示：
第3题：将每个元素替换为右侧最大元素
试题要求如下：
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
int* replaceElements(int* arr, int arrSize, int* returnSize){
-
int temp_max = 0,temp_num = 0;
-
-
temp_max = arr[arrSize-1];
-
-
for(int i = arrSize-2; i >= 0; i--){
-
temp_num = arr[i];
-
arr[i] = temp_max;
-
-
if(temp_max < temp_num){
-
temp_max = temp_num;
-
}
-
}
-
-
arr[arrSize-1] = -1;
-
-
*returnSize = arrSize;
-
return arr;
-
}
运行效率如下所示：
第4题：删除最外层的括号
试题要求如下：
回答（C语言）：
-
char * removeOuterParentheses(char * S){
-
int cnt = 0,k = 0;
-
-
for(int i = 0;i < strlen(S);i++){
-
if(S[i] == '('){
-
if(cnt != 0) S[k++] = S[i];
-
cnt ++;
-
}
-
if(S[i] == ')'){
-
cnt--;
-
if(cnt != 0) S[k++] = S[i];
-
}
-
}
-
-
S[k] = '\0';
-
return S;
-
}
运行效率如下所示：
第5题：6和9组成的最大数
试题要求如下：
解答思路：
现在把 9 翻转成 6 是不合理的，因为它会使得数字变小。因此我们应当找到 num 中最高位的 6，将其翻转成 9。
回答（C语言）：
-
#include <Math.h>
-
-
int maximum69Number (int num){
-
int count = 0, th = 0; // count 记录除了多少次，th记录最大的6在第几位
-
int re = num;
-
-
while(re){
-
count++;
-
-
if(re%10==6)
-
th = count;
-
-
re /= 10;
-
}
-
-
return num+3*pow(10,th-1);
-
}
运行效率如下所示：
第6题：搜索插入位置
试题要求如下：
回答（C语言）：
-
int searchInsert(int* nums, int numsSize, int target){
-
int low = 0;
-
int high = numsSize - 1;
-
int mid = 0;
-
-
while (low <= high){
-
mid = low + (high - low) / 2;
-
-
if (target > nums[mid]){
-
low = mid + 1;
-
}
-
else if (target < nums[mid]){
-
high = mid - 1;
-
}
-
else if (target == nums[mid]){
-
return mid;
-
}
-
}
-
-
return low;
-
}
运行效率如下所示：
第7题：判定字符是否唯一
试题要求如下：
回答（C语言）：
-
bool isUnique(char* astr){
-
int len = strlen(astr);
-
char* temp_data = (char*)malloc(sizeof(char)*(26));
-
memset(temp_data,0,26);
-
-
for(int i = 0,cou = 0; i < len; i++){
-
cou = astr[i]-'a';
-
-
if(temp_data[cou] == 0){
-
temp_data[cou] = astr[i];
-
}
-
else{
-
return false;
-
}
-
}
-
-
return true;
-
}
运行效率如下所示：
第8题：唯一摩尔斯密码词
试题要求如下：
解答思路：
建立字符串数组morse，存放words中的字符串转成莫尔斯密码后的字符串，每次处理words中的字符串，如果不重复，就添加到morse里面，最终输出morse中字符串的个数。
回答（C语言）：
-
int uniqueMorseRepresentations(char ** words, int wordsSize){
-
char dict[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
-
//5*12 = 60
-
-
char morse[100][60] = {0};
-
int count = 0;
-
-
for (int i = 0; i < wordsSize; i++) {
-
char tmp[60] = { 0 };
-
int flag = 0;
-
-
//每个字符串对应的摩斯码放入tmp中
-
for (int j = 0; j < strlen(words[i]); j++) {
-
strcat(tmp, dict[words[i][j] - 'a']);
-
}
-
-
//定义flag分辨相同和不同，如果tmp和morse中的不同 就放入morse中
-
for (int k = 0; k < count; k++) {
-
if (strcmp(morse[k], tmp) == 0) {
-
flag = 1;
-
break;
-
}
-
}
-
//不同的话就放入morse中
-
if (flag == 0) {
-
strcpy(morse[count], tmp);
-
count++;
-
}
-
}
-
return count;
-
}
运行效率如下所示：
第9题：统计有序矩阵中的负数
试题要求如下：
解答思路：
从最后一行最后一列扫描，若此行最后一个元素 >0 则直接返回，若此列某个元素 >0 则跳出内循环，检查上一行。
回答（C语言）：
-
int countNegatives( int ** grid , int gridSize , int * gridColSize)
-
{
-
int count = 0;
-
-
for( int i = gridSize - 1 ; i >= 0 ; i-- )
-
{
-
int j = *( gridColSize + i ) - 1;
-
-
if( *( *( grid + i ) + j ) >= 0 )
-
{
-
return count;
-
}
-
-
for( ; j >= 0 ;j-- )
-
{
-
if( *( *( grid + i ) + j ) >= 0 )
-
{
-
break;
-
}
-
count++;
-
}
-
}
-
-
return count;
-
}
运行效率如下所示：
第10题：二叉搜索树的第k大节点
试题要求如下：
解答思路：
本文解法基于此性质：二叉搜索树的中序遍历为 递增序列 。
根据以上性质，易得二叉搜索树的 中序遍历倒序 为 递减序列 。因此，求 “二叉搜索树第 kk 大的节点” 可转化为求 “此树的中序遍历倒序的第 kk 个节点”。
回答（C语言）：
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
-
void inOrderReverse(struct TreeNode *root, int k, int *cnt, int *ret) {
-
if (NULL == root || *cnt >= k)
-
return;
-
inOrderReverse(root->right, k, cnt, ret);
-
(*cnt)++;
-
if (*cnt == k)
-
*ret = root->val;
-
inOrderReverse(root->left, k, cnt, ret);
-
}
-
-
int kthLargest(struct TreeNode *root, int k) {
-
int ret;
-
int cnt;
-
inOrderReverse(root, k, &cnt, &ret);
-
-
return ret;
-
}
运行效率如下所示：
文章来源: blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/m0_38106923/article/details/107309976
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）