算法

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){ ...

题目给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 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)&# ...

算法练中将包含相关算法和一些与考研题目结合的C语言的算法题进行延伸思考，在用Java简单实现的同时，对内容深化并尝试C语言的叙述来更加巩固当前知识点。 题目1存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。 方法：一次遍历思路这个题的思路比较简单，因为是按升序排列的，所以重复的元素基本都是相邻着的，因此只需要比较相邻两个节点的值，就能判断出是否是重复的。 代码实现//删除链表中的重复元素public class test { public static void main(String[] args) { Node head = new Node(0); Node node1 = new Node(1); Node node2 = new Node(1); Node node3 = new Node(3); Node node4 = new Node(3); Node node5 = ...