Code – 第98页

LeetCode 724. Find Pivot Index

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:
Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.
Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Note:

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].

题目大意：在一个数组中找到一个数字的下标，要求这个数字左边的数字和等于右边的数字和，如果不存在就返回-1

分析：计算数组所有元素和sum，然后遍历数组，每次将前i-1个数字的和累加在t中，每次从sum中减去nums[i]，这样sum就是nums[i]后面所有数字的和，如果sum == t就返回i，否则就返回-1

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size(), sum = 0, t = 0;
        if (n == 0) return -1;
        if (n == 1) return 0;
        for (int i : nums) sum += i;
        for (int i = 0; i < n; i++) {
            sum -= nums[i];
            if (sum == t) return i;
            t += nums[i];
        }
        return -1;
    }
};

class Solution {

public:

int pivotIndex(vector<int>& nums) {

int n = nums.size(), sum = 0, t = 0;

if (n == 0) return -1;

if (n == 1) return 0;

for (int i : nums) sum += i;

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

sum -= nums[i];

if (sum == t) return i;

t += nums[i];

}

return -1;

}

};

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);

}

};

「为什么我的这段代码有几个测试点不通过呢」系列及常见问题FAQ

0. 写在前
在刷算法题的过程中，每个人都不可避免的会出现测试点不通过的情况，于是很多人都会通过各种方式联系我，给我发自己写的代码想让我帮忙看一看错在哪，其实这是一个代码新手的常见误区：认为曾经通过了该题的人就能够知道别人写的代码错误点在哪。因为对于一段代码来说，最了解这段代码思路的人是代码的作者自己，而让我来看这段代码，我需要先打开题目重新理解题意，然后仔细看别人写的代码进行测试用例调试，接着反复努力看懂别人的代码，因为时隔多年，遇到不熟悉的算法或是STL我还需要查阅文档和笔记重新复习才能够理解代码的意思，很多变量命名、代码风格都和自己写的代码有很大差异，理解起来更是没有数小时就无法搞定，更别说我大多数时候电脑不在身边，没有了IDE的调试、编译运行，直接在手机上看代码根本无法解决问题。一开始我很热心的帮助所有来求助的人，后来发现我仔细阅读理解别人的代码后总是觉得写的没有任何问题——最后的结果总是我也找不到为什么测试点不通过。因为最理解这段代码知道自己所写的每一句代码的含义、代码间逻辑关系的还是自己。
我在刷题过程中也不可避免的会遇到测试点无法通过的情况，我以及身边各位算法大神的做法是：对照着能够答案正确的他人代码，对比自己的代码，一点点更改，慢慢缩小目标区域，直到最后找到答案。如果自己的代码和别人思路方法完全不同，那我会思考，我所写的方法是不是比别人写的代码都优秀？很多时候会发现，并不能找到错误原因的那段代码本身逻辑就较为混乱，所以我的建议是对自己写的代码用更好的方法进行重构，因为即使这段代码勉强调试写出来了，下一次见到它还是难以理解，对自己的考前复习也是一种打击，会让自己看到这段代码就想要跳过不看，而且还让自己错过了一次学习他人优秀方法的机会，要知道刷题的真正意义是学到知识呀～
鉴于我每天都会遇到很多向我求助代码错误点的朋友，所以我花了数天时间，重读了我过往刷过的几千道算法题和一些刷题过程中的笔记，从报错信息方面总结了一些代码错误的常见原因，希望能帮助你成功找到不能AC的真正原因～
1. 所有测试点都是段错误
段错误指数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
段错误是非常喜闻乐见的一种报错方式，因为段错误锁定问题代码区域的方式较为简单：首先对可疑的代码段进行注释掉，然后提交到OJ上看是否会发生段错误，如果确实是自己注释掉的这段代码发生了段错误，那么对应的OJ判题结果就会变为答案错误，说明注释掉的代码正是引起越界溢出的原因所在～以下是一些可能引起段错误的常见原因：
1.1 多层for循环中内层循环明明应该写j或者k，却写成了外层循环的变量i，导致数组访问i下标的时候发生了越界
1.2 数组开小了导致指针指向了未开辟的数组区域，出现了越界访问
1.3 大数组一定要开全局，而不是写在main函数里面，否则容易发生段错误
1.4 递归的出口写的有问题，递归层数太多导致了堆栈溢出，发生段错误
2. 有几个测试点是段错误
2.1 是否没有考虑0或者边界值的情况？比如对于一个空数组却判断arr[0]，可能会出现段错误的情况
2.2 对于树来说，当前结点如果是NULL，一定要先判断再使用root->val或者root->left、root->right的情况，因为NULL是没有val、left、right等指针的（这个在LeetCode里面是非常常见的错误）
2.3 while循环的边界条件未判断正确，导致访问了数组的非法内存
3. 所有测试点都运行超时
如果所有测试点都是运行超时，一般情况是出现了死循环
3.1 明明i从s.length()-1开始向前遍历，结果i误写成了i++导致了无限循环
3.2 while循环的边界判断有问题，使得无限循环
3.3 代码的算法需要优化，过于暴力破解的算法在一些运行时间、算法复杂度要求较高的题目中会经常发生运行超时
4. 有几个测试点运行超时
4.1 cin的输入比scanf更耗时，如果个别测试点超时可以考虑是否可以通过优化cin来实现
4.2 对数据进行排序的过程中，有很多数据是无效数据，如果对所有数据都排序可能会引起超时，所以可以考虑在放入数组之前就做一些条件判断剔除无用数据，然后再对数组进行排序
4.3 如果写了main函数之外的其他函数，传引用会比传值的方式更省时，所以可以考虑优化为void func(int& a)的方式传递参数减少耗时
4.4 在for或者while循环中的及时判断条件，用break提前退出当前层的循环可以降低代码运行时间是常用的降低代码运行时间的方式～
4.5 for循环内定义int i和在外面定义int i其实有少许区别，在for循环内定义的i可能会更耗时，这也是降低代码运行时间的一种可考虑方式哦～
4.6 求最短路径的题目中以用Dijkstra解决的非要用DFS强行深搜获得答案可能会导致超时哦～
4.7 使用了v.size()-1等方式，如果v的size本身就是0，因为v.size()返回值是无符号整数，无符号整数的0-1得到的是无符号整数的最大值而非-1，这可能会让int i循环时超时～
4.8 是不是明明可以用键值对找到对应的值【比如bool visit[100]寻找对应的visit[80]是否为true，复杂度为O(1)】却用了for循环一个个找的存储方式【比如邻接矩阵可以一次查找得到，却用了邻接表一个个查找】，以空间换时间的方式是常用降低算法时间复杂度的方式～
5. 有几个测试点答案错误
答案错误的原因太多了，代码思路稍有不对或是小粗心都会出现很多答案错误，甚至有的时候没有完全理解对题意却能得到大部分答案正确、个别答案错误的情况（比如PAT红黑树那道题，我在考场上就未能完全理解题意却得到了大部分分数，但这也影响了我调试找到错误的原因），对着代码找半天都不知道错在哪的情况也常有发生，具体问题具体分析，以下是我调试过程中遇到过的一些常见错误～
5.1 输出语句的错误。比如输出的个别字母不正确、输出yes no的大小写没有按照要求、true false拼写错误、1 后面不要加s，2以上的个数后面单词要加s、is和are的区别等问题，有时候不正确的拼写遇上多条输出语句还会引起一半答案错误、一半答案正确的情况还始终找不到原因在哪emmmmmm
5.2 switch后面只能int或者char类型其它类型不可以～
5.3 memset只能赋值0、-1和最大值，如果你想要给数组赋值一个特定的值，请使用fill函数～
5.4 getline读取的是一整行字符串，如果接下来还要读取字符char，会读取到回车换行符，所以为了避免这种情况，要在getline(cin, s);后面加一句getchar();才能得到自己想要读取到的char～
5.5 int + int、int * int的过程中都有可能出现结果超过了int的值而产生溢出的情况，这样就会使一些数据较大的测试用例因为溢出变成了别的数字而得到答案错误～
5.6 有时候会给一组ab区间，但是a b并没有按照从小到大的方式输入，可能个别数据是a > b，所以要先判断一下～
5.7 如果是给id的题目，可能输出中要求按照不满4位在前面补0的情况，所以要用printf(“%04d”, a);的方式输出，否则遇到不满4位的id输出结果可能会导致答案错误（有的题目会显示为格式错误）～
6. 内存超限
开的数组或占用的内存过大，超过了要求的内存范围：
6.1 可以考虑开vector或者动态开辟数组的方式避免直接开1000000这样很大的数组
6.2 如果是为了存储一些键值对，可以避免开int hash[100000]这样的大数组，而是用map来处理键值对的映射
6.3 如果是为了存储稀疏矩阵，可以用邻接表存储的方式代替邻接矩阵存储的方式来降低空间复杂度（以时间复杂度换空间复杂度的方式）～
7. 自己IDE上好好的，OJ上却编译错误
OJ的判题系统有自己的编译器，这个编译器的版本配置应该会在它的OJ系统中阐述介绍
比如PAT编译C/C++时用的是gcc/g++ 4.7.2，Java用的是javac 1.6.0等，而每个IDE自带的编译器版本不同，比如Visual Studio只支持了部分C++11标准，更不用说Visual C++ 6.0 和 Turbo C++ 3.0 等IDE有较多违背 C++ 标准，我的建议是使用Dev-C++（使用时请在设置中包含-std=c++11）、XCode等IDE，不过最重要的是选自己考场上提供的、熟悉的IDE进行平时的代码刷题练习～
8. 提交第一次超时了，第二次却AC了
OJ系统大多有很多服务器，在平时练习过程中，提交那一瞬间如果遇到了新买的高配置服务器就能够让你的代码AC，有的时候遇上了普通或者慢的服务器，就有可能会运行超时～但是PAT考试时候不要心存侥幸或是觉得这不公平哦～他们会关闭个别特别快的服务器只留下势均力敌的几个服务器hhhhhhha～
9. 别人blog上AC了的代码，在我编译器里却编译不通过
编译器版本不同，所得到的结果自然不同。如果你使用的是Visual Studio，可能会有部分C99标准的库函数或者标准是不被支持的，但是这在C++11中是支持的，所以会导致在vs上无法编译通过的情况。如果你使用的是Dev-C++，可能忘记了在设置中包含-std=c++11，具体的某个函数在哪个版本中，可以访问http://www.cplusplus.com/查阅官方文档（我在刚刷题的过程中几乎离不开查阅该文档）。如果你用的是Xcode或CLion等，因为它们内置了较多的常用库函数，很多变量名可能在OJ中不是关键字但是在自己IDE上却是，更严格的标准和更先进的IDE确实会引起一些warning甚至error。如果你使用的是vc++6.0或者turbo c++，emmmmm人生苦短，为什么不考虑换个好用的IDE呢？
10. 浮点错误
程序中出现了除以0、取余0的这种非法操作～
11. 返回非零
11.1 如果你用的是C/C++，请使用int main和return 0;
11.2 如果你用的是Java，那么可能原因是你写的代码里面的public class后面的那个名字不是Main，改成Main就可以通过了～
12. 为什么别人blog的代码是处理一组测试数据就输出一组？不是应该全部读入之后再输出吗？
大多数OJ系统都是支持“处理一组测试数据就输出一组”的做法的，由于PAT的OJ系统是在你的程序运行结束后开始检查输出是否是正确的，对于有多组测试数据的输入，可以全部读入之后再输出，也可以处理一组测试数据就输出一组～这样做是没有任何问题的不要担心哦摸摸头～（而且更省事了呀不用把答案保存下来再输出了呀～O(∩_∩)O～）
13. 格式错误
13.1 可能是换行、空格等出现了问题，输出语句内可能有拼写错误、空格多打少打等情况～
13.2 行末的不必要的换行或是缺少了必要的换行也有可能引起格式错误～
13.3 题目要求小写/大写而自己没有按照题目要求输出也有可能格式错误～
13.4 题目要求输出4位数字不足前面添加0的时候没有按照要求用printf(“%04d”, a);的方式输出，否则遇到不满4位的id输出结果可能会导致格式错误～
14. 写在后
14.1 刷题的过程中坚持自己找到错误的原因并总结经验，才能获得AC时的成就感和喜悦感，才能在考试中游刃有余(～ o ～)~
14.2 感谢曾经刷每道算法都会写笔记记录自己的经验和收获的自己，这让我能从过往的调试过程中吸取教训，少走很多弯路
14.3 感谢@聪明可爱的小学弟谢民皆提供的一些常见问题和解决方案～