输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

1. 0 <= nums.length <= 50000
2. 0 <= nums[i] <= 10000

双指针原地交换

双指针

1. 一个找偶数数字
2. 一个往后找奇数数字
3. 需要判断下cur = Math.max(i,cur);，因为当找偶数数字的指针往后移动的时候，找奇数的指针可能留在原地，这样再找奇数的时候会找到偶数位前面的奇数
4. swap()方法常规操作

class Solution {
    public int[] exchange(int[] nums) {
        if (nums.length < 2){
            return nums;
        }
        int cur = 1;
        for (int i = 0; cur < nums.length && i < nums.length ; i++) {
            if (nums[i] % 2 == 0){
                cur = Math.max(i,cur);
                while (cur < nums.length && nums[cur] % 2 == 0){
                    cur++;
                }
                swap(nums,i,cur);
            }
        }
        return nums;

    }

    private void swap(int[] nums, int x, int y){
        if (y >= nums.length){
            return;
        }
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

位运算->哈希，位运算->重复判断

抄大佬作业，这个我是真想不来

class Solution {
    public int maxProduct(String[] words) {
        int max = 0;
        int[] arr = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int h = 0;
            for (int c = 0; c < words[i].length(); c++) {
                h |= 1 << (words[i].charAt(c) - 'a');
            }
            arr[i] = h;
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = i+1; j < words.length; j++) {
                if ((arr[i] & arr[j]) != 0){
                    continue;
                }
                max = Math.max(max,words[i].length() * words[j].length());
            }
        }
        return max;
    }
}

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。

1. 沿着当前方向尝试 往前一步 。
2. 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。

如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。

请你实现 Robot 类：

• Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。
• void move(int num) 给机器人下达前进 num 步的指令。
• int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。
• String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。

示例 1：

