Skip to content

Commit ecc39a2

Browse files
author
傅峣
committed
new p
1 parent 26c9f13 commit ecc39a2

6 files changed

Lines changed: 362 additions & 0 deletions

File tree

‎src/baidu/Criminal.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package jtest.com.baidu;
2+
3+
import java.util.Random;
4+
5+
/**
6+
* Created by YAO on 2017/2/28.
7+
*/
8+
public class Criminal {
9+
private int id; // 编号按照时间从小到大 time
10+
private int value; // 犯罪值 extent
11+
12+
Criminal(int id, int CriminalNumber) {
13+
this.id = id;
14+
this.value = estimateExtent(CriminalNumber);
15+
}
16+
17+
private int estimateExtent(int CriminalNumber) {
18+
int max = CriminalNumber;
19+
int min = 1;
20+
Random random = new Random();
21+
22+
int s = random.nextInt(max) % (max - min + 1) + min;
23+
return s;
24+
}
25+
26+
27+
public Integer getId() {
28+
return id;
29+
}
30+
31+
public void setId(Integer id) {
32+
this.id = id;
33+
}
34+
35+
public Integer getValue() {
36+
return value;
37+
}
38+
39+
public void setValue(Integer value) {
40+
this.value = value;
41+
}
42+
}

‎src/baidu/MoveCriminal.java‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
package jtest.com.baidu;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashSet;
5+
import java.util.List;
6+
import java.util.Set;
7+
8+
import static java.lang.System.out;
9+
10+
/**
11+
* Created by YAO on 2017/2/27.
12+
* C市现在要转移一批罪犯到D市，C市有n名罪犯，按照入狱时间有顺序，另外每个罪犯有一个罪行值，值越大罪越重。
13+
* 现在为了方便管理，市长决定转移入狱时间连续的c名犯人，同时要求转移犯人的罪行值之和不超过t，问有多少种选择的方式？
14+
*/
15+
public class MoveCriminal {
16+
17+
public static Set<List<Criminal>> move(Prison prison, int count, int limit) {
18+
Set<List<Criminal>> ways = new HashSet<>();
19+
List<Criminal> CriminalsInPrison = prison.getCriminals();
20+
List<Criminal> toMove = new ArrayList<>();
21+
22+
int totalValue = 0;
23+
// 第一批C-1名犯人
24+
for (int i = 0; i < count - 1; i++) {
25+
Criminal moveOne = CriminalsInPrison.get(i);
26+
toMove.add(moveOne);
27+
totalValue += moveOne.getValue();
28+
}
29+
30+
//滑动窗口模式
31+
try {
32+
for (int i = count - 1, j = 0; i < CriminalsInPrison.size(); i++, j++) {
33+
Criminal moveOne = CriminalsInPrison.get(i);
34+
toMove.add(moveOne);
35+
totalValue += moveOne.getValue();
36+
if (totalValue <= limit) {
37+
ways.add(toMove);
38+
// showTheCriminals(toMove, totalValue);
39+
}
40+
Criminal next = CriminalsInPrison.get(j);
41+
totalValue -= next.getValue();
42+
toMove.remove(0);
43+
}
44+
} catch (IndexOutOfBoundsException e) {
45+
out.println(toMove);
46+
}
47+
return ways;
48+
}
49+
50+
private static void showTheCriminals(List<Criminal> toMove, int totalValue) {
51+
out.println("===============================");
52+
for (Criminal c : toMove) {
53+
out.println("id:" + c.getId());
54+
out.println("value:" + c.getValue());
55+
}
56+
out.println("totalValue:" + totalValue);
57+
out.println("===============================");
58+
}
59+
60+
public static void main(String[] args) {
61+
int criminals = 2000;
62+
int moveNum = 100; // move criminal numbers should be more then 2
63+
int limit = 90000; // should small then criminals*moveNum,should more then min value
64+
65+
Prison C = new Prison(criminals);
66+
Set<List<Criminal>> a = move(C, moveNum, limit);
67+
System.out.println("ways:" + a.size());
68+
}
69+
70+
// public static void main(String[] args){
71+
//
72+
// Scanner scanner = new Scanner(System.in);
73+
// while (scanner.hasNext()){
74+
// int number = scanner.nextInt(); // 罪犯总数
75+
// int limit = scanner.nextInt(); // 犯罪值总数
76+
// int count = scanner.nextInt(); // 移动的罪犯个数
77+
//
78+
// int[] arr = new int[number];
79+
//
80+
// for (int i =0;i<number;i++){
81+
// arr[i] = scanner.nextInt(); // 每个罪犯值？
82+
// }
83+
// int total = 0;
84+
// for (int i =0; i < count -1 && i < arr.length; ++i) {
85+
// total += arr[i];
86+
// }
87+
// int result =0;
88+
// for (int i = count -1,j=0; i < arr.length; ++i,++j){
89+
// total += arr[i];
90+
// if (total <= limit){
91+
// ++result;
92+
// }
93+
// total -=arr[j];
94+
// }
95+
// System.out.println(result);
96+
// }
97+
// scanner.close();
98+
// }
99+
}

