每日一题(快乐数)+cpp实现求解真值表
第202题. 快乐数
哈希表更像是一个备用方案？貌似都不太需要强制使用
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> uset={n};
while (n!=1){
int num=0;
while (n){
num+= pow(n%10,2);
n=n/10;
}
if(uset.find(num)!=uset.end()) return false;
uset.emplace(num);
n=num;
}
return true;
}
};
鸽了几周的离散数学实验终于写完了，转为后缀表达式真不想写，copy了下，其他自己琢磨的
还有主析/合取范式，存个二维数组遍历下应该就完成了
//
// Created by 徐昊岩 on 2023/10/8.
//
//否定¬替换为!,析取替换为|，合取替换为&，条件替换为-，双条件替换为=
#include "windows.h"
#include "iostream"
#include "vector"
#include "cmath"
#include "stack"
using namespace std;
bool judge(char p, char q){ //判断运算符优先级
int x = 0;
int y = 0;
if(p == '!')
x = 5;
else if(p == '&')
x = 4;
else if(p == '|')
x = 3;
else if(p == '-')
x = 2;
else if(p == '=')
x = 1;
if(q == '!')
y = 5;
else if(q == '&')
y = 4;
else if(q == '|')
y = 3;
else if(q == '-')
y = 2;
else if(q == '=')
y = 1;
return x > y;
}
void change(string s,string &output,int &pos,stack<char>& Stack){ //中缀表达式转后缀表达式
char c;
for(int i = 0; i < s.length(); i++)
{
if(s[i] >= 'a' && s[i] <= 'z')
output[++pos] = s[i];
else
{
if(s[i] == '(') //如果是左括号直接压进去
Stack.push(s[i]);
else if(s[i] == ')') //如果是有括号弹掉左括号之前的所以的运算符
{
while(!(Stack.top() == '('))
{
output[++pos] = Stack.top();
Stack.pop();
}
Stack.pop(); //弹左括号
}
else
{
if(Stack.empty()) //栈空直接进栈
Stack.push(s[i]);
else //非空就比较优先级
{
while(!judge(s[i],Stack.top())) //如果当前复合优先级小于等于栈顶符号的就弹栈
{
output[++pos] = Stack.top();
Stack.pop();
if(Stack.empty()) //防止弹空栈
break;
}
Stack.push(s[i]); //压入当前运算符
}
}
}
}
while(!Stack.empty()) //全部处理完之后将栈内剩余的运算符放到表达式里
{
if(Stack.top() != '(' && Stack.top() != ')')
{
output[++pos] = Stack.top();
}
Stack.pop();
}
}
int caculator(const int num,vector<int> vec_list,string& output,int pos){
stack<int> stack_cal;
int tp1,tp2;
for(int i=0;i<=pos;i++){
if(output[i] >= 'a' && output[i] <= 'z')
stack_cal.push(vec_list[output[i]-'a']); //后缀表达式,只把变量压入堆栈内
else{
tp1=stack_cal.top();
stack_cal.pop();
tp2=stack_cal.top();
stack_cal.pop();
switch (output[i]) {
case '&':
stack_cal.push(tp1 && tp2);
break;
case '|':
stack_cal.push(tp1 || tp2);
break;
case '-':
stack_cal.push((!tp1) || tp2);
break;
case '=':
stack_cal.push(tp1 == tp2);
break;
case '!':
stack_cal.push(tp2);
stack_cal.push(!tp1);
break;
}
}
}
return stack_cal.top();
}
void vec_list_pr(int num,string& output,int pos){
vector<int> vec_list(num,1);
for(int i=0;i< pow(2,num);i++){
for(int o=0;o<num;o++){
if(i%(int)pow(2,num-1-o)==0){
vec_list[o]=!vec_list[o];
}
}
for(int i=0;i<num;i++) cout<<vec_list[i]<<" ";
cout<<caculator(num,vec_list,output,pos)<<endl;
}
}
string IO(int& count,string& input){
int a[26]={0};
for(int i=0;i<input.size();i++){
if(input[i]>='A' && input[i]<='Z'){
int flag=0;
for(int o=0;o<count;o++) {
if(input[i]==a[o]){
flag=1;
break;
}
}
if(!flag){
a[count]=input[i];
count++;
}
}
}
// 把PQ等字母转换为ab的目的是方便后续映射为一个vector容器的某个下标对应数
for(int i=0;i<input.size();i++){
if(input[i]>=65 && input[i]<=90){
for(int o=0;o<count;o++){
if (input[i]==a[o]) input[i]=char(97+o);
}
}
}
return input;
}
int main(){
system("chcp 65001 > nul");
int num=0;
int pos = -1;
stack<char> Stack;
string input;
string output;
cout<<"运算符替换规则:否定¬替换为!,析取替换为|，合取替换为&，条件替换为-，双条件替换为="<<endl<<"(请使用大写字母表示变量!)"<<endl;
cin>>input;
IO(num,input);
change(input,output,pos,Stack);
cout<<num<<endl<<input<<endl;
vec_list_pr(num,output,pos);
}