首页 > > 程序设计 > C/C++ >

LeetCode 1,20,26,27,38,48

2018-06-17 21:27:36来源：未知阅读 ()

Python写多了 C++都不会写了

开始刷LeetCode, 从easy刷起

1. Two Sum

比较简单用一个hash可以做到O(n), 可以用STL中unordered_map。

unordered_map与map还是有本质区别的，关于map详见 https://www.cnblogs.com/ranjiewen/p/5901296.html

里面还有pair和make_pair的介绍，以后应该用的到。

20. Valid Parentheses

栈的应用，没什么好说的

26. Remove Duplicates from Sorted Array

27. Remove Element

比较简单，记录下标 a[i++]= ...

38. Count and Say

字符串操作，注意数字到字符可以用 to_string() 函数

48. Rotate Image

矩阵顺时针旋转90度，主要有两种解法：

1. 直接旋转

我最头疼的还是坐标的变换。我的思路如下：

在(0,0)为原点的坐标轴中 (x,y)->(y,-x)

而二维数组中的某个坐标(i,j)是要以((n-1)/2,(n-1)/2)为圆心旋转，因此旋转后坐标为 (j,n-1-i)

迭代得出 (i,j) -> (j,n-1-i)

| |

(n-1-j,i) <- (n-1-i,n-1-j)

写循环时，由外到内第一层也就是第一行，为i

第二层循环时第i行的第j个元素，注意j的边界条件可以根据n=3，n=4 总结

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for (int i=0;i<n/2;++i){
            for (int j=i;j<n-i-1;++j){
                int tmp=matrix[i][j];
                matrix[i][j]            = matrix[n-1-j][i];
                matrix[n-1-j][i]        = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j]    = matrix[j][n-1-i];
                matrix[j][n-1-i]        = tmp;
            }
        }
    }
};

2. 分两步旋转

这里方法比较多，可以先转置矩阵，然后每行反一反，也可以先上下反一反，再转置。（建议画个坐标轴判断一下对不对）

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        
        // first transpose, then reverse each row
        for (int i=0;i<n;++i){
            for (int j=i+1;j<n;++j){
                swap(matrix[i][j], matrix[j][i]);
            }
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(),matrix.end());
        
        int n=matrix.size();
        for (int i=0;i<n;++i){
            for (int j=i+1;j<n;++j){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};