‎src/baidu/Prison.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package jtest.com.baidu;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
7+
/**
8+
* Created by YAO on 2017/2/28.
9+
*/
10+
public class Prison {
11+
public List<Criminal> Criminals = new ArrayList<>();
12+
private List<Criminal> Sorted = new ArrayList<>();
13+
14+
Prison(int criminals) {
15+
for (int i = 0; i < criminals; i++) {
16+
putIn(i, criminals);
17+
}
18+
}
19+
20+
private void putIn(int id, int criminals) {
21+
Criminal newOne = new Criminal(id, criminals);
22+
this.Criminals.add(newOne);
23+
// System.out.println(newOne.getId() + " " + newOne.getValue());
24+
}
25+
26+
public int getCriminalNumber() {
27+
return Criminals.size();
28+
}
29+
30+
public List<Criminal> getCriminals() {
31+
return Criminals;
32+
}
33+
34+
private void sortByValue() {
35+
this.Sorted.addAll(this.Criminals);
36+
Collections.sort(Sorted, (o1, o2) -> o1.getValue().compareTo(o2.getValue()));
37+
}
38+
39+
}

‎src/leetCode/AddBinary.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package jtest.com.leetCode;
2+
3+
import static java.lang.System.out;
4+
5+
/**
6+
* Given two binary strings, return their sum (also a binary string).
7+
*
8+
* 二进制数相加计算返回相加结果。
9+
* 二进制数由0和1组成,取位数长的数为基准循环，从低位分别取出两个二进制数的数值。
10+
* 将数值相加并记录进位。对结果除以2分别取余取整，余数为结果对应位的数值，整数为进位值。
11+
* 将所有位的结果和最高位的进位值拼接成相加的结果。
12+
*
13+
* For example,
14+
* a = "111"
15+
* b = "10"
16+
* Return "1001".
17+
*/
18+
public class AddBinary {
19+
public static String add(String a, String b) {
20+
int len = Math.max(a.length(), b.length()); // 取出位数较长的数
21+
System.out.println(len);
22+
String res = ""; // 用于记录余数与结果
23+
int carry = 0; // 用于记录进位
24+
for (int i = 0; i < len; i++) {
25+
int ca = i < a.length() ? a.charAt(a.length() - i - 1) - '0' : 0; // 从低位开始取值，char - '0' 将char对象转换成int
26+
out.println("ca: " + ca);
27+
int cb = i < b.length() ? b.charAt(b.length() - i - 1) - '0' : 0;
28+
out.println("cb: " + cb);
29+
res = (ca + cb + carry) % 2 + res; // % 取余 1%2=1,0%2=0,2%2=0, 拼接低位结果
30+
out.println("res: " + res);
31+
carry = (ca + cb + carry) / 2; // / 取整 1/2=0 没有进位 2/2=1 有进位
32+
out.println("carry:" + carry);
33+
}
34+
if (carry > 0) {
35+
res = carry + res; // 最高位如果有进位, 拼接结果
36+
}
37+
out.println("rs: " + res);
38+
return res;
39+
}
40+
41+
public static void main(String[] args) {
42+
out.println(add("111", "10"));
43+
}
44+
}

