leetcode 刷题挑战之 数组

704. 二分查找

• 学习了 vector 的用法
  • 需要在开头声明 #include <vector>.
  • vector<int> nums;.
  • 不能直接把数组的值输入到 vector 中, 要通过循环来 pushback 到 vector 中去.
  • int search(vector<int>& nums) 其中带一个 & 是传引用的意思.
• 关键是处理边界问题, 我默认会选择左闭右闭的情况:
  • int left = 0; int right = nums.size() - 1;.
• 最终代码:

// 给定升序序列，通过二分法查找目标值
#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            int middle = (left + right) / 2;
            if (target < nums[middle])
            {
                right = middle - 1;
            }
            else if (target > nums[middle])
            {
                left = middle + 1;
            }
            else
            {
                return middle;
            }
        }
        return -1;
    }
};

int main()
{
    Solution s;
    int a[10] = {1, 3, 4, 5, 6, 7, 8, 9, 10, 10};
    vector<int> nums;
    for (int i = 0; i < 10; i++)
    {
        nums.push_back(a[i]);
    }
    //vector<int> b(a,a+2);

    int target = 5;
    int res = s.search(nums, target);
    cout << "Location is " << res << endl;
    return 0;
}

27. 移除元素

• 有两种方法
  • 嵌套循环暴力解法
  • 双指针
• c++没有直接获取数组长度的函数, 可以在累开头定义一个模板

tampate <class T>

int getArrayLen(T& array)
{
  return (sizeof(array)/sizeof(array[0]));
}

• 最终代码:

#include <iostream>
#include <vector>
using namespace std;
// 暴力解法
class Solution1
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int size = nums.size();
        for (int i = 0; i < size; i++)
        {
            if (nums[i] == val)
            {
                for (int j = i + 1; j < nums.size(); j++)
                {
                    nums[j - 1] = nums[j];
                }
                i--;
                size--;
            }
        }
    }
};
// 双指针法
class Solution2
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

int main() {
    Solution2 s2;
    int array[10] = {1,2,3,4,5,6,7,8,9,10};
    int size = sizeof(array) / sizeof(array[0]);
    vector<int> nums;
    for (int i = 0; i < size ; i++)
    {
        nums.push_back(array[i]);
    }
    int val = 4;
    int res = s2.removeElement(nums,val);

    cout << "The new lenth of the array is :" << res << endl;
    cout <<  size << endl;
    return 0;
}

977. 有序数组的平方

• vector<int> result(A.size(), 0) 创建一个长度和 A 样的 vector, 并且初始值为 0.

• 因为对vector<int> sortedSqaures(vector<int>& A)引用传参有疑问, 我尝试在函数调用前后向量 A 的值, 结果发现是一样的. 所以决定写一个小程序来验证传引用的效果.

  • 经过验证, 需要在函数体内对形参再赋值. 赋值后, 函数执行完毕, 实参也会发生改变.

• 最终代码:

#include <iostream>
#include <vector>
using namespace std;
// 暴力解法
class Solution
{
public:
    vector<int> sortedSquares(vector<int> &A)
    {
        for (int i = 0; i < A.size(); i++)
        {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end());
        return A;
    }
};
// 双指针法
class Solution2
{
public:
    vector<int> sortedSquares(vector<int>& A)
    {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;)
        {
            if (A[i] * A[i] > A[j] * A[j])
                {
                    result[k--] = A[i] * A[i];
                    i++;
                }
                
            else
            {
                result[k--] = A[j] * A[j];
                j--;
            }
            
        }

        return result;
    }
};

int main() {
    Solution2 s2;
    int a[10] = {-4,-3,-2,-1,0,1,2,3,4,5};
    vector<int> nums;
    for (int i = 0; i<10; i++) {
        nums.push_back(a[i]);
    }
    cout << "The original vector:" << nums[0] << endl;
    cout << "Start to ouput the result vector: " << endl;
    vector<int> res = s2.sortedSquares(nums);
    for ( int i = 0; i < 10; i++) {
        cout << res[i] << endl;
    }
    
    cout <<"The calculated result vector: " <<nums[0] << endl;
}

