这篇记录在学习算法过程中遇到的关于数组、矩阵的一些题目。

867 Transpose Matrix

题目描述

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

题目解析

求矩阵A的转置A’，对应矩阵的元素，A’[i][j] = A[j][i]

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        vector<vector<int>> ans(A[0].size(),vector<int>(A.size(),0));
        for(int i=0;i<A.size();i++)
            for(int j=0;j<A[i].size();j++)
                ans[j][i] = A[i][j];
        return ans;
        
    }
};

优化

提交之后看到一种算法，对行数和列数相同和不同的矩阵分别有不同的处理，对于行数和列数不相同的矩阵，在ans初始化时就对应push_back A中相应的元素：

n=A.size();
m=A[0].size();
if(n!=m)
        {
            vector<vector<int>>ans(m);
            for(j=0;j<m;j++)
            {
                for(i=0;i<n;i++)
                    ans[j].push_back(A[i][j]);
            }
            return ans;
        }

对行数和列数相同的矩阵来说，其实求转置矩阵就是以对角线为中心，来交换对应的元素，而且在遍历过程中，每次行数增加，在对应列数的循环上可以少遍历一个元素，因为在上一行已经交换过了，就是col起的作用。

int col=0;
for(i=0;i<n;i++)
        {
            for(j=col;j<m;j++)
            {
                temp=A[i][j];
                A[i][j]=A[j][i];
                A[j][i]=temp;
            }
            col++;
        }
        return A;

806 Number of Lines To Write String

题目描述

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

题目解析

数组widths给出了26个小写字母每个字母所占的宽度，一行的宽度为100，给定字符串S，按照widths对应宽度进行排列，如果一行中的空闲宽度不足以放下字符S[i]，S[i]就放在下一行，最后返回的是总的行数和最后一行已用的宽度。
思路：遍历字符串，每次进行判断，总宽度是否大于100，若大于100，就换下一行，行数加一；否则只累加字符宽度。

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string S){
        vector<int> ans = {1,0};
        for(int i=0;i<S.size();i++){
            if(ans[1] + widths[S[i]-'a'] > 100){
                ans[0] += 1;
                ans[1] = widths[S[i]-'a'];
            }
            else
                ans[1] += widths[S[i]-'a'];
        }

        return ans;
}
};

766 Toeplitz Matrix

题目描述

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

题目解析

判断矩阵的对角线元素是否相等，若相等，返回true，否则返回false。

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        for(int i=0;i<matrix.size()-1;i++)
            for(int j=0;j<matrix[i].size()-1;j++){
                if(matrix[i][j] != matrix[i+1][j+1])
                    return false;
        }
        return true;
        
    }
};

463 Island Perimeter

题目描述

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

题目解析

给定一个二维数组，1代表陆地，0代表水，计算由水围成的岛屿的周长。
如果不是边缘的陆地，就会有重复的边。可以先重复累加边，每一块陆地增加4，然后对每一块陆地进行判断，如果它的上、下、左、右是否为陆地，如果是陆地，每有一块陆地，总边数就要减1。

class Solution {
public:
    int islandPerimeter(vector<vector<int> >& grid) {
        ios::sync_with_stdio(0),
        cin.tie(0), cout.tie(0);
        int ans = 0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j] == 1){
                    ans += 4;
                    ans -= islandNeighbor(grid,i,j);
                }
            }
        }
        return ans;
        
    }
    
    int islandNeighbor(vector<vector<int> >& grid,int row,int col){
        int sum = 0;
        if(row - 1 >= 0) //up
            sum += grid[row-1][col];
        if(row + 1 < grid.size()) //down
            sum += grid[row+1][col];
        if(col - 1 >= 0) //left
            sum += grid[row][col-1];
        if(col + 1 < grid[row].size()) //right
            sum += grid[row][col+1];
        return sum;
    }
    
};