‎src/leetCode/AddTwoNumbers.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package jtest.com.leetCode;
2+
/*
3+
* You are given two linked lists representing two non-negative numbers. The
4+
* digits are stored in reverse
5+
* order and each of their nodes contain a single digit. Add the two numbers
6+
* and return it as a linked list.
7+
8+
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
9+
* Output: 7 -> 0 -> 8
10+
*/
11+
12+
/**
13+
* Definition for singly-linked list.
14+
* public class ListNode {
15+
* int val;
16+
* ListNode next;
17+
* ListNode(int x) {
18+
* val = x;
19+
* next = null;
20+
* }
21+
* }
22+
*/
23+
public class AddTwoNumbers {
24+
public class ListNode {
25+
int val;
26+
ListNode next;
27+
28+
ListNode(int x) {
29+
val = x;
30+
next = null;
31+
}
32+
}
33+
34+
// public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
35+
// return addTwoNumbersHelper(l1, l2, 0);
36+
// }
37+
//
38+
// public ListNode addTwoNumbersHelper(ListNode l1, ListNode l2, int carry) {
39+
// if (l1 == null && l2 == null)
40+
// return carry == 0 ? null : new ListNode(carry);
41+
// int i = 0, j = 0;
42+
// if(l1 != null)
43+
// i = l1.val;
44+
// if(l2 != null)
45+
// j = l2.val;
46+
// ListNode head = new ListNode((i + j + carry) % 10);
47+
// head.next = addTwoNumbersHelper(l1 == null ? null : l1.next,
48+
// l2 == null ? null : l2.next, (i + j + carry) / 10);
49+
// return head;
50+
// }
51+
52+
53+
/**************************** updated 2014.03.16 *****************************/
54+
55+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
56+
int carry = 0;
57+
ListNode dummy = new ListNode(0);
58+
ListNode cur = dummy;
59+
while (l1 != null || l2 != null) {
60+
int a = 0;
61+
int b = 0;
62+
if (l1 != null) {
63+
a = l1.val;
64+
l1 = l1.next;
65+
}
66+
if (l2 != null) {
67+
b = l2.val;
68+
l2 = l2.next;
69+
}
70+
cur.next = new ListNode((a + b + carry) % 10);
71+
carry = (a + b + carry) / 10;
72+
cur = cur.next;
73+
}
74+
if (carry != 0) {
75+
cur.next = new ListNode(carry);
76+
}
77+
return dummy.next;
78+
}
79+
}

‎src/ninety_nine/Lists/java99.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package jtest.com.ninety_nine.Lists;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Collections;
6+
import java.util.LinkedList;
7+
import java.util.List;
8+
import java.util.NoSuchElementException;
9+
10+
import static java.util.Arrays.asList;
11+
import static org.hamcrest.CoreMatchers.equalTo;
12+
import static org.hamcrest.CoreMatchers.is;
13+
import static org.hamcrest.MatcherAssert.assertThat;
14+
15+
16+
/**
17+
* P01 (*) Find the last element of a list
18+
*/
19+
public class java99 {
20+
public static class core {
21+
22+
public static <T> List<T> tail(LinkedList<T> elements) {
23+
if (elements == null || elements.isEmpty()) {
24+
throw new NoSuchElementException();
25+
}
26+
if (elements.size() == 1) {
27+
return Collections.emptyList();
28+
}
29+
return elements.subList(1, elements.size());
30+
}
31+
}
32+
33+
34+
public static class P01 {
35+
36+
@Test
37+
public void shouldFindLastElementFromAListOfAlphabets() throws Exception {
38+
assertThat(P01.last(asList("a", "b", "c", "d")), is(equalTo("d")));
39+
}
40+
41+
private static <T> T last(java.util.List<T> elements) {
42+
LinkedList<T> list = new LinkedList<T>(elements);
43+
return list.getLast();
44+
}
45+
}
46+
47+
public static class P02 {
48+
@Test
49+
public void shouldFindSecondLastElementFromAList() throws Exception {
50+
List<Integer> numbers = asList(1, 2, 11, 4, 5, 8, 10, 6);
51+
assertThat(P02.secondLast(numbers), is(equalTo(10)));
52+
}
53+
54+
private static <T> T secondLast(List<T> numbers) {
55+
LinkedList<T> list = new LinkedList<T>(numbers);
56+
return secondLast(list.subList(0, list.size() - 1));
57+
}
58+
}
59+
}

0 commit comments

Comments
 (0)