Codes – gongel-coder

Round A 2019 – Kick Start 2019

#include<bits/stdc++.h>

using namespace std;
const int N = 100000, INF = 0x3f3f3f3f;
int T, n, p;
int a[N], sum[N + 1];

/**
 * sum[i] - sum[i - p] = a[i-p+1] + a[i-p+2] +...+ a[i]
 * p * a[i] - (sum[i] - sum[i - p])=(p-1)*a[i] - (a[i-p+1] + a[i-p+2] + ... +  a[i-1])
 * 假设p=3，i=5
 * 那么有3*a[5]- (sum[5] - sum[2])=2 * a[5] - (a[3] + a[4]) = (a[5] - a[3]) + (a[5] - a[4])
 * 即每次计算当前元素和前面p-1个元素的差的和，依次遍历取最小值,利用前缀和来优化
 * */
int main() {
    cin >> T;
    int cnt = 1;
    while (T-- > 0) {
        cin >> n >> p;
        for (int i = 1; i < n + 1; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int ans = INF;
        for (int i = 1; i < n + 1; i++) {
            sum[i] = sum[i - 1] + a[i];
        }
        for (int i = p; i < n + 1; i++) {
            ans = min(ans, p * a[i] - (sum[i] - sum[i - p]));
        }
        printf("Case #%d: %d\n", cnt, ans);
        cnt++;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 100000, INF = 0x3f3f3f3f;

int T, n, p;

int a[N], sum[N + 1];

/**

* sum[i] - sum[i - p] = a[i-p+1] + a[i-p+2] +...+ a[i]

* p * a[i] - (sum[i] - sum[i - p])=(p-1)*a[i] - (a[i-p+1] + a[i-p+2] + ... + a[i-1])

* 假设p=3，i=5

* 那么有3*a[5]- (sum[5] - sum[2])=2 * a[5] - (a[3] + a[4]) = (a[5] - a[3]) + (a[5] - a[4])

* 即每次计算当前元素和前面p-1个元素的差的和，依次遍历取最小值,利用前缀和来优化

* */

int main() {

cin >> T;

int cnt = 1;

while (T-- > 0) {

cin >> n >> p;

for (int i = 1; i < n + 1; i++) {

cin >> a[i];

}

sort(a + 1, a + n + 1);

int ans = INF;

for (int i = 1; i < n + 1; i++) {

sum[i] = sum[i - 1] + a[i];

}

for (int i = p; i < n + 1; i++) {

ans = min(ans, p * a[i] - (sum[i] - sum[i - p]));

}

printf("Case #%d: %d\n", cnt, ans);

cnt++;

}

return 0;

}

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

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);

}

一	二	三	四	五	六	日
« 10月
				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