LeetCode OJ – 第4页 – 柳婼の blog

LeetCode 733. Flood Fill

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
Note:

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

题目大意：给定表示填充的开始像素（行和列）的坐标（sr，sc）和像素值newColor，“填充”图像。从上下左右四个方向填充，只要是和原来颜色一样的都填充为新的颜色～

分析：从(sr, sc)处遍历四个方向，用visit标记是否访问过，每次将所有和原来相同颜色的坐标填充为新的颜色并将当前坐标标记为访问过，最后返回image数组～

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        n = image.size();
        if (n == 0) return image;
        m = image[0].size();
        visit.resize(n, vector<bool>(m, false));
        dfs(image, sr, sc, image[sr][sc], newColor);
        return image;
    }
private:
    int n, m, arr[5] = {1, 0 , -1, 0, 1};
    vector<vector<bool>> visit;
    void dfs(vector<vector<int>>& image, int sr, int sc, int oldColor, int& newColor) {
        image[sr][sc] = newColor;
        visit[sr][sc] = true;
        for (int i = 0; i < 4; i++) {
            int tx = sr + arr[i], ty = sc + arr[i+1];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && visit[tx][ty] == false && image[tx][ty] == oldColor)
                dfs(image, tx, ty, oldColor, newColor);
        }
    }
};

class Solution {

public:

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {

n = image.size();

if (n == 0) return image;

m = image[0].size();

visit.resize(n, vector<bool>(m, false));

dfs(image, sr, sc, image[sr][sc], newColor);

return image;

}

private:

int n, m, arr[5] = {1, 0 , -1, 0, 1};

vector<vector<bool>> visit;

void dfs(vector<vector<int>>& image, int sr, int sc, int oldColor, int& newColor) {

image[sr][sc] = newColor;

visit[sr][sc] = true;

for (int i = 0; i < 4; i++) {

int tx = sr + arr[i], ty = sc + arr[i+1];

if (tx >= 0 && tx < n && ty >= 0 && ty < m && visit[tx][ty] == false && image[tx][ty] == oldColor)

dfs(image, tx, ty, oldColor, newColor);

}

};

LeetCode 695. Max Area of Island

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

题目大意：给一个地图，0表示水1表示陆地，计算最大的一个岛屿的面积～

分析：遍历所有grid[x][y] == 1的地盘，每次将tempcnt = 0，然后进行dfs，dfs中从4个方向遍历，每次对于grid[x][y] == 1的地盘进行更深一层的dfs，进入dfs先将当前地盘标记为0且tempcnt++，最后tempcnt的值即为这个岛屿的数量，当main函数中遍历过所有的岛屿后返回cnt的最大值即是面积最大的岛屿～

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        n = grid.size(), m = grid[0].size();
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (grid[x][y] == 1) {
                    tempcnt = 0;
                    dfs(x, y, grid);
                    cnt = max(cnt, tempcnt);
                }
            }
        }
        return cnt;
    }
private:
    int n, m, cnt = 0, tempcnt = 0;
    int arr[5] = {0, 1, 0, -1, 0};
    void dfs(int x, int y, vector<vector<int>>& grid) {
        grid[x][y] = 0;
        tempcnt++;
        for (int i = 0; i < 4; i++) {
            int tx = x + arr[i], ty = y + arr[i+1];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && grid[tx][ty] == 1)
                dfs(tx, ty, grid);
        }
    }
};

class Solution {

public:

int maxAreaOfIsland(vector<vector<int>>& grid) {

if (grid.size() == 0) return 0;

n = grid.size(), m = grid[0].size();

for (int x = 0; x < n; x++) {

for (int y = 0; y < m; y++) {

if (grid[x][y] == 1) {

tempcnt = 0;

dfs(x, y, grid);

cnt = max(cnt, tempcnt);

}

return cnt;

}

private:

int n, m, cnt = 0, tempcnt = 0;

int arr[5] = {0, 1, 0, -1, 0};

void dfs(int x, int y, vector<vector<int>>& grid) {

grid[x][y] = 0;

tempcnt++;

for (int i = 0; i < 4; i++) {

int tx = x + arr[i], ty = y + arr[i+1];

if (tx >= 0 && tx < n && ty >= 0 && ty < m && grid[tx][ty] == 1)

dfs(tx, ty, grid);

}

};

LeetCode 200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

题目大意：给一个地图，0表示水，1表示陆地，计算陆地的个数

分析：计算连通分量的个数，每次遍历是陆地(grid[x][y] == 1)的区域，dfs中从4个方向遍历，每次将访问过的grid标记为’0’，main函数中进入dfs多少次就表示有多少个岛屿（也就是有多少个连通分量的个数）

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0) return 0;
        n = grid.size(), m = grid[0].size();
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (grid[x][y] == '1') {
                    dfs(x, y, grid);
                    cnt++;
                }
            }
        }
        return cnt;
    }
