C++幂运算
浮点型 pow(x,y)
//函数名称: pow //函数原型: double pow( double x, double y ); //函数功能: 计算x的y次幂 //所属文件:#include #include int main () { printf ("3 ^ 4 = %fn", pow (3.0, 4.0) ); return 0; }
整数型 简单幂运算
for(int i=0;i<4;i++){
ans=ans*3%1000000007;
}
整数型 快速幂运算 1
//m取模 一般为1000000007
typedef long long ll;
ll quick_pow(ll x,ll n,ll m){
ll res = 1;
while(n > 0){
if(n & 1) res = res * x % m;
x = x * x % m;
n >>= 1;//相当于n=n/2.详情请参考位移运算符。
}
return res;
}
整数型 快速幂运算 2
ll q_pow(ll x,ll n,ll m){
if(n == 0) return 1;
ll res = q_pow(x * x % m,n/2,m);
if(n & 1) res = res * x % m;
return res;
}
1
cpp
class Solution {
public:
int hammingWeight(uint32_t n) {
int ret = 0;
for(int i=0;i<32;i++){
if(n & 1<
python
class Solution:
def hammingWeight(self, n: int) -> int:
ret = sum(1 for i in range(32) if n & (1 << i))
return ret
运算符优先级
2
cpp
class Solution {
public:
double quickMul(double x, long long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
python
class Solution:
def myPow(self, x: float, n: int) -> float:
def quickMul(N):
if N == 0:
return 1.0
y = quickMul(N // 2)
return y * y if N % 2 == 0 else y * y * x
return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)
cpp
class Solution {
public:
double quickMul(double x, long long N) {
double ans = 1.0;
// 贡献的初始值为 x
double x_contribute = x;
// 在对 N 进行二进制拆分的同时计算答案
while (N > 0) {
if (N % 2 == 1) {
// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
ans *= x_contribute;
}
// 将贡献不断地平方
x_contribute *= x_contribute;
// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
N /= 2;
}
return ans;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
python
class Solution:
def myPow(self, x: float, n: int) -> float:
def quickMul(N):
ans = 1.0
# 贡献的初始值为 x
x_contribute = x
# 在对 N 进行二进制拆分的同时计算答案
while N > 0:
if N % 2 == 1:
# 如果 N 二进制表示的最低位为 1，那么需要计入贡献
ans *= x_contribute
# 将贡献不断地平方
x_contribute *= x_contribute
# 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
N //= 2
return ans
return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)
3
cpp
class Solution {
public:
vector printNumbers(int n) {
if(n <= 0) return vector(0);
vector res;
int num = 1;
for(int i=0; i
cpp
class Solution {
public:
vector printNumbers(int n) {
vector res;
if (n == 0) return res;
//打印到数组中
for (int i=1,max=pow(10,n);i
cpp大数解法char版
class Solution {
public:
vector res;
vector printNumbers(int n) {
if (n <= 0) return res;
//创建一个能容纳最大值的字符数组,由于有一位要存储' '，因此要开大一格
char* number = new char[n + 1];
//初始全部设置为0
memset(number, '0', n);
number[n] = ' ';//第n位设为' '
while (!Increment(number))
{
PrintNumber(number);
}
delete[]number;//注意要释放内存
return res;
}
bool Increment(char* number) {//形参传递char*指针
bool isOverflow = false;//检测是否越界
int nTakeOver = 0;//存储进位
int nLength = strlen(number);//长度为n,不是n+1
for (int i = nLength - 1; i >= 0; i--)
{
int nSum = number[i] - '0' + nTakeOver;
if (i == nLength - 1)
//如果是第一位，进位
{
nSum++;
}
if (nSum >= 10)
//有进位
{
if (i == 0)
//如果是最高位有进位，说明超过了给定得到最大值，越界
{
isOverflow = true;
}
else//非最高位有进位
{
nTakeOver = 1;
number[i] = nSum - 10 + '0';//对第i位进行设置
}
}
else//没有进位
//设置第i位数字
//并直接跳出循环
{
number[i] = nSum + '0';
break;
}
}
return isOverflow;
}
void PrintNumber(char* number)
//形参传递char*指针，此处改变形参number指向的位置，不会使原始的number指针所指位置改变
{
string s = "";
bool isBegin0 = true;
while (*number != ' ')
{
if (isBegin0 && *number != '0') isBegin0 = false;
//碰到'0'，则不输出
if (!isBegin0)
{
s += *number;
}
number++;
}
int num = stoi(s);//转为整数
res.push_back(num);
}
};
cpp大数解法string版
class Solution {
public:
vector res;
vector printNumbers(int n) {
if (n <= 0) return res;
//创建一个能容纳最大值的字符数组
string number(n, '0');
//初始全部设置为0
while (!Increment(number))
{
saveNumber(number);
}
return res;
}
bool Increment(string& number) {
//注意要使用引用传递，否则无法修改number
bool isOverflow = false;//检测是否越界
int nTakeOver = 0;//存储进位
int nLength = number.size();
for (int i = nLength - 1; i >= 0; i--)
{
int nSum = number[i] - '0' + nTakeOver;
if (i == nLength - 1)
//如果是第一位，进位
{
nSum++;
}
if (nSum >= 10)//有进位
{
if (i == 0)
//如果是最高位有进位，说明超过了给定得到最大值，越界
{
isOverflow = true;
}
else
{
nTakeOver = 1;
number[i] = nSum - 10 + '0';//对第i位进行设置
}
}
else//没有进位
//设置第i位数字
//并直接跳出循环
{
number[i] = nSum + '0';
break;
}
}
return isOverflow;
}
void saveNumber(string number)
//由于此处输出，不需要修改number，因此不需要加引用
{
string s = "";
bool isBegin0 = true;
string::iterator it = number.begin();
while (it != number.end())
{
if (isBegin0 && *it != '0') isBegin0 = false;
if (!isBegin0)
{
s += *it;
}
it++;
}
int num = stoi(s);
res.push_back(num);
}
};
cpp递归解法
class Solution
{
public:
vector res;
vector printNumbers(int n) {
if (n <= 0) return res;
string number(n, '0');
for (int i = 0; i <= 9; i++)
//从高位到低位进行全排列
{
number[0] = i + '0';//首字符赋初值
permutationNumbers(number, n, 1);//设置下一位
}
return res;
}
//对数字全排列
void permutationNumbers(string& number, int length, int index) {
if (index == length) {//递归边界
saveNumber(number);//存储结果
return;
}
else
{
for (int i = 0; i <= 9; i++)
{
number[index] = '0' + i;//设置第index位的字符
permutationNumbers(number, length, index + 1);
}
}
}
//存储结果
//只能存储前导非0的排列
void saveNumber(string number) {
bool isBegin0 = true;
string tempStr = "";
string::iterator it = number.begin();
while (it != number.end())
{
if (isBegin0 && *it != '0') isBegin0 = false;
if (!isBegin0) {
tempStr += *it;
}
it++;
}
//从高位到低位全排列，要注意首字符为0时，tempStr为空，不能执行stoi
if (tempStr != "") {
int tempNum = stoi(tempStr);
res.push_back(tempNum);
}
}
};
python
class Solution:
def printNumbers(self, n: int) -> List[int]:
return [i for i in range(1, 10**n)]
4
cpp
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head->val == val) return head->next;
ListNode *pre = head, *cur = head->next;
while(cur != nullptr && cur->val != val) {
pre = cur;
cur = cur->next;
}
if(cur != nullptr) pre->next = cur->next;
return head;
}
};
python
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head.val == val: return head.next
pre, cur = head, head.next
while cur and cur.val != val:
pre, cur = cur, cur.next
if cur: pre.next = cur.next
return head
