Skip to content

Commit f5bd7e4

Browse files
author
Tianye
committed
add homework of week1
1 parent 0fd6bbe commit f5bd7e4

9 files changed

Lines changed: 261 additions & 0 deletions

‎Week01/DesignCircularDeque.java‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
class MyCircularDeque {
2+
3+
public int[] arr;
4+
private int front;
5+
private int rear;
6+
private int capacity;
7+
8+
9+
10+
/** Initialize your data structure here. Set the size of the deque to be k. */
11+
public MyCircularDeque(int k) {
12+
capacity = k +1;
13+
arr = new int[capacity];
14+
front = 0;
15+
rear = 0;
16+
}
17+
18+
/** Adds an item at the front of Deque. Return true if the operation is successful. */
19+
public boolean insertFront(int value) {
20+
if (isFull()) return false;
21+
22+
front = (front -1 + capacity)% capacity;
23+
arr[front] = value;
24+
return true;
25+
26+
}
27+
28+
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
29+
public boolean insertLast(int value) {
30+
if (isFull()) return false;
31+
arr[rear] = value;
32+
rear = (rear + 1 ) % capacity;
33+
34+
return true;
35+
}
36+
37+
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
38+
public boolean deleteFront() {
39+
if (isEmpty()) return false;
40+
front = (front +1 ) % capacity;
41+
return true;
42+
}
43+
44+
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
45+
public boolean deleteLast() {
46+
if (isEmpty()) return false;
47+
48+
rear = (rear -1 + capacity)% capacity;
49+
return true;
50+
}
51+
52+
/** Get the front item from the deque. */
53+
public int getFront() {
54+
if (isEmpty()){
55+
return -1;
56+
}
57+
return arr[front];
58+
}
59+
60+
/** Get the last item from the deque. */
61+
public int getRear() {
62+
if (isEmpty()){
63+
return -1;
64+
}
65+
return arr[(rear - 1 + capacity) % capacity];
66+
}
67+
68+
/** Checks whether the circular deque is empty or not. */
69+
public boolean isEmpty() {
70+
return front == rear;
71+
}
72+
73+
/** Checks whether the circular deque is full or not. */
74+
public boolean isFull() {
75+
return (rear +1 ) % arr.length == front ;
76+
}
77+
}
78+
79+
/**
80+
* Your MyCircularDeque object will be instantiated and called as such:
81+
* MyCircularDeque obj = new MyCircularDeque(k);
82+
* boolean param_1 = obj.insertFront(value);
83+
* boolean param_2 = obj.insertLast(value);
84+
* boolean param_3 = obj.deleteFront();
85+
* boolean param_4 = obj.deleteLast();
86+
* int param_5 = obj.getFront();
87+
* int param_6 = obj.getRear();
88+
* boolean param_7 = obj.isEmpty();
89+
* boolean param_8 = obj.isFull();
90+
*/

‎Week01/MergeSortedArray.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class MergeSortedArray {
2+
public void merge(int[] nums1, int m, int[] nums2, int n) {
3+
int i = m - 1 ;
4+
int j = n - 1;
5+
int totalSize= m + n;
6+
for(int k = totalSize-1; k >= 0; k--){
7+
if(j <0){
8+
return;
9+
}
10+
if ( i >= 0 && nums1[i] > nums2[j] ) {
11+
nums1[k]= nums1[i];
12+
i--;
13+
}else {
14+
nums1[k] = nums2[j];
15+
j--;
16+
}
17+
}
18+
}
19+
}

‎Week01/MergeTwoSorted.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* public class ListNode {
4+
* int val;
5+
* ListNode next;
6+
* ListNode() {}
7+
* ListNode(int val) { this.val = val; }
8+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9+
* }
10+
*/
11+
class MergeTowSortedList {
12+
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
13+
ListNode newHead = new ListNode();
14+
ListNode pNode = newHead;
15+
16+
17+
while(l1 != null && l2 != null){
18+
if(l1.val <= l2.val){
19+
pNode.next = l1;
20+
l1 = l1.next;
21+
}else{
22+
pNode.next = l2;
23+
l2 = l2.next;
24+
}
25+
pNode = pNode.next;
26+
27+
28+
}
29+
if(pNode == null){
30+
return l1 !=null ? l1 :l2;
31+
}
32+
if (l1 != null ) {
33+
pNode.next = l1;
34+
}
35+
if (l2 != null) {
36+
pNode.next = l2;
37+
}
38+
return newHead.next;
39+
40+
}
41+
}

