矩阵区域和(还没太搞明白)

2020-12-12

给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

i - K <= r <= i + K, j - K <= c <= j + K 
(r, c) 在矩阵内。
 

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]
 

提示：

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100
通过次数5,830提交次数8,042

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/matrix-block-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二维前缀和

题目的意思是对于每个元素$(i,j)$，求其相邻范围上下左右范围为$i+k,i-k,j+k,j-k$的区域内所有元素的和

例如：

1
2
3

[1,2,3]     [12,21,16]
[4,5,6]     [27,45,33]      
[7,8,9]     [24,39,28]

其中：

5的相邻范围内的所有和为整个矩阵的所有元素的和

1的相邻范围内的所有和为，1，2，4，5四个元素的和

3的相邻范围内的所有和为，2，3，5，6四个元素的和

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int K) {
        int h = mat.length;
        int w = mat[0].length;
        int dp[][] = new int[h + 1][w + 1];
        
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                mat[i][j] = getSum(dp, h, w, i + K + 1, j + K + 1) -
                        getSum(dp, h, w, i - K, j + K + 1) -
                        getSum(dp, h, w, i + K + 1, j - K) +
                        getSum(dp, h, w, i - K, j - K);
            }
        }
        return mat;
    }

    public int getSum(int[][] dp, int h, int w, int y, int x) {
        y = Math.max(Math.min(y, h), 0);
        x = Math.max(Math.min(x, w), 0);
        return dp[y][x];
    }
}

展开全文 >>

二维前缀和

2020-12-12

设二维数组A的大小为m*n,行下表的范围为[1,m]列下标的范围为[1,n].

数组P是A的前缀和数组，等价于P中的每个元素P[i][j]:

如果i和j均大于0，那么P[i][j]表示A中以（1，1）为左上角，（i,j）为右下角的矩形区域的元素之和；
如果i和j中至少有一个等于0，那么P[i][j]也等于0;

数组P可以帮助我们在O（1）的时间内求出任意一个矩形区域的元素之和。具体地，设我们需要求和的矩形区域的左上角为（x1,y1）,右下角为（x2,y2），则该矩形区域的元素之和可以表示为：

1 2	sum = A[x1...x2][y1...y2] = P[x2][y2]-P[x1-1][y2]-P[x2][y1-1]+P[x1-1][y1-1]

其正确性可以通过容斥远离得出。以下图为例，当A的大小为8*5，需要求和的矩形区域（深绿色部分）的左上角为（3，2），右下角为（5，5）时，该矩形区域的元素之和为

1	P[5][5]-P[2][5]-P[5][1]+P[2][1]

avatar

那么如何得到数组P（数组P是A的前缀数组也就是开头讲的）呢？我们按照行优先的顺序依次计算数组P中的每个元素，即当我们在计算P[i][j]时，数组P的前i-1行，以及第i行的前j-1各元素都已经计算完成。此时我们可以考虑（i,j）这个1*1的矩形区域，根据上面的等式，有：

1	A[i][j] = P[i][j] - P[i - 1][j] - P[i][j - 1] + P[i - 1][j - 1]

A[i][j]是：左上角第一个元素到A[i][j]包含的矩形区域的和

由于等式中的A[i][j],P[i-1][j],P[i][j-1]和P[i-1][j-1]均已知我们可以通过

1	P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + A[i][j]

在O（1）的时间计算出P[i][j]。因此按照行优先的顺序，我们可以在O（MN）的时间得到数组P。在此之后，我们就可以很方便的在O（1）时间能求出任意一个矩形区域的元素之和了。

注意事项：

在大部分语言中，数组下标是从 0 而不是 1 开始，在实际的代码编写过程中需要考虑这一情况。

参考文献

力扣官方题解

展开全文 >>

电话号码的字母组合

2020-12-11

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

static Map<Character, List<Character>> d2AMap = new HashMap<>();

d2AMap.put('2', Arrays.asList('a', 'b', 'c'));
d2AMap.put('3', Arrays.asList('d', 'e', 'f'));
d2AMap.put('4', Arrays.asList('g', 'h', 'i'));
d2AMap.put('5', Arrays.asList('j', 'k', 'l'));
d2AMap.put('6', Arrays.asList('m', 'n', 'o'));
d2AMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
d2AMap.put('8', Arrays.asList('t', 'u', 'v'));
d2AMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最暴力的回溯

