greedy/string/sort 20210703 23:12

xiaoshuai96 · Jul 3, 2021 · ae75c48 · ae75c48
1 parent 6174c03
commit ae75c48
Show file tree

Hide file tree

Showing 3 changed files with 243 additions and 0 deletions.
diff --git a/src/leetCode/greedy/maxIceCream_1833.java b/src/leetCode/greedy/maxIceCream_1833.java
@@ -0,0 +1,59 @@
+package leetCode.greedy;
+
+import sun.management.CompilerThreadStat;
+
+import java.util.Arrays;
+
+/**
+ * 夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
+ * 商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
+ * 给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
+ * 注意：Tony 可以按任意顺序购买雪糕。
+ *
+ *
+ * 示例 1：
+ * 输入：costs = [1,3,2,4,1], coins = 7
+ * 输出：4
+ * 解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7
+ *
+ * 示例 2：
+ * 输入：costs = [10,6,8,7,7,8], coins = 5
+ * 输出：0
+ * 解释：Tony 没有足够的钱买任何一支雪糕。
+ *
+ * 示例 3：
+ * 输入：costs = [1,6,3,1,2,5], coins = 20
+ * 输出：6
+ * 解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。
+ *
+ * 提示：
+ *     costs.length == n
+ *     1 <= n <= 10^5
+ *     1 <= costs[i] <= 10^5
+ *     1 <= coins <= 10^8
+ */
+public class maxIceCream_1833 {
+    public static void main(String[] args) {
+        int[] costs = {1,6,3,1,2,5};
+        int coins = 20;
+        new maxIceCream_1833().maxIceCream(costs,coins);
+    }
+
+    /**
+     * 如果要拿有限的金额买到足够多的雪糕，那么一定是先挑便宜的买，之后再买贵的
+     * 算法：贪心算法
+     * @param costs
+     * @param coins
+     * @return
+     */
+    public int maxIceCream(int[] costs, int coins) {
+        Arrays.sort(costs);
+        int index = 0;
+        int res  = 0;
+        while (coins > 0 && index < costs.length) {
+            coins -= costs[index++];
+            res++;
+        }
+        return coins < 0 ? res - 1 : res;
+    }
+}
diff --git a/src/leetCode/string/convertToTitle_168.java b/src/leetCode/string/convertToTitle_168.java
@@ -0,0 +1,53 @@
+package leetCode.string;
+/**
+ * 给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称
+ * 例如：
+ *
+ * A -> 1
+ * B -> 2
+ * C -> 3
+ * ...
+ * Z -> 26
+ * AA -> 27
+ * AB -> 28
+ * ...
+ *
+ * 示例 1：
+ * 输入：columnNumber = 1
+ * 输出："A"
+ *
+ * 示例 2：
+ * 输入：columnNumber = 28
+ * 输出："AB"
+ *
+ * 示例 3：
+ * 输入：columnNumber = 701
+ * 输出："ZY"
+ *
+ * 示例 4：
+ * 输入：columnNumber = 2147483647
+ * 输出："FXSHRXW"
+ *
+ * 提示：
+ *     1 <= columnNumber <= 2^31 - 1
+ */
+public class convertToTitle_168 {
+    public static void main(String[] args) {
+        //FXSHRXW
+        String s = new convertToTitle_168().convertToTitle(2147483647);
+        System.out.println(s);
+    }
+    public String convertToTitle(int n) {
+        if(n <= 0){
+            return "";
+        }
+        StringBuilder res = new StringBuilder();
+        while(n > 0){
+            n--;
+            res.append((char)(n % 26 + 'A'));
+            n /= 26;
+        }
+        return res.reverse().toString();
+
+    }
+}
diff --git a/src/leetCode/string/frequencySort_451.java b/src/leetCode/string/frequencySort_451.java
@@ -0,0 +1,131 @@
+package leetCode.string;
+
+import java.util.*;
+
+/**
+ * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
+ * 示例 1:
+ * 输入:
+ * "tree"
+ *
+ * 输出:
+ * "eert"
+ *
+ * 解释:
+ * 'e'出现两次，'r'和't'都只出现一次。
+ * 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
+ *
+ * 示例 2:
+ * 输入:
+ * "cccaaa"
+ *
+ * 输出:
+ * "cccaaa"
+ *
+ * 解释:
+ * 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
+ * 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
+ *
+ * 示例 3:
+ * 输入:
+ * "Aabb"
+ *
+ * 输出:
+ * "bbAa"
+ *
+ * 解释:
+ * 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
+ * 注意'A'和'a'被认为是两种不同的字符。
+ */
+public class frequencySort_451 {
+    public static void main(String[] args) {
+        String s = "cccaa";
+        new frequencySort_451().frequencySort(s);
+    }
+
+
+    /**
+     * 官方题解
+     * @param s
+     * @return
+     */
+    public String frequencySort02(String s) {
+        Map<Character, Integer> map = new HashMap<Character, Integer>();
+        int length = s.length();
+        for (int i = 0; i < length; i++) {
+            char c = s.charAt(i);
+            int frequency = map.getOrDefault(c, 0) + 1;
+            map.put(c, frequency);
+        }
+        List<Character> list = new ArrayList<Character>(map.keySet());
+        Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
+        StringBuffer sb = new StringBuffer();
+        int size = list.size();
+        for (int i = 0; i < size; i++) {
+            char c = list.get(i);
+            int frequency = map.get(c);
+            for (int j = 0; j < frequency; j++) {
+                sb.append(c);
+            }
+        }
+        return sb.toString();
+    }
+
+
+    public String frequencySort(String s) {
+        Node[] nodes = new Node[128];
+        for(char c : s.toCharArray()){
+            if (nodes[c] != null) {
+                nodes[c].c = c;
+                nodes[c].count++;
+            } else {
+                nodes[c] = new Node(c, 1);
+            }
+        }
+        List<Node> list = new ArrayList<>();
+        for (Node node : nodes){
+            if (node != null) {
+                list.add(node);
+            }
+        }
+        Collections.sort(list);
+        StringBuilder sb = new StringBuilder();
+        StringBuilder res = new StringBuilder();
+        for (Node node : list) {
+            String aChar = generateStringByChar(node.c, node.count, sb);
+            res.append(aChar);
+        }
+        return res.toString();
+    }
+    //自定义类，c代表该字符，count表示该字符在字符串中出现的次数
+    private class Node implements Comparable<Node>{
+        char c;
+        int count;
+
+        public Node(char c, int count) {
+            this.c = c;
+            this.count = count;
+        }
+
+        public void setC(char c) {
+            this.c = c;
+        }
+
+        public void setCount(int count) {
+            this.count = count;
+        }
+
+        @Override
+        public int compareTo(Node o) {
+            return o.count - count;
+        }
+    }
+    private String generateStringByChar(char c ,int n,StringBuilder sb){
+        sb.delete(0, sb.length());
+        if (n <= 0) return "";
+        for (int i = 0; i < n; i++) {
+            sb.append(c);
+        }
+        return sb.toString();
+    }
+}