209. 长度最小的子数组

C++函数返回一个数组

• 做这个题之前, 我想要写一个单独的文件来存储一个函数. 这个函数可以生成一个随机的数组. 然后可以把这个数组 pushback 到一个 vector 中去. (现在回想起来, 未尝不可直接生成一个 vector, 反而要简单很多. 不过, 探索数组的过程, 我也再次复习了一遍指针.)
• 回想一下, 数组之所以不能作为函数的返回值, 是因为数组的本质是一个指针. int arr = new arr[4], 这里的 arr 作为一个指针实际指向的是数组的第一个元素. arr == 0x7ffeefbff450 . 并且*arr 取的是数组的第一个元素, *(arr + 1) 得到的是第二个元素, 因为数组在内存上是连续的, 又由于这是一个 int 数组, 所以二者的地址差别应该是 4 个字节, 即 32 bits.

#include <iostream>

using namespace std;

int main()
{
    int  var[5] = {1,2,3,4,5};   // 实际变量的声明
    int  *ip;        // 指针变量的声明

    ip = var;       // 在指针变量中存储 var 的地址

    cout << "Value of var variable: ";
    cout << var << endl; // Value of var variable: 0x7ff7b6c3f720
		
    // 输出在指针变量中存储的地址
    cout << "Address stored in ip variable: "; 
    cout << ip << endl; //Address stored in ip variable: 0x7ff7b2202720

    // 访问指针中地址的值
    cout << "Value of *ip variable: ";
    // *ip = 30;
    *var = 30;
    cout << *ip << endl; // Value of *ip variable: 30
    cout << var << endl; // 0x7ff7b2202720
    cout << var[0] << endl; // 30

    system("pause");
    return 0;
}

• 下面 &height[0] 就是取得是数组第一个元素的地址，假设地址为 1000；&height 是直接对数组名进行取地址，这个时候就是取得是 height 整个数组的地址，指向包含 10 个元素的 int 型数组，地址范围为 1000~1036；
• 我们知道 height 等价于 &height[0]，height+1 会将地址加 4 个字节；但 &height+1 就是将地址增加 10*4 个字节。

int height[10];//int型的数组
cout << &height << endl;//&用在数组名上
cout << &height[0] << endl;//&用在数组第一个元素上

• 如果想返回一个数组, 则可以返回一个指针数组:

#include <iostream>

using namespace std;

float* MultMatrix(float A[4], float B[4])
{
    float *M = new float[4];
    M[0] = A[0]*B[0] + A[1]*B[2];
    M[1] = A[0]*B[1] + A[1]*B[3];
    M[2] = A[2]*B[0] + A[3]*B[2];
    M[3] = A[2]*B[1] + A[3]*B[3];
    cout << M[0] << " " << M[1] << endl;
    cout << M[2] << " " << M[3] << endl;

    return M; // M 是一个指针
}

int main()
{
    float A[4] = { 1.75, 0.66, 0, 1.75 };
    float B[4] = {1, 1, 0, 0};
    float *M = MultMatrix(A, B);
    cout << M[0] << " " << M[1] << endl;
    cout << M[2] << " " << M[3] << endl;
    delete[] M;

    return 0;
}

题目解答

• int minlength = INT32_MAX; 是因为要取一个比数组长度大的数, 这样能保证在给最小长度赋值的时候, 可以包含全部的数字长度. 因此, 及时int minlength = nums.size() + 1 应该也是可取的.
• 最终代码:

#include<iostream>
#include<vector>
#include "RandomArray.cpp"
using namespace std;
class Solution {
    public:
    int minSubArrayLength(int target, vector<int>& nums) {
        int minlength = INT32_MAX;
        int length = 1;
        int sum = 0;
        int start =  0;
        for(int i = 0; i < nums.size(); i++) {
            sum = sum + nums[i];
            // 这里必须是 while 循环, 因为如果下一个加的nums[i] 是一个很大的数, start 可能
            // 会往后移动多次
            while(sum >= target) {
                length = i - start + 1;
                sum = sum - nums[start];
                start++;         
                // 最小值必须在循环内赋值, 如果在 for 循环里, 会赋值为 1, 也就是初始值.       
                minlength = minlength < length ? minlength : length;
            }
            
        }
        return minlength == INT32_MAX ? 0 : minlength;

    }
};
int main () {
    Solution s1;
    int array[] = {2,3,4,0,1};
    int size = sizeof(array) / sizeof(array[0]);
    vector<int> nums;
    for (int i = 0; i < size ; i++)
    {
        nums.push_back(array[i]);
    }
    int s = 8;
    int res = s1.minSubArrayLength(s,nums);
    cout << res << endl;
}

