c++实际应用编程汇总(一)堆与栈|位操作

r囧r小猫 2022-01-21 06:57 201阅读 0赞

**目录**

一、数值的次方

1.1 python次方

1.2 c++次方

二、堆与栈

定义与概念

数据结构中

操作系统中

2.1 两个栈当作队列

c++两个栈当成队列

python两个栈当成队列

2.2 带有最小值的栈

c++带有最小值的栈

python带有最小值的栈

2.3 判断是否栈的压入弹出

c++栈的压入弹出

三、位操作

3.1 移位与位与

c++的位操作

python位操作

4、位异或操作

4.1 异或的性质

4.2 解法

4.3 运算优先级

--------------------

# 一、数值的次方 #

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

## 1.1 python次方 ##

相当简单

class Solution:
        def Power(self, base, exponent):
            # write code here
            return base**exponent

## 1.2 c++次方 ##

如果不能调用math.h头文件的话，需要重新编写。注意，matlab的次方操作好像是^，并不是c++的次方操作。

c++的次方操作是pow（base, exp）

class Solution {
 public:
 double Power(double base, int exponent) {
 double exp;
 if(exponent<0){
 exp=pow(base,-exponent);
 exp=1/exp;
 }
 else{
 exp=pow(base,exponent);
 }
 return exp;
 }
 };

并不用像上面那样麻烦，直接这样也可以：

class Solution {
    public:
        double Power(double base, int exponent) {
            double exp;
            exp=pow(base,exponent);
            return exp;
        }
    };

毫无难度

# 二、堆与栈 #

## 定义与概念 ##

数据结构中的堆，栈，与操作系统中的堆栈是两个不同的概念。

### 数据结构中 ###

堆，栈常分开说，且表示两种不同的数据结构。

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。完全二叉树。

栈，是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，

### 操作系统中 ###

