0%

只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入:[2,2,1] 输出:1

示例 2:

输入:[4,1,2,1,2] 输出:4

算法思想

老规矩找到问题给出的性质——目标元素只出现一次,剩余元素出现两次

不多不少,正好两次。显然这是一个主要的突破口。

两次很容易让我们想到,假如非目标元素两两揍一顿互相抵消就好了。什么方式可以让相同的数抵消,不同的数保留呢?

数位的异或运算

位的角度来看:1^1=0 0^0=0 10=01=1

即相同的位会清空,不相同的位会保留。

并且多位运算时:110=1(10)=(10)1=0

易知位的异或运算具有结合律和交换律——即运算顺序不影响运算结果

数的异或

从数位异或中可以看出,偶数次的 1 或者 0 运算后都是 0,在数的层面上也是一样,出现偶数次的数两两运算后也为 0。而 0 和任何数异或等于数本身。

因此对整个数组进行异或运算,相当于最后剩个 0 和目标元素异或,结果就是目标值。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int singleNumber(vector<int& nums)
{
//异或运算 相同的数异或归 0 且异或具有交换律
int result=0;
for (auto num :nums)
{
result^=num;
}

return result;
}
};

奇怪的问题汇总

git连接GitHub每次都需要输入账号密码

背景

问题在于git clone 的时候选择的链接是HTTPS的,因此在这个仓库中,git不会通过SSH密钥去进行免密认证。

解决方案

命令行输入git config -l

可以看到一大堆信息,关注其中一条与链接相关的:

1
remote.origin.url=https://...

我们需要url的https链接改回ssh即可。

命令行输入

1
git config remote.origin.url git@github.com:你的仓库地址

试着git push一下=。=

阅读全文 »

局部静态对象

有些时候,我们需要保留一些对象在函数体结束后依然使用,定义时使用static将其声明为静态类型,直到程序终止才销毁。

虽然在函数外没有销毁,但是其仍然是局部变量,外部不可访问,只不过其内存也不释放。

局部静态变量如果没有显式的初始化值,将执行值初始化,内置类型的值初始化为0。

一个简单的例子,这个程序会输出 1~10 的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
size_t count_calls()
{
static size_t num=0;
num++;
return num;
}

int main()
{
for(size_t i=0;i<10;i++)
cout<<count_calls()<<endl;
return 0;
}

指针变量传递

指针变量作为参数和普通变量作为参数一样,都是值传递。即形参和实参是两个不同的指针变量,两个指针自己的地址不一样,但是它们的值一样——即它们指向的地址是一样的。因此可以通过传递指针修改实参。

const 参数

实参传给形参会忽略掉顶层const,即从函数外部看函数,我们不知道这个函数的参数究竟有没有顶层const,也因此不能通过顶层const来重载函数。例如:

1
2
3
4
5
6
7
8
9
10
11
void fcn1(const int i){···}     //忽略顶层 const
void fcn1(int i){···} //错误,重复定义

void fcn2( int * const i){···} //忽略顶层 const
void fcn2(int * i){···} //错误,重复定义

void fcn3(const int * i){···} //这是底层 const,不会造成重复定义
void fcn3(int * i){···} //正确

void fcn4(const int &i){···} //正确,也类似于底层const,const int 算作一种独立类型
void fcn4(int &i){···} //int优先匹配int&,其次匹配const int&。 const int只能匹配const int&

顶层可以理解为离变量最近的一层,顶层 const 修饰指针本身的值,即指向哪一个地址不能被修改,底层 const 修饰指针指向的对象的值不能被修改。

形参初始化和变量初始化一样,关于 const 的要求都是可降格兼容,不能升格。即如上int可用于初始化const int变量,const int不能初始化int变量。引用和指针层面也是类似,cont int引用可绑定到int对象,int引用不可绑定到const int对象。

尽量使用常量引用。使用常量引用可以避免拷贝数据,同时阻止非必要的修改操作。另一方面由于外部的 const 类型不能升格传参给非 const 形参,容易发生类型匹配错误。而外部的非 const 类型可以传给 const 形参,因此使用 const 引用,也可以有效减少这种类型错误的情况。

数组形参

