【每日刷题】Day60
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 1122. 数组的相对排序 - 力扣（LeetCode）
2. 419. 甲板上的战舰 - 力扣（LeetCode）
3. 513. 找树左下角的值 - 力扣（LeetCode）
1. 1122. 数组的相对排序 - 力扣（LeetCode）
//思路：哈希+记数。
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
int* ans = (int*)malloc(sizeof(int)*1001);
int count = 0;
int hash[1001] = {0};
int max = arr1[0];
for(int i = 0;i<arr1Size;i++)
{
hash[arr1[i]]+=1;
if(arr1[i]>max)
max = arr1[i];
}
for(int i = 0;i<arr2Size;i++)
{
while(hash[arr2[i]]--)
{
ans[count++] = arr2[i];
}
}
for(int i = 0;i<=max;i++)
{
while(hash[i]>0)
{
hash[i]--;
ans[count++] = i;
}
}
*returnSize = count;
return ans;
}
2. 419. 甲板上的战舰 - 力扣（LeetCode）
//思路：遍历判断。本题来源于游戏《海战棋》(海战棋 （网络游戏） (battleship-game.org))
//每个相邻的X组成战舰，战舰只能横着或者竖着，比如：
//如上图，下图则是错误的形式。
//知道了规则后我们着手实现代码。
//首先，判断战舰的数量肯定是判断‘X’的数量，但是不是每个X都有效，如下图
//那么如何判断是否为无效‘X’呢，很简单，只需要判断当前位置上一个是否为‘X’即可，如果当前位置上一个为‘X’，则需要将当前位置及当前位置后面的以及下面的相邻的为‘X’的位置改为‘.’。
int countBattleships(char** board, int boardSize, int* boardColSize)
{
int ans = 0;
for(int i = 0;i<boardSize;i++)
{
for(int j = 0;j<*boardColSize;j++)
{
if(board[i][j]=='X')//判断当前位置是否为‘X’
{
ans++;//为X记为一艘战舰，当前位置记为战舰头
int x = j+1;//将与战舰头相连的战舰身以及无法组成战舰的无效‘X’改为‘.’
while(x<*boardColSize&&board[i][x]=='X')
{
board[i][x] = 'x';
x++;
}
int y = i+1;
while(y<boardSize&&board[y][j]=='X')
{
board[y][j] = '.';
y++;
}
}
}
}
return ans;
}
3. 513. 找树左下角的值 - 力扣（LeetCode）
//思路：深度优先遍历。算出二叉树的最大深度(用于判断是否遍历到了最第层)，深度优先遍历二叉树，遍历到叶子结点时，判断是否是最底层，不是则继续遍历二叉树。
//判断是否为叶子结点
bool IsLeafNode(struct TreeNode* root)
{
return !root->left&&!root->right;
}
//求二叉树最大深度
int BinaryTreeHigh(struct TreeNode* root)
{
if(!root)
return 0;
int HighLeft = BinaryTreeHigh(root->left);
int HighRight = BinaryTreeHigh(root->right);
return 1+(HighLeft>HighRight?HighLeft:HighRight);
}
double FindVal(struct TreeNode* root,int high)
{
if(!root||(IsLeafNode(root)&&high!=1))
return INT_MAX+10;//不满足则返回一个＞INT_MAX的值
if(IsLeafNode(root)&&high==1)
return root->val;//满足则返回结点值
double left = FindVal(root->left,high-1);
if(left!=(INT_MAX+10))//如果已经找到了则不用继续遍历
return left;
return FindVal(root->right,high-1);//否则继续遍历
}
int findBottomLeftValue(struct TreeNode* root)
{
int high = BinaryTreeHigh(root);
return (int)FindVal(root,high);
}
