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.