LeetCode 53. Maximum Subarray Description Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

LeetCode 53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
我们用res来表示最终的和,用temp来表示临时的和
初始时res = nums[0],temp = 0
遇到一个值,我们就把它加到temp上面,如果temp大于res,把temp赋值给res
如果temp小于res但是大于0,继续加和
如果temp小于零,我把temp置为零,因为此时temp已经小于零了,如果保留temp当前的值再往里面加值,整个的和一定会变得更小[因为temp当前是负数],
也就是说当temp是负数时,temp的贡献一定是负,无论后面加什么值,一定会使得当前的子数组和更小

继续阅读

LeetCode 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
n皇后问题,即要求将n个皇后放置在n*n的棋盘(以下称矩阵)中,使得任意一个皇后都不能攻击其她皇后,皇后能够攻击的位置是皇后所在的一整行,所在的一整列,所在的两条对角线。要求皇后不能互相攻击,即是要求任意一个皇后,她所在位置的行,列,两条对角线没有其他皇后.
此题目需要用到递归
n皇后问题,关键是要确定哪些位置可以放置,哪些位置不能放置.
根据题意,矩阵的每一行只能有一个皇后,每一列也只能一个皇后.
我们每一行每一行的寻找,看一行的哪个位置可以放置,为了确定这个位置是否可以放置皇后.
我们需要检查:
这个位置所在的列是否有皇后.
这个位置所在的左对角线是否有皇后.
这个位置所在的右对角线是否有皇后.
可以不用检查行,因为我们是按行从每一个位置开始检查的,改行一定没有其他皇后.

继续阅读

LeetCode 50. Pow(x,n)

Implement pow(x, n), which calculates x raised to the power n (xn).
拿到这道题第一个想到的是循环,但是循环显然不是这道题考察的重点,而且,在此题中,采用循环(或者递归)会超时
此题主要考察二分法
我们计算xn时(以计算28说明),如果采用循环需要进行乘法运算约8(O(n))次,但是如果使用二分法,计算2*2得到4,计算4*4得到16,计算16*16得到245,只需要3(log2(8))次
即28=(((22)2)2)
pow(x,n)中,我们每次让x自乘一次,n就可以减半,这里要注意奇数的情况,如果n是奇数,需要在结果中自乘一下当前的x,不然会少一次x

继续阅读

LeetCode 49. Group Anagrams

Given an array of strings, group anagrams together.
这道题思路很清晰,也比较简单
对字符串排序,以排好序的字符串为键,构建hash表,值为包含字符串的list
用python实现很容易,因为由内置函数,如果改用C语言,会增加难度

继续阅读

LeetCode 48. Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
这道题主要考察发现规律,在不申请额外矩阵空间的条件下,我们需要知道如何转换,如上图,以四维矩阵进行说明
如上图,需要观察发现:
1–>4–>16–>13–>1
2–>8–>15–>9–>2
3–>12–>14–>5–>3
如上是最外一层的变化,内层同样的道理

继续阅读
LeetCode 47. Permutations II

LeetCode 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.此问题同46题思路,条件基本一致,只是给定的数组中可能有重复值,需要去掉.
假设数组A[10],我们在遍历每个元素A[i]的时候,都检查A[i]是否在A[1:i]中出现过,如果曾经出现,则直接跳过

继续阅读

LeetCode 46. Permutations

Given a collection of distinct integers, return all possible permutations.写好递归函数的要点是:1.确定递归关系式 2. 确定递归结束条件 3.A问题可以分解成B,C,D···Z几个子问题,假设子问题已经解决,在此情况下来解决A问题
此题目中,假设有一个数组A[10],我们拿出A[1],假设A[1:10](两端的值都可以取到)组成的所有序列都已经取到,我们把A[1]和所有的组合相加,就得到了
以A[1]为首的所有可能组合
同理,我们把A[2]拿出来,把A[1]+A[3:10]组成一个新的数组,假设此数组的所有排列组合和已经取到,再把A[2]和它们相加,就得到了以A[2]为首的所有组合

继续阅读
LeetCode 45. Jump Game II

LeetCode 45. Jump Game II

Description

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.

Your goal is to reach the last index in the minimum number of jumps.

Example: Input: [2,3,1,1,4] Output: 2

Explanation: The minimum number of jumps to reach the last index is 2.

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:You can assume that you can always reach the last index.

继续阅读