2017年12月27日
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 的情况
triangle.add(new ArrayList<Integer>());
triangle.get(0).add(1);
for(int i = 1; i <numRows;i++){
List<Integer> curRow = new ArrayList<Integer>();
List<Integer> preRow = triangle.get(i-1);
//first element
curRow.add(1);
for(int j = 0 ;j<preRow.size()-1;j++){
curRow.add(preRow.get(j)+preRow.get(j+1));
}
curRow.add(1);
triangle.add(curRow);
}
return triangle;
}
}
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
2018年1月3日
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;
}
}
class Solution(object):
def isOneBitCharacter(self, bits):
parity = bits.pop()
while bits and bits.pop(): parity ^= 1
return parity == 0
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++){
result.add(1);
for(int j = i-1 ; j > 0 ; j--){
result.set(j,result.get(j)+result.get(j-1));
}
}
return result;
}
}
递归
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);
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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:
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;
}
}
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;
}
}