循环停止

字符串

  字符串的终止符是’\0’，可以用’\0’作为跳出循环的判断条件。’\0’在此时被视为0。当指针移动到字符串末尾遇到字符串结束符’\0’，*p就为’\0’循环就会结束

  例子一：

1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
using namespace std;

int main()
{
	const char* p = "12345";
	while (*p)
	{
		cout << *(p++);
	}
}

例子二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

char* StrStr(const char *str,const char *target)
    if(!*target) return str;
    char *p1 = (char*)str;
    while (*p1)
    {
        char *p1Begin = p1, 
        char *p2 = (char*)target;
        while(*p1 && *p2 && *p1 == *p2)
        {
            p1++;
            p2++;
        }
        if(!*p2)
            return p1Begin;
        p1 = p1Begin +1;
    }
    return NULL;

（链表）指针

  数据结构中，构造单链表都是定义最后的指针指向NULL，这样指针遇到NULL就不再移动。
例子：leetcode第二题

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
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(0);
        ListNode*head = result;
        int carry = 0;
        while(l1||l2)
        {
            int n1=l1?l1->val:0;
            int n2=l2?l2->val:0;
            
            ListNode* new_point = new ListNode(0);
            int sum=n1+n2+carry;
            carry = sum/10;
            
            new_point->val=sum%10;
            result->next=new_point;
            result=result->next;
            if(l1)
            {
                l1=l1->next;
            }
            if(l2)
            {
                l2=l2->next;
            }
            
            
        }
        if(carry!=0)
        {
            ListNode* new_point =new ListNode(0);
            new_point->val=1;
            result->next = new_point; 
        }
        return head->next;
    }
};


vector容器（27题）

  vector容器，底层是定义在heap（堆）中的动态数组
  定义了vector< int > nums;如果这个动态数组为空，那么nums[0],nums.size()都会输出很奇怪的数字，而不是所想象的空、0。vector有专门的判别工具，nums.empty()。

1
2
3
4
5
if(nums.empty())
    {
        cout<<"nothing";
        return 0;
    }

  vector< string > nums;这个动态容器中,可以对nums[n]进行判断，因为每个nums[n]都是string类型，String类有一个empty()函数,就可以对字符串判空了因此可以调用nums[n].empty()。

1
2
3
while(!v[n].empty())
{
}

  对于vector，使用vector中的end()函数，判断是否到达最后一个元素，注意nums.end()指向的是最后一个元素的下一个位置，nums.begin()则就是nums的初始位置，它们返回的是迭代器！

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

   vector<int> nums;
   //size访问
for (int i = 0; i<nums.size(); ++i)
{

	cout << nums[i] << endl;
}

//第二种遍历方式，迭代器
for (vector<Point>::iterator iter = nums.begin(); iter != nums.end(); iter++)
{
	cout << (*iter) << endl;
}

//第三种遍历方式，auto关键字
for (auto iter = nums.begin(); iter != nums.end(); iter++)
{
	cout << (*iter) << endl;
}

//第四种遍历方式，auto关键字的另一种方式
for (auto i : m_testPoint)
{
	cout << i<< endl;
}

  nums.back()返回的是最后一个元素。nums.front()返回的是vector第一个元素。vector.clear()清空容器。

二分法（704题）

二分法注意

  注意是用闭开区间还是闭区间（选择任意）。

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 search(vector<int>& nums, int target) {
      //左闭右闭  还是左闭右开
      int right = nums.size()-1;//右开这里去掉减一
      int left = 0;
      int middle =0;
      while(left<=right)//右开这里不取等于
      {
        middle=(left+right)/2 ;
        if(nums[middle]<target)
        {
          left = middle+1;
        }
        else if(nums[middle]>target)
        {
          right = middle-1;//因为右边是闭区间，所以减一；右开这里去掉-1
        }
        else
        {
          return middle;
        }
      }
      return -1;
    }
};

如何实现二维数组（leetcode 59）

vector

  1. vector< vector< int >> vec(行数, vector< int >(列数));
  2. vector< vector< int >> vec(行数, vector< int >(列数, 初始值));
  3. vector< vector< int >> vec; vec.resize(行数); vec[i].resize(列数); vec[i] = {值};

    stack定义法

1
2
3
4
5
6
7
8

int array[M][N];

void setarray(array[M][N])
{
    //M可以省略，N必须存在
}

heap定义法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int** array = new int*[M];//或(int**)malloc(M*sizeof(int*));双指针可以保证arry[i]是int*类型
for(int i=0;i<M;i++)
{
    array[i]=new int[N];
}

void func(int** arr,int M,int N)
{
    //访问矩阵
}

//释放内存

for(int i=0;i<M;i++)
    delete[] array[i];
delete[] array;


删除一个链表节点（LCR 136）

暴力

  在题目给出双指针的情况下，可以考虑这种方法。并且需要单独考虑删除头节点、尾节点、中间节点。

添加虚拟节点

  再创一个虚拟节点，将头节点作为虚拟节点的下一个节点，这样仅需要考虑删除中间节点与最后一个节点的情况了。（注意给节点命名是不要用典型的名字）圣经式方法。

递归实现反转链表（leetcode 206）

1
2
3
4
5
6
7
8
9
10
11
12
13

ListNode* reverse1(ListNode* current,ListNode* pre)
{
    if(current==nullptr)
    {
        return pre;
    }
    ListNode* temp = current->next;
    current->next=pre;
    return reverse1(temp,current);

}

反转链表注意最后一行代码，return回收数据。

利用STL迭代器指针进行相互转化

vector与unordered_set

给定一个unordered_set，如何将其转化为vector？
反之给定一个vector，怎样将其转化为unordered_set?
vector< typename > name(初始迭代器，末尾迭代器)；

1
2
3
4

unordered_set<int> nums1={1,2,3};
vector<int> nums2(nums1.begin(),nums1.end())

反之一样成立。注意，把数据存在set中，set自动排序

排序

插入排序

最小为O(n),最大为O(n^2)，平均为O(n^2)，空间复杂度O(1),稳定。
对于基本排好序的数据来说，插入排序很快。

希尔排序

最坏复杂度为O(nlogn)，空间复杂度O(1)不稳定。

堆排序

最坏为O(nlogn),空间复杂度O(1),不稳定。

快速排序

在极端情况下，很有序（正或逆）效率很低。数据很乱就很快。
平均复杂度O(nlogn),最坏O(n^2)，空间复杂度O(nlogn)，不稳定。

归并排序

平均复杂度O(nlogn),最坏O(n^2),空间复杂度O(n)，稳定。