[https://blog.csdn.net/myqq1418/article/details/81584761][https_blog.csdn.net_myqq1418_article_details_81584761]

1、栈区（stack） 一级缓存， 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。  
2、堆区（heap） 二级缓存一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表

3、全局区（静态区）（static），全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放  
4、文字常量区，常量字符串就是放在这里的。 程序结束后由系统释放  
5、程序代码区，存放函数体的二进制代码。

//main.cpp
    int a = 0; //全局初始化区
    int a = 0; //全局初始化区
    char *p1; //全局未初始化区
    main() {
        int b; //栈
        char s[] = "abc"; //栈
        char *p2; //栈
        char *p3 = "123456"; //123456\0在常量区，p3在栈上。
        static int c = 0; //全局（静态）初始化区
        p1 = (char *)malloc(10);
        p2 = (char *)malloc(20);
        //分配得来得10和20字节的区域就在堆区。
        strcpy(p1, "123456"); //123456\0放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。
    }

**动态数据区一般就是“堆栈”。“栈(stack)”和“堆(heap)”是两种不同的动态数据区，栈是一种线性结构，堆是一种链式结构**。进程的每个线程都有私有的“栈”，所以每个线程虽然代码一样，但本地变量的数据都是互不干扰。一个堆栈可以通过“基地址”和“栈顶”地址来描述。**全局变量和静态变量分配在静态数据区，本地变量分配在动态数据区，即堆栈中**。程序通过堆栈的基地址和偏移量来访问本地变量。

├———————┤低端内存区域
    │ …… │
    ├———————┤
    │ 动态数据区 │
    ├———————┤
    │ …… │
    ├———————┤
    │ 代码区 │
    ├———————┤
    │ 静态数据区 │
    ├———————┤
    │ …… │
    ├———————┤高端内存区域

## 2.1 两个栈当作队列 ##

用两个栈来实现一个队列。完成队列的Push和Pop操作。 队列中的元素为int类型。

解析：思路，一个栈只用于进，一个栈只用于出。

### c++两个栈当成队列 ###

数据结构对于c++来说十分重要，因此基础的结构，比如stack，以及其中的函数需要熟练掌握。

class Solution
 {//stack1 to push, stack2 to pop
 public:
 void push(int node) {
 if(stack1.empty()==true){
 while(stack2.empty()!=true){
 stack1.push(stack2.top());
 stack2.pop();
 }
 }
 stack1.push(node);
 }
 
 int pop() {
 if(stack2.empty()==true){
 while(stack1.empty()!=true){
 stack2.push(stack1.top());
 stack1.pop();
 }
 }
 int value=stack2.top();
 stack2.pop();
 return value;
 }
 
 private:
 stack<int> stack1;
 stack<int> stack2;
 };

stack.pop()出栈操作

stack.top()栈顶数值

stack.empty()判断栈是否为空

### python两个栈当成队列 ###

思路与c++一样。

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack1=[]
            self.stack2=[]
        def push(self, node):
            # write code here
            if(len(self.stack1)==0):
                while(len(self.stack2)!=0):
                    self.stack1.append(self.stack2.pop())
            self.stack1.append(node)
        def pop(self):
            # return xx
            if(len(self.stack2)==0):
                while(len(self.stack1)!=0):
                    self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

需要我们自己创建list变量。即class的初始化函数。

## 2.2 带有最小值的栈 ##

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

解析：这题需要注意意思，可以理解为在原有栈的基础上增加一个新的栈定义，带有最小值，因此可以用两个栈来实现，一个栈用于存储数值，另一个栈用于存储最小值。

### c++带有最小值的栈 ###

需要注意到是一个结构，private表示只在当前class内调用，stack的<>后面表示类模板。

class Solution {
 public:
 void push(int value) {
 stack_ins.push(value);
 if(stack_min.empty()==true)stack_min.push(value);
 else if(value<stack_min.top())stack_min.push(value);
 else stack_min.push(stack_min.top());
 }
 void pop() {
 stack_ins.pop();
 stack_min.pop();
 }
 int top() {
 return stack_ins.top();
 }
 int min() {
 return stack_min.top();
 }
 private:
 stack<int> stack_ins;
 stack<int> stack_min;
 };

### python带有最小值的栈 ###

类比c++代码，需要自己创建init函数，并且需要知道的是，

最后一个元素可以用value\[-1\]来表示

非空可以用 not self.stack\_min表示栈非空

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack_value=[]
            self.stack_min=[]
        def push(self, node):
            self.stack_value.append(node)
            if(not self.stack_min):
                self.stack_min.append(node)
            elif(self.stack_min[-1]>node):
                self.stack_min.append(node)
            else:
                self.stack_min.append(self.stack_min[-1])
        def pop(self):
            self.stack_value.pop()
            self.stack_min.pop()
        def top(self):
            return self.stack_value[-1]
        def min(self):
            return self.stack_min[-1]

还有更简单的方法：即直接用min函数实现查找最小值：

class Solution:
        def __init__(self):
            self.stack_value=[]
        def push(self, node):
            self.stack_value.append(node)
        def pop(self):
            return self.stack_value.pop()
        def top(self):
            return self.stack_value[-1]
        def min(self):
            return min(self.stack_value)

## 2.3 判断是否栈的压入弹出 ##

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

### c++栈的压入弹出 ###

这里我们需要多注意一点，空栈不能进行.top()操作。同时，与python区分，python的pop直接返回pop的值，而c++只是把值弹出来，与python等价应该为top，pop。

class Solution {
 public:
 bool IsPopOrder(vector<int> pushV,vector<int> popV) {
 int seq_size=pushV.size();
 if(seq_size!=popV.size())return false;
 if(pushV.size()<1)return true;
 stack<int> stack_ins;
 int pop_idx=0;
 for(int push_idx=0;push_idx<seq_size;push_idx++){
 stack_ins.push(pushV[push_idx]);
 while((!stack_ins.empty())&&(stack_ins.top()==popV[pop_idx])){
 stack_ins.pop();
 pop_idx++;
 }
 }
 if(pop_idx==seq_size)return true;
 else {
 return false;
 }
 }
 };

这一题一定要注意思路，千万不能先pop的循环再push的循环，不然发现很多bug，很难编出来。

需要先push，再pop。

class Solution {
 public:
 	bool IsPopOrder(vector<int> pushV, vector<int> popV) {
 		if (pushV.size() < 1 || popV.size() < 1)return false;
 		stack<int> stack_ins;
 		int idx_pop = 0;
 
 		for (int idx_push = 0; idx_push < pushV.size(); idx_push++){
 			stack_ins.push(pushV[idx_push]);
 			while (!stack_ins.empty() && stack_ins.top() == popV[idx_pop]){
 				stack_ins.pop();
 				idx_pop++;
 			}
 		}
 		if (idx_pop == popV.size())return true;
 		else return false;
 	}
 };

需要确认stack非空，再进行top()操作，不然运行时候会报错。

while (!stack\_ins.empty() && stack\_ins.top() == popV\[idx\_pop\])

# 三、位操作 #

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

## 3.1 移位与位与 ##

c语言相关的位操作

如下函数，在32位系统中func((1<<31)-3)输出的值是1。为什么？

int func(int x)
    	{
    		return x & -x;
    	}

解析：

相当于-0-3=-3

即3的二进制数与-3的二进制数位与操作。

000011与111101，结果为1

### c++的位操作 ###

输出一个数字二进制中1的个数：

*  定义一个数的时候，即0x表示16进制。
 *  while或者if之后，只要值非0，即表示条件成立，即是true
 *  位与操作为&，（区分与逻辑操作为&&）

class Solution {
 public:
 int NumberOf1(int n) {
 int mask=0x00000001;
 int count=0;
 while(mask){
 if(n&mask){
 count++;
 
 }
 mask=mask<<1;
 }
 return count;
 }
 };

### python位操作 ###

[https://www.cnblogs.com/everest33Tong/p/6586634.html][https_www.cnblogs.com_everest33Tong_p_6586634.html]

与c++的位操作类似

class Solution:
 def NumberOf1(self, n):
 # write code here
 mask=0x00000001
 count=0
 for shift in range(0,32):
 if(n&(mask<<shift)!=0):
 count=count+1
 return count

# 4、位异或操作 #

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

此题较难，但是如果知道异或的话，会相对简单很多。

## 4.1 异或的性质 ##

*  交换律 a^b=b^a
 *  结合律（即(a^b)^c == a^(b^c)）
 *  对于任何数x，都有x^x=0，x^0=x
 *  自反性 A XOR B XOR B = A xor  0 = A

## 4.2 解法 ##

*  一系列数组，假设这两个数字为a，b，其他都出现了两次，则最终经过异或抵消，所以最终所有数字异或的结果为a^b
 *  结果中，必有一位为1的必然是a和b不同的位。
 *  把整个数组分成两组，一个组中所有数字该位为1，另一组中所有数字该位为0
 *  则每组异或的结果为a，或者b

#include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 
 class Solution {
 public:
 	void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
 		int length = data.size();
 		if (length < 2)return;
 		*num1 = 0;
 		for (int idx = 0; idx < length; idx++){
 			(*num1) ^= data[idx];
 		}
 		int mask = 0x00000001;
 		while ((mask&(*num1)) == 0){
 			mask = mask << 1;
 		}
 		cout << mask << endl;
 		*num1 = 0; *num2 = 0;
 		for (int idx = 0; idx < length; idx++){
 			if (mask&data[idx]){
 				*num1 ^= data[idx];
 				cout <<"1:"<< *num1 << endl;
 			}
 			else{
 				*num2 ^= data[idx];
 				cout << "2:" << *num2 << endl;
 			}
 		}
 		return;
 	}
 };
 
 int main(){
 	vector<int>gas = { 2, 4, 3, 6, 3, 2, 5, 5 }; //4,6
 	int a; int b;
 	int *num1 = &a; int *num2 = &b;
 	Solution s1;
 	s1.FindNumsAppearOnce(gas, num1, num2);
 	cout << a << " " <> end;
 	return 0;
 }

此题中，容易出现的错误是，下面这个语句表示mask往左移位，直到找到num1中第一个非0的位。

while ((mask&(*num1)) == 0){
 mask = mask << 1;
 }

但是写的时候容易写成：

while (mask&\*num1 == 0)

则mask的值就会出错。因为优先级别的问题。异或的优先级为最低的优先级，因此先进行了==判断，再进行了异或。

## 4.3 运算优先级 ##

优先级表：[https://baike.baidu.com/item/%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BC%98%E5%85%88%E7%BA%A7/4752611?fr=aladdin][https_baike.baidu.com_item_E8_BF_90_E7_AE_97_E7_AC_A6_E4_BC_98_E5_85_88_E7_BA_A7_4752611_fr_aladdin]

以后涉及位运算操作的，必须加括号，以便运算。

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:middle;"> 5 </td> 
 <td style="vertical-align:middle;"> &lt;&lt; </td> 
 <td style="vertical-align:middle;"> 左移 </td> 
 <td style="vertical-align:middle;"> 整型表达式&lt;&lt;整型表达式 </td> 
 <td style="vertical-align:middle;"> 左到右 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> &gt;&gt; </td> 
 <td style="vertical-align:middle;"> 右移 </td> 
 <td style="vertical-align:middle;"> 整型表达式&gt;&gt;整型表达式 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> 6 </td> 
 <td style="vertical-align:middle;"> &gt; </td> 
 <td style="vertical-align:middle;"> 大于 </td> 
 <td style="vertical-align:middle;"> 表达式&gt;表达式 </td> 
 <td style="vertical-align:middle;"> 左到右 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> &gt;= </td> 
 <td style="vertical-align:middle;"> 大于等于 </td> 
 <td style="vertical-align:middle;"> 表达式&gt;=表达式 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> &lt; </td> 
 <td style="vertical-align:middle;"> 小于 </td> 
 <td style="vertical-align:middle;"> 表达式&lt;表达式 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> &lt;= </td> 
 <td style="vertical-align:middle;"> 小于等于 </td> 
 <td style="vertical-align:middle;"> 表达式&lt;=表达式 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> 7 </td> 
 <td style="vertical-align:middle;"> == </td> 
 <td style="vertical-align:middle;"> 等于 </td> 
 <td style="vertical-align:middle;"> 表达式==表达式 </td> 
 <td style="vertical-align:middle;"> 左到右 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> != </td> 
 <td style="vertical-align:middle;"> 不等于 </td> 
 <td style="vertical-align:middle;"> 表达式!= 表达式 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> 8 </td> 
 <td style="vertical-align:middle;"> &amp; </td> 
 <td style="vertical-align:middle;"> 按位与 </td> 
 <td style="vertical-align:middle;"> 整型表达式&amp;整型表达式 </td> 
 <td style="vertical-align:middle;"> 左到右 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> 9 </td> 
 <td style="vertical-align:middle;"> ^ </td> 
 <td style="vertical-align:middle;"> 按位异或 </td> 
 <td style="vertical-align:middle;"> 整型表达式^整型表达式 </td> 
 <td style="vertical-align:middle;"> 左到右 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:middle;"> 10 </td> 
 <td style="vertical-align:middle;"> | </td> 
 <td style="vertical-align:middle;"> 按位或 </td> 
 <td style="vertical-align:middle;"> 整型表达式|整型表达式 </td> 
 <td style="vertical-align:middle;"> 左到右 </td> 
 <td style="vertical-align:middle;"> 双目运算符 </td> 
 </tr> 
 </tbody> 
</table>

[https_blog.csdn.net_myqq1418_article_details_81584761]: https://blog.csdn.net/myqq1418/article/details/81584761
[https_www.cnblogs.com_everest33Tong_p_6586634.html]: https://www.cnblogs.com/everest33Tong/p/6586634.html
[https_baike.baidu.com_item_E8_BF_90_E7_AE_97_E7_AC_A6_E4_BC_98_E5_85_88_E7_BA_A7_4752611_fr_aladdin]: https://baike.baidu.com/item/%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BC%98%E5%85%88%E7%BA%A7/4752611?fr=aladdin