【每日算法Day 45】七月上旬回顾总结

技术

七月上旬，入门了MyBatis，熟悉了MyBatis的配置及使用方法、mapper的编写（parameterType ResultType、ResultMap），MyBatis到POJO/VO的关联映射，使用SqlSession或接口代理发送SQL语句。

另外，开始学习Spring框架，初步认识了Spring的体系结构、Spring Bean的配置、Bean与Spring IOC容器的关系、Bean的作用域与生命周期、Bean的属性依赖注入以及Bean的自动装配。

算法

• 回溯算法：我们在解决回溯问题时，只需要考虑三点：递归的结束条件、当前路径（已经做过的选择）、下一步的选择列表。对于选择列表内的每一种选择，我们做出选择并在递归结束后撤销选择。
• 动态规划：关键在于能抽象出元素的状态并找到问题的状态转移方程。在一些字符串转换相关的问题中，往往会用到二维的DP数组来表示问题的某些状态，例如str.substring(i,j)是否为回文串，str1.substring(0,i)和str2.substring(0,j)经过几次编辑能够相同，str1.substring(0,i)和str2.substring(0,j)能否交错拼成str3等等，值得注意。
• 链表：很多链表操作的问题具有迭代和递归两种解法，在处理时要小心空节点，要善用dummy节点。
• 二分查找：二分查找最关键的就是确定搜索区间，一旦搜索区间确定了最终的停止条件和返回值也就确定了。另外一些二分查找不一定是值比较，而是观察mid元素是否满足有关特性来判断该选择哪一半搜索区间而舍弃另一半。
• 矩阵：单独考察矩阵变换操作的情况不多，有少量的转置、翻转。更多时候矩阵，会结合二分查找、DFS/BFS的搜索空间来出现。
• DFS/BFS：不知道为什么，对于需要搜索全部空间的问题，DFS往往比BFS快很多（不知道是不是JCF队列的性能问题）。对于最短路径或者状态间最短距离的问题，往往可以想到尝试用BFS去搜索。

---

另外，今晚做了两题ByteDance的笔试题，考查的似乎都是数据结构。

不包含减号的括号对的数量

输入一个合法的数学表达式，其中只包含左右括号、整数和加减运算符，输出该表达式中不包含减号在内的括号对数。

示例：输入((1+2)+(3-4))，输出1

思路：使用一个栈保存每个左括号的索引，每遇到一个右括号就取出栈顶作为索引对，搜索字符串对应位置的字串是否包含减号，没有则符合条件的括号对数加一。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String exp=scanner.nextLine();
            Deque<Integer> stack =new ArrayDeque<>();
            int count = 0;
            for (int i = 0; i < exp.length(); i++) {
                if (exp.charAt(i)=='('){
                    stack.push(i);
                } else if (exp.charAt(i) == ')') {
                    int left = stack.pop();
                    if (!containMinus(left, i, exp)) {
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    private static boolean containMinus(int left, int right, String exp) {
        for (int index = left + 1; index < right; index++) {
            if (exp.charAt(index) == '-') {
                return true;
            }
        }
        return false;
    }
}

访问量最大的网站

输入多行记录，每行记录包含"用户ID 域名 访问时长"，每个用户只会有1条记录，找出访问总时长超过180分钟的网站中，访问用户数量最多的。

思路：使用一个HashMap，以域名为key，统计每个唯一域名的总访问时长和访问人次。接下来对于每条符合条件的键值对，放入大顶堆中（也可以先存到动态数组中再排序），最后堆为空则输出"null"，不为空则输出堆顶元素的key也就是网站域名。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        Map<String, TimeAndCount> map = new HashMap<>();
        while (scanner.hasNextLine()) {
            String record = scanner.nextLine();
            String[] details = record.split(" ");
            if (details.length != 3) break;
            TimeAndCount entry = map.getOrDefault(details[1],new TimeAndCount(0,0));
            entry.accessCount += 1;
            entry.totalTime += Integer.parseInt(details[2]);
            map.put(details[1],entry);
        }
        
        PriorityQueue<Map.Entry<String, TimeAndCount>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, TimeAndCount>>() {
            @Override
            public int compare(Map.Entry<String, TimeAndCount> o1, Map.Entry<String, TimeAndCount> o2) {
                return o2.getValue().accessCount - o1.getValue().accessCount;
            }
        });

        for (Map.Entry<String, TimeAndCount> ent : map.entrySet()) {
            if (ent.getValue().totalTime > 180) {
                heap.offer(ent);
            }
        }
        if (heap.size() == 0) {
            System.out.println("null");
        } else {
            System.out.println(heap.poll().getKey());
        }
    }

    private static class TimeAndCount {
        int totalTime;
        int accessCount;

        public TimeAndCount(int totalTime, int accessCount) {
            this.totalTime = totalTime;
            this.accessCount = accessCount;
        }
    }
}