信息

发表于 | 分类于

判断浮点数a,b是否相等
if(a==b)
if(fabs(a=b)<1e-9)

判断是否是奇数
x%2!=0 更好
x%2==1(不能判断负数)

vector

int n;
cin>>n;
int a[n];

vector num；

###027 移除元素
双指针，一次扫描
设置两个指针 分别
fornt tail
思路：front和tail分别从前后向中间扫描，当两个指针相遇，就结束。
如果两个指针没有相遇
if（front<tail）
移动frnot,如果遇到了A[front]==val,暂停
移动tail，如果我们遇到了一个不是val,把值复制给A[front]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int front=0;
        int tail=nums.size()-1;
        while(front<=tail)
        {
            if(nums[front]==val  &&  nums[tail]!=val)
            {
                nums[front]=nums[tail];
                nums[tail]=val;
            }
            if(nums[front]!=val)
                front++;
            if(nums[tail]==val)
                tail--;
        }
        return tail+1;
    }
};

双指针，顾名思义，就是利用两个指针去遍历数组，
一般来说，遍历数组是采用一个指针，而两个指针就是一般在有序数组中使用，一个放在头部，一个放在尾部，同时向中间走，直到两个指针相交。
front=0;
tail=A.size()-1;

一般的循环结束条件、
while(front<tail)
{
……
}

in place 不额外开数组（不用额外的空间）

1 两数之和

思路1：双重循环 o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;//动态数组
        
        for(int i=0;i<nums.size();i++)
        {
             for(int j=i+1;j<nums.size();j++)
             {
                 if(nums[i]+nums[j]==target)
                 {
                     result.push_back(i);
                     result.push_back(j);
                     return result;
                 }
             }
        }
    }
};

思路2：
双指针

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
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;//动态数组
        
        vector<int> n=nums;//backup
        
        sort(nums.begin(),nums.end());//已经完成排序
        
        int front=0;
        int tail=nums.size()-1;
        
        while(front<tail)
        {
            if(nums[front]+nums[tail]==target)
            {
                
                for(int i=0;i<n.size();i++)
                {
                    if(nums[front]==n[i])
                    {
                        result.push_back(i);
                        break;
                    }
                }
                    
                
                 for(int i=n.size()-1;i>=0;i--)
                 {
                     if(nums[tail]==n[i])
                    {
                        result.push_back(i);
                         break;
                    }
                 }
                    
                
                return result;
            }
            
            if(nums[front]+nums[tail]>target)
                tail--;
            else
                front++;
        }
        
        return nums;
    }
};

思路3：利用hashmap优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       //用hashmap O(1) c++ unorder_map 实现键值对应
        vector<int> res;
        unordered_map<int,int> map;
        int tmp;
        for(int i=0;i<nums.size();i++)
        {
            tmp=target-nums[i];
            unordered_map<int,int>::iterator it =map.find(tmp);
            if(it != map.end())
            {
                return vector<int>({it->second,i});
            }
            map[nums[i]]=i;
        }
    }
};

15 三数之和

思路1 三重循环，容器判重
思路2
随机确定了一个数 a –》在剩下的数，找2个数，和0-a

1.数组中允许重复的数
2.结果按照升序排序
3.不能出现重复 在操作前，首先进行排序

l m r

如何确定第一个数left？肯定是第一层循环，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int l=0;l<nums.size()&&nums[l]<=0;l++)

接下来，确定mid和right

m=l+1;
r=nums.size()-1;
while(m<r)
{
    //....
    int tmp=0-nums[l];
    if(nums[m]+mums[r]==tmp)
    {
        //加入结果集
    }
    else if(nums[m]+nums[r]>tmp)
        r--;
    else
        m++;
}

//不能判重
如果l指向的是前面判断过的，跳过，
如果m和r在往中间移动的时候，是刚才的数，跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
m=l+1;
r=nums.size()-1;
while(m<r)
{
    //....
    int tmp=0-nums[l];
    
    if(left>0 && nums[left]==nums[left-1])
        continue;
    
    if(nums[m]+mums[r]==tmp)
    {
        //加入结果集
        
        //判断m,r
        while(m<r && nums[m+1]==nums[m]) m++;
        while(m<r && nums[r-1]==nums[r]) r--;
    }
    else if(nums[m]+nums[r]>tmp)
        r--;
    else
        m++;
}

AC代码

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
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> list;
        
        int m,r;
        
        for(int l=0;l<nums.size()&&nums[l]<=0;l++)
        {
            m=l+1;
            r=nums.size()-1;
            
            int tmp=0-nums[l];
            
            if(l>0 && nums[l]==nums[l-1])
                continue;
            
            while(m<r)
            {
   
                if(nums[m]+nums[r]==tmp)
                {
                    //加入结果集
                    int t_m = nums[m],t_r=nums[r];
                    
                    vector<int> tmp;
                    tmp.push_back(nums[l]);
                    tmp.push_back(nums[m]);
                    tmp.push_back(nums[r]);
                    //cout<<nums[l]<<" "<<nums[m]<<" "<<nums[r]<<" "<<endl;

                    list.push_back(tmp);
                    //判断m,r
                    
                    
                    while(m<r && nums[++m]==t_m);
                    while(m<r && nums[--r]==t_r);
                    
                    
                }
                else if(nums[m]+nums[r]>tmp)
                    r--;
                else
                    m++;
            }

        }
        return list;
    }
};