练习题（2024/4/3）

 1题目描述：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

实现途径：

思路1：简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。

// 定义一个函数来找到两个有序数组的中位数

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {

    // 创建一个新数组，用于存放合并后的有序数组

    int arr[nums1Size + nums2Size];

    int i = 0, j = 0, k = 0; // i 和 j 分别为 nums1 和 nums2 的索引，k 为 arr 的索引

    // 遍历 nums1 和 nums2 直到其中一个数组被完全遍历

    while (i < nums1Size && j < nums2Size) {

        // 比较当前两个数组元素的大小，将较小的元素放入 merged 中，并移动相应的索引

        if (nums1[i] < nums2[j]) {

            arr[k++] = nums1[i++];

        } else {

            arr[k++] = nums2[j++];

        }

    }

    // 如果 nums1 还有剩余元素，将其全部复制到 merged 中

    while (i < nums1Size) {

        arr[k++] = nums1[i++];

    }

    // 如果 nums2 还有剩余元素，将其全部复制到 merged 中

    while (j < nums2Size) {

        arr[k++] = nums2[j++];

    }

// 计算合并后数组的长度

    int length = nums1Size + nums2Size;

    // 根据合并后的数组长度是奇数还是偶数来计算中位数

    if (length % 2 == 0) {

        // 如果是偶数，中位数为中间两个数的平均值

        return (double)(arr[length / 2 - 1] + arr[length / 2]) / 2.0;

    } else {

        // 如果是奇数，中位数为中间的数

        return (double)arr[length / 2];

    }

}

 思路二：

中位数相关的二分查找算法如下：

1. 对于两个有序数组，我们可以分别在它们的所有可能的分割位置上进行二分查找，直到找到合适的位置。
2. 设定左边的分割线为第k个元素，那么右边的分割线为第(m+n+1)/2 - k个元素，保证左边的元素个数不少于右边的。
3. 然后对k进行二分查找，直到找到合适的位置

代码：

// 函数：在两个已排序数组中找到第k小的元素

// 参数：nums1和nums2是两个已排序数组，len1和len2分别是它们的大小，k是要找的第k小的元素的位置

// 返回值：第k小的元素的值

int find_k_th_nums(int* nums1, int len1, int* nums2, int len2, int k) {

    int low1 = 0; // nums1的起始索引

    int low2 = 0; // nums2的起始索引

    // 循环直到找到第k小的元素或者其中一个数组被遍历完

    while (k > 1 && low1 < len1 && low2 < len2) {

        int x1 = low1 + k / 2 - 1; // nums1的中间索引

        int x2 = low2 + k / 2 - 1; // nums2的中间索引

        int reduce_len; // 需要减去的长度

        // 处理其中一个数组已经被遍历完的情况

        if (x1 >= len1 && x2 < len2) {

            reduce_len = len1 - low1;

        } else if (x1 < len1 && x2 >= len2) {

            reduce_len = len2 - low2;

        } else {

            // 计算需要减去的长度，选取较小的长度

            if (len1 - low1 > len2 - low2) {

                reduce_len = len2 - low2;

            } else {

                reduce_len = len1 - low1;

            }

        }

        // 更新减去的长度

        int x3 = k / 2;

        if (x3 < reduce_len) {

            reduce_len = x3;

        }

        // 更新k值和数组起始索引

        k = k - reduce_len;

        if (nums1[low1 + reduce_len - 1] > nums2[low2 + reduce_len - 1]) {

            low2 += reduce_len;

        } else {

            low1 += reduce_len;

        }

    }

    // 返回第k小的元素

    if (k == 1) {

        if (low1 < len1 && low2 < len2) {

            return nums1[low1] < nums2[low2] ? nums1[low1] : nums2[low2];

        } else if (low1 >= len1) {

            return nums2[low2];

        } else {

            return nums1[low1];

        }

    } else if (low1 >= len1) {

        return nums2[low2 + k - 1];

    } else {

        return nums1[low1 + k - 1];

    }

}

// 函数：在两个已排序数组中找到中位数

// 参数：nums1和nums2是两个已排序数组，nums1Size和nums2Size分别是它们的大小

// 返回值：中位数的值

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {

    int len = nums1Size + nums2Size; // 总长度

    // 如果总长度为偶数

    if (len % 2 == 0) {

        int x1 = find_k_th_nums(nums1, nums1Size, nums2, nums2Size, len / 2); // 找到第 len/2 个元素

        int x2 = find_k_th_nums(nums1, nums1Size, nums2, nums2Size, len / 2 + 1); // 找到第 len/2 + 1 个元素

        return (double)(x1 + x2) / 2; // 返回中位数

    } else {

        int ret = find_k_th_nums(nums1, nums1Size, nums2, nums2Size, len / 2 + 1); // 找到第 len/2 + 1 个元素

        return ret; // 返回中位数

    }

}

2题目描述 

给你一个字符串 s，找到 s 中最长的回文

子串

。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

思路1如下：

思路是通过中心扩展法来找到字符串中的最长回文子串。其主要步骤如下：

