源之居
0%

算法题笔记

发表于 更新于 分类于

开始暑假的集中刷题了，时隔两个月没刷算法，今天发现之前获得的手感和技巧都丧失的差不多了，所以萌生了记笔记的想法。记下一些有价值的题目

LeetCode Easy

剑指offer 05 替换空格

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
class Solution {
public:
    string replaceSpace(string s) {
        
        int length=s.size();
        int count=0;
        for(int i=0;i<length;i++){
            if(s[i]==' ')
            count++;
        }
        s.resize(length+2*count);
        int old=length-1;// 从后向前替换 双指针
        int n=length+2*count-1;//n为new 
        while(old>=0){
            if(s[old]==' '){
                s[n--]='0';
                s[n--]='2';
                s[n--]='%';
            }
            else{
                s[n--]=s[old];
            }
            old--;
        }
        return s;    
    }
};

精髓在于，从后向前替换，而不是从前向后替换，后者做法每次替换都要移动后面元素 o(n^2),前者不需要 o(n);因为 从后向前，n走在old后面(相对于前进方向)，从前向后n在old的前面，s[n]依靠s[old],因此 n应该在old后面。

35 搜索插入位置

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int length=nums.size();
        int left=0;
        int right=length-1;
        int mid=left+(right-left)/2;

        while(left<=right){
            int now=nums[mid];
            if(now<target) left=mid+1; 
            else if(now>target) right=mid-1;
            else return mid;
            mid=left+(right-left)/2;
        }
        
        return right+1; 

    }
};

这道题目我的犹豫点在于循环的时候target是否会落在获得的区间之外，比如[0，100，110，200] target=102,第一次迭代后，nums[left]=110；target其实在left的左边，因此在二分处理的时候一直思考很多限制，一个简单的Easy题目却想了很多。后来想明白了，我的犹豫点是对的，但是这不影响什么。

这道题目，可以找到和target相等的目标值也就罢了（704题），找不到也就是需要插入的时候，要把target插入在两个数字中间的区域，这种情况下 按照从大到小排序，某次迭代后target一定会落在获得的区间旁边的区域，也就是right和right+1之间或者left和left-1之间，此后紧挨着target的区间边界left/right不动，另一个边界不断移动，直到 right小于left ,此时迭代终止，而target的位置等于right+1也就是在right和left之间；

二分加暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int length=nums.size();
        int left=0;
        int right=length-1;
        int temp=right-left;
        while(temp>2){
            int mid=left+temp/2;
            int now=nums[mid];
            if(now<target) left=mid+1;
            else if(now>target) right=mid-1;
            else return mid;
            temp=right-left;
        }
        for(int i=left;i<=right;i++){
            if(nums[i]>=target) return i;
        } //这个暴力写法很优雅。
        return right+1;
    }
};

仅仅在区间很小的时候采用了暴力，这可能会更高效一点。

27 移除元素

快慢双指针

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

        return left;

    }
};

本质上是，将两个指针看成在两个相同的数组上操作，而不是一个数组，快指针right将自己所在的数组上的所有不等于val的数值移动到慢指针所在的数组上，(0，right)开区间内的点都!=val。

双指针优化 前后双指针

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

        return left;

    }
};

用后指针指向的元素替换前指针指向的需要删除的元素，直到两指针相遇后进入最后一次循环。

LeetCode Mid

59 螺旋矩阵||

便于理解带注释

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop_times = n / 2; // 一圈处理两层，需要循环几圈，例如n为奇数3，那么loop_times = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
        int i,j;
        while (loop_times --) {
            i = startx;
            j = starty;//竖着为x 横着为y  y轴上是同一个一维数组的。

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < starty + n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < startx + n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 2;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

习惯写法

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> answer(n,vector<int>(n,0));
        int loop_times=n/2;
        int end=n/2;
        int start_x=0;
        int start_y=0;
        int number=1;
        int cut_length=1;
        int x,y;
        while(loop_times--){
            x=start_x;
            y=start_y;

            for(;y<n-cut_length;y++){
                answer[x][y]=number++;
            }
            for(;x<n-cut_length;x++){
                answer[x][y]=number++;
            }
            for(;y>cut_length-1;y--){
                answer[x][y]=number++;
            }
            for(;x>cut_length-1;x--){
                answer[x][y]=number++;
            }

            start_x++;
            start_y++;
            cut_length++;
        }

        if(n%2){
            answer[end][end]=number;
        }

        return answer;

        
    }
};

这道模拟有点意思，像这种模拟我一直不太在行，打印乘法表这种大一C++作业题我都有点怵，菜鸡本菜了。

142 环形链表||

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        if(head==nullptr||head->next==nullptr) return nullptr;
        slow=slow->next;
        fast=fast->next->next; 
        while(fast!=nullptr&&fast->next!=nullptr&&slow!=fast){
            slow=slow->next;
            fast=fast->next->next;
        }//fast指针经过的长度 是 slow经过的长度的 2 倍数
        if(fast==nullptr||fast->next==nullptr) return nullptr;
        slow=head; //slow从头节点开始 fast从两者在环上相遇的位置开始 两者到入口处长度相等(解方程可得该信息
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return fast;

    }
};

