Arrays类

(1) Arrays.toString(); //返回数组的字符串形式

(2) Arrays.sort(); //排序(自然排序和定制排序)

static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;
        Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
        public int compareTo(Edge e) {
            return w - e.w;
        }
    }

public class 数位排序 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        Integer[] array = new Integer[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        Arrays.sort(array, (o1, o2) -> digitSum(o1) != digitSum(o2) ? digitSum(o1) - digitSum(o2) : o1 - o2);
        System.out.println(array[m - 1]);
        scan.close();
    }
    private static int digitSum(Integer num) {
        int ans = 0;
        while (num > 0) {
            ans += num % 10;
            num /= 10;
        }
        return ans;
    }
}

(3）Arrays.binarySearch(int[] a,int key); //参数：a - 要搜索的数组,key - 要搜索的值

//使用二进制搜索算法在指定的整数数组中搜索指定的值。

//注意！：在进行此调用之前，必须对数组进行排序（如通过sort(int[])方法）。

//如果数组中不存在该元素，就返回一个负数： return -(low + 1);

（low即是该元素应该出现的索引位置）

(4）Arrays.copyOf(int[] original, int newLength );

//从 original 数组中拷贝 newLength 个元素到新的数组中

//参数：original – 要复制的数组

newLength – 要返回的副本的长度

(5）Arrays.fill(int[] a, int val); //数组元素的填充

//将指定的 int 值分配给指定的 int 数组的每个元素。

//参数：a - 要填充的数组 val – 要存储在数组所有元素中的值

(6）Arrays.equals(); //如果两个指定的 int 数组彼此相等，则返回true 。

(7）Arrays.asList( ); //会将输入的数据转成一个List集合

例如：List list = Arrays.asList(3,6,888,99);

基础数论

欧几里得（辗转相除法）求最大公约数：

  static int gcd(int a, int b) { //最大公约数
                if(b==0) return a;
                else return gcd(b,a%b);
        }

最小公倍数 = 两数相乘 ÷ 两数的最大公约数.

static int lcm(int a , int b) { 
        return a * b / gcd(a,b);
   }

判断奇偶数：

将这个数与1做&运算。原因：二进制中奇数最后一位为1，偶数最后一位为0.

判断闰年：

①、普通年能被4整除且不能被100整除的为闰年. ②、世纪年能被400整除的是闰年

用2得到8最快的方法：

2<<2。原因：二进制中左移n位相当于乘以2的n次方.

分解质因数：

例1：

public class demo_数论_分解质因数 {
    /**
     * 根据算术基本定理又称唯─分解定理，对于任何一个合数，我们都可以用几个质数的幂的乘积来表示。
     * 如:
     * 12 = 2^2 * 3
     * 20 = 2^2 * 5
     * 30 = 2 * 3 * 5
     * 接下来我们利用这个公式分解质因数。
     * 设一个质数为p,如果 n % p == 0，那么p就是n的一个质因数，
     * 接下来就是求p的指数，我们让n = n / p , 这样就从n中剔除了一个p,
     * 接着重复上述两步，直到 n % p != 0
     */
    public static void prime(int n) {
        for (int i = 2; i <= n / i; i++) {//即i*i<=n
            int a = 0, b = 0;
            while (n % i == 0) {
                a = i;
                n /= i;
                b++;
            }
            if (b > 0)
                System.out.println("质因数之一： " + a + " 的 " + b + " 次方");
        }
        if (n > 1) System.out.println("有一个大于根号n 的质因数:" + n);
    }
    /**
     * 注意：以上代码中for循环的结束条件也是i <= n / i，因为根据公式，最多只可能有一个质因数是大于 根号n,
     * 因为有两个的话，乘积肯定超过n了。所以当for循环结束后判断n是否大于1，如果大于就说明有一个大于 根号n 的质因数。
     */
    public static void main(String[] args) {
        prime(30);
    }
}

例2：

import java.util.*;
/**
 * 1. 编程将一个正整数n分解质因数。
 * 输入输出示例1：
 * 请输入一个数:90
 * 90=2*3*3*5
 * 输入输出示例2：
 * 请输入一个数:50
 * 50=2*5*5
 */
public class demo01 {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int org = num;
        for (int i = 2; i < num; i++) {
            int a = 0, b = 0;
            while (num % i == 0) {
                a = i;
                num /= i;
                b++;
            }
            if (b != 0)
                while (b-- > 0) {
                    queue.add(a);
                }
        }
        if (num > 1)
            queue.add(num);
        System.out.print(org+"=");
        while (!queue.isEmpty()){
            System.out.print(queue.poll());
            if (!queue.isEmpty())
                System.out.print("*");
        }
    }
}

" 快速幂" && “素数筛法” 见后文的 --> Algorithm

格式控制

String.format("%02d", year)
   year格式化为至少2位十进制整数                 --> int year = 5;结果为05

 double ans=0.11111111;
        作格式转换 String.format("%.nf", ans)        
        作输出 System.out.printf("%.nf",ans);     --> n为小数点后保留的位数。
        System.out.printf("%.2f",4);   输出---> 4.00

=======================================================

输入字符数组

c[i] = scan.nextLine().toCharArray();

=======================================================

测试类

import java.io.*;
import java.util.*;
public class Main{
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        //测试writr 不能直接输出int类型
            int a = 65;
        out.write(a);
        out.write("\n");
            out.write(a + "\n");  // 使用 + 号拼接个字符串 使参数整体为一个字符串 
        out.write(Integer.toString(a)); // 输出a的字符串形式
        out.write("\n");
        //测试 read() 和  readLine();
        int b = in.read();   // read()只读取一个字符
        int c = in.read();   // 吸收 \n
        int x = in.read();   // 吸收 \r
       // String e = in.readLine();
        String d = in.readLine();
        out.write("\n");
        out.write(b + "\n");
        out.write(c + "\n");
        out.write(x + "\n");
        out.write(d + "\n");
        //out.write(e);
        out.flush();
    }
}

一共输入了：

1 （按回车键）

ABC DEF

然后下面输出了

49（1的ASCii码）

13（回车键的ACSii码）

10 (换行键的ASCII码)

ABC DEF

无穷大的坑!

System.out.println(Integer.MIN_VALUE - 1);//2147483647
   System.out.println(Integer.MAX_VALUE);//2147483647
   System.out.println(Integer.MIN_VALUE);//-2147483648
    最好是都右移一位避免过于极端
System.out.println(Integer.MAX_VALUE >> 1);//1073741823
System.out.println(Integer.MIN_VALUE >> 1);//-1073741824

坐标存储小技巧

 保存经过的每一个点位置信息，采用(x)*m+y的公式表示(x,y);m:大于最长边的随便一个数
      private static Queue<Integer> location = new LinkedList<>();
        int x, y;//当前位置坐标
        location.add(x * m + y);
        int l = location.poll();//获取当前位置的坐标
        x = l / 50;//获取当前位置x
        y = l % 50;//获取当前位置y

合排序

 ArrayList<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(0);
        list.add(5);
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);//0 2 5 前后 --> 从小到大
            }
        });
        把上面的代码可以使用lambda表达式进一步简化
            升序：
            list.sort((a,b)->{
                                   return Integer.compare(a,b);
                        });
            list.sort(Integer::compare);
                        直接调用list.sort(Comparator.naturalOrder());
            降序：
            list.sort((a,b) ->{
                            return Integer.compare(b,a);
                        });
                        直接调用list.sort(Comparator.reverseOrder());

