LeetCode 628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

题目大意:给一个数组,找三个数字,使这三个数乘积最大,返回乘积的最大值~

分析:先对数组排序,要么是最后三个数字乘积,要么可能会有负数,则是前两个数的乘积*最后一个数字的乘积,取这个两个乘积结果的最大值即可~

LeetCode 674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it is not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.
Note: Length of the array will not exceed 10,000.

题目大意:给一个乱序数组,返回这个数组中递增连续子序列中最长的长度~

分析:遍历从i = 1到结尾,每次比较nums[i-1]和nums[i],如果是递增的就将temp++,否则temp=1,每次将temp最大值保存在ans中,最后返回ans的值~

 

LeetCode 633. Sum of Square Numbers

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False

题目大意:给一个数c,判断是否存在两个数字a b满足a*a+b*b=c,存在就返回true,否则返回false

分析:i和j分别从根号c开始到0,如果找到了i * i + j * j == c就return true,如果i * i + j * j < c就break第二层for循环,最后如果都没有找到就返回false~

 

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

 

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数组~

 

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的最大值即是面积最大的岛屿~