经典快慢指针做法，后面找环入口用到简单的数学知识。应该设长度，而不是节点数目。

15 三数之和

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:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int length=nums.size();
        vector<vector<int>> answer;
        if(length<3) return answer;
        sort(nums.begin(),nums.end());
        
        
        for(int cur=0;cur<length;cur++){
            if(nums[cur]>0) return answer;
            int left=cur+1;
            int right=length-1;
            if(cur>0&&nums[cur]==nums[cur-1]) continue;// 避免排除 -1 -1 2 这种正确情况 cur 在重复序列的第一个
            // cur重复且nums[cur]对应有正确结果 则会出现重复答案，cur不重复且固定 只考虑left重复，结果一样，cur left 不重复且固定，只考虑right重复，结果也可能重复。
            // 故三种情况均需要去重  
            while(left<right){
                
                if(nums[cur]+nums[right]+nums[left]>0){
                    right--;//nums[right] 变为新的数值，但在right=length-1或者上一个判断循环满足三者相加等于0时，不一定变为新的数值，在下一次循环时候才会变化
                    while(left<right&&nums[right]==nums[right+1]) right--;// right位置移动到 (新的)重复的序列的 第一个位置，若为最后一个位置，则排除了nums[right]==nums[left]的正确结果
                }
                else if(nums[cur]+nums[right]+nums[left]<0){
                    left++;
                    while(left<right&&nums[left]==nums[left-1]) left++;
                }
                else{
                    answer.push_back(vector<int>{nums[cur],nums[left],nums[right]});
                    while(left<right&&nums[right]==nums[right-1]) right--;// 去掉right重复，right移动到重复序列的最后一个位置,此时为最后一个是因为 已经符合结果 需要更新数值避免重复。
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    
                    right--; //nums[right]变为新的数值 
                    left++;
                }
            }

        }
        return answer;
    }
};

双指针，去重麻烦。

四数之和

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
52
53
54
55
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
	    // 剪枝处理
            if (nums[k] > target && (nums[k] >= 0 || target >= 0)) {
            	break; // 这里使用break，跳出循环
            }
            // 去重 k移动到新的重复序列的最左端 nums[k] 更新, 并且避免排除 -1 -1 -1 3 target为0的正确答案
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
	    	// 2级剪枝处理
		        if (nums[k] + nums[i] > target && (nums[k] + nums[i] >= 0 || target >= 0)) {
		            break; // 跳出 二级循环
		        }
		
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
                        right--;
                        // 当前元素不合适了，可以去重，right移动到新的重复序列的最右端，nums[right]更新
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if (nums[k] + nums[i]  < target - (nums[left] + nums[right])) {
                        left++;
                        // 不合适，去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;// right移动到旧重复序列的最左端
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;//此时nums[right]才更新
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

经典，需要背诵(×

151 颠倒字符串单词

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
class Solution {
public:
    
    void reverse(string& s,int begin,int end){
        while(begin<end){
            swap(s[begin++],s[end--]);
        }
    }// 翻转函数 左闭右闭

    string reverseWords(string s) {
        
        
        while(s[0]==' '){
            s.erase(s.begin());
            
        } // 清除前面的空格
    
        while(s[s.size()-1]==' '){
            s.erase(s.end()-1);
        }// 清除后面空格
        
        int cur=0;
        int length=s.size();
        
        int slow=0;
        reverse(s,0,length-1); // 整体字符串翻转
        
        while(cur<s.size()){ // 删除空格导致size动态变化 所以用s.size() 随时更新 而不是固定的数值
            if(s[cur]==' '){
                reverse(s,slow,cur-1); // 局部单词内部翻转
                slow=cur+1;
            }
            else if(cur==s.size()-1) reverse(s,slow,cur); // 局部最后一个单词翻转
            
            while(s[slow]==' '){
                s.erase(s.begin()+slow);
            }// 清除单词之间多余的空格
            
            cur++;
        }
        return s;
    }
};

巧妙之处在于，先整体翻转 后 局部反转，改变了单词的位置顺序 而 不改变单词内部的字母顺序。

不足之处在于，reverse时间复杂度为o(n)，加上外面循环o(n),一共为o(n^2)，优化的话可以采用双指针，提前清除所有多余空格，时间复杂度为o(n)，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int length=s.size();
int slow=0; 
int fast=0;
while(fast<length){
    if(s[fast]==' '){
        if(slow!=0&&s[slow-1]==' ') slow--;
        s[slow]=s[fast]; // 无法去除两端的空格，两侧存在至多一个空格。
    }
    else{
        s[slow]=s[fast];
    }
    slow++;
    fast++; // slow 和 fast 处理也巧妙，夸我一句。
}
if(s[slow-1]==' ') s.resize(slow-1);// 去除后面多余的一个空格
else s.resize(slow);

if(s[0]==' ') s.erase(s.beigin());

清除空格 时间复杂度o(n)