class Solution {

    
    static Map<Character, List<Character>> d2AMap = new HashMap<>();
    List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")){
            return new ArrayList<String>();
        }
        d2AMap.put('2', Arrays.asList('a', 'b', 'c'));
        d2AMap.put('3', Arrays.asList('d', 'e', 'f'));
        d2AMap.put('4', Arrays.asList('g', 'h', 'i'));
        d2AMap.put('5', Arrays.asList('j', 'k', 'l'));
        d2AMap.put('6', Arrays.asList('m', 'n', 'o'));
        d2AMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
        d2AMap.put('8', Arrays.asList('t', 'u', 'v'));
        d2AMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));
        backtrack(0, digits, new StringBuilder());
        return result;
    }

    public void backtrack(int cur, String digits, StringBuilder bd) {
        if (cur == digits.length()) {
            result.add(bd.toString());
        } else {
            List<Character> list = d2AMap.get(digits.charAt(cur));
            for (int i = 0; i < list.size(); i++) {
                bd.append(list.get(i));
                backtrack(cur + 1, digits, bd);
                bd.deleteCharAt(bd.length() - 1);
            }

        }

    }
}

官方题解


class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

时间复杂度：O(3^m \times 4^n)其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 nn 个对应 44 个字母的数字时，不同的字母组合一共有 3^m \times 4^n种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

dota2参议院

2020-12-11

649. Dota2 参议院

难度：中等

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的**一**项：

禁止一名参议员的权利：

参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
宣布胜利：

如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。

示例 1：

1
2
3

输入："RD"
输出："Radiant"
解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人

示例 2：

输入："RDD"
输出："Dire"
解释：
第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示：

给定字符串的长度在 [1, 10,000] 之间.

模拟


class Solution {
    public String predictPartyVictory(String senate) {
        char[] sen = senate.toCharArray();
        int dCount = 0;
        int rCount = 0;

        for (int i = 0; i < sen.length; i++) {//统计每个阵营的议员数量
            if (sen[i] == 'D') {
                dCount++;
            } else {
                rCount++;
            }
        }
        int conD = 0, conR = 0;//需要跳过的相应阵营人的数量
        boolean[] senFlag = new boolean[sen.length];//是否已经被禁言

        while (dCount > 0 && rCount > 0) {//双方都还有人剩下
            for (int i = 0; i < sen.length; i++) {
                if (sen[i] == 'D') {//如果是D阵营

                    if (conD == 0) {//并且不需要跳过当前的
                        if (!senFlag[i]) {//并且没有被禁言
                            rCount--;//禁掉一个R阵营的人
                            conR++;//R阵营需要跳过的人数多1
                        }

                    } else {
                        if (conD > 0 && !senFlag[i])//如果D阵营有需要跳过的，并且当前的没被禁言，那么将该参议员禁言，且该阵营需要禁言的减一
                            conD--;
                        senFlag[i] = true;//禁言
                        continue;
                    }
                    if (rCount <= 0) {//如果R阵营没有可以发声的了，那么D阵营获胜
                        return "Dire";
                    }


                } else {
                    if (conR == 0) {
                        if (!senFlag[i]) {
                            dCount--;
                            conD++;
                        }

                    } else {
                        if (conR > 0 && !senFlag[i])
                            conR--;
                        senFlag[i] = true;
                        continue;
                    }
                    if (dCount <= 0) {
                        return "Radiant";
                    }
                }

            }
        }
        return dCount > rCount ? "Dire" : "Radiant";
    }
}

「循环」队列

用两个队列维护每个阵营的议员的下标，如果哪个阵营的下标小就先选哪个，另外阵营的那个被丢掉，没被丢掉的阵营的那个直接放到下一轮的index也就是curIndex+n


class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        Queue<Integer> radiant = new LinkedList<Integer>();
        Queue<Integer> dire = new LinkedList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (senate.charAt(i) == 'R') {
                radiant.offer(i);//将每个阵营中的下标加入队列
            } else {
                dire.offer(i);
            }
        }
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int radiantIndex = radiant.poll(), direIndex = dire.poll();
            if (radiantIndex < direIndex) {//哪个阵营的人靠前先哪个阵营说话，禁掉对方阵营的第一个，将这个元素放到下一轮
                radiant.offer(radiantIndex + n);//radiantIndex + n是下一轮的顺序，对方阵营的那个人直接丢掉了
            } else {
                dire.offer(direIndex + n);//direIndex + n是下一轮的顺序，对方阵营的那个人直接丢掉了
            }
        }
        return !radiant.isEmpty() ? "Radiant" : "Dire";
    }
}

