FilesExpand file tree

 master

/

leetcode128.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

57 lines (49 loc) · 1.51 KB

 master

/

leetcode128.java

Top

File metadata and controls

• Code
• Blame

57 lines (49 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

package leetcode.dp;

import java.lang.reflect.Array;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

public class leetcode128 {

public int dp_longestConsecutive(int[] nums) {

Arrays.sort(nums);

int res=0;

int[] dp=new int[nums.length]; //dp[i]以nums[i]为末尾的连续数组的长度

dp[0]=1;

for (int i = 1; i <nums.length ; i++) {

if (nums[i-1]==nums[i]-1){

dp[i]=dp[i-1]+1;

}else if (nums[i]==nums[i-1]){

dp[i]=dp[i-1];

}

res= Math.max(res,dp[i]);

}

return res;

}

public int col_longestConsecutive(int[] nums) {

Set<Integer> num_set = new HashSet<Integer>();

for (int num : nums) {

num_set.add(num);

}

int longestStreak = 0;

for (int num : num_set) {

if (!num_set.contains(num-1)) { // O(1)存取，不往前看，往后看

int currentNum = num;

int currentStreak = 1;

while (num_set.contains(currentNum+1)) {

currentNum += 1;

currentStreak += 1;

}

longestStreak = Math.max(longestStreak, currentStreak);

}

}

return longestStreak;

}

public static void main(String[] args) {

new leetcode128().col_longestConsecutive(

new int[]{

0,1,2,1

}

);

}

}