题目描述:

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example, Given n = 3,

You should return the following matrix:

[
  [ 1, 2, 3 ],
  [ 8, 9, 4 ],
  [ 7, 6, 5 ]
]

螺旋输出序列. 首先用一个循环, 在循环体内填充一圈数字, 直到所有位置填满.

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int> > ret(n, vector<int>(n, 0));
        if(n == 0)return ret;
        int a = 1;
        for(int i = n; i > 0; i-=2){ // 圈数应为n/2
            if(i == 1 && n % 2 == 1){ // 当n为奇数时, 最内圈只有一个元素
                ret[(n - i) / 2][(n - i) / 2] = a++;
                break;
            }
            for(int j = (n - i) / 2; j < n - (n - i) / 2 - 1; j++) // 填充上边的行
                ret[(n - i) / 2][j] = a++;
            for(int j = (n - i) / 2; j < n - (n - i) / 2 - 1; j++) // 填充右边的列
                ret[j][n - (n - i) / 2 - 1] = a++;
            for(int j = n - (n - i) / 2 - 1; j > (n - i) / 2; j--) // 填充下边的行
                ret[n - (n - i) / 2 - 1][j] = a++;
            for(int j = n - (n - i) / 2 - 1; j > (n - i) / 2; j--) // 填充左边的列
                ret[j][(n - i) / 2] = a++;
        }
        
        return ret;
    }
};

题目描述:

Given a string s consists of upper/lower-case alphabets and empty space characters ’ ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, Given s = “Hello World”, return 5.

找出一个字符串中最后一个单词的长度, 没有什么好说的, 从后往前搜索.

class Solution {
public:
    int lengthOfLastWord(string s) {
        int end = s.size();
        if(end == 0)
            return 0;
        for(; end >= 1 && s[end - 1] == ' '; end--); // 跳过结尾的空格
        int i;
        for(i = end - 1; i >= 0 && s[i] != ' '; i--);
        return end - i - 1;
    }
};

题目描述:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

向一个已经按照start排好序的区间数组中插入新区间, 问题分为两个部分:

1. 找到插入位置
2. 确定区间是否需要合并, 如何合并

用语言来说还是不太好说清楚, 还是看注释吧.

/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> ret;
        if(intervals.empty()){ // 如果intervals为空就返回只包含newInterval的数组
            ret.push_back(newInterval);
            return ret;
        }
        int i;
        // 以下循环用于跳过所有end小于newInterval.start, 也就是所有小于newInterval并且
        // 与newInterval没有交集的区间
        for(i = 0; i < intervals.size() && intervals[i].end < newInterval.start; i++);
        // 如果i == intervals.size(), 说明所有元素都小于newInterval, 把它插入到最后即可
        if(i == intervals.size()){
            intervals.push_back(newInterval);
            return intervals;
        }
        int j = i;
        // 将要插入的新区间
        Interval t;
        // 此时j = i, intervals[j]是end >= newInterval.start的第一个元素,但它们的start
        // 关系还不确定, 因此要插入的start值是intervals[j].start和newInterval.start中较
        // 小的一个
        t.start = min(intervals[j].start, newInterval.start);
        // 寻找start > newInterval.end的元素, 该元素之前的元素是要与newInterval合并的区间
        for(; j < intervals.size() && intervals[j].start <= newInterval.end; j++);
        // 如果j == intervals.size()说明i之后的所有区间都要与newInterval合并,
        // 所以t.end是newInterval.end和intervals.back().end中较大的值.
        // 然后删除intervals中i之后的元素(包括i, 因为i也与newInterval有交集),
        // 最后插入t
        if(j == intervals.size()){
            t.end = max(newInterval.end, intervals.back().end);
            intervals.erase(intervals.begin() + i, intervals.end());
            intervals.push_back(t);
            return intervals;
        }
        // 否则intervals[j - 1]是start <= newInterval.end的最后一个元素, 也就是与newInterval
        // 有交集的最后一个元素, t.end的值是newInterval.end和intervals[j - 1].end中较大的.
        // 从intervals中移除下标在[i, j-1]范围内的元素, 在i位置插入新区间t.
        else{
            t.end = max(newInterval.end, intervals[j - 1].end);
            intervals.erase(intervals.begin() + i, intervals.begin() + j);
            intervals.insert(intervals.begin() + i, t);
        }
        return intervals;
    }
};