参考文献

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/dota2-senate/solution/dota2-can-yi-yuan-by-leetcode-solution-jb7l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

字母异位词分组

2020-12-10

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：

所有输入均为小写字母。
不考虑答案输出的顺序。
通过次数124,766提交次数194,667

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

利用哈希表统计正确的词语，然后暴力比较

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[][] bucket = new int[strs.length][26];

        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            for (int j = 0; j < str.length(); j++) {
                bucket[i][str.charAt(j) - 'a']++;
            }
        }
        List<List<String>> result = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            List<String> inner = new ArrayList<>();
            if (strs[i].equals("0")) {
                continue;
            }
            inner.add(strs[i]);
            for (int j = i + 1; j < strs.length; j++) {

                if (strs[j].equals("0")) {
                    continue;
                }
                boolean flag = true;

                for (int t = 0; t < 26; t++) {
                    if (bucket[i][t] != bucket[j][t]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    inner.add(strs[j]);
                    strs[j] = "0";
                }

            }
            result.add(inner);
        }


        return result;
    }
}

对字符串排序，并使用字典对字符串分类，异位的字符串分到同一类别

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);//首先对字母进行排序
            String key = String.valueOf(ca);//然后以排序后的字符作为字典的键值
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());//将原来的字符串以链表的形式保存在map的值中
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

使用桶计数计算字符串的唯一识别串

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) count[c - 'a']++;//先对字符串进行桶计数

            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {//生成某个字符串的唯一识别字符串作为Map的key
                sb.append('#');//不加#号时，当用例为 ["bdddddddddd", "bbbbbbbbbbc"] ，生成的Map key值为[ 010100000000000000000000000 010100000000000000000000000] ，就通过不了哦！
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

参考文献

官方题解

作者：LeetCode
链接：https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

括号生成

2020-12-10

22. 括号生成

难度中等1762

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1 2	输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1 2	输入：n = 1 输出：["()"]

提示：

1 <= n <= 8

回溯方法

如果左括号的数量还没有满足,先生成左括号
如果右括号的数量小于左括号的数量就生成右括号,否则不生成右括号

class Solution {
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0,0,n*2);
        return list;
    }
    int n=0;
    List<String> list = new ArrayList<>();
    StringBuilder bd = new StringBuilder();
    public void dfs(int left,int right,int rest){
        if(rest==0){
            String s=bd.toString();
            list.add(s);
            return;
        }
        // 如果左括号的数量还没有满足,先生成左括号
        if(left<n){
            bd.append("(");
            dfs(left+1,right,rest-1);
            bd.deleteCharAt(bd.length()-1);
        }
        // 如果右括号的数量小于左括号的数量就生成右括号,否则不生成右括号
        if(left>right){
            bd.append(")");
            dfs(left,right+1,rest-1);
            bd.deleteCharAt(bd.length()-1);
        }
    }
}

暴力回溯

class Solution{
   List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        char[] seq = new char[2 * n];

        backtrack(seq, 0, 2 * n);

        return result;
    }

    public void backtrack(char[] seq, int cur, int max) {
        if (cur == max) {
            if (isValid(seq)) {
                result.add(new String(seq));
            }
        } else {
            seq[cur] = '(';
            backtrack(seq, cur + 1, max);
            seq[cur] = ')';
            backtrack(seq, cur + 1, max);
        }
    }


    public boolean isValid(char[] seq) {
        int balance = 0;
        for (char c : seq) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }
}

优化的回溯

//如果左括号的数量小于n，可以继续添加左括号
//如果右括号的数量小于左括号，可以继续添加右括号
这样就可以不用验证生成序列的正确性了

class Solution{
    List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        char[] seq = new char[2 * n];
        backtrack(seq, 0, 2 * n);
        return result;
    }
    //如果左括号的数量小于n，可以继续添加左括号
    //如果右括号的数量小于左括号，可以继续添加右括号
    public static void backtrack(StringBuilder bd, int cur, int max, int left, int right) {
        if (cur == max) {
            result.add(bd.toString());
        } else {
            if (left < max / 2) {
                bd.append('(');
                backtrack(bd, cur + 1, max, left + 1, right);
                bd.deleteCharAt(bd.length() - 1);
            }
            if (right < left) {
                bd.append(')');
                backtrack(bd, cur + 1, max, left, right + 1);
                bd.deleteCharAt(bd.length() - 1);
            }


        }

    }
}

按括号序列的长度递归


class Solution {
    ArrayList[] cache = new ArrayList[100];