59. 螺旋矩阵

• n x n 的二维 vector 的初始化

vector< vector<int> > res(n, vector<int>(n,0)) // n 是长度, 0 是初始值.

• 解题思路就是左闭右开的走法, 从左上角开始走, 每一次走都留最后一格. 然后下一次走把最后一格作为起点. 然后每走完一圈, 到坐上角的右下方的格子, 这时候起点相当于比一开始加 1. 后面也是一样. 每多走一圈, 起点就加 1. 并且每走一圈相当于上下各减 1 的长度, 即减 2 的长度, 所以一共会走 n/2 圈. 奇数 n 需要考虑最中间的一格单独加上值.
• 最终代码

#include <iostream>
#include <vector>

using namespace std;

class Solution1
{
public:
    vector<vector<int> > generateMatrix(int n)
    {
        vector<vector<int> > res(n, vector<int>(n, 0));
        int loop = n / 2;
        int start_x = 0;
        int start_y = 0;
        // 起始数字从 1 开始
        int count = 1;
        // 奇数情况, 要单独定义一下最中间的数
        int mid = (n - 1) / 2;

        while (loop--)
        {
            // (0,0) -> (0,n-2)
            for (int i = start_y; i < n - start_y - 1; i++)
            {
                res[start_x][i] = count++;
            }
            // (0,n-1) -> (n-2,n-1)
            for (int j = start_x; j < n - start_x - 1; j++)
            {
                res[j][n - start_y - 1] = count++;
            }
            // (n-1,n-1) -> (n-1,1)
            for (int i = n - start_y - 1; i > start_y; i--)
            {
                res[n - start_x - 1][i] = count++;
            }
            // (n-1,0) -> (1,0)
            for (int j = n - start_x - 1; j > start_x; j--)
            {
                res[j][start_y] = count++;
            }
            start_x++;
            start_y++;
        }
        // 如果为奇数, 要单独给最中间的赋值

        if (n % 2)
        {
            res[mid][mid] = n * n;
        }
        return res;
    }
};

class Solution2
{
public:
    vector<vector<int> > generateMatrix(int n)
    {
        vector<vector<int> > res(n, vector<int>(n, 0));
        int loop = n / 2;
        // x 和 y 的起点都是每次递增一次, 所以可以只定义一个开始.
        int start = 0;
        // 起始数字从 1 开始
        int count = 1;
        // 奇数情况, 要单独定义一下最中间的数
        int mid = (n - 1) / 2;

        while (loop--)
        {
            // (0,0) -> (0,n-2)
            for (int i = start; i < n - start - 1; i++)
            {
                res[start][i] = count++;
            }
            // (0,n-1) -> (n-2,n-1)
            for (int j = start; j < n - start - 1; j++)
            {
                res[j][n - start - 1] = count++;
            }
            // (n-1,n-1) -> (n-1,1)
            for (int i = n - start - 1; i > start; i--)
            {
                res[n - start - 1][i] = count++;
            }
            // (n-1,0) -> (1,0)
            for (int j = n - start - 1; j > start; j--)
            {
                res[j][start] = count++;
            }
            start++;
        }
        // 如果为奇数, 要单独给最中间的赋值

        if (n % 2)
        {
            res[mid][mid] = n * n;
        }
        return res;
    }
};

int main()
{
    Solution2 s2;
    int n = 6;
    vector<vector<int> > res = s2.generateMatrix(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << res[i][j] << " ";
        }
        cout << "\n"
             << endl;
    }

    return 0;
}