private:
    int n, m, cnt = 0;
    int arr[5] = {1, 0, -1, 0, 1};
    void dfs(int x, int y, vector<vector<char>>& grid) {
        grid[x][y] = '0';
        for (int i = 0; i < 4; i++) {
            int tx = x + arr[i], ty = y + arr[i+1];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && grid[tx][ty] == '1')
                dfs(tx, ty, grid);
        }
    }
};

class Solution {

public:

int numIslands(vector<vector<char>>& grid) {

if (grid.size() == 0) return 0;

n = grid.size(), m = grid[0].size();

for (int x = 0; x < n; x++) {

for (int y = 0; y < m; y++) {

if (grid[x][y] == '1') {

dfs(x, y, grid);

cnt++;

}

return cnt;

}

private:

int n, m, cnt = 0;

int arr[5] = {1, 0, -1, 0, 1};

void dfs(int x, int y, vector<vector<char>>& grid) {

grid[x][y] = '0';

for (int i = 0; i < 4; i++) {

int tx = x + arr[i], ty = y + arr[i+1];

if (tx >= 0 && tx < n && ty >= 0 && ty < m && grid[tx][ty] == '1')

dfs(tx, ty, grid);

}

};

LeetCode 653. Two Sum IV – Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7

Target = 9

Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7

Target = 28

Output: False

题目大意：给一棵二叉搜索树和一个目标数字，如果这棵树中存在两个元素，这两个元素的和等于目标数字，则返回true

分析：设立set，如果set里面存在k – 当前结点的值，则返回true；每次将当前结点的值放入set中，否则返回它左子树的结果 || 右子树的结果。相当于每次比较的是当前结点i之前的所有数字中是否有和i相加为k的数字，如果有就返回true，否则就继续遍历左子树和右子树，只要其中一个满足就返回true

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    set<int> s;
    bool findTarget(TreeNode* root, int k) {
        if (root == NULL) return false;
        if (s.count(k - root->val)) return true;
        s.insert(root->val);
        return findTarget(root->left, k) || findTarget(root->right, k);
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

set<int> s;

bool findTarget(TreeNode* root, int k) {

if (root == NULL) return false;

if (s.count(k - root->val)) return true;

s.insert(root->val);

return findTarget(root->left, k) || findTarget(root->right, k);

}

};

LeetCode 599. Minimum Index Sum of Two Lists

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:
Input:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
Output: [“Shogun”]
Explanation: The only restaurant they both like is “Shogun”.
Example 2:
Input:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“KFC”, “Shogun”, “Burger King”]
Output: [“Shogun”]
Explanation: The restaurant they both like and have the least index sum is “Shogun” with index sum 1 (0+1).
Note:
The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

题目大意：假设安迪和多丽丝想选择一家餐厅吃饭，他们有一串最喜欢的餐厅名单。你需要帮助他们用最小的指数总和找到他们的共同兴趣。如果答案有多个则没有顺序要求地返回所有答案在string数组中～

分析：当i+j比minSum小时将数组清空，minSum赋值为i+j，list1[i]放入ans数组中

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> ans;
        int minSum = 2000;
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if (list1[i] == list2[j] && minSum > i + j) {
                    ans.clear();
                    ans.push_back(list1[i]);
                    minSum = i + j;
                } else if (list1[i] == list2[j] && minSum == i + j) {
                    ans.push_back(list1[i]);
                }
            }
        }
        return ans;
    }
};

class Solution {

public:

vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {

vector<string> ans;

int minSum = 2000;

for (int i = 0; i < list1.size(); i++) {

for (int j = 0; j < list2.size(); j++) {

if (list1[i] == list2[j] && minSum > i + j) {

ans.clear();

ans.push_back(list1[i]);

minSum = i + j;

} else if (list1[i] == list2[j] && minSum == i + j) {

ans.push_back(list1[i]);

}

return ans;

}

};

LeetCode 581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

题目大意：给定一个整数数组，你需要找到一个连续的子数组，如果你按升序对这个子数组排序，那么整个数组将也是升序。你需要找到最短的这样的子数组并输出它的长度。

分析：对v排序，i找到第一个和排序后的数组v不相等的元素，j找到最后一个和排序后的数组v不相等的元素，如果i<=j说明存在这样一个长度，长度为j-i+1，否则不存在这样一个长度，则返回0～

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> v(nums);
        sort(v.begin(), v.end());
        int i = 0, j = nums.size() - 1;
        while (i < nums.size() && nums[i] == v[i]) i++;
        while (j >= 0 && nums[j] == v[j]) j--;
        return i <= j ? j - i + 1 : 0;
    }
};

class Solution {

public:

int findUnsortedSubarray(vector<int>& nums) {

vector<int> v(nums);

sort(v.begin(), v.end());

int i = 0, j = nums.size() - 1;

while (i < nums.size() && nums[i] == v[i]) i++;

while (j >= 0 && nums[j] == v[j]) j--;

return i <= j ? j - i + 1 : 0;

}

};