题目描述:

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

合并(闭)区间, 区间以对象的形式给出. 首先将输入的区间数组按照start从小到大排序, 然后先取第一个元素放入结果集中, 从第二个元素开始遍历. 取当前区间为cur, 结果集中的最后一个元素为pre. 如果cur.start > pre.end, 说明cur与pre并无交集, 由于有序, 所以cur以后的区间与pre也都没有交集, 所以可以将cur放入结果集中. 如果cur.start <= pre.end, 说明有交集, 由于必然存在cur.start >= pre.start, 所以新区间的start等于pre.start, 只要考虑cur.end与pre.end的大小关系, 如果cur.end <= pre.end, 那么新区间与pre相同; 如果cur.end > pre.end那么要把pre也就是结果集的最后一个区间的end修改为cur.end.

/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> ret;
        if(intervals.empty()) return ret;
        sort(intervals.begin(), intervals.end(), [=](Interval &a, Interval &b){
            return a.start < b.start;
        });
        ret.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++){
            Interval cur = intervals[i], pre = ret.back();
            if(cur.start > pre.end){
                ret.push_back(cur);
            }
            else{
                if(cur.end > pre.end){
                    ret.back().end = cur.end;
                }
            }
        }
        return ret;
    }
};

题目描述:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

数组中的每个元素表示从当前下标可以向前跳的距离, 返回能不能到达最后一个下标. 从第一个元素开始记录从当前元素能到达的最远的下标值, 对之后的每个元素更新这个值, 如果该值小于当前下标则说明该下标无法到达.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int farthest = nums[0], i;
        for(i = 1; i < nums.size() && farthest >= i; i++){
            farthest = max(farthest, nums[i] + i);
        }
        if(farthest >= nums.size() - 1)
            return true;
        else
            return false;
    }
};

题目描述:

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
  [ 1, 2, 3 ],
  [ 4, 5, 6 ],
  [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

螺旋形输出一个矩阵, 我的方法就是螺旋形地遍历这个矩阵. 用一个变量来表示方向, 到达矩阵边缘的时候就更改方向.

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> re;
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return re;
        int m = matrix.size(), n = matrix[0].size(), num = m * n;
        vector<int> row(n, 0);
        vector<vector<int>> visited(m, row);
        int direction = 0;// 0 => right, 1 => down, 2 => left, 3 => up
        int posRow = 0, posCol = 0, cnt = 0;
        while (cnt < num) {
            int nextPosRow, nextPosCol;
            if(!visited[posRow][posCol]){
                re.push_back(matrix[posRow][posCol]);
                visited[posRow][posCol] = 1;
                cnt++;
            }
            bool nextPosValid = true;
            switch (direction) {
            case 0:
                nextPosRow = posRow;
                nextPosCol = posCol + 1;
                if (nextPosCol >= n || visited[nextPosRow][nextPosCol] == 1) {
                    nextPosValid = false;
                }
                break;
            case 1:
                nextPosRow = posRow + 1;
                nextPosCol = posCol;
                if (nextPosRow >= m || visited[nextPosRow][nextPosCol] == 1) {
                    nextPosValid = false;
                }
                break;
            case 2:
                nextPosRow = posRow;
                nextPosCol = posCol - 1;
                if (nextPosCol < 0 || visited[nextPosRow][nextPosCol] == 1) {
                    nextPosValid = false;
                }
                break;
            case 3:
                nextPosRow = posRow - 1;
                nextPosCol = posCol;
                if (nextPosRow < 0 || visited[nextPosRow][nextPosCol] == 1) {
                    nextPosValid = false;
                }
                break;
            }
            if(nextPosValid){
                posRow = nextPosRow;
                posCol = nextPosCol;
            }
            else{
                direction = (direction + 1) % 4;
            }
        }
        return re;
    }
};

