Mock Interview: Microsoft

1470. Shuffle the Array

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[2 * n];
        
        for (int i = 0; i < n; i++) {
            result[i * 2] = nums[i];
            result[i * 2 + 1] = nums[i + n];
        }
        
        return result;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Shuffle the Array.
Memory Usage: 38.8 MB, less than 95.36% of Java online submissions for Shuffle the Array.
そのまま・・・RG??^^

1156. Swap For Longest Repeated Character Substring

class Solution {
    public int maxRepOpt1(String text) {
        int allowance = 1;
        int maxlength = 1; 
        int curlength = 1; 
        char longest = text.charAt(0);
        char before = text.charAt(0);
        char potential = text.charAt(0);
        
        for (int i = 1; i < text.length(); i++) {
            //character repeats
            if (text.charAt(i) == before) {
                curlength++;
                before = text.charAt(i);
                //doesnt repeat
            } else {
                //if no gaps have been made
                if (allowance == 1) {
                    allowance--;
                //gap has already been used
                } else {
                    allowance = 1;
                    before = text.charAt(i);
                    curlength = 1; 
                    //if before the gap the character was the same
                    if (before == potential) {
                        curlength++;
                    //before the gap char was different - using allowa
                    } else {
                        before = potential;
                        allowance = 0; 
                        curlength = 1; 
                    }
                }
            }
            //updating the max char
            if (maxlength < curlength) {
                longest = text.charAt(i);
                maxlength = curlength;
            }
        }
        
        allowance = 1;
        before = text.charAt(0);
        int result = 0;
        if (before == longest) {
            result++;
        }
        for (int j = 0; j < text.length(); j++) {
            if (text.charAt(j) == longest && allowance == 1) {
                result++;
            } else if (text.charAt(j) == longest) {
                result++;
            } else if (text.charAt(j) != longest && allowance == 0) {
                
            }
        }
    }
}

あ、私は見るからに嫌いです.
考えたいものが多すぎたので、しょっぱくてしばらくして諦めました.

ソリューション

class Solution {
    public int maxRepOpt1(String text) {
        List<CharState> stateList = new ArrayList<CharState>();
        int startPos=0, endPos=0;
        char c = text.charAt(0);
        int i = 1;
        
        int[] charCount = new int[26];
        
        charCount[c-'a']++;
        
        while(i<text.length())
        {
            char cur = text.charAt(i);
            charCount[cur-'a']++;
            
            if(cur != c)
            {
                stateList.add(new CharState(c, startPos, endPos));
                
                c = cur;
                startPos = i;
                endPos = i;                
            }
            else
            {
                endPos = i;
            }
            
            i++;
        }
        
        stateList.add(new CharState(c, startPos, endPos));
        
        int maxLen = 1;
        // scenario 1, aaabba, find another a to replace b to increase maxlen+1;
        for(i=0;i<stateList.size();i++)
        {
            CharState cs = stateList.get(i);
            int len = cs.endPos-cs.startPos+1;
            
            if(len < charCount[cs.c-'a'])
            {
                len++;
            }
            
            maxLen = Math.max(maxLen, len);            
        }
        
        // scenario 2, aaabaa, find another a to replace b
        
        for(i=1;i<stateList.size()-1;i++)
        {
            CharState before = stateList.get(i-1);
            CharState cs = stateList.get(i);
            CharState after = stateList.get(i+1);
            
            int beforeLen = before.endPos-before.startPos+1;
            int afterLen = after.endPos-after.startPos+1;
            
            if(cs.startPos == cs.endPos && before.c == after.c)
            {
                int totalLen = beforeLen + afterLen;
                if(beforeLen + afterLen < charCount[before.c - 'a'])
                {
                    totalLen++;
                }
                maxLen = Math.max(maxLen, totalLen);                
            }
        }
        
        return maxLen;
    }
    
    public class CharState
    {
        char c;
        int startPos;
        int endPos;
        
        public CharState(char ch, int s, int e)
        {
            c = ch;
            startPos = s;
            endPos = e;
        }
    }
}

Runtime: 6 ms, faster than 69.97% of Java online submissions for Swap For Longest Repeated Character Substring.
Memory Usage: 39.1 MB, less than 48.16% of Java online submissions for Swap For Longest Repeated Character Substring.

ソリューション2

class Solution {
    public int maxRepOpt1(String text) {
        int[] hash = new int[26];
         int max = 0;
        for(char c : text.toCharArray()) {
            hash[c - 'a']++;
            max = Math.max(max, hash[c - 'a']);
        }
        if(max <= 1) return max;
        max = 1;
        int i = 0, n = text.length();
        while(i < n) {
            int j = i;
            char cur = text.charAt(i);
			// find the left side length;
            while(j < n && text.charAt(j) == cur) j++;
            int k = j + 1;
			// find the right side length;
            while(k < n && text.charAt(k) == cur) k++;
			// max should be  the longest of (left + right) 
            max = Math.max(max, (k - i - 1 == hash[cur - 'a']) ? k - i - 1 : k - i);
            i = j;
        }
        return max;
    }
}

Runtime: 3 ms, faster than 95.47% of Java online submissions for Swap For Longest Repeated Character Substring.
Memory Usage: 37.9 MB, less than 82.72% of Java online submissions for Swap For Longest Repeated Character Substring.
でもこうやって解けば数の多い人が勝つとは限らないのか…?
構造そのものがそうなのでしょうか?