記錄一下自己刷題的錯題

1、小v所在的公司即將舉行年會，年會方案設計過程中必不可少的一項就是抽獎活動。小v在本次活動中被委以重任，負責抽獎活動的策劃；為了讓中獎的禮物更加精美且富有神秘感，打算采用禮品盒來包裝獎品，此時小v發揮了自己的創意想捉弄一下獲獎的同事，便采取了多重包裝來包裝獎品。

現給出一個字符串，并假定用一對圓括號( )表示一個禮品盒，0表示獎品，你能據此幫獲獎者算出最少要拆多少個禮品盒才能拿到獎品嗎？

輸入描述：

一行字符串，僅有'('、')'、'0' 組成，其中一對'(' ')'表示一個禮品盒，‘0’表示獎品；輸入的字符串一定是有效的，即'(' ')'一定是成對出現的。

輸出描述:

輸出結果為一個數字，表示小v要拆的最少禮品盒數量

輸入例子1:

(()(()((()(0)))))

輸出例子1:

5

解題思路：

在找到 "0" 之前，凡遇到成對的"()"表示一個完整的 空 盒子，可以丟掉，也可以拆開。如果選擇丟掉，那么output是最小的拆盒子數。 sum++ 是說選擇拆開一層包裝，sum-- 說明 試著拆開后發現 這是成對的"()" 空盒子，不如不拆，可以丟掉，不計入最小的拆盒子數中 private static int solution(String str) {int sum = 0;for(int i=0;i<str.length();i++){if(str.charAt(i)=='0'){break;}else if(str.charAt(i)=='('){sum++;//拆開一層包裝}else{sum--;//"()"情況的盒子可以不用拆開，直接丟掉即可}} return sum;}

2、一個長方體，長寬高分別為x,y,z，都為自然數。

現在要把若干個相同的長方體擺成高為N的一根柱形體。

每層擺1個，如果兩種擺法的高度是一樣的，則認為這兩種擺法等價，所以每層只有三種擺法。

求一共有多少種擺法。
輸入描述:
第一行為一個數字N，N>=1且N<=100，表示要擺放的高度
第二行為長方體的長寬高,x、y、z都為無符號整數，按升序排列。

輸出描述:
擺法總數，已知該總數會小于10000000
輸入
10
5 6 7
輸出
1

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int N = input.nextInt();int x = input.nextInt();int y = input.nextInt();int z = input.nextInt();int db[] = new int[N+1];db[x] = 1;db[y] = 1;db[z] = 1; 注意這里x最小，升序，db的計算順序要從小到大，所以從x+1開始計算。因為后面的要用到前面的計算結果。for (int i = x+1; i < N+1; i++) {db[i] += i-x>0?db[i-x]:0;db[i] += i-y>0?db[i-y]:0;db[i] += i-z>0?db[i-z]:0;}System.out.println(db[N]);}}

3、一個長方體，長寬高分別為x,y,z，都為自然數。

現在要把若干個相同的長方體擺成高為N的一根柱形體。

每層擺1個，如果兩種擺法的高度是一樣的，則認為這兩種擺法等價，所以每層只有三種擺法。

求一共有多少種擺法。

輸入描述:
第一行為一個數字N，N>=1且N<=100，表示要擺放的高度
第二行為長方體的長寬高,x、y、z都為無符號整數，按升序排列。

輸出描述:
擺法總數，已知該總數會小于10000000
示例1
輸入
10
5 6 7
輸出
1

備注:
如果沒有任何一種擺法可以達成目的，輸出0

import java.util.*;public class Main {public static void main(String[] args) {run();}public static void run(){Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();HashMap<String,List<Integer>> amap = new HashMap<String, List<Integer>>();for(int i=0;i<n;i++){int m = sc.nextInt();這里把一個序列當成一個字符串來處理，之后比較相同就比較方便了sc.nextLine();String t = sc.nextLine();List<Integer> a = new ArrayList<>();if(amap.containsKey(t)){a = amap.get(t);}a.add(i);amap.put(t, a);}TreeMap<Integer,List<Integer>> re = new TreeMap<Integer, List<Integer>>();for(String k:amap.keySet()){List<Integer> a = amap.get(k);if(a.size()>1){re.put(a.get(0), a);}}for(int i:re.keySet()){List<Integer> a = re.get(i);for(int j:a){System.out.print(j+" ");}System.out.println();}if(re.size()<1){System.out.println("no");}} }

4、一個數字段由首尾兩個數字標識，表示一個自然數集合，
比如數字段[beg, end)表示從beg到end之間的所有自然數，
包含beg，但不包含end。

有若干個數字段，這些數字段之間可能有重疊，
怎么把這些數字段合并去重，用最少個數的數字段來表示。

合并前后，整個集合包含的數字不發生變化。

輸入描述:
第一行為數字N，表示接下來有N個數字段(N<=100000)
第二行開始一共有N行，每行兩個數字，分別表示一個數字段的beg和end
(beg和end為無符號32位整數)

輸出描述:
合并去重后形成的數字段集合，按升序排列。
示例1
輸入
4
3 8
3 7
4 6
7 9
輸出
3 9

先把數據按照左值小的，右值大的排序，然后再遍歷整個數組。如果兩個值對(a,b),(c,d)，如果a<=b &&b>=d那么對于(a,b)來說，(c,d)就可以被合并，如果b<d那么就可以把b的值替換為d，把(a,b)更新為 （a,d）,如果c>b那么就意味著一個區間不能表示（a,b）和（c，d），必須要用兩個區間來表示。遍歷 一遍數組就行了。import java.util.*;public class Main{static class Pair implements Comparable<Pair>{public int a;public int b;public Pair(int a,int b){this.a=a;this.b=b;}@Override自己設計數據結構，重構比較方式public int compareTo(Pair p){if(a==p.a) return p.b-b;else return a-p.a;}}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();Pair[] ps=new Pair[n];for(int i=0;i<n;i++){int k=sc.nextInt();int l=sc.nextInt();ps[i]=new Pair(k,l);}Arrays.sort(ps);/*for(int i=0;i<n;i++){System.out.println(ps[i].a+" "+ps[i].b);}*/List<Pair> result=new ArrayList<>();Pair now=ps[0];for(int i=1;i<n;i++){if(now.a<=ps[i].a&&now.b>=ps[i].b){continue;}else if(ps[i].a>now.b){result.add(now);now=ps[i];}else now.b=ps[i].b;}result.add(now);for(Pair p:result){System.out.println(p.a+" "+p.b);}sc.close();}}

5、有K種顏色的小球(K<=10)，每種小球有若干個，總數小于100個。
現在有一個小盒子，能放N個小球(N<=8)，現在要從這些小球里挑出N個小球，放滿盒子。
想知道有哪些挑選方式。注：每種顏色的小球之間沒有差別。

請按數字遞增順序輸出挑選小球的所有方式。

如有3種顏色，每種顏色小球的個數分別為a:1,b:2,c:3，挑出3個小球的挑法有：
003,012,021,102,111,120

輸入描述:
第一行兩個數字K N，分別表示小球種類數目和挑選的小球個數
第二行開始為每種小球的數目，共K行數據

輸出描述:
輸出所有可行的挑選方案，按升序排列

輸入例子1:
3 3
1
2
3

輸出例子1:
003
012
021
102
111
120

import java.util.Scanner; import java.util.List; import java.util.LinkedList; import java.lang.Math; public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext()){int k = sc.nextInt();int n = sc.nextInt();//nums記錄顏色球的個數int[] nums = new int[k];for(int i = 0;i < k; i++){nums[i] = sc.nextInt();}List<String> result = new LinkedList<>();help(result,n,0,nums,"");result.forEach(System.out::println);}} 利用遞歸思想，深度優先遍歷protected static void help(List<String> result,int target,int start,int[] nums,String s){if(target == 0 && start == nums.length){result.add(s);return;}if(start == nums.length){return;}for(int i = 0;i <= Math.min(target,nums[start]);i++){// 取當前 target 和對應球的數量中的較小值。help(result,target - i,start+1,nums,s+i);}} }

6、題目描述
有n個1~23的整數，寫一個算法，求出有多少個相互不同的子集合的和為24點。

輸入

輸入數據包含一組，每組占一行，包括n個整數 （1<=整數 <=23）

輸出

對于每個測試實例，要求輸出能組成24點的所有子集合的數量（子集合相互不同）。如果不存在，則輸出0。每個測試實例的輸出占一行。

輸入樣例

1 2 22 23

輸出樣例

2

import java.util.*;public class Main {public static int sum = 0;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int length = scanner.nextInt();scanner.nextLine();int[] input = new int[length];boolean[] used = new boolean[input.length];for (int i = 0; i < length; i++) {input[i] = scanner.nextInt();}FullSort(input, used, 24, 0, length - 1);System.out.println(sum);}private static void FullSort(int[] input, boolean[] used, int sum1, int start, int end) {if (sum1 <= 0) return;if (start == end && sum1 != 0) return;for (int i = start; i <= end; i++) {if (i > 0 && input[i] == input[i - 1] && !used[i - 1]) continue;//去重if (!used[i]) {used[i] = true;if (sum1 == input[i]) sum++;else {FullSort(input, used, sum1 - input[i], i + 1, end);}used[i] = false;}}}}

總結

以上是生活随笔為你收集整理的记录一下自己刷题的错题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。