数组有两个特殊性质,影响我们对数组的传参操作:

  • 数组不能进行拷贝
  • 使用数组时相当于使用指针

所以我们不能值传递数组,但是我们可以通过指针进行传递,如下三个等价的传递数组的函数,看起来不一样,其实都是形参都是 const int*,导致重复定义:

1
2
3
4
5
//会互相造成重复定义错误
void fcn(const int * a);
void fcn(const int a[]);
void fcn(const int a[10]);//这里数组大小只是一个期望大小,有没有完全一样,和没有的会造成重复定义。

但是正如示例所述,只传递指针的话,我们不知道传进来的数组有多大,因此可以通过别的途径传递长度信息:

  • 加一个length变量 void fcn(const int a[],int length);//用另一个变量标记长度
  • 取得尾后迭代器 void fcn(const int *begin,const int * end)//标准库规范做法,传递尾后元素,进行尾后检测

多维数组

我们知道多维数组其实就是一维数组,只不过数组元素是新数组指针而已。多维数组即看作指针的指针进行传递。如下,首先明确传参的只是一个指针,指向首元素,这个指针的类型是首元素类型。

1
2
3
void fcn(int (* matrix)[10]);   //matrix 是一个指针,指向首元素类型为 int[10]
void fcn(int matrix[][10]); //等价形式,前面示例知道 matrix[] 其实也是看作指针。
void fcn(int * matrix[10]) //错误,这是一个一维数组,数组元素类型是 int*

注意,虽然上述传递一维数组会忽略数组大小,但是第二维及以上的数组大小算作一种数据类型,需要严格对应:

1
2
3
4
5
6
7
8
void fcn(int a[][2]) // == int (*a) [2]  , != int *a[2]
{
return ;
}

int b[2][4];

fcn(b);//错误,int (*)[4] 和 int(*)[2] 类型的形参不兼容。a指向int [2],b指向int[4]。

另外注意 int ** 和 int (*) [10] 不是同一个类型。

变长形参

有时候我们不确定要传递几个实参给函数,因此 C++提供了两种方法。

Initializer_list

Initializer_list 是一个很简单的列表容器,有点像python的*args

  • 形参使用initializer_list<T>来接受列表参数
  • 实参使用初始化列表传参{T1,T2,T3}
  • 函数体内则和其他容器一样访问。
1
2
3
4
5
6
7
void error_msg(int count,initializer_list<string> msg)
{
for(auto arg =msg.begin();arg!=msg.end();++arg)
...
}

error_msg(217,{"Hello",",","World","!"});

省略符

省略符是为了兼容 C 而设置的。通常不建议在 C 之外使用

1
2
void foo(parm_list,...);
void foo(...)

返回值

返回数组指针

函数返回一个普通指针很简单,返回值 type * 即可,但是返回一个指向数组的指针呢?正常声明数组指针变量是type (*var)[size] : var是一个指针,指向一个大小为size的数组,数组元素类型是type。

那么函数返回同理:

1
type (* func(param...)) [size]

decltype返回

如果已知返回的是什么变量的类型,可以使用decltype来推断返回类型:

1
2
3
4
decltype(somevar) * func(int i)
{
retrun &somevar;
}

尾置返回

C++11更方便的尾置返回,在返回复杂的东西时显得很方便,例如返回数组指针:

1
auto func(int i) -> int(*) [size]

函数指针

和普通类型的指针type *一样,把函数看作一种类型,可以定义函数指针如下,并且可以将函数名赋值给该指针,然后当做函数一样使用:

1
2
3
4
5
6
7
8
9
bool func (string,string);//原函数
bool (*p) (string,string);//定义该函数的指针,注意括号,没有括号则是一个叫做p的函数。
//两种赋值方式等价
p=0; //0不指向任何函数
p=func;
p=&func;
//两种调用方式等价
bool a=p(str1,str2);
bool b=(*p)(str1,str2);

拥有了指针,自然也能将函数指针作为 函数参数 和 函数返回值 使用。

1
2
3
4
5
6
7
8
//两种形参方式等价,自动将函数类型转为函数指针
void f(bool p(string,string));
void f(bool (*p)(string,string));
//两种传参方式等价,自动将函数类型转为函数指针
f(func);
f(p);
//注意在作为返回值时,函数名不会自动转为函数指针
bool (*f(int a)) (string,string); //f(int a)是一个函数,它返回一个指针,这个指针指向函数 bool func (string,string)。