    public List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c) {
                for (String left: generate(c)) {
                    for (String right: generate(n - 1 - c)) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }

    public List<String> generateParenthesis(int n) {
        return generate(n);
    }
}

参考文献


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

旋转图像（矩阵）

2020-12-10

面试题 01.07. 旋转矩阵

难度中等

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

注意：本题与主站 48 题相同：https://leetcode-cn.com/problems/rotate-image/

先转置矩阵，然后对矩阵的每一行的左右进行替换

class Solution {
    public void rotate(int[][] matrix) {
        //先进行矩阵转置
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i + 1; j < matrix[0].length; j++) {
                swap(matrix, i, j, j, i);
            }
        }
        //再对每一行进行左右替换
        for (int y = 0; y < matrix.length; y++) {
            for (int x = 0; x < matrix[0].length / 2; x++) {
                swap(matrix, y, x, y, matrix[0].length - 1 - x);
            }
        }

    }

    public void swap(int[][] matrix, int y1, int x1, int y2, int x2) {
        int temp = matrix[y1][x1];
        matrix[y1][x1] = matrix[y2][x2];
        matrix[y2][x2] = temp;
    }
}

时间复杂度O(N*N),空间复杂度O(1)

avatar

avatar

旋转四个矩形

class Solution {
  public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2 + n % 2; i++) {
      for (int j = 0; j < n / 2; j++) {
        int[] tmp = new int[4];
        int row = i;
        int col = j;
        for (int k = 0; k < 4; k++) {
          tmp[k] = matrix[row][col];
          int x = row;
          row = col;
          col = n - 1 - x;
        }
        for (int k = 0; k < 4; k++) {
          matrix[row][col] = tmp[(k + 3) % 4];
          int x = row;
          row = col;
          col = n - 1 - x;
        }
      }
    }
  }
}

时间复杂度O(N*N),空间复杂度O(1)

单次循环中旋转四个矩形

class Solution {
  public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < (n + 1) / 2; i ++) {
      for (int j = 0; j < n / 2; j++) {
        int temp = matrix[n - 1 - j][i];
        matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
        matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i];
        matrix[j][n - 1 - i] = matrix[i][j];
        matrix[i][j] = temp;
      }
    }
  }
}

时间复杂度O(N*N),空间复杂度O(1)

参考文献

作者：LeetCode
链接：https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

柠檬水找零(简单题)

2020-12-10

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：
输入：[5,5,10]
输出：true

示例 3：
输入：[10,10]
输出：false

示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
 

提示：

0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lemonade-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fiveCount = 0;
        int tenCount = 0;
        for (int i = 0; i < bills.length; i++) {

            switch (bills[i]) {
                case 5:
                    fiveCount++;//收到五元，直接存下来
                    break;
                case 10:
                    fiveCount--;//收到十元，找五元
                    tenCount++;
                    if (fiveCount < 0) {//如果五元的数量不够，那么不能继续
                        return false;
                    }
                    break;
                case 20:
                    if (tenCount > 0) {//收到20首先看看有没有10元的，有的话找一个10元和一个五元
                        tenCount--;
                        fiveCount--;
                    } else {//如果没有十元的找3个五元的
                        fiveCount = fiveCount - 3;
                    }
                    if (fiveCount < 0) {//如果五元的不够，那么不能继续
                        return false;
                    }
                    break;
            }
        }

        return true;
    }
}

官方题解

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

参考文献

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/lemonade-change/solution/ning-meng-shui-zhao-ling-by-leetcode-sol-nvp7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

统计字典序元音字符串的数目

2020-12-08

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例 1：

输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：
输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：
输入：n = 33
输出：66045
 
提示：

1 <= n <= 50 
通过次数5,190提交次数6,595

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-sorted-vowel-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一看到排列组合就想到了回溯

class Solution {

    public int count = 0;
    public int countVowelStrings(int n) {
        backtrack(0, 0, n);
        return count;
    }

    public void backtrack(int start, int deep, int maxDeep) {
        if (deep >= maxDeep) {
            count++;
            return;
        }
        for (int i = start; i < 5; i++) {
            backtrack(i, deep + 1, maxDeep);
        }
    }
}

动态规划方法

一维动归

class Solution {
    public int countVowelStrings(int n) {
        int[] dp = new int[]{1, 1, 1, 1, 1};
        for(int i = 1;i < n;i++) {
            for(int j = 1;j < 5;j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
    }
}

二维动归

class Solution {
    public int countVowelStrings(int n) {
        int[][] dp = new int[n][5];
        dp[0][0] = 1;
        dp[0][1] = 2;
        dp[0][2] = 3;
        dp[0][3] = 4;
        dp[0][4] = 5;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 5; ++j) {
                if (j == 0){
                    dp[i][j] = dp[i-1][j];
                } 
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } 
            }
        }
        return dp[n-1][4];
    }
}

