Java – gongel

分治：为运算表达式设计优先级

241. 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2
示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"

输出: [0, 2]

解释:

((2-1)-1) = 0

(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"

输出: [-34, -14, -10, -10, 10]

解释:

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

import java.util.ArrayList;
import java.util.List;

public class Twohundred_fortyOne {
    /**
     * 分治法
     */
    public List<Integer> diffWaysToCompute(String input) {
        if (input == null || input.length() == 0)
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char opt = input.charAt(i);
            if (opt == '+' || opt == '-' || opt == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        switch (opt) {
                            case '+':
                                ans.add(l + r);
                                break;
                            case '-':
                                ans.add(l - r);
                                break;
                            case '*':
                                ans.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(Integer.valueOf(input));
        }
        return ans;
    }
}

import java.util.ArrayList;

import java.util.List;

public class Twohundred_fortyOne {

/**

* 分治法

public List<Integer> diffWaysToCompute(String input) {

if (input == null || input.length() == 0)

return new ArrayList<>();

List<Integer> ans = new ArrayList<>();

for (int i = 0; i < input.length(); i++) {

char opt = input.charAt(i);

if (opt == '+' || opt == '-' || opt == '*') {

List<Integer> left = diffWaysToCompute(input.substring(0, i));

List<Integer> right = diffWaysToCompute(input.substring(i + 1));

for (int l : left) {

for (int r : right) {

switch (opt) {

case '+':

ans.add(l + r);

break;

case '-':

ans.add(l - r);

break;

case '*':

ans.add(l * r);

break;

}

if (ans.size() == 0) {

ans.add(Integer.valueOf(input));

}

return ans;

}

最长数对链

646. 最长数对链

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意：

给出数对的个数在 [1, 1000] 范围内。

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]

输出: 2

解释: 最长的数对链是 [1,2] -> [3,4]

注意：

给出数对的个数在 [1, 1000] 范围内。

import java.util.*;

public class Sixhundred_fortySix {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0 || pairs[0].length == 0)
            return 0;
        Arrays.sort(pairs, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int ans = 1;
        int temp = pairs[0][1];
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > temp) {
                ans += 1;
                temp = pairs[i][1];
            }
        }
        return ans;
    }
}

import java.util.*;

public class Sixhundred_fortySix {

public int findLongestChain(int[][] pairs) {

if (pairs == null || pairs.length == 0 || pairs[0].length == 0)

return 0;

Arrays.sort(pairs, new Comparator<int[]>() {

public int compare(int[] o1, int[] o2) {

return o1[1] - o2[1];

}

});

int ans = 1;

int temp = pairs[0][1];

for (int i = 1; i < pairs.length; i++) {

if (pairs[i][0] > temp) {

ans += 1;

temp = pairs[i][1];

}

return ans;

}

字符串

151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

 

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"
示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"

输出: "blue is sky the"

示例 2：

输入: " hello world! "

输出: "world! hello"

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good example"

输出: "example good a"

解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。

输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

class Solution {
    public String reverseWords(String s) {
        String[] str=s.split(" ");
        for(int i=0;i<str.length/2;i++){
            String es=str[i];
            str[i]=str[str.length-i-1];
            str[str.length-i-1]=es;
        }
        return String.join(" ", str).trim().replaceAll("\\s{2,}", " ");
    }
}

class Solution {

public String reverseWords(String s) {

String[] str=s.split(" ");

for(int i=0;i<str.length/2;i++){

String es=str[i];

str[i]=str[str.length-i-1];

str[str.length-i-1]=es;

}

return String.join(" ", str).trim().replaceAll("\\s{2,}", " ");

}

179. 最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]

输出: 210

示例 2:

输入: [3,30,34,5,9]

输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

class Solution {
    //"2"+"12">"12"+"2",所以需要排序
    public String largestNumber(int[] nums) {
        if(nums==null || nums.length==0)
            return "0";
            String[] str=new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i]=String.valueOf(nums[i]);
        }
        Arrays.sort(str,new Comparator<String>(){
                public int compare(String o1,String o2){
                    return (o2+o1).compareTo(o1+o2);
                }
            });
        if(str[0].equals("0")){//说明原始数组只有一个元素"0"
            return "0";
        }
        String ans=new String();
        for(int i=0;i<str.length;i++){
            ans+=str[i];
        }
        return ans;
    }
}

class Solution {

//"2"+"12">"12"+"2",所以需要排序

public String largestNumber(int[] nums) {

if(nums==null || nums.length==0)

return "0";

String[] str=new String[nums.length];

for(int i=0;i<nums.length;i++){

str[i]=String.valueOf(nums[i]);

}

Arrays.sort(str,new Comparator<String>(){

public int compare(String o1,String o2){

return (o2+o1).compareTo(o1+o2);

}

});

if(str[0].equals("0")){//说明原始数组只有一个元素"0"

return "0";

}

String ans=new String();

for(int i=0;i<str.length;i++){

ans+=str[i];

}

return ans;

}

Collections.sort和Arrays.sort自定义排序/部分排序

归并

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]

输出: [2,1,1,0]

解释:

5 的右侧有 2 个更小的元素 (2 和 1).

2 的右侧仅有 1 个更小的元素 (1).

6 的右侧有 1 个更小的元素 (1).

1 的右侧有 0 个更小的元素.

import java.util.*;

public class Threehundred_fifteen {
    /**
     * 对于数组 a[lo..hi)，如果 a[lo..mid) 与 a[mid..hi) 都已经归并有序，则：
     * 对于左半区间中 a[lo..mid) 中的每个元素 a[left]，计算 a[mid..hi) 中有多少个元素小于它。
     */
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            ans.add(0);
        }
        int[][] index = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            index[i] = new int[]{nums[i], i};
        }
        merge_sort(index, 0, index.length, ans);
        return ans;
    }

    public void merge_sort(int[][] index, int start, int end, List<Integer> ans) {
        if (end - start <= 1)
            return;
        int mid = start + (end - start) / 2;
        merge_sort(index, start, mid, ans);
        merge_sort(index, mid, end, ans);
        int right = mid;
        // 对于左半区间中的每个元素left，统计右侧比它小的元素的个数
        for (int i = start; i < mid; i++) {
            while (right < end && index[i][0] > index[right][0])
                right++;
            ans.set(index[i][1], ans.get(index[i][1]) + right - mid);
        }
        Arrays.sort(index, start, end, new Comparator<int[]>() {//相当于归并排序中合并左右区间，end不包含在内
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
    }
}

import java.util.*;

public class Threehundred_fifteen {

/**

* 对于数组 a[lo..hi)，如果 a[lo..mid) 与 a[mid..hi) 都已经归并有序，则：

* 对于左半区间中 a[lo..mid) 中的每个元素 a[left]，计算 a[mid..hi) 中有多少个元素小于它。

public List<Integer> countSmaller(int[] nums) {

if (nums == null || nums.length == 0)

return new ArrayList<>();

List<Integer> ans = new ArrayList<>();

for (int i = 0; i < nums.length; i++) {

ans.add(0);

}

int[][] index = new int[nums.length][2];

for (int i = 0; i < nums.length; i++) {

index[i] = new int[]{nums[i], i};

}

merge_sort(index, 0, index.length, ans);

return ans;

}

public void merge_sort(int[][] index, int start, int end, List<Integer> ans) {

if (end - start <= 1)

return;

int mid = start + (end - start) / 2;

merge_sort(index, start, mid, ans);

merge_sort(index, mid, end, ans);

int right = mid;

// 对于左半区间中的每个元素left，统计右侧比它小的元素的个数

for (int i = start; i < mid; i++) {

while (right < end && index[i][0] > index[right][0])

right++;

ans.set(index[i][1], ans.get(index[i][1]) + right - mid);

}

Arrays.sort(index, start, end, new Comparator<int[]>() {//相当于归并排序中合并左右区间，end不包含在内

@Override

public int compare(int[] o1, int[] o2) {

return o1[0] - o2[0];

}

});

}

327. 区间和的个数

给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3 
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:

最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,

输出: 3

解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

mport java.util.*;

public class Threehundred_twentySeven {
    public int merge_sort(List<Long> list, int start, int end, int lower, int upper) {
        if (end - start <= 1)
            return 0;
        int mid = start + (end - start) / 2;
        int cnt = merge_sort(list, start, mid, lower, upper) + merge_sort(list, mid, end, lower, upper);
        int right1 = mid;
        int right2 = mid;
        for (int i = start; i < mid; i++) {
            // 统计右侧-nums[left] < lower 的个数
            while (right1 < end && list.get(right1) - list.get(i) < lower)
                right1++;
            // 统计右侧-nums[left] <= upper 的个数
            while (right2 < end && list.get(right2) - list.get(i) <= upper)
                right2++;
            // 因此右侧-nums[left]的差在 [lower,upper] 的个数为：
            //count += (right2 - mid) - (right1 - mid); 可以简写为下面这样
            cnt += right2 - right1;
        }
        Collections.sort(list.subList(start, end));
        return cnt;
    }

    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0)
            return 0;
        List<Long> list = new ArrayList<>();
        list.add(Long.valueOf(0));
        // 计算前缀和
        for (int i = 0; i < nums.length; i++) {
            list.add(list.get(i) + nums[i]);
        }
        return merge_sort(list, 0, list.size(), lower, upper);
    }
}

mport java.util.*;

public class Threehundred_twentySeven {

public int merge_sort(List<Long> list, int start, int end, int lower, int upper) {

if (end - start <= 1)

return 0;

int mid = start + (end - start) / 2;

int cnt = merge_sort(list, start, mid, lower, upper) + merge_sort(list, mid, end, lower, upper);

int right1 = mid;

int right2 = mid;

for (int i = start; i < mid; i++) {

// 统计右侧-nums[left] < lower 的个数

while (right1 < end && list.get(right1) - list.get(i) < lower)

right1++;

// 统计右侧-nums[left] <= upper 的个数

while (right2 < end && list.get(right2) - list.get(i) <= upper)

right2++;

// 因此右侧-nums[left]的差在 [lower,upper] 的个数为：

//count += (right2 - mid) - (right1 - mid); 可以简写为下面这样

cnt += right2 - right1;

}

Collections.sort(list.subList(start, end));

return cnt;

}

public int countRangeSum(int[] nums, int lower, int upper) {

if (nums == null || nums.length == 0)

return 0;

List<Long> list = new ArrayList<>();

list.add(Long.valueOf(0));

// 计算前缀和

for (int i = 0; i < nums.length; i++) {

list.add(list.get(i) + nums[i]);

}

return merge_sort(list, 0, list.size(), lower, upper);

}

线段树

数组下标[i, j]–>线段树[i, (i+j)/2]和[(i+j)/2+1, j]

线段树数组空间为4*len(arr)=4n,证明如下：

预备：二叉树用满二叉树存储

情况一：所有的元素都在最后一层，则分支节点个数为n-1，共需要2n-1空间，已经为满二叉树，不需要补空间；

情况二：只有2个节点在最有一层，另外n-2个节点在倒数第二层，则需要对这n-2个节点补充左右孩子，则需要2(n-2)=2n-4，原始二叉树共有2n-1个节点，那么一共有2n-1+2n-4=4n-5<4n；

综上：开4n空间

307. 区域和检索 – 数组可修改

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:

数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9

update(1, 2)

sumRange(0, 2) -> 8

说明:

数组仅可以在 update 函数下进行修改。

你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

class NumArray {
    public static int[] tree;
    public static int[] nums;
    public static int len;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return;
        this.len = nums.length;
        this.nums = nums;
        this.tree = new int[4 * len];
        buildTree(1, 0, len - 1);
    }

    //start/end是数组的下标，current/left_node/right_node为树的下标
    public void buildTree(int current, int start, int end) {
        if (start == end)
            tree[current] = nums[start];
        else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            buildTree(left_node, start, mid);
            buildTree(right_node, mid + 1, end);
            tree[current] = tree[left_node] + tree[right_node];
        }
    }

    public void update(int i, int val) {
        updateTree(1, 0, len - 1, i, val);
    }

    public void updateTree(int current, int start, int end, int pos, int val) {
        if (start == end) {
            nums[pos] = val;
            tree[current] = val;
        } else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            if (start <= pos && pos <= mid)
                updateTree(left_node, start, mid, pos, val);
            else
                updateTree(right_node, mid + 1, end, pos, val);
            tree[current] = tree[left_node] + tree[right_node];
        }

    }

    public int sumRange(int i, int j) {
        return sumTree(1, 0, len - 1, i, j);
    }

    public int sumTree(int current, int start, int end, int left, int right) {
        if (right < start || left > end)//需要求解的区间不在[start,end]内
            return 0;
        else if (left <= start && right >= end)//[left,right]将[start,end]包含，已经没必要向子节点走了
            return tree[current];
        else if (start == end)
            return tree[current];
        else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            return sumTree(left_node, start, mid, left, right) + sumTree(right_node, mid + 1, end, left, right);
        }
    }
}

class NumArray {

public static int[] tree;

public static int[] nums;

public static int len;

public NumArray(int[] nums) {

if (nums == null || nums.length == 0)

return;

this.len = nums.length;

this.nums = nums;

this.tree = new int[4 * len];

buildTree(1, 0, len - 1);

}

//start/end是数组的下标，current/left_node/right_node为树的下标

public void buildTree(int current, int start, int end) {

if (start == end)

tree[current] = nums[start];

else {

int left_node = 2 * current;

int right_node = 2 * current + 1;

int mid = (start + end) / 2;

buildTree(left_node, start, mid);

buildTree(right_node, mid + 1, end);

tree[current] = tree[left_node] + tree[right_node];

}

public void update(int i, int val) {

updateTree(1, 0, len - 1, i, val);

}

public void updateTree(int current, int start, int end, int pos, int val) {

if (start == end) {

nums[pos] = val;

tree[current] = val;

} else {

int left_node = 2 * current;

int right_node = 2 * current + 1;

int mid = (start + end) / 2;

if (start <= pos && pos <= mid)

updateTree(left_node, start, mid, pos, val);

else

updateTree(right_node, mid + 1, end, pos, val);

tree[current] = tree[left_node] + tree[right_node];

}

public int sumRange(int i, int j) {

return sumTree(1, 0, len - 1, i, j);

}

public int sumTree(int current, int start, int end, int left, int right) {

if (right < start || left > end)//需要求解的区间不在[start,end]内

return 0;

else if (left <= start && right >= end)//[left,right]将[start,end]包含，已经没必要向子节点走了

return tree[current];

else if (start == end)

return tree[current];

else {

int left_node = 2 * current;

int right_node = 2 * current + 1;

int mid = (start + end) / 2;

return sumTree(left_node, start, mid, left, right) + sumTree(right_node, mid + 1, end, left, right);

}

线段树详解

【数据结构】线段树（Segment Tree）

线段树开4N空间证明

processon

一	二	三	四	五	六	日
« 12月
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31