显然上述的函数指针形式很繁琐,因此可以利用typedefdecltype等改名工具来简化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//两种改名方式等价
typedef bool f2(string,string);//f2类型==func类型
typedef decltype(func) f3; //f3类型==func类型
using f4=bool (string,string) //f4类型==func类型

typedef bool (*p2)(string,string); //p2类型==p类型
typedef decltype(func) *p3; //p3类型==p类型
using p4=bool (*) (string,string) //p4类型==p类型

//函数指针作为参数。两种方式等价,因为函数类型自动转换为函数指针类型
void f(f3 afunc);
void f(p3 apoint);
//作为返回值时不等价。
p3 f(int a);//f(int a)是一个函数,返回p3类型,即指向func的函数指针类型。
f3 f(int a);//错误,不能将函数类型作为返回值
auto f(int a) -> bool (*) (string,string);//后置返回语法

类型别名 不是 变量名,上述代码没有创建一个f3变量或者一个p3变量,应当看作类型名去使用。

参考资料

C++ Primer 5 edition 中文版

语法

在构造函数的()之后,冒号开头,逗号分隔,括号传参,这一段就是初始化列表,随后是在{}里写构造函数内容。

1
2
3
4
Example(argv):a(1),b(2) 
{
···
}

初始化作用

无法赋值的成员,必须使用初始化列表进行初始化

例如假设有个类成员,它本身是个没有默认构造函数的类。

1
2
3
4
5
class CMember
{
public:
CMember(int x){···}
}

我们都知道此时CMember* pm=new CMember;是错误的,必须调用有参数的构造函数。

此时 CMember 是另一个类的成员时,我们怎么初始化呢?

阅读全文 »

最大正方形

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

输入:

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

输出: 4

算法思想

大正方形必然是由小正方形迭代上来的。因此这题是个明显的动态规划题,但是我们怎么去确定状态转移方程呢?

状态转移方程的理解

首先我们确定,正方形是从左上往右下进行延展(其他延展方向也行)。

我们什么时候可以延展这个正方形呢?

首先新找到的点肯定得是 1,要不然不可能构成正方形。以matrix[i][j]位为1,我们可以得到示例如下: a a a x a a a x a a a x x x x 1

因为是正方形,所以假如 [i][j]位要构成新的正方形,那必然是从左上角的 a 区域延展下来的。

但是即使 a 区域是正方形,[i][j]位是1,就一定形成新正方形吗?并没有

当我们把正方形延展到[i][j]位时,其实[i]行和[j]列对应边也都扩展进去了,也就是上例的 x 区域,也要是1才能延展构成新正方形。

即我们现在知道延展正方形受限于哪些环境
  • 左上角的 a 区域的正方形有多大,新正方形则是边长++

  • x 区域,从[i][j]分别往左和往上走,能提供的最大边长。

    如下,虽然 a 区域是边长3的正方形,本来想要以[i][j]为新顶点扩展成边长4的正方形,但是由于新的两条边长度只有1,满足不了边长4的正方形的要求。

    因此[i][j]只能构成边长2的正方形。

受限于 x 区域新边长的延展 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1

得出状态转移方程

因此总结一下状态转移方程:

[i][j]位的正方形边长=min( [i-1][j-1]的正方形边长,新的两边边长 ) + 1

伪代码即 dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

其中dp[i][j]表示[i][j]位作为左下角时,形成正方形的边长。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int maximalSquare(vector<vector<char& matrix)
{
//动态规划,如何理解dp的递归式
int width=matrix.size();if(width==0) return 0;
int length=matrix[0].size();if(length==0) return 0;
vector<vector<int dp(width+1,vector(length+1,0));
int result=0;

for(int i=0;i<width;i++)
{
for(int j=0;j<length;j++)
{
if(matrix[i][j]=='1')
dp[i+1][j+1]=min(min(dp[i][j],dp[i][j+1]),dp[i+1][j])+1;
else
dp[i+1][j+1]=0;

if(dp[i+1][j+1]result)
result=dp[i+1][j+1];
}
}

return result*result;

}
};