Collection工具类的使用

排序操作

reverse(List)：反转 List 中元素的顺序

shuffle(List)：对 List 集合元素进行随机排序

sort(List)：根据元素的自然顺序对指定 List 集合元素升序排序

sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序

swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

@Test
public void test1() {
    List list = new ArrayList();
    list.add(123);
    list.add(43);
    list.add(765);
    list.add(-97);
    list.add(0);
    System.out.println(list);//[123, 43, 765, -97, 0]
    //reverse(List)：反转 List 中元素的顺序
    Collections.reverse(list);
    System.out.println(list);//[0, -97, 765, 43, 123]
    //shuffle(List)：对 List 集合元素进行随机排序
    Collections.shuffle(list);
    System.out.println(list);//[765, -97, 123, 0, 43]
    //sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
    Collections.sort(list);
    System.out.println(list);//[-97, 0, 43, 123, 765]
    //swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
    Collections.swap(list,1,4);
    System.out.println(list);//[-97, 765, 43, 123, 0]
}

查找、替换

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素

Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素

Object min(Collection)

Object min(Collection，Comparator)

int frequency(Collection，Object)：返回指定集合中指定元素的出现次数

void copy(List dest,List src)：将src中的内容复制到dest中

boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所旧值

 @Test
public void test2(){
    List list = new ArrayList();
    list.add(123);
    list.add(123);
    list.add(123);
    list.add(43);
    list.add(765);
    list.add(-97);
    list.add(0);
    System.out.println(list);//[123, 43, 765, -97, 0]
    //Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
    Comparable max = Collections.max(list);
    System.out.println(max);//765
    //Object min(Collection)
    Comparable min = Collections.min(list);
    System.out.println(min);//-97
    //int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
    int frequency = Collections.frequency(list,123);
    System.out.println(frequency);//3
    //void copy(List dest,List src)：将src中的内容复制到dest中
    List dest = Arrays.asList(new Object[list.size()]);
    System.out.println(dest.size());//7
    Collections.copy(dest,list);
    System.out.println(dest);//[123, 123, 123, 43, 765, -97, 0]
    //boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值
}

