Java

lowBitlowBit一般用在树状数组里，主要功能是: 找到x的二进制数的最后一个1所表示的二进制 比如x=6=00000110 (2)，-x=x(补)=11111010(2)，lowBit(x)=10(2)=2 也就是说,就是lowbit(x)的值必然是2的幂次(最高位为1,其他位为0) x 1 2 3 4 5 6 7 8 9 lowbit(x) 1 2 1 4 1 2 1 8 1 注意: x不能等于0, 否则会进入死循环, 所以树状数组通常使用的下标会执行+1操作 lowbit只有一行操作，而且是位运算，效率很高 private int lowBit(int x){ return x & (-x);} 具体的应用后面在树状数组里讲 质数优化之前在LeetCode里看到这么一个题 给两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。 1 <= left <= right &l ...

题目给出一个字符串 s（仅含有小写英文字母和括号）。 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。 注意，结果中不应包含任何括号。 方法一：栈思路    对于括号序列相关的题，通用的解法是用递归或者栈。     从左至右地遍历整个字符串，用字符串 str 来记录当前层所遍历到的小写英文字母。对于当前遍历的字母： 如果是左括号：把 str 插入到栈中，并且把 str 置空，进入到下一层 如果是右括号：遍历到了右括号，说明当前层的字母已经遍历完了，把 str 反转，并把栈顶的字符串弹出，将反转后的 str 插入到弹出字符串的末尾，将结果赋值给 str 如果是小写英文字母：追加到 str 末尾     可以看到，只有在遍历到了右括号（第一个出现的右括号是最里面的）才会对字符串进行操作，这样可以保证能从括号里到外处理字符串 代码实现import java.util.*;public class test{ publi ...

    针对王道考研第三章（栈与队列）的拓展思考题–最小栈的实现。本文会探讨三种方法来实现，分别是辅助类、单个栈和双栈。 题目    请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。 注：这里要求的是常量级的时间里找到最小值，所以先排序、再查找是不行的，我们必须在需要的时候就要得到最小值 方法一：辅助类（链表类）思路    我们知道，栈其实是一种操作受限的线性表，所以栈的一些操作可以通过链表来实现。这里要我们设计一个栈，而栈的实现我们可以使用链表，先定义一个链表类。 class ListNode{ public int val; public int min; //最小值 public ListNode next; public ListNode(int val, int min, ListNode next){ ...

什么是HashMap?    简单点来说，HashMap 是一个散列表，它的存储内容是键值对（key—value）映射     我们需要用算术操作将键（key）转化为数组的索引来访问数组中的键值对，这个算术操作其实就是找到一个合适的散列函数来将查找的键转化为数组的一个索引。理想情况下，不同的键能转化为不同的索引值，不过，如果出现两个或多个键都会散列到相同的索引值，就会发生散列冲突（也叫哈希冲突），具体解决方法会另外介绍。     HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，访问速度很快。其实哈希表的主干就是数组，因为在不考虑哈希冲突的情况下，仅仅只需要一次定位就能找到，这和数组的特点很像。     HashMap 的 key 和 value 的类型可以相同也可以不同，可以都是字符串(String)型的，也可以 key 是整型(Integer)、value 是字符串型的。HashMap 中的元素实 ...

题目给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 示例：{()}，()[]，都是有效匹配，{()]为无效匹配 方法：栈思路由题目可以知道，要有效匹配，就得左括号和右括号匹配，后出现的左括号总是和先出现的右括号匹配，遵循后进先出的特点，而这一特点就和栈的特点类似 代码实现import java.util.*;public class test{ public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isVaild("{[]}")); }}class Solution{ //算法主体 public boolean isVaild(String s)&# ...