题目描述:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

题目要求找出最大的连续子序列的和, 首先采用一种分治法. 对于一个数组, 把它中中间分成两半, 和最大的连续子序列可能出现在左半边, 可能出现在右半边, 也有可能出现跨越左右的情况. 对于在左半边或右半边的情况, 可以使用递归缩小问题, 对于跨越左右的情况, 可以使用线性算法来获得结果. 最后返回三个值中的最大值.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSub(nums, 0, nums.size());
    }

    int maxSub(vector<int>& nums, int left, int right) {
        if (right - left == 1) {
            return nums[left];
        }
        int leftSum, rightSum, mid = (left + right) / 2;
        leftSum = maxSub(nums, left, mid);
        rightSum = maxSub(nums, mid, right);

        int midLeftSum = 0, midLeftMaxSum = INT_MIN, midRightSum = 0, midRightMaxSum = INT_MIN;
        for (int i = mid - 1; i >= left; i--) {
            midLeftSum += nums[i];
            if (midLeftSum > midLeftMaxSum) midLeftMaxSum = midLeftSum;
        }
        for (int i = mid; i < right; i++) {
            midRightSum += nums[i];
            if (midRightSum > midRightMaxSum) midRightMaxSum = midRightSum;
        }
        int midSum = midRightMaxSum + midLeftMaxSum;

        return max(midSum, max(leftSum, rightSum));
    }
};

还可以使用动态规划法. 使用dp[i]来表示包含nums[i]的和最大的连续子串的和. 如果dp[i-1]是大于0的, 那么就可以加上dp[i-1], 因为nums[i]是必须有的. 用另一种方式来说, 这个题目的主要问题在于和最大的连续子串中可能出现负数, 要考虑的是负数及负数之前的子串要不要加到当前子串中来, 而这个判断就是看以该负数结尾的连续子串的和是否大于0, 如果小于0则不能加进来, 大于0则可以.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        int ret = nums[0];
        dp[0] = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
            if(ret < dp[i])
                ret = dp[i];
        }
        return ret;
    }
};

题目描述:

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

与上一题51. N-Queens基本类似, 但是要求返回共有多少个解, 对上一个程序稍加改动即可. 当然, 最投机取巧的做法是算出n=1到9的结果然后直接返回.

class Solution {
public:
    int totalNQueens(int n) {
        vector<vector<int>> board(n, vector<int>(n, 0));
        int re = 0;
        NQueensRow(n, board, 0, re);
        return re;
    }
    void NQueensRow(int n, vector<vector<int>> &board, int row, int &re) {
        if (row == n) {
            re++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (validPos(board, row, i)) {
                board[row][i] = 1;
                NQueensRow(n, board, row + 1, re);
                board[row][i] = 0;
            }
        }
    }

    bool validPos(vector<vector<int>> &board, int x, int y) {
        int n = board.size();
        for (int i = 0; i < n; i++) {
            if (board[x][i] && i != y)
                return false;
            else if (board[i][y] && i != x)
                return false;
        }

        int xt, yt;
        for (xt = x - 1, yt = y - 1; xt >= 0 && yt >= 0; xt--, yt--){
            if (board[xt][yt])
                return false;
        }
        for (xt = x + 1, yt = y + 1; xt < n && yt < n; xt++, yt++) {
            if (board[xt][yt])
                return false;
        }
        for (xt = x - 1, yt = y + 1; xt >= 0 && yt < n; xt--, yt++){
            if (board[xt][yt])
                return false;
        }
        for (xt = x + 1, yt = y - 1; xt < n && yt >= 0; xt++, yt--) {
            if (board[xt][yt])
                return false;
        }

        return true;
    }
};

题目描述:

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:

[
    [".Q..",  // Solution 1
    "...Q",
    "Q...",
    "..Q."],

    ["..Q.",  // Solution 2
    "Q...",
    "...Q",
    ".Q.."]
]

N皇后问题, 采用递归+回溯的方法, 依次穷举每一种情况.

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<int>> board(n, vector<int>(n, 0));
        vector<vector<string>> re;
        NQueensRow(n, board, 0, re);
        return re;
    }

    void NQueensRow(int n, vector<vector<int>> &board, int row, vector<vector<string>> &re) {
        if (row == n) {
            reItem(board, re);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (validPos(board, row, i)) {
                board[row][i] = 1;
                NQueensRow(n, board, row + 1, re);
                board[row][i] = 0;
            }
        }
    }

    bool validPos(vector<vector<int>> &board, int x, int y) {
        int n = board.size();
        for (int i = 0; i < n; i++) {
            if (board[x][i] && i != y)
                return false;
            else if (board[i][y] && i != x)
                return false;
        }

        int xt, yt;
        for (xt = x - 1, yt = y - 1; xt >= 0 && yt >= 0; xt--, yt--){
            if (board[xt][yt])
                return false;
        }
        for (xt = x + 1, yt = y + 1; xt < n && yt < n; xt++, yt++) {
            if (board[xt][yt])
                return false;
        }
        for (xt = x - 1, yt = y + 1; xt >= 0 && yt < n; xt--, yt++){
            if (board[xt][yt])
                return false;
        }
        for (xt = x + 1, yt = y - 1; xt < n && yt >= 0; xt++, yt--) {
            if (board[xt][yt])
                return false;
        }

        return true;
    }

    void reItem(vector<vector<int>> &board, vector<vector<string>> &ret) {
        int n = board.size();
        vector<string> re(n, string(n, '.'));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j]) re[i][j] = 'Q';
            }
        }
        ret.push_back(re);
    }
};

题目描述:

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:

You may assume k is always valid, 1 ≤ k ≤ n².

首先的想法是每次从n行中取最前端的n个值中的最小值, 然后这个值从该行删除, 重复k次. 时间复杂度O(nk). 实际运行时间280ms.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        vector<int> matrixPos(n, 0);
        int ret;
        for(int i = 0; i < k; i++){
            int minNum = INT_MAX, minPos = 0;
            for(int j = 0; j < n; j++){
                if(matrixPos[j] == n) continue;
                if(matrix[j][matrixPos[j]] < minNum){
                    minNum = matrix[j][matrixPos[j]];
                    minPos = j;
                }
            }
            matrixPos[minPos]++;
            ret = minNum;
        }
        return ret;
    }
};

使用二分搜索, 不过搜算范围是int类型的整个表示范围, 为避免溢出, 使用long long来保存左右边界. Runtime: 80ms.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        long long l = INT_MIN, r = INT_MAX, mid;
        while(l < r){
            mid = (l + r) >> 1;
            int kth = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n && matrix[i][j] <= mid; j++){
                    kth++;
                }
            }
            if(kth < k) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

另一种使用堆的方法, 先按从上往下, 从左往右的顺序将k个元素放入堆中. 对于剩下的元素, 每一行从头开始与堆顶比较, 如果小于堆顶, 就把它放入堆中, 把原堆顶弹出. 改行中出现>=堆顶的元素时即可停止对这一行的处理. 运行时间112ms.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        priority_queue<int> heap;
        for(int i = 0; i < n; i++){
            if(heap.size() < k){
                int j;
                for(j = 0; j < n && heap.size() < k; j++){
                    heap.push(matrix[i][j]);
                }
                for(; j < n && heap.top() > matrix[i][j]; j++){
                    heap.pop();
                    heap.push(matrix[i][j]);
                }
            }
            else{
                for(int j = 0; j < n && heap.top() > matrix[i][j]; j++){
                    heap.pop();
                    heap.push(matrix[i][j]);
                }
            }
        }
        return heap.top();
    }
};