参考文献

fzt01057的评论

听韬声画倩影的评论

展开全文 >>

将数组拆分成斐波那契序列

2020-12-08

给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

形式上，斐波那契式序列是一个非负整数列表 F，且满足：

0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
F.length >= 3；
对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。


示例 1：
输入："123456579"
输出：[123,456,579]

示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]

示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。

示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
 

提示：

1 <= S.length <= 200
字符串 S 中只含有数字。
通过次数15,430提交次数32,521

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯 + 剪枝

将给定的字符串拆分成斐波那契式序列，可以通过回溯的方法实现。

使用列表存储拆分出的数，回溯过程中维护该列表的元素，列表初始为空。遍历字符串的所有可能的前缀，作为当前被拆分出的数，然后对剩余部分继续拆分，直到整个字符串拆分完毕。

根据斐波那契式序列的要求，从第 3 个数开始，每个数都等于前 2 个数的和，因此从第 3 个数开始，需要判断拆分出的数是否等于前 2 个数的和，只有满足要求时才进行拆分，否则不进行拆分。

回溯过程中，还有三处可以进行剪枝操作。

拆分出的数如果不是 0，则不能以 0 开头，因此如果字符串剩下的部分以 0 开头，就不需要考虑拆分出长度大于 1 的数，因为长度大于 1 的数以 0 开头是不符合要求的，不可能继续拆分得到斐波那契式序列；

拆分出的数必须符合 32 位有符号整数类型，即每个数必须在 [0,2^{31}-1]的范围内，如果拆分出的数大于 2^{31}-1，则不符合要求，长度更大的数的数值也一定更大，一定也大于 2^{31}-1，因此不可能继续拆分得到斐波那契式序列；

如果列表中至少有 2 个数，并且拆分出的数已经大于最后 2 个数的和，就不需要继续尝试拆分了。

当整个字符串拆分完毕时，如果列表中至少有 3 个数，则得到一个符合要求的斐波那契式序列，返回列表。如果没有找到符合要求的斐波那契式序列，则返回空列表。

实现方面，回溯需要带返回值，表示是否存在符合要求的斐波那契式序列。

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> list = new ArrayList<Integer>();
        backtrack(list, S, S.length(), 0, 0, 0);
        return list;
    }

    public boolean backtrack(List<Integer> list, String S, int length, int index, int sum, int prev) {
        if (index == length) {
            return list.size() >= 3;
        }
        long currLong = 0;
        for (int i = index; i < length; i++) {
            if (i > index && S.charAt(index) == '0') {
                break;
            }
            currLong = currLong * 10 + S.charAt(i) - '0';//先前的数字乘以10加上现在的数字
            if (currLong > Integer.MAX_VALUE) {//如果溢出了直接跳出
                break;
            }
            int curr = (int) currLong;
            if (list.size() >= 2) {
                if (curr < sum) {
                    continue;
                } else if (curr > sum) {
                    break;
                }
            }
            list.add(curr);
            if (backtrack(list, S, length, i + 1, prev + curr, curr)) {
                return true;
            } else {
                list.remove(list.size() - 1);
            }
        }
        return false;
    }
}

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> res = new ArrayList<>();
        dfs(S.toCharArray(), 0, S.length(), res);
        return res;
    }

    // TODO: 从[begin,end)找到符合条件的数,并加入res
    private boolean dfs(char[] s, int begin, int end, List<Integer> res) {
        if (begin == end)
            return res.size() > 2;
        long num = 0;
        for (int i = begin; i < end; i++) {
            num = num * 10 + (s[i] - '0');//取[begin,i]的数
            //首位为0或超过整型范围就不能继续了
            if (i == begin + 1 && s[begin] == '0' || num > Integer.MAX_VALUE)
                break;
            int length = res.size();

            if (length < 2 || res.get(length - 1) + res.get(length - 2) == num) {
                res.add((int) num);
                if (dfs(s, i + 1, end, res))//剩下部分也符合条件
                    return true;
                res.remove(length);//回溯
            }
        }
        return false;
    }
}

参考文献

Gerrit的评论

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/solution/jiang-shu-zu-chai-fen-cheng-fei-bo-na-qi-ts6c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>