Date: 8:33 PM, Tuesday, May 25, 2021

Personal brush question record, code collection, source is leetcode

After a lot of discussion and consultation, I'm going to work towards Java

The main answer language is Java

## Title:

#### Sword finger Offer 61. Shunzi in playing cards

Simple 131

Randomly draw 5 cards from playing cards to judge whether it is a Shun Zi, that is, whether the 5 cards are continuous. 2-10 is the number itself, a is 1, J is 11, Q is 12, K is 13, and big, small Wang is 0, can be regarded as any number. A cannot be regarded as 14.

Example 1:

input: [1,2,3,4,5] output: True

Example 2:

input: [0,0,1,2,5] output: True

Restrictions:

The array length is 5

The number value of the array is [0, 13]

#### Topic analysis

That is to say, the mapping from cards to numbers has been solved. As long as there are several zeros in it, is it enough to make up the number of digits.

The length of the array is also unique. At present, we can't see from the examples whether all the inputs are incremental sequences.

The discussion was based on different situations.

If you don't set five flag s, you have to make sure that all of them are incremented to meet the conditions.

## Initial answer:

Violence, quite violence.

class Solution { public boolean isStraight(int[] nums) { //The default nums satisfies the increment Arrays.sort(nums); //First of all, if we do not consider the case of 0, then it must be an incremental sequence. if(nums[4] - nums[0] == 4) { for (int i = 1; i < nums.length; i++) {//Yes, definitely not if(nums[i] == nums[i-1] && nums[i] != 0) return false; } return true; } //A 0 if(nums[0] == 0 && nums[1] != 0 && (nums[4] - nums[1] <= 4)) { for (int i = 1; i < nums.length; i++) {//Yes, definitely not if(nums[i] == nums[i-1] && nums[i] != 0) return false; } return true; } //Two zeros if(nums[0] == 0 && nums[1] == 0 && (nums[4] - nums[2] <= 4)) { for (int i = 1; i < nums.length; i++) {//Yes, definitely not if(nums[i] == nums[i-1] && nums[i] != 0) return false; } return true; } if(nums[0] == 0 && nums[1] == 0 && nums[2] == 0 &&(nums[4] - nums[3] <= 4)) { for (int i = 1; i < nums.length; i++) {//Yes, definitely not if(nums[i] == nums[i-1] && nums[i] != 0) return false; } return true; } return false; } }

Just ask who else

Submit results | Execution time | Memory consumption | language | Submission time | remarks |
---|---|---|---|---|---|

adopt | 1 ms | 35.4 MB | Java | 2021/05/25 21:05 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 21:02 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 21:00 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 20:59 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 20:58 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 20:57 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 20:56 | Add notes |

Compilation error | N/A | N/A | Java | 2021/05/25 20:56 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 20:53 | Add notes |

Wrong answer | N/A | N/A | Java | 2021/05/25 20:52 | Add notes |

Implementation result: passed

Show details add notes

Execution time: 1 ms, beating 91.53% of users in all Java submissions

Memory consumption: 35.4 MB, beating 99.18% of users in all Java submissions

Improved code

class Solution { public boolean isStraight(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length - 1; i++){ if(nums[i] == nums[i + 1] && nums[i] != 0) return false; //There are duplicate and not zero, error } if(nums[4] - nums[0] == 4) return true; //The default nums satisfies the increment if(nums[0] == 0 && nums[1] != 0 && (nums[4] - nums[1] <= 4)) return true;//A 0 if(nums[0] == 0 && nums[1] == 0 && (nums[4] - nums[2] <= 4)) return true;//Two zeros if(nums[0] == 0 && nums[1] == 0 && nums[2] == 0 &&(nums[4] - nums[3] <= 4)) return true;//Three zeros is ridiculous return false; } }

Implementation result: passed

Show details add notes

Execution time: 1 ms, beating 91.53% of users in all Java submissions

Memory consumption: 35.6 MB, beating 93.56% of users in all Java submissions

K God or cow

class Solution { public boolean isStraight(int[] nums) { Arrays.sort(nums); int joker = 0; //King and King for(int i = 0; i < 4; i++) { if(nums[i] == 0) joker++; else if(nums[i] == nums[i + 1]) return false; //It's right } return nums[4] - nums[joker] < 5;// The biggest card - the smallest card < 5 can constitute a shunzi } }

Implementation result: passed

Show details add notes

Execution time: 1 ms, beating 91.53% of users in all Java submissions

Memory consumption: 35.9 MB, beating 33.85% of users in all Java submissions

## Learn from others:

### Method 1

Dream small cold L1 (edited) March 4, 2020

In fact, at first glance, I was confused, because I didn't play cards, and I didn't know what shunzi was, crying. Later, after reading other people's answers, I think the simple understanding is that 0 in this array can be used as any number, so when the cards are not continuous, it can be replaced, and then achieve the requirements of Shun. For example, in this array, there are two zeros, so we have two universal substitutes. Then we can find that there is a discontinuity between 2-4 and there is a lack of 3, so where can we put a zero? When three, 0, 1, 2, 0, 4, 56 and 0 replace 3, we can meet the requirement of continuity. When can't we do that? When there is no big gap, the number of universal substitutes is zero, For example, you only have one 0, but there is a big difference between two consecutive numbers in the array. The number of 0 is not enough, for example, 1-7. If there is a difference of 5 numbers in the middle, you will have one 0, which is obviously not enough, so this is not smooth. Ah, we should play more cards in the future

class Solution { public boolean isStraight(int[] nums) { Arrays.sort(nums); int zeroCnt=0,diff=0; for(int i=0;i<nums.length-1;i++){ if(nums[i]==0){ zeroCnt++; }else{ if(nums[i]==nums[i+1]) return false; if(nums[i]+1!=nums[i+1]){ diff+=nums[i+1]-nums[i]-1; } } } return zeroCnt>=diff; } }

### Method 2

ResolmiL3 (edited) March 2, 2020

Only 5 cards, first exclude the pair, and then seek the maximum and minimum card surface difference on the line, less than or equal to 4 is certainly shunzi

public boolean isStraight(int[] nums) { int[] bucket=new int[14]; int min=14,max=-1; for(int i=0;i<nums.length;i++){ if(nums[i]==0) continue; //If there are non-zero pairs, direct false if(bucket[nums[i]]==1) return false; bucket[nums[i]]++; //Record the maximum and minimum of card surface min=Math.min(min,nums[i]); max=Math.max(max,nums[i]); } //Less than or equal to 4 on the line, less with 0 complement return max-min<=4; }

### Method 3

Tang Dong L1 Six hours ago

class Solution { public boolean isStraight(int[] nums) { Arrays.sort(nums); int count = 0; //Number of records 0 for(int i = 0,j = 1;j < nums.length;i++,j++){ if(nums[i] == 0){ count++; }else{ if(nums[j] == nums[i]) return false; if(nums[j] - nums[i] == 1) continue; else count -= nums[j] - nums[i] - 1; if(count < 0) return false; } } return true; } }

### Method 4

Jupiter 2021-04-28 java 1ms

public boolean isStraight(int[] nums) { Arrays.sort(nums); int count = 0;// record the number of zero for(int i = 0; i < 4; i ++){ if(nums[i] == 0) count ++; else{ if(nums[i + 1] - nums[i] > count + 1 || nums[i + 1] == nums[i]){ return false; } } } return true; }

### Method 5

K-god's solution:

Author: jyd

Link: https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/

Source: LeetCode

#### Method 1: Set + traversal

Traverse five cards, meet the size of the king (that is 0) directly skip.

Repeat discrimination: Set is used to realize traversal and duplicate discrimination, and the time complexity of the search method of Set is O(1);

Get the maximum / minimum card: with the help of auxiliary variables ma and mi, traverse statistics.

class Solution { public boolean isStraight(int[] nums) { Set<Integer> repeat = new HashSet<>(); int max = 0, min = 14; for(int num : nums) { if(num == 0) continue; // Jump over Xiao Wang max = Math.max(max, num); // The biggest brand min = Math.min(min, num); // Minimum card if(repeat.contains(num)) return false; // If there is repetition, return false in advance repeat.add(num); // Add this card to Set } return max - min < 5; // The biggest card - the smallest card < 5 can constitute a shunzi } }

#### Method 2: sort + traverse

class Solution { public boolean isStraight(int[] nums) { int joker = 0; Arrays.sort(nums); // Array sorting for(int i = 0; i < 4; i++) { if(nums[i] == 0) joker++; // Count the number of big and small kings else if(nums[i] == nums[i + 1]) return false; // If there is repetition, return false in advance } return nums[4] - nums[joker] < 5; // The biggest card - the smallest card < 5 can constitute a shunzi } }

K God or cow, the same idea is more intuitive and easier to write

## summary

The above is the content and learning process of this problem. It's hard to find out more than 90 answers by myself. I'll reward myself for leaving work early. Ha ha.

Welcome to discuss and make progress together.