1. 定义了两个函数：expandAroundCenter 和 longestPalindrome。

   • expandAroundCenter 函数用于判断以给定的中心位置为中心的回文子串的长度。
   • longestPalindrome 函数用于找到整个字符串中的最长回文子串。

2. 在 longestPalindrome 函数中，遍历字符串中的每个字符，以当前字符为中心，分别向左右两边扩展，同时判断扩展的回文子串的长度。

3. 在扩展过程中，利用 expandAroundCenter 函数计算以当前字符为中心的奇数长度和偶数长度的回文子串的长度，并记录最长的回文子串的起始和结束位置。

4. 不断更新最长回文子串的起始和结束位置，直到遍历完整个字符串。

5. 最后，根据记录的最长回文子串的起始和结束位置，截取出最长回文子串，并返回。

整体思路是从每个字符开始，以其为中心向两边扩展，寻找回文子串，并记录最长的回文子串。通过这种方法，可以在遍历一次字符串后找到最长的回文子串。

代码如下：

// 判断字符串 s 中以 left 和 right 为中心的回文子串的长度

int expandAroundCenter(char *s, int left, int right) {

    int len = strlen(s);

    while (left >= 0 && right < len && s[left] == s[right]) {

        left--; // 向左移动左边界

        right++; // 向右移动右边界

    }

    return right - left - 1; // 返回回文子串的长度

}

// 找到字符串 s 中最长的回文子串

char *longestPalindrome(char *s) {

    if (s == NULL || strlen(s) < 1) return ""; // 空串或长度小于1的情况直接返回空字符串

    int start = 0, end = 0; // 记录最长回文子串的起始和结束位置

    for (int i = 0; i < strlen(s); i++) {

        int len1 = expandAroundCenter(s, i, i); // 以 s[i] 为中心的奇数长度的回文子串长度

        int len2 = expandAroundCenter(s, i, i + 1); // 以 s[i] 和 s[i+1] 为中心的偶数长度的回文子串长度

        int len = len1 > len2 ? len1 : len2; // 取较长的回文子串长度

        if (len > end - start) { // 如果当前回文子串长度比之前记录的最长回文子串长度长

            start = i - (len - 1) / 2; // 更新最长回文子串的起始位置

            end = i + len / 2; // 更新最长回文子串的结束位置

        }

    }

    // 截取最长回文子串

    char *result = (char *)malloc((end - start + 2) * sizeof(char)); // 分配内存

    strncpy(result, s + start, end - start + 1); // 复制最长回文子串

    result[end - start + 1] = '\0'; // 添加字符串结束符

    return result; // 返回最长回文子串

}

方法2:动态规划     

回文天然具有「状态转移」性质：一个长度严格大于 222 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。

动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

2 确定递推公式

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

3

dp数组如何初始化

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

4

确定遍历顺序

从递归公式中，可以看出，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，如图

所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。

j的话，可以正常从左向右遍历。

代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        // 初始化一个二维向量来存储最长回文子序列的长度
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        
        // 基本情况：单个字符是长度为1的回文
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        
        // 填充二维表格，计算不同长度的子串的最长回文子序列长度
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    // 如果两端字符相等，长度加2
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    // 如果字符不相等，取不包括两端的最大值
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 返回整个字符串的最长回文子序列长度
        return dp[0][s.size() - 1];
    }
};

3题目描述

鸡和兔关在一个笼子里，鸡有2只脚，兔有4只脚。输入笼子里头的总数m和脚的总数n，求鸡和兔子各有多少只？若问题无解，也要输出相应的信息。

输入
输入两个整数m和n，分别代表笼子里头的个数和脚的个数。

输出
若问题有解，依次输出鸡和兔的只数。若问题无解，则输出"No Answer"。

思路：，脚都是偶数，n为奇数必然无解。二是，脚太少了，引入负数的鸡和兔子。显然依旧无解。 设鸡和兔各有x,y 只  联立方程组  x+y=m  2x+4y=n;可以得出x,y的表达式

#include<stdio.h>
int main()
{
    int m,n,x,y;//定义整型m,n,x,y
    int flag=0;//设置标志flag，确定有解与否 
    scanf("%d %d",&m,&n);//键盘输入头的数量m，脚的数量n的值
    x=2*m-n/2; //鸡的个数x
    y=n/2-m;//兔子的个数y 
    //如果脚的数量不是2的倍数，兔子和鸡的数量小于0均视为无解 
    if(n%2!=0||x<0||y<0) 
        flag=1;
    if(flag)//如果满足无解 
        printf("No Answer"); 
    else//有答案 
        printf("%d %d",x,y);//输出鸡的个数x和兔子的个数y
    return 0;//正常结束
}

   

4 题目描述

百钱买百鸡问题：公鸡五文钱一只，母鸡三文钱一只，小鸡三只一文钱，用100文钱买100只鸡，公鸡、母鸡、小鸡各买多少只？
本程序要求解的问题是：给定一个正整数n，用n文钱买n只鸡，问公鸡、母鸡、小鸡各买多少只？