Pattern类的使用（匹配正则表达式）

//根据匹配不同的内容返回不同的数值；
//注意：这里的匹配指的是 " 仅含有 "，
//所以，如果要判断一个字符串中是否包含多种字符，可以采用顺序拼接，也可以采用逐个判断
//拼接是这样写：Pattern.matches("^[a-z]+[\\d]+$", str),如果是a4一类的，则为true，很局限...
//所以，这道题采用逐个判断
public class demo04 {
    private static int teShu(String str) {
        if (Pattern.matches("^[@#!%*$~]+$", str))
            return 1;
        if (Pattern.matches("[\\d]+", str))
            return 2;
        if (Pattern.matches("^[a-z]+$", str))
            return 3;
        if (Pattern.matches("^[A-Z]+$", str))
            return 4;
        return 0;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        if (str.length() < 8) {
            System.out.println("NG");
            return;
        }
        String[] split = str.split("");
        int[] kinds = new int[5];
        for (String s : split) {
            if (kinds[1] == 1 && kinds[2] == 1 && kinds[3] == 1 && kinds[4] == 1)
                break;
            if (teShu(s) == 1) {
                kinds[1] = 1;
            } else if (teShu(s) == 2) {
                kinds[2] = 1;
            } else if (teShu(s) == 3) {
                kinds[3] = 1;
            } else if (teShu(s) == 4) {
                kinds[4] = 1;
            }
        }
        int count = kinds[1] + kinds[2] + kinds[3] + kinds[4];
        if (count <= 1) {
            System.out.println("NG");
        } else if (count == 2) {
            System.out.println("MG");
        } else if (count == 3) {
            System.out.println("VG");
        } else if (count == 4) {
            System.out.println("EG");
        }
    }
}

进制转换（x进制转10进制，10进制转y进制）

    // 如果题目要进行转化的进制在2~36之间的话直接调用库函数就行了。
    String s = in.readLine();        
    int a = Integer.parseInt(s, 16) // 将16进制的字符串转化十进制数
    //BigInteger a = new BigInteger(s, 16);// 高精度数
    out.write(Integer.toString(a, 8));        // 转化为8进制输出
          //out.write(a.toString(8));
    out.flush();

🍏五、Algorithm（重点二）

快速幂

快速幂的思想是：

①把指数想象成二进制的表示方式；

②如果指数不等于0，则判断最后一位是否为1（&），如果是，则用结果变量result 乘底数并取模（根据题意设定模的大小），否则不能乘，因为0 * result = 0；

