LeetCode第二天&第三天

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 的情况
        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;
    }
}
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++){
            result.add(1);
            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;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

974
来自专栏测试开发架构之路

数据结构之哈夫曼编码

例题: 假设一个文本文件TFile中只包含7个字符{A,B,C,D,E,F,G},这7个字符在文本中出现的次数为{5,24,7,17,34,5,13} 利用哈夫...

4848
来自专栏java学习

每日一练(2017/5/17)

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

2956
来自专栏用户2442861的专栏

二叉树的非递归遍历

                                                            二叉树的非递归遍历

1081
来自专栏kevindroid

leetcode538 Convert BST to Greater Tree

1744
来自专栏老马说编程

(32) 剖析日期和时间 / 计算机程序的思维逻辑

本节和下节,我们讨论在Java中如何进行日期和时间相关的操作。 日期和时间是一个比较复杂的概念,Java API中对它的支持不是特别好,有一个第三方的类库反而特...

21310
来自专栏Vamei实验室

纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

2267
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

5378
来自专栏一枝花算不算浪漫

Java中常见数据结构List之LinkedList

3255
来自专栏数据结构与算法

24:打印月历

24:打印月历 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定年月,打印当月的月历表。 输入输入为一行两个整数,...

3826

扫码关注云+社区

领取腾讯云代金券