‎Week01/MoveZeroes.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class MoveZeroes {
2+
public void moveZeroes(int[] nums) {
3+
int j =0 ;
4+
for (int i = 0; i < nums.length; i++) {
5+
if (nums[i]!= 0 ){
6+
// 当i==j 时无需交换
7+
if(i!=j){
8+
int tmp = nums[i];
9+
nums[i] = nums[j];
10+
nums[j++] = tmp;
11+
}else{
12+
j++;
13+
}
14+
}
15+
}
16+
}
17+
}

‎Week01/PlusOne.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class PlusOne {
2+
public int[] plusOne(int[] digits) {
3+
int size = digits.length;
4+
for(int n = size -1; n >= 0; n--){
5+
digits[n]++;
6+
digits[n] = digits[n] % 10;
7+
if (digits[n] != 0 ){
8+
return digits;
9+
}
10+
}
11+
digits = new int[size+1];
12+
digits[0] = 1;
13+
return digits ;
14+
15+
}
16+
}

‎Week01/RemoveDuplicatesFromSortedArray.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
class RemoveDuplicatesFromSortedArray {
2+
3+
public int removeDuplicates(int[] nums) {
4+
5+
if (nums.length == 0) return 0;
6+
int i = 0 ;
7+
for(int j = 1; j< nums.length; j++){
8+
if(nums[j] !=nums[i]){
9+
i++;
10+
nums[i] = nums[j];
11+
}
12+
}
13+
return i + 1;
14+
}
15+
}

‎Week01/RotateArray.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class RotateArray {
2+
public void rotate(int[] nums, int k) {
3+
int n = nums.length;
4+
k = k % n;
5+
reverse(nums, 0, n - 1);
6+
reverse(nums, 0, k - 1);
7+
reverse(nums, k, n - 1);
8+
}
9+
public void reverse(int[] nums, int start, int end) {
10+
while(start <end){
11+
int tmp = nums[start];
12+
nums[start++] = nums[end];
13+
nums[end--] = tmp;
14+
}
15+
}
16+
}

‎Week01/TowSum.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class TwoSum {
2+
public int[] twoSum(int[] nums, int target) {
3+
HashMap<Integer, Integer> cache = new HashMap<>();
4+
int[] res = new int[2];
5+
for(int i = 0; i < nums.length; i++) {
6+
int secondValue = target - nums[i];
7+
Integer secondIndex = cache.get(secondValue);
8+
if (secondIndex != null && secondIndex >= 0 && secondIndex != i ){
9+
if (secondIndex > i ){
10+
res[0] = i;
11+
res[1] = secondIndex;
12+
}else{
13+
res[0] = secondIndex;
14+
res[1] = i;
15+
}
16+
17+
return res;
18+
}
19+
cache.put(nums[i], i);
20+
}
21+
return res;
22+
}
23+
}

‎Week01/TrappingRainWater.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class TrappingRainWater {
2+
public int trap(int[] height) {
3+
int sum = 0;
4+
Stack<Integer> stack = new Stack<>();
5+
int current = 0;
6+
while(current < height.length){
7+
// 大于开始处理
8+
while(!stack.isEmpty() && height[current] > height[stack.peek()] ){
9+
int h = height[stack.peek()];
10+
stack.pop();
11+
if(stack.isEmpty()){
12+
break;
13+
}
14+
int d = current - stack.peek() -1;
15+
16+
int min = Math.min(height[stack.peek()], height[current]);
17+
sum = sum + d *(min - h);
18+
}
19+
stack.push(current);
20+
current ++;
21+
}
22+
return sum;
23+
}
24+
}

0 commit comments

Comments
 (0)