③每进行一次，底数 = 底数 * 底数 % 模（将指数表示为二进制之后，底数应该对应每次的指数），

即 a的1次 a的2次 a的4次 a的8次（同底数相乘，指数相加，正好对应二进制的每一位），

例如：20的3次方（3的二进制为11）= 20的（2的1次方）次方 * 20的（2的0次方）次方；

④将指数往右边移动一位，方便进行下一次的判断

⑤其实到这里，快速幂的思想分析已然结束，但是格外的取模操作让人感到不太理解（不考虑数据溢出的情况下可以不取模），为什么每次都可以取模？其实只要是乘法，不论何时取模都是一样的，可以参考以下公式：

例如：（a * b）% c = (a % c) * (b % c); --> (5 * 6) % 4 = ( 5 % 4) * (6 % 4) = 2

下面以一道省赛例题为例，在不清楚数据是否会溢出的情况下，推荐使用快速幂：

import java.io.*;
public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int mod = 7;
    public static void main(String[] args) throws IOException {
        bw.write(String.valueOf(FastPower(20, 22) + 6));
        bw.flush();
        bw.close();
    }
    public static int FastPower(int a, int b) {
        int res = 1;
        while (b != 0) {
            if ((b & 1) == 1) {
                res = res * a % mod;
            }
            //无论如何，a都要不断倍增，b都要不断右移
            a *= a % mod;
            b = b >> 1;
        }
        return res;
    }
}

素数筛法

埃氏筛

其思想就是：筛掉质数的倍数

package java_Algorithm;
public class demo85_数论2_埃氏筛 {
    static final int N = (int) (1e7 + 5);
    static int[] st = new int[N];
    public static void E_sieve(int n) {
        for (int i = 2; i <= n / i; i++)
            if (st[i] == 0)
                for (int j = i * i; j <= n; j += i)
                    st[j] = 1; // j是i的一个倍数，j是合数，筛掉。
    }
}

欧拉筛（最快）

欧拉筛，又称为线性筛，时间复杂度为O ( n ) O(n)O(n)。

先看下代码再看解析：

public class Main {
    static final int N = (int) (1e7 + 5);
    static int count = 0;
    static int[] status = new int[N], primes = new int[N];
    static void ola(int n) {
        for (int i = 2; i <= n; i++) {
            if (status[i] == 0)
                primes[count++] = i;//将质数存到primes中
            for (int j = 0; primes[j] <= n / i; j++) {//要确保质数的第i倍是小于等于n的。
                status[primes[j] * i] = 1;
                if (i % primes[j] == 0)
                    break;//欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。
            }
        }
    }
    public static void main(String[] args) {
        ola(8);
        for (int i = 0; i < count; i++) {
            System.out.println(primes[i]);
        }
    }
}

欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。

例题：

筛质数

代码：

package java_Algorithm;
public class 欧拉筛 {
    static final int N = (int) (1e7 + 5);
    static int cnt = 0;
    static int[] st = new int[N], primes = new int[N];
    static void ola(int n) {
        for (int i = 2; i <= n; i++) {
            if (st[i] == 0) primes[cnt++] = i;//将质数存到primes中
            for (int j = 0; primes[j] <= n / i; j++) {//要确保质数的第i倍是小于等于n的。
                st[primes[j] * i] = 1;
                if (i % primes[j] == 0) break;
            }
        }
    }
    public static void main(String[] args) {
        ola(8);
        for (int i = 0; i < cnt; i++) {
            System.out.println(primes[i]);
        }
    }
}

双指针（链表）

如果有环，fast一定会追上slow，如果没有环，fast跑完之后就会return false。

//判断是否有环 --- 双指针！！！
    public static boolean isCycle(LinkedNode head) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;//必须保证 ：fast != null
            fast = fast.next.next;//必须保证 ：fast.next != null
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

完整的链表代码

//判断是否有环 — 双指针！！！

//返回倒数第k个节点的值(无环)

//合并两个有序无环单链表，返回新链表的头结点

