1、简单的N转K进制输出,并判断输出是否回文。
该题主要考察进制转换
分为两步:
(1)比如求x的b进制,那么求出x每次对b取模的余数,拼接在字符串后边。这里注意如果余数大于10的话,需要用大写英文字母进行表示,比如\'A\'
表示11,\'B\'
表示12等等。。。
(2)最后,将余数组成的字符串反转过来即可。
代码如下:
#include <iostream>#include <algorithm>using namespace std;const int N = 22;int b;// 检查是否是回文bool check(string str){for(int i = 0 , j = str.size() - 1; i < j; i++ , j--){if(str[i] != str[j]) return false;}return true;}// 进行进制转换string get(int x){string res; // 存储x在b进制下的表示while(x){int t = x % b; // 获取余数if(t >= 10) res += (t - 10) + \'A\'; // 如果是余数是10以上使用AB...来表示else res += t + \'0\'; // 否则将余数t添加到res后边,加上\'0\'是为了让数字t转化为字符t x /= b; // 记得除以b}reverse(res.begin() , res.end()); // 最后将余数倒过来return res;}int main(){cin >> b;for(int i = 1; i <= 300; i++){int t = i * i;string s = get(t); // 用b进制表示tif(check(s)) // 如果判断是回文{cout << get(i) << \' \' << s << endl;}}return 0;}
2、Leetcode-435 无重叠区间
解题思路:题目中需要移除最少的区间,使得剩下的全是无重叠区间,也就是说,需要找到最多的无重叠区间。
贪心
将列表按照区间的最大值进行排序,遍历列表,用end值表示当前遍历过的最大值,当当前列表的最小值大于等于end,说明当前区间与end所在的区间无重叠,无重叠区间+1,end更新为当前区间的最大值,直至遍历完成。
代码:
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:n = len(intervals)if n == 0: return 0ans = 1intervals.sort(key=lambda a: a[1])end = intervals[0][1]for i in range(1,n):if intervals[i][0] >= end:ans += 1end = intervals[i][1]return n - ans
动态规划
状态定义
dp[i]表示列表从0开始到位置i之间的最多的无重叠区间
状态转移方程
dp[i] = max(dp[i].dp[j]+1),j是从i遍历到位置0遇到的第一个与i无重复区间的位置
dp[i] = max(dp[i],dp[i-1]),找到从位置0到位置i中最多的无重叠区间
代码:
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:n = len(intervals)if n == 0: return 0dp = [1] * nans = 1intervals.sort(key=lambda a: a[1])for i in range(len(intervals)):for j in range(i - 1, -1, -1):if intervals[i][0] >= intervals[j][1]:dp[i] = max(dp[i], dp[j] + 1)breakdp[i] = max(dp[i], dp[i - 1])ans = max(ans, dp[i])return n - ans