输入：
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.move(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.move(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.move(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.move(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.move(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

提示：

• 2 <= width, height <= 100
• 1 <= num <= 105
• move ，getPos 和 getDir 总共 调用次数不超过 104 次。

JAVA模拟

模拟得有点费劲

1. 调用move()方法的时候并不去实际模拟走动，而是增加步数并取模
2. 调用getPos()和getDir()的时候才去模拟走动
3. 初始direction定义为SOUTH，后面取模为0的话不用另算
4. 但是初始定为SOUTH初始查询方向的时候就不对了，所以再加一个moved判断，只要执行过move()就返回真实的direction，没执行过moved的话，就返回向东

可能还是数学计算的方法简单点吧，

class Robot {

    int[][] matrix;

    private static String NORTH = "North";
    private static String EAST = "East";
    private static String SOUTH = "South";
    private static String WEST = "West";

    private int[] position;
    private static String[] dirArr;
    {
        dirArr = new String[]{ EAST, NORTH,  WEST, SOUTH };
    }

    private int direction = 3;

    private int perimeter = 0;

    private int count = 0;

    boolean moved = false;

    public Robot(int width, int height) {
        matrix = new int[width][height];
        position = new int[2];
        perimeter = (width * 2 + height * 2) - 4;
    }

    public void move(int num) {
        count += num;
        count %= perimeter;
        moved = true;
    }


    /**
     *
     *        西 ↑
     *   南         北
     *   ←          →
     *        东 ↓
     *
     */
    private void goNext(){
        int[] next;
        switch (direction){
            case 0:
                next = new int[]{position[0]+1,position[1]};
                break;
            case 1:
                next = new int[]{position[0],position[1]+1};
                break;
            case 2:
                next = new int[]{position[0]-1,position[1]};
                break;
            case 3:
                next = new int[]{position[0],position[1]-1};
                break;
            default:
                return;
        }
        if (next[0] >= matrix.length || next[1] >= matrix[0].length || next[0]<0 ||next[1] <0){
            direction = (direction+1)%4;
            goNext();
            return ;
        }
        position = next;
    }


    private void __move(){
        while (count>0){
            goNext();
            count--;
        }
    }

    public int[] getPos() {
        __move();
        return position;
    }

    public String getDir() {
        __move();
        return moved?dirArr[direction]:dirArr[0];
    }
}

如果两个字符串 word1 和 word2 中从 'a' 到 'z' 每一个字母出现频率之差都 不超过 3 ，那么我们称这两个字符串 word1 和 word2 几乎相等 。

给你两个长度都为 n 的字符串 word1 和 word2 ，如果 word1 和 word2 几乎相等 ，请你返回 true ，否则返回 false 。

一个字母 x 的出现 频率 指的是它在字符串中出现的次数。

示例 1：

输入：word1 = "aaaa", word2 = "bccb"
输出：false
解释：字符串 "aaaa" 中有 4 个 'a' ，但是 "bccb" 中有 0 个 'a' 。
两者之差为 4 ，大于上限 3 。

示例 2：

输入：word1 = "abcdeef", word2 = "abaaacc"
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。
- 'b' 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。
- 'c' 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。
- 'd' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
- 'e' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
- 'f' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。

示例 3：

输入：word1 = "cccddabba", word2 = "babababab"
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。
- 'b' 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。
- 'c' 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。
- 'd' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。

提示：

• n == word1.length == word2.length
• 1 <= n <= 100
• word1 和 word2 都只包含小写英文字母。

哈希、统计

class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int n = word1.length();
        int[] count = new int[26];
        while (--n >=0){
            count[word1.charAt(n)-'a']++;
            count[word2.charAt(n)-'a']--;
        }
        for (int i : count) {
            if (i>3 || i<-3){
                return false;
            }
        }
        return true;
    }
}

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

示例 1：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。 

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

提示：

• 1 <= rectangles.length <= 2 * 104
• rectangles[i].length == 4
• -105 <= xi, yi, ai, bi <= 105

依葫芦画瓢

class Solution {


    public boolean isRectangleCover(int[][] rectangles) {
        HashMap<String,Integer> hashMap = new HashMap<>();
        HashSet<String> hashSetSingle = new HashSet<>();
        int totalArea = 0;
        int[] bigRectangle = new int[]{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
        for (int[] rectangle : rectangles) {
            int[][]fourPoints = getFourPoints(rectangle);
            totalArea += getArea(rectangle);
            bigRectangle[0] = Math.min(bigRectangle[0],rectangle[0]);
            bigRectangle[1] = Math.min(bigRectangle[1],rectangle[1]);
            bigRectangle[2] = Math.max(bigRectangle[2],rectangle[2]);
            bigRectangle[3] = Math.max(bigRectangle[3],rectangle[3]);
            for (int[] point : fourPoints) {
                String key = hash(point[0],point[1]);
                if (hashMap.containsKey(key)){
                    hashSetSingle.remove(key);
                }else{
                    hashSetSingle.add(key);
                }
                hashMap.put(key,hashMap.getOrDefault(key,0)+1);
            }
        }
        if (hashSetSingle.size() != 4){
            return false;
        }
        if (totalArea != getArea(bigRectangle)){
            return false;
        }
        int[][] bigFourPoints = getFourPoints(bigRectangle);
        for (int[] bigFourPoint : bigFourPoints) {
            if (!hashSetSingle.contains(hash(bigFourPoint[0],bigFourPoint[1]))){
                return false;
            }
        }
        for (String s : hashMap.keySet()) {
            if ( !hashSetSingle.contains(s) && hashMap.get(s)!=2 && hashMap.get(s)!=4 ){
                return false;
            }
        }
        return true;
    }

    private int[][] getFourPoints(int[] rectangle){
        return new int[][]{
                {rectangle[0],rectangle[3]},
                {rectangle[2],rectangle[3]},
                {rectangle[2],rectangle[1]},
                {rectangle[0],rectangle[1]}
        };
    }

    //哈希
    private String hash(int x, int y) {
        return x + "_" + y;
    }

    //面积
    public int getArea(int[] rectangle){
        return ( rectangle[2] - rectangle[0] ) *  ( rectangle[3] - rectangle[1] );
    }


}

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

• 0 <= num < 231

带注解，动态规划

动态规划题，其实思路还是比较简单的，只是当中的if/else判断条件啰嗦了点，算不上复杂

把各种情况都理清楚的话，本题还是相当好解的

1. 当前数字独立成字母
2. 如果前面是0或者大于2，当前数字只能独立成字母
3. 如果前面数字是1，当前数字可以独立成字母，也可以和前面的1组成字母
4. 如果前面的数字是2，如果当前数字小于等于5，可以独立成字母，也可以和前面的1组成字母
5. 如果前面的数字是2，如果当前数字大于5，当前数字只能独立成字母

各种情况的数量

1. 当前数字独立成字母的时候。数量继承dp[i-1]
2. 和前一位数字组成字母的时候，数量为 “独立成字母的dp[i-1]” + “和前一位组成字母的时候继承的前前一位的dp[i-2]”
3. 如果dp[i-2]不存在，不妨简单假设个情况25，应当是 [2,5] + [25]两种情况，那么可知不存在的时候的dp[i-2]的值应当为1
4. 初始边界条件一个数字的时候只能为1，即dp[0] = 1

class Solution {
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public int translateNum(int num) {
        if (num<10){
            return 1;
        }
        int size = numSize(num);
        //构建 num数字拆分出来的数组，便于用下标处理
        int[] arr = new int[size];
        int idx = arr.length;
        while (num > 0){
            arr[--idx] = num % 10;
            num /= 10;
        }
        int[] dp = new int[size];
        dp[0] = 1;
        while (++idx < size){
            //如果前一位是0，或者前一位大于2，当前位置只能独立组成字母
            if (arr[idx-1] == 0 || arr[idx-1]>2){
                dp[idx] = dp[idx-1];
                continue;
            }
            //如果前一位为1，当前位置可以和前一位组成  1X  表示一个字母，那么当前位置可以组成的情况为
            // 当前位置单独成字母的情况  dp[idx-1]  加上  和前一位一起组成字母的情况  dp[idx-2]
            if (arr[idx-1] == 1){
                dp[idx] = dp[idx-1] + (idx>1?dp[idx-2]:1);
                continue;
            }
            //如果前一位为2，
            if (arr[idx-1] == 2){
                if (arr[idx] > 5){
                    //如果当前位置大于5，只能独立成字母
                    dp[idx] = dp[idx-1];
                }else{
                    //如果当前位置小于等于5，可以和前一位组成一个新字母
                    dp[idx] = dp[idx-1] + (idx>1?dp[idx-2]:1);
                }
            }
        }
        return dp[dp.length-1];
    }

    public int numSize(int num){
        int i = -1;
        while (++i < sizeTable.length){
            if (sizeTable[i] >= num){
                return i+1;
            }
        }
        return -1;
    }
}

本题和91. 解码方法是一样的，我还记得当初第一次做91的时候时候要命的提交了十多次，隔了两个月现在这题也能一次通过了。

都没啥问题的话可以再尝试下639 解码方法 II

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

愣了好久没看懂，反复思考下：堆排序

class Solution {
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public String minNumber(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int size1 = stringSize(o1);
                int size2 = stringSize(o2);

                int join1 = o1;
                while (size2>0){
                    join1 *= 10;
                    size2--;
                }
                join1 += o2;
                int join2 = o2;
                while (size1>0){
                    join2 *= 10;
                    size1--;
                }
                join2 += o1;
                return join1 - join2;
            }
        });
        for (int num : nums) {
            queue.offer(num);
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()){
            sb.append(queue.poll());
        }
        return sb.toString();
    }


    public int stringSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }
}