package java_wuji.JXY.algorithm;
public class LinkedListTest {
    public static class LinkedNode {
        public int value;
        public LinkedNode next;
    }
    public static void print(LinkedNode head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }
    //判断是否有环 --- 双指针！！！
    public static boolean isCycle(LinkedNode head) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    //返回倒数第k个节点的值(无环)
    public static int getNthFromEnd(LinkedNode head, int k) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        //先让他们间隔k-1个距离，即：规定好初始时的间隔
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }
        //当fast指向最后一个结点时结束循环
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.value;
    }
    //合并两个有序无环单链表，返回新链表的头结点
    public static LinkedNode mergedTwoSortedLinkedList(LinkedNode l1, LinkedNode l2) {
        LinkedNode preHead = new LinkedNode();
        LinkedNode prev = preHead;
        while (l1 != null && l2 != null) {
            if (l1.value <= l2.value) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return preHead.next;
    }
    public static void main(String[] args) {
        LinkedNode node1 = new LinkedNode();
        node1.value = 1;
        LinkedNode node2 = new LinkedNode();
        node2.value = 2;
        LinkedNode node3 = new LinkedNode();
        node3.value = 3;
        LinkedNode node4 = new LinkedNode();
        node4.value = 4;
        node1.next = node2;
//        node2.next = node3;
        node3.next = node4;
//        node4.next = node1;//形成环
//        print(node1);
//        System.out.println(isCycle(node1));
//        System.out.println(getNthFromEnd(node1, 2));
        LinkedNode node = mergedTwoSortedLinkedList(node1, node3);
        print(node);
    }
}

前缀和与差分

前缀和(一维)

高中时曾学过数列的前n项和Sn，即若存在一组数列{ a1，a2，a3，…，an }，则Sn = a1+a2+a3+…+an，在计算机领域，我们把Sn称为“前缀和”。

我们知道，对于m(m<n)，有：

Sn - Sm= (a1+a2+a3+…+am-1+am+am+1+…+an) - ( a1+a2+a3+…+am) = am+1+am+2+…+an

根据该公式，我们便找到了解决上面提出的问题的一种方法，即定义一个数组prefix[ ]用以保存数列中的前n项和（此时，prefix[1]=S1，prefix[2]=S2，…，prefix[n]=Sn），这样就可以在求区间[L，R]里的数列之和时直接用prefix[R] - prefix[L-1]得到。而构造前缀数组的方法如下（为了方便起见，通常要求前缀数组中的索引从1开始）：

public static void main(String[] args) throws IOException {
    Scanner scanner = new Scanner(System.in);
    int N = (int) (1e7 + 5);
    int[] prefix = new int[N];
    int[] arr = new int[N];
    int n = 3;
    for (int i = 1; i <= n; i++) {
        arr[i] = scanner.nextInt();
        prefix[i] = prefix[i - 1] + arr[i];
    }
    for (int i = 1; i <= n; i++) {
        System.out.print(prefix[i] + " ");
    }
}

差分

差分与前缀和实际上是刚好相反的两个概念（若设原数组为ary[ ]，前缀和为prefix[ ]，差分为subfix[ ]）。则前缀和的当前项等于原数组中的当前项再加上前缀和的前一项，即prefix[i] = ary[i] + prefix[i-1]；而差分的当前项则等于原数组中的当前项减去原数组中的前一项，即：subfix[i] = ary[i] - ary[i-1]。于是可以得到构造差分数组的方法如下（其索引也是从1开始）。

int subfix[N],ary[N];
for(int i=1;i<=n;i++)
{
        cin>>ary[i];
        subfix[i]=ary[i]-ary[i-1];
}

接下来举个例子以直观地认识差分数组：

