# leetcode 第二天

2017年12月27日

#### 4.（118）Pascal's Triangle

##### JAVA
```class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>();
//当numRows = 0 的情况
if(numRows == 0) return triangle;
//当numRows != 0 的情况

for(int i = 1; i <numRows;i++){
List<Integer> curRow = new ArrayList<Integer>();
List<Integer> preRow = triangle.get(i-1);
//first element

for(int j = 0 ;j<preRow.size()-1;j++){
}
}
return triangle;
}
}```
##### Python
```def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
triangle = []

if numRows == 0:
return triangle

triangle.append([1])

for i in range(1,numRows):
curRow = []
preRow = triangle[i-1]

curRow.append(1)

for j in range(len(preRow)-1):
curRow.append(preRow[j]+preRow[j+1])

curRow.append(1)
triangle.append(curRow)
return triangle```

# leetcode 第三天

2018年1月3日

#### 5.（217）Contains Duplicate

##### JAVA
1. // T:O(nlogn) S:O(1) public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length - 1; ++i) { if (nums[i] == nums[i + 1]) return true; } return false; }
2. T:O(n) S:O(n) public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(nums.length); for (int x: nums) { if (set.contains(x)) return true; set.add(x); } return false; } 6.（717）1-bit and 2-bit Characters
##### JAVA
1. class Solution { public boolean isOneBitCharacter(int[] bits) { int i = 0; while (i<bits.length - 1){ i += bits[i]+1; } return i == bits.length-1; } }
```class Solution {
public boolean isOneBitCharacter(int[] bits) {
int i = bits.length - 2;
while (i >= 0 && bits[i] > 0) i--;
return (bits.length - i) % 2 == 0;
}
}```
##### Python
1. class Solution(object): def isOneBitCharacter(self, bits): i = 0 while i < len(bits) - 1: i += bits[i] + 1 return i == len(bits) - 1
```class Solution(object):
def isOneBitCharacter(self, bits):
parity = bits.pop()
while bits and bits.pop(): parity ^= 1
return parity == 0```

#### 7.（119）Pascal's Triangle II

##### Java
```class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>();
if(rowIndex < 0) return result;
for(int i = 0 ;i <= rowIndex;i++){
for(int j = i-1 ; j > 0 ; j--){
result.set(j,result.get(j)+result.get(j-1));
}
}
return result;
}
}```

#### 8.（695）Max Area of Island

##### JAVA

```class Solution {
int[][] grid;
boolean[][] seen;
public int maxAreaOfIsland(int[][] grid) {
this.grid = grid;
int result = 0;
seen = new boolean[grid.length][grid[0].length];
for(int r = 0;r<grid.length;r++)
for(int c = 0 ;c<grid[0].length;c++)
result = Math.max(result,area(r,c));
return result;
}

public int area(int r,int c){
if(r<0||r>=grid.length||c<0||c>=grid[0].length||seen[r][c]||grid[r][c]==0) return 0;
seen[r][c] = true;
return 1+area(r-1,c)+area(r,c-1)+area(r+1,c)+area(r,c+1);
}

}```

#### 9.（26）Remove Duplicates from Sorted Array

##### JAVA
```class Solution {
public int removeDuplicates(int[] nums) {
int newLength = 1;
if(nums.length == 0) return 0;
for(int i = 0;i<nums.length;i++)
if(nums[newLength-1] != nums[i]){
nums[newLength]= nums[i];
newLength++;
}
return newLength;
}
}```

#### 10.（27）Remove Element

##### JAVA
```class Solution {
public int removeElement(int[] nums, int val) {
int newLength = 0;
if(nums.length ==0) return newLength;
for(int i = 0;i<nums.length;i++)
if(nums[i]!=val)
nums[newLength++] = nums[i];
return newLength;
}
}```

#### 11.（121）Best Time to Buy and Sell Stock

##### JAVA
```class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
int min = Integer.MAX_VALUE;
for(int i = 0;i<prices.length;i++){
min = Math.min(prices[i],min);
profit = Math.max(prices[i]-min,profit);
}
return profit;
}
}```

#### 12.（122）Best Time to Buy and Sell Stock II

##### JAVA
```class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for(int i =0;i<prices.length-1;i++)
if(prices[i+1]>prices[i])
profit += prices[i+1]-prices[i];
return profit;
}
}```

#### 13.（624）==Maximum Distance in Arrays==

Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.

Example 1:

Input: [[1,2,3], [4,5], [1,2,3]] Output: 4 Explanation: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
3. The integers in the m arrays will be in the range of [-10000, 10000]. JAVA
```public class Solution {
public int maxDistance(List<List<Integer>> arrays) {
int res = 0;
int min = arrays.get(0).get(0);
int max = arrays.get(0).get(arrays.get(0).size() - 1);
for (int i = 1; i < arrays.size(); i++) {
List<Integer> array = arrays.get(i);
res = Math.max(Math.abs(min - array.get(array.size() - 1)), Math.max(Math.abs(array.get(0) - max), res));
min = Math.min(min, array.get(0));
max = Math.max(max, array.get(array.size() - 1));
}
return res;
}
}  ```

#### 14.（35）Search Insert Position

##### JAVA
```class Solution {
public int searchInsert(int[] nums, int target) {
for(int i =0;i<nums.length;i++){
if(nums[i] == target)
return i;
if(nums[i]>target)
return i;
}
return nums.length;
}
}```

128 篇文章38 人订阅

0 条评论

## 相关文章

974

4848

### 每日一练（2017/5/17）

Java基础 | 数据库 | Android | 学习视频 | 学习资料下载 课前导读 ●回复"每日一练"获取以前的题目！ ●答案公布时间：为每期发布题目的第二...

2956

### 二叉树的非递归遍历

二叉树的非递归遍历

1081

1744

21310

2267

5378