2021-01-09 第 43 场双周赛

1716. 计算力扣银行的钱

思路

：模拟即可

class Solution {
    public int totalMoney(int n) {
        int res = 0;
        for(int i = 0;i < n;i++) {
            int week = i / 7;
            int day = i % 7 + 1;
            res += (week+day);
        }
        return res;
    }
}

1717. 删除子字符串的最大得分

思路1

：贪心即可，哪种字符串的得分高先删哪种字符串。

class Solution {
    public int cal(String _s, int x, int y, char[] a, char[] b) {
        int cnt_x = 0, cnt_y = 0,start = 0;
        boolean flag = true;
        Deque<Character> q1 = new LinkedList<>();
        Deque<Character> q2 = new LinkedList<>();
        char[] s = _s.toCharArray();
        
        for(char ch : s) {
            if(ch == a[1] && q1.size() > 0 && q1.getLast() == a[0]) {
                q1.pollLast();
                cnt_x++;
            } else {
                q1.offerLast(ch);
            }
        }
        
        while(q1.size() > 0) {
            char ch = q1.pollFirst();
            if(ch == b[1] && q2.size() > 0 && q2.getLast() == b[0]) {
                cnt_y++;
                q2.pollLast();
            } else {
                q2.offerLast(ch);
            }
        }
        return x * cnt_x + y * cnt_y;
    }

    public int maximumGain(String s, int x, int y) {
        if(x >= y) {
            return cal(s, x, y, "ab".toCharArray(), "ba".toCharArray());
        } else {
            return cal(s, y, x, "ba".toCharArray(), "ab".toCharArray());
        }
    }
}

思路2

：题解区大牛的思路，可以做到无需额外空间

class Solution {
    public int maximumGain(String _s, int x, int y) {
        char[] s = _s.toCharArray();
        int n = s.length, res = 0;
        if(x < y) {
            int t = x;  x = y;  y = t;
            for(int i = 0;i < s.length;i++) {
                if(s[i] == 'a') s[i] = 'b';
                else if(s[i] == 'b')    s[i] = 'a';
            }
        }
        int i = 0;
        while(i < n) {
            while(i < n && s[i] != 'a' && s[i] != 'b')  i++;
            int ca = 0, cb = 0;
            while(i < n && (s[i] == 'a' || s[i] == 'b')) {
                if(s[i] == 'a') {
                    ca++;
                } else {
                    if(ca > 0) {
                        ca--;
                        res += x;
                    } else {
                        cb++;
                    }
                }
                i++;
            }
            res += Math.min(ca, cb) * y;
        }
        return res;
    }
}

1718. 构建字典序最大的可行序列

思路

：观察数据范围，发现使用dfs + 剪枝即可。

class Solution {
    int[] nums = new int[50];
    int[] vis = new int[21];

    public int[] constructDistancedSequence(int n) {
        Arrays.fill(nums, -1);  Arrays.fill(vis, -1);
        int len = n*2-1;    dfs(0,n,len);
        int[] res = new int[len];
        for(int i = 0;i < len;i++) {
            res[i] = nums[i];
        }
        return res;
    }

    public boolean dfs(int pos, int n,int limit) {
        if(pos == limit) {
            return true;
        } else if(nums[pos] != -1) {
            return dfs(pos+1,n,limit);
        }
        
        for(int i = n;i >= 1;i--) {
            if(vis[i] != -1)    continue;
            if(i != 1 && pos + i < limit && nums[i+pos] == -1) {
                nums[pos] = i;  nums[i+pos] = i;
                vis[i] = 1;
                if(dfs(pos+1, n, limit)) {
                    return true;
                }
                nums[pos] = -1;  nums[i+pos] = -1;
                vis[i] = -1;
            } else if(i == 1) {
                nums[pos] = i;  vis[i] = 1;
                if(dfs(pos+1, n, limit)) {
                    return true;
                }
                nums[pos] = -1; vis[i] = -1;
            }
        }
        return false;
    }
}