设数组ary[ ]={1，2，4，3，6，2}，那么其对应的差分数组subfix[ ]={1，1，2，-1，3，-4}。现在若我们对原数组中区间为[2，4]的元素都加上2的话，则原数组变为ary[ ]={1，4，6，5，6，2}，差分数组变为subfix[ ]={1，3，2，-1，1，-4}。我们发现，subfix[ ]中只有subfix[2]和subfix[5]发生了改变。这是因为区间[2，4]中的元素是同时加上2的，所以在区间[2,4]中的元素之差并未发生改变。同样地，其外部非端点部分的元素之差也不会发生改变。但是在给定区间的起始端点处（索引为2），由于该元素增加了2，故其相对其前一个元素而言增加了2，因此该处subfix[2]的值就增加了2；相反，在给定区间的结束端点处（索引为4），由于该元素增加了2，故其相对其后一个元素而言增加了2，因此在其后的subfix[5]的值就减少了2。

根据差分数组的此特性，我们可以先通过原数组来构建一个差分数组，此过程的时间复杂度为O(n)。然后再把上述问题中于每次操作里需要修改值的某段区间[L，R]优化为仅仅只对区间的两个端点进行修改，这样就可以把修改操作的时间复杂度降低到常数级，进而使得这m个操作的时间复杂度降至O(m)。最终计算区间[L，R]内的数列之和时，仅需要再调用一次SumOfSection函数便可得到，该算法的平均时间复杂的为O(m)。此时，整个程序的时间复杂度将降低至max{ O(m), O(n) }。下面给出求解上述问题的完整代码：

#include<iostream>
using namespace std;
const int N=100010;        // 数组的最大阈值 
int n,m,ans;                // 数列长度、操作次数、最终答案 
int l,r,value;                // m次操作的左右边界与Value 
int ary[N];                        // 原数组 
int subfix[N];                // 差分数组
int main()
{
        cin>>n>>m;
        // 输入原数组 
        for(int i=1;i<=n;i++) cin>>ary[i];
        // 构建subfix数组 
        for(int i=1;i<=n;i++) subfix[i] = ary[i] - ary[i-1];
        // 执行m次操作 
        for(int i=m;i>0;i--){
                cin>>l>>r>>value;
                subfix[l] += value;
                subfix[r+1] -= value;
        }
        // 还原原数组
        for(int i=1;i<=n;i++) ary[i] = ary[i-1] + subfix[i];
        cin>>l>>r;
        // 计算最终询问给出的区间之和
        for(int i=l;i<=r;i++) ans += ary[i];
        cout<<ans<<endl;
        return 0; 
}

小明的彩灯

import java.io.*;
public class demo78_差分_小明的彩灯 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 500005;
    static long[] arr = new long[N];
    static long[] sub = new long[N];
    public static void main(String[] args) throws IOException {
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);
        String[] nextLine = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Long.parseLong(nextLine[i - 1]);
            sub[i] = arr[i] - arr[i - 1];
        }
        while (m-- > 0) {
            String[] subLine = br.readLine().split(" ");
            sub[Integer.parseInt(subLine[0])] += Long.parseLong(subLine[2]);
            sub[Integer.parseInt(subLine[1]) + 1] -= Long.parseLong(subLine[2]);
        }
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i - 1] + sub[i];
            if (arr[i] < 0) System.out.print(0 + " ");
            else System.out.print(arr[i] + " ");
        }
    }
}

Java算法笔记（二）

Arrays类

基础数论

格式控制

输入字符数组

无穷大的坑!

坐标存储小技巧

合排序

Collection工具类的使用

排序操作

查找、替换

Pattern类的使用（匹配正则表达式）

进制转换（x进制转10进制，10进制转y进制）

🍏五、Algorithm（重点二）

快速幂

素数筛法

埃氏筛

欧拉筛（最快）

双指针（链表）

前缀和与差分

前缀和(一维)

热门文章

最新文章

相关课程

相关电子书

相关实验场景

Java算法笔记（二）

Arrays类

基础数论

格式控制

输入字符数组

无穷大的坑!

坐标存储小技巧

合排序

Collection工具类的使用

排序操作

查找、替换

Pattern类的使用（匹配正则表达式）

进制转换（x进制转10进制，10进制转y进制）

🍏五、Algorithm（重点二）

快速幂

素数筛法

埃氏筛

欧拉筛（最快）

双指针（链表）

前缀和 与 差分

前缀和(一维)

热门文章

最新文章

相关课程

相关电子书

相关实验场景

前缀和与差分