输入
输入一个正整数n(n<=100)。

输出
如果有解，种组合占一行，包含公鸡、母鸡、小鸡的个数，用正整数表示，每个数据占4列。公鸡母鸡小鸡个数均大于等于0，按公鸡数目从小到大输出，公鸡数目相同按母鸡数目从小到大输出，以此类推。如果无解，输出“No Answer”。
 

思路：典型的循环题目。注意标志的设立，还有就是第三种鸡的处理，不用再重新再开设循环，那样循环次数太多，费时费力，第三种鸡就等于n减去前两种鸡的数量，这样就不用循环多余的次数了

 

代码1： 

#include<stdio.h>
int main()
{
    int i,j,k,n,answer=0;//定义公鸡数i，母鸡数j以及小鸡数k
    //还有n元也即是鸡数n，以及设立标志answe并初始化
    scanf("%d",&n);//键盘输入一个正整数n,用n文钱买n只鸡
    for(i=0;i<=n/5;i++)
    {
    for(j=0;j<=n/3;j++)
    {
        k=n-i-j;//第三种鸡的数量k等于总鸡数量n与其他两种鸡数量之差
        if(i*15+j*9+k==n*3)//这里通分一下，将表达式直接整式运算
        {
        answer=1;//找到答案，把标志更改
        printf("%4d%4d%4d\n",i,j,k);//按照格式要求输出
        }    
    }
    } 
     if(!answer)//如果标志还是没有更改，依旧是0
     {
         printf("No Answer");//说明没办法实现百钱买百鸡，输出无解
     }
    return 0;//
}

                       

 代码2：

#include <stdio.h>

void buyChickens(int n) {
    int cock, hen, chicken;
    // 公鸡的数量范围为0到n/5，每只公鸡5文钱
    for (cock = 0; cock <= n / 5; cock++) {
        // 母鸡的数量范围为0到n/3，每只母鸡3文钱
        for (hen = 0; hen <= n / 3; hen++) {
            // 小鸡的数量为总数减去公鸡和母鸡的数量
            chicken = n - cock - hen;
            // 检查是否满足买鸡的总数及钱数的要求
            if (chicken >= 0 && (5 * cock + 3 * hen + chicken / 3) == n && (chicken % 3 == 0)) {
                // 输出结果
                printf("公鸡数量：%d，母鸡数量：%d，小鸡数量：%d\n", cock, hen, chicken);
            }
        }
    }
}

int main() {
    int n;
    printf("请输入用n文钱买n只鸡（n为正整数）：\n");
    scanf("%d", &n);
    buyChickens(n);
    return 0;
}

 5  题目描述：

表：Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+
在 SQL 中，id 是该表的主键。
id 是一个自增列。

找出所有至少连续出现三次的数字。

返回的结果表中的数据可以按 任意顺序 排列。

结果格式如下面的例子所示：

示例 1:

输入：
Logs 表：
+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+
输出：
Result 表：
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+
解释：1 是唯一连续出现至少三次的数字。

代码如下：

//"SELECT DISTINCT"语句用于选择唯一的结果，以避免重复的数字。

select  distinct

    l1.Num as ConsecutiveNums

//代码中的"FROM Logs l1, Logs l2, Logs l3"语句表示从名为Logs的表中选择三次，

//分别用l1，l2和l3来表示

from

    Logs l1,

    Logs l2,

    Logs l3

//"WHERE"子句用于筛选满足特定条件的行。在这种情况下，条件是l1的Id等于l2的Id减1，l2的Id等于l3的Id减1，

//以及l1的Num等于l2的Num，l2的Num等于l3的Num。

where

    l1.Id = l2.Id - 1

    and l2.Id = l3.Id - 1

    and  l1.Num = l2.Num

    and  l2.Num = l3.Num;

6题目描述：

：Employee 

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| name        | varchar |
| salary      | int     |
| managerId   | int     |
+-------------+---------+
id 是该表的主键（具有唯一值的列）。
该表的每一行都表示雇员的ID、姓名、工资和经理的ID。

编写解决方案，找出收入比经理高的员工。

以 任意顺序 返回结果表。

结果格式如下所示。

示例 1:

输入: 
Employee 表:
+----+-------+--------+-----------+
| id | name  | salary | managerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | Null      |
| 4  | Max   | 90000  | Null      |
+----+-------+--------+-----------+
输出: 
+----------+
| Employee |
+----------+
| Joe      |
+----------+
解释: Joe 是唯一挣得比经理多的雇员。

代码如下：

select

    a.Name as  'Employee'

from

    Employee as  a,

    Employee as  b

where

    a.ManagerId = b.Id

        and a.Salary > b.Salary

select a.Name as 'Employee': 选择员工表中的姓名，并将其显示为"Employee"。

from Employee as a, Employee as b: 从员工表中进行自我连接，将其分别表示为a和b。

where a.ManagerId = b.Id and a.Salary > b.Salary: 筛选出a员工的经理ID等于b员工的ID，同时a员工的薪资高于b员工的薪资。

;