leetcode刷题

1、78. 子集

问题

解析

非正常解法：直接看输入、输出，能找出规律。每个数字都会和前面的数字进行合并，例如1:1和空集(不包含)，2:2和空集(不包含),2和1,3：3和空集(不包含)，3和1,3和2，3和2和1

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList());
        for(int i = 0; i < nums.length; i++) {
            int len = ans.size();
            for(int j = 0; j < len; j++) {
                List temp = new ArrayList(ans.get(j));
                temp.add(nums[i]);
                ans.add(temp);
            }
        }
        return ans;
    }
}

2、2396. 严格回文的数字

题目

解析

此题中的任何数的n-2进制数都是12(非十进制,n-2进制), 也可以暴力每个进制都去匹配一下

代码

class Solution {
    public boolean isStrictlyPalindromic(int n) {
        return false;
    }
}

3、1470. 重新排列数组

题目

解析

一个数组对半拼接

代码

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] ans = new int[nums.length];
        for(int i = 0, step = 0; i < n; i++, step += 2) {
            int cur = step;
            ans[cur++] = nums[i];
            ans[cur] = nums[n + i];
        }
        return ans;
    }
}

3、LCP 06. 拿硬币

题目

解析

偶数 = 硬币数 / 2, 奇数 = 硬币数 / 2 + 1

代码

class Solution {
    public int minCount(int[] coins) {
        int ans = 0;
        for(int i = 0; i < coins.length; i++) {
            if(coins[i] % 2 == 0) {
                ans += coins[i] / 2;
            } else {
                ans += coins[i] / 2 + 1;
            }
        }
        return ans;
    }
}

4、1769. 移动所有球到每个盒子所需的最小操作数

题目

解析

1、直接看示例，当前二进制数的前面到当前的距离(数字为1)和后面的所有距离的和(数字为1)。两层循环，外层遍历当前所有二进制数，内层遍历当前的前面的和后面的数字为1的距离。然后每个数字装到对应下标中。
2、左右两次遍历，从左往右，记录小球个数和到当前的前总共需要多少步。右往左同理。

代码

class Solution {
    public int[] minOperations(String boxes) {
        int len = boxes.length();
        int[] ans = new int[len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if (j != i && boxes.charAt(j) == '1') {
                    ans[i] += Math.abs(j - i);
                }
            }
        }
        return ans;
    }
}


class Solution {
    public int[] minOperations(String boxes) {
       int n = boxes.length();
       int[] ans = new int[n];
       // 前面的所有小球的移动数到当前
       int pre = 0;
       // 小球个数
       int count = 0;

        // 1011
       for (int i = 1; i < n; i++) {
           if (boxes.charAt(i - 1) == '1') count++;
           ans[i] = pre + count;
           pre += count;
       }

       count = 0;
       pre = 0;
       for (int i = n - 2; i >= 0; i--) {
           if (boxes.charAt(i + 1) == '1') count++;
           ans[i] += pre + count;
           pre += count;
       }
        

       return ans;
    }
}

5、2656. K 个元素的最大和

题目

解析

先求出最大值，然后叠加

代码

class Solution {
    public int maximizeSum(int[] nums, int k) {
        Arrays.sort(nums);
        int maxValue = nums[nums.length - 1];
        int ans = 0;
        for (int i = 0; i < k; i++) {
           ans += maxValue + i;
        }
        return ans;
    }
}

6、LCP 67. 装饰树

题目

解析

递归，先判定左子树在判定右子树。对于左边 root.left = new TreeNode(-1, expandBinaryTree(root.left), null); 右边同理

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode expandBinaryTree(TreeNode root) {
        if (root.left != null) {
            root.left = new TreeNode(-1, expandBinaryTree(root.left), null);
        }

        if (root.right != null) {
            root.right = new TreeNode(-1, null, expandBinaryTree(root.right));
        }
        return root;
    }
}

7、2894. 分类求和并作差

题目

解析

遍历，然后统计能整除的和不能整除，最后相减

代码

class Solution {
    public int differenceOfSums(int n, int m) {
        int success = 0;
        int fail = 0;

        for (int i = 1; i <= n; i++) {
            if (i % m == 0) {
                success += i;
            } else {
                fail += i;
            }
        }
        return fail - success;
    }
}

8、1689. 十-二进制数的最少数目

题目

解析

找出最大数字即可

代码

class Solution {
    public int minPartitions(String n) {
        int ans = 0;
        char[] arr = n.toCharArray();
        for (char c : arr) {
            if (c == '9') return 9;
            if (ans < c) ans = c;
        }
        return ans - '0';
    }
}

9、1476. 子矩形查询

题目

解析

矩阵遍历，获取

代码

class SubrectangleQueries {

    private int[][] rectangle;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
    }
    
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                rectangle[i][j] = newValue;
            }
        }
    }
    
    public int getValue(int row, int col) {
        return rectangle[row][col];
    }
}

10、1282. 用户分组

题目

解析

将groupSizes中的数字放在相同长度的分组中。例如示例2中的groupSizes中的2有两个，故放在一个长度为2的数组中(存放的是groupSizes这个数组对应数组的下标), 利用hashmap来统计相同数字，和长度，但是没有集合数组快

代码

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List[] arrayLists = new ArrayList[groupSizes.length + 1]; // 换成Map也行
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < groupSizes.length; i++) {
            int key = groupSizes[i];
            if (arrayLists[key] != null) {
                List arrayList = arrayLists[key];
                if (arrayList.size() + 1 >= key) {
                    arrayList.add(i);
                    ans.add(arrayList);
                    arrayLists[key] = null;
                } else {
                    arrayList.add(i);
                }
            } else {
                ArrayList<Integer> tem = new ArrayList<>();
                tem.add(i);
                if (key == 1) {
                    ans.add(tem);
                } else {
                    arrayLists[key] = tem;
                }
            }
        }
        return ans;
    }
}

11、237. 删除链表中的节点

题目

解析

没有head，将当前node的下一个值前移，并且node.next = node.next.next

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

12、2011. 执行操作后的变量值

题目

解析

判定自增自减

代码

class Solution {
    public int finalValueAfterOperations(String[] operations) {
        int ans = 0;
        for (int i = 0; i < operations.length; i++) {
            String op = operations[i];
            if (op.indexOf('+') != -1) {
                ans++;
            }else {
                ans--;
            }
        }
        return ans;
    }
}

13、1773. 统计匹配检索规则的物品数量

题目

解析

遍历比较匹配

代码

class Solution {
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int ans = 0;
        char ch = ruleKey.charAt(0);
        int index = ch == 't' ? 0 : ch == 'c' ? 1 : 2;
        for (List<String> item : items) {
            if (item.get(index).equals(ruleValue)) ans++;
        }
        return ans;
    }
}

14、