著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
提示：
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
双指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curN = head;
while (--n >= 0 && curN != null){
curN = curN.next;
}
if (curN==null){
return head.next;
}
ListNode cur = head;
curN = curN.next;
while (curN != null){
cur = cur.next;
curN = curN.next;
}
cur.next = cur.next.next;
return head;
}
}给你一个字符串 s ，字符串的「能量」定义为：只包含一种字符的最长非空子字符串的长度。
请你返回字符串 s 的 能量。
示例 1：
输入：s = "leetcode" 输出：2 解释：子字符串 "ee" 长度为 2 ，只包含字符 'e' 。
示例 2：
输入：s = "abbcccddddeeeeedcba" 输出：5 解释：子字符串 "eeeee" 长度为 5 ，只包含字符 'e' 。
提示：
1 <= s.length <= 500s 只包含小写英文字母。双指针，简单步骤分析理解
双指针，简单题
max长度值，取较大的那个class Solution {
public int maxPower(String s) {
if (s.length() == 0) return 0;
int max = 1;
int left = 0;
int right = 0;
while (left < s.length()){
while (++right < s.length() && s.charAt(right) == s.charAt(right-1)){}
max = Math.max(max,right - left);
left = right;
}
return max;
}
}给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i]（从 i=0 到 i=queries.length-1）：
P=[1,2,3,...,m]。i ，请你找出待查项 queries[i] 在排列 P 中的位置（下标从 0 开始），然后将其从原位置移动到排列 P 的起始位置（即下标为 0 处）。注意， queries[i] 在 P 中的位置就是 queries[i] 的查询结果。请你以数组形式返回待查数组 queries 的查询结果。
示例 1：
输入：queries = [3,1,2,1], m = 5 输出：[2,1,2,1] 解释：待查数组 queries 处理如下： 对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，接着我们把 3 移动到 P 的起始位置，得到 P=[3,1,2,4,5] 。 对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,3,2,4,5] 。 对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，接着我们把 2 移动到 P 的起始位置，得到 P=[2,1,3,4,5] 。 对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,2,3,4,5] 。 因此，返回的结果数组为 [2,1,2,1] 。
示例 2：
输入：queries = [4,1,2,2], m = 4 输出：[3,1,2,0]
示例 3：
输入：queries = [7,5,5,8,3], m = 8 输出：[6,5,0,7,5]
提示：
1 <= m <= 10^31 <= queries.length <= m1 <= queries[i] <= m树状数组实现
思路同官方题解
queries.length + m，把原先的m序列在树状数组中后面部分构件起来key进行减1，并在前面移动到的新位置加1class Solution {
public int[] processQueries(int[] queries, int m) {
int l = queries.length + m;
FenwickTree fenwickTree = new FenwickTree(l);
int[] numPos = new int[m+1];
for (int i = queries.length + 1; i <= l; i++) {
fenwickTree.add(i,1);
numPos[i - queries.length] = i;
}
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int num = queries[i];
res[i] = fenwickTree.query(numPos[num]) - 1;
fenwickTree.add(numPos[num],-1);
numPos[num] = queries.length - i;
fenwickTree.add(numPos[num],1);
}
return res;
}
class FenwickTree{
int[] arr;
public FenwickTree(int n){
arr = new int[n+1];
}
public int lowBit(int i){
return i & (-i);
}
public void add(int idx , int num){
while (idx < arr.length){
arr[idx] += num;
idx += lowBit(idx);
}
}
public int query(int idx){
int sum = 0;
while (idx > 0){
sum += arr[idx];
idx -= lowBit(idx);
}
return sum;
}
}
}有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。
对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
示例 1：
输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 输出：[2,7,14,8] 解释： 数组中元素的二进制表示形式是： 1 = 0001 3 = 0011 4 = 0100 8 = 1000 查询的 XOR 值为： [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8
示例 2：
输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] 输出：[8,0,4,4]
提示：
1 <= arr.length <= 3 * 10^41 <= arr[i] <= 10^91 <= queries.length <= 3 * 10^4queries[i].length == 20 <= queries[i][0] <= queries[i][1] < arr.length树状数组
基本是模板套用，不过思路要转变下
原本的前缀和套用为异或操作，本质没有改变
class Solution {
public int[] xorQueries(int[] arr, int[][] queries) {
FenwickTree fenwickTree = new FenwickTree(arr.length);
for (int i = 0; i < arr.length; i++) {
fenwickTree.add(i+1, arr[i]);
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
ans[i] = fenwickTree.query(queries[i][0]) ^ fenwickTree.query(queries[i][1]+1);
}
return ans;
}
class FenwickTree{
int[] arr;
public FenwickTree(int n){
arr = new int[n+1];
}
public int lowBit(int i){
return i & ( -i );
}
public void add(int idx, int num){
while (idx < arr.length){
arr[idx] ^= num;
idx += lowBit(idx);
}
}
public int query(int idx){
int res = 0;
while (idx > 0 ){
res ^= arr[idx];
idx -= lowBit(idx);
}
return res;
}
}
}假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：
实现 track(int x) 方法，每读入一个数字都会调用该方法；
实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。
注意：本题相对原题稍作改动
示例:
输入: ["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"] [[], [1], [0], [0]] 输出: [null,0,null,1]
提示：
x <= 50000track 和 getRankOfNumber 方法的调用次数均不超过 2000 次树状数组结构直接套模板使用
在该题中，树状数组对应下标表意为当前下标数字的出现次数
track(int x) 方法，每读入一个数字都会调用该方法, 等价于在给树状数组对应下标数值加1，即当前下标出现次数加1getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数，等价于求下标0到当前下标的前缀和，即从0到当前下标的所有数字出现次数之和class StreamRank {
private FenwickTree fenwickTree;
public StreamRank() {
fenwickTree = new FenwickTree(50001);
}
public void track(int x) {
fenwickTree.add(x+1,1);
}
public int getRankOfNumber(int x) {
return fenwickTree.query(x+1);
}
class FenwickTree{
int[] arr;
public FenwickTree(int num){
arr = new int[num+1];
}
int lowBit(int x){
return x & ( -x );
}
public void add(int idx, int num){
while (idx < arr.length){
arr[idx] += num;
idx += lowBit(idx);
}
}
public int query(int idx){
int sum = 0;
while (idx > 0){
sum += arr[idx];
idx -= lowBit(idx);
}
return sum;
}
}
}给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1：
输入：n = 3 输出：3
示例 2：
输入：n = 11 输出：0 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
提示：
1 <= n <= 231 - 1同剑指Offer 44 题 数字序列中某一位的数字
按图分析
按照这个规律分析，我们只需从头开始，依次从头开始
10个字符90 * 2 个字符900 * 3个字符9000 * 4个字符1 x 10^pow开始，1 x 10^pow，就能得到当前是在哪个数字问题
cur + 9 * powOf10 * ( pow+1 ) 会超过int型上限，所以最简单的处理办法中间的运算过程用了long型数据
class Solution {
public int findNthDigit(int n) {
if (n < 10){
return n;
}
long cur = 10;
long powOf10 = 10;
long pow = 1;
while (cur + 9 * powOf10 * ( pow+1 )< n){
cur += 9 * powOf10 * (pow+1);
powOf10 *= 10;
pow++;
}
long order = powOf10 + (n-cur) / (pow+1);
long idx = (n - cur) % (pow+1);
String orderStr = Long.toString(order);
return orderStr.charAt((int)idx)-'0';
}
}给你一个数组 nums ，请你完成两类查询。
nums 下标对应的值nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）
示例 1：
输入： ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] 输出： [null, 9, null, 8] 解释： NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1,2,5] numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
提示：
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.lengthupdate 和 sumRange 方法次数不大于 3 * 104 树状数组套模板
class NumArray {
private FenwickTree fenwickTree;
public NumArray(int[] nums) {
fenwickTree = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; i++) {
fenwickTree.add(i+1,nums[i]);
}
}
public void update(int index, int val) {
fenwickTree.add(index+1,val - fenwickTree.queryIndex(index+1));
}
public int sumRange(int left, int right) {
return fenwickTree.rangeSum(left,right+1);
}
class FenwickTree{
int[] arr;
public FenwickTree(int n){
arr = new int[n+1];
}
public int lowBit(int x){
return x & (- x);
}
public void add(int idx, int num){
while (idx < arr.length){
arr[idx] += num;
idx += lowBit(idx);
}
}
public int querySum(int idx){
int res = 0;
while (idx > 0){
res += arr[idx];
idx -= lowBit(idx);
}
return res;
}
public int queryIndex(int idx){
return querySum(idx) - querySum(idx-1);
}
public int rangeSum(int left, int right){
if (left > right){
int tmp = right;
right = left;
left = tmp;
}
return querySum(right) - querySum(left);
}
}
}