leetcode - 探索初级算法

初级算法

数组

买卖股票的最佳时机 II

贪心算法,只考虑当前最有解

1
2
3
4
5
6
7
8
9
10
11
12
13
//c
int maxProfit(int* prices, int pricesSize){
if(pricesSize <=1 )
return 0;
int curr = 1;
int profits = 0;
while(curr < pricesSize ){
if(prices[curr] > prices[curr-1])
profits += prices[curr] - prices[curr-1];
curr++;
}
return profits;
}

从排序数组中删除重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//c
int removeDuplicates(int* nums, int numsSize){
if(numsSize <= 1)
return numsSize;
int temp = 0;
int pre = 0,curr = 1;
while(curr < numsSize){
temp = nums[pre];
if(temp != nums[curr]){
nums[++pre] = nums[curr++];
}else{
curr++;
}

}
return pre+1;
}

旋转数组

方法一:粗暴,超时了。

1
2
3
4
5
6
7
8
9
10
11
12
//c
void rotate(int* nums, int numsSize, int k){
int temp = 0;
for(int j = 0;j < k;j++){
for(int i = 1 ;i < numsSize ;i++){
temp = nums[i];
nums[i] = nums[0];
nums[0] = temp;
}
}

}

方法二:
先把数组的元素全部反转,然后反转前k个元素,最后再将后numsSize-k元素反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//c
void rotate(int* nums, int numsSize, int k){
k = k%numsSize;
reverse(nums,0,numsSize-1);
reverse(nums,0,k-1);
reverse(nums,k,numsSize-1);
}

void reverse(int *nums,int start,int end){
int temp;
while(start < end){
temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}

存在重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//c
int comp( const void * p, const void * q)
{
return ( * ( int * ) p - * ( int * ) q);
}
bool containsDuplicate(int* nums, int numsSize){
if(numsSize <=1 )
return false;
qsort(nums,numsSize,sizeof(int),comp);
int pre = nums[0];
for(int i = 1;i < numsSize;i++){
if(pre == nums[i])
return true;
pre = nums[i];
}
return false;
}

只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//c
int comp( const void * p, const void * q)
{
return ( * ( int * ) p - * ( int * ) q);
}
int singleNumber(int* nums, int numsSize){
if(numsSize <=1)
return nums[0];
qsort(nums, numsSize, sizeof(int),comp);
int i;
for(i = 0;i < numsSize - 1; i+=2){
if(nums[i] != nums[i+1])
return nums[i];
}
return nums[i];
}

两个数组的交集ii

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
32
33
//c
int comp( const void * p, const void * q)
{
if( * ( int * ) p > * ( int * ) q)
return 1;
else if( * ( int * ) p < * ( int * ) q)
return -1;
else
return 0;
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){

qsort(nums1,nums1Size,sizeof(int),comp);
qsort(nums2,nums2Size,sizeof(int),comp);

int k = 0;
for(int i = 0,j = 0;i < nums1Size && j < nums2Size;){
if(nums1[i] < nums2[j])
i++;
else if(nums1[i] > nums2[j])
j++;
else{
nums1[k++] = nums1[i];
i++;
j++;
}
}
*returnSize = k;
int *returnNums = (int*)malloc(sizeof(int)*k);
if(!returnNums) {
printf("fail to malloc !");
return NULL;
}

加一

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
//c
int* plusOne(int* digits, int digitsSize, int* returnSize){
int carry = 1;
for(int i = digitsSize-1; i >= 0;i--){
if(carry == 1){
digits[i] = digits[i]+1;
if(digits[i] > 9){
carry = 1;
digits[i] = digits[i]%10;
}else{
carry = 0;
}
}

}
if(carry){
*returnSize = digitsSize + 1;
}else{
*returnSize = digitsSize;
}
int *temp = (int*)malloc(sizeof(int)*(digitsSize + 1));
for(int i = 0,j = 0;j < *returnSize;j++){

if(carry){
temp[j] = 1;
carry = 0;
}else
temp[j] = digits[i++];
}
return temp;
}

移动零

就是将所有的非零元素往前移,最后不足的用0填充。利用快慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
//c
void moveZeroes(int* nums, int numsSize){
int pre,curr;
for(pre = 0,curr = 0;curr < numsSize;curr++){
if(nums[curr] != 0){
nums[pre++] = nums[curr];
}
}
if(pre < numsSize){
for(int i = pre;i < numsSize;i++)
nums[i] = 0;
}
}

两数之和

利用hash表实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//java
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for(int i = 0; i < nums.length;i++){
hashMap.put(nums[i],i);
}
for(int i = 0; i < nums.length;i++){
if(hashMap.containsKey(target-nums[i]) && hashMap.get(target-nums[i]) != i)
return new int[] {i,hashMap.get(target-nums[i])};
}
throw new IllegalArgumentException("No two sum solution");
}
}

有效的数独

思路是用三个hash数组来分贝存储给出数独中遇到的每行、每列、每个子box的数字。

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
32
33
34
//java
class Solution {
public boolean isValidSudoku(char[][] board) {
HashMap<Integer,Integer>[] rowMap = new HashMap[9];
HashMap<Integer,Integer>[] colMap = new HashMap[9];
HashMap<Integer,Integer>[] boxMap = new HashMap[9];

//initial hashmap array
for(int i = 0; i < 9;i++){
rowMap[i] = new HashMap<>();
colMap[i] = new HashMap<>();
boxMap[i] = new HashMap<>();
}
for(int i = 0; i < 9;i++)
for(int j = 0;j < 9;j++){
if(board[i][j] != '.'){
int num = Character.getNumericValue(board[i][j]);
int boxIndex = (i/3)*3 + j/3;

rowMap[i].put(num, rowMap[i].getOrDefault(num,0)+1);
colMap[j].put(num, colMap[j].getOrDefault(num,0)+1);
boxMap[boxIndex].put(num, boxMap[boxIndex].getOrDefault(num,0)+1);


if(rowMap[i].get(num) > 1 || colMap[j].get(num) > 1
|| boxMap[boxIndex].get(num) > 1)
{
return false;
}

}
}
return true;
}

旋转图像

顺时针旋转90度:先将矩阵副对角线两边的数字交换,然后将第i行和第n-i-1行交换。
逆时针旋转90度:先将矩阵主对角线两边的数字交换,然后将第i行和第n-i-1行交换。
举例比如要求顺指针旋转180度,就可以进行两个顺时针旋转90度的操作来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//java
class Solution {
public void rotate(int[][] matrix) {
int column = matrix[0].length;
for(int i = 0; i < column ; i++)
for(int j = 0;j < column - i ; j++){
int temp = matrix[column-1-j][column-1-i];
matrix[column-1-j][column-1-i] = matrix[i][j];
matrix[i][j] = temp;
}

for(int i = 0; i < column / 2;i++)
for(int j = 0;j < column ;j++){
int temp = matrix[column-1-i][j];
matrix[column-1-i][j] = matrix[i][j];
matrix[i][j] = temp;
}
}
}

字符串

反转字符串

1
2
3
4
5
6
7
8
9
10
11
//java
class Solution {
public void reverseString(char[] s) {
int len = s.length;
for(int i = 0; i < len/ 2;i++){
char temp = s[i];
s[i] = s[len-1-i];
s[len-1-i] = temp;
}
}
}

整数反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//java
class Solution {
public int reverse(int x) {

int result = 0;
while(x != 0){
int mod = x%10;
if(result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && mod > 7))
return 0;
if(result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && mod < -8))
return 0;
result = result*10 + mod;
x = x / 10;
}

return result;
}
}

字符串中的第一个唯一字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//java
class Solution {
public int firstUniqChar(String s) {
HashMap<String,Integer> hashMap = new HashMap<>();

for(int i = 0; i < s.length();i++){
String cc = s.substring(i, i+1);
hashMap.put(cc,hashMap.getOrDefault(cc,0)+1);
}

for(int i = 0;i < s.length();i++ ){
String cc = s.substring(i, i+1);
if(hashMap.get(cc) == 1)
return i;
}
return -1;
}
}

有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//java
class Solution {
public boolean isAnagram(String s, String t) {
HashMap<String,Integer> hashMap_s = new HashMap<>();
HashMap<String,Integer> hashMap_t = new HashMap<>();
for(int i = 0; i < s.length();i++){
String cc = s.substring(i, i+1);
hashMap_s.put(cc,hashMap_s.getOrDefault(cc,0)+1);
}

for(int i = 0; i < t.length();i++){
String cc = t.substring(i, i+1);
hashMap_t.put(cc,hashMap_t.getOrDefault(cc,0)+1);
}

if(hashMap_t.equals(hashMap_s))
return true;
else
return false;
}
}

验证回文字符串

先把原字符串中的字符和数字组成新的字符串。然后首尾对比。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//java
class Solution {
public boolean isPalindrome(String s) {
int len = s.length();
char chr[] = s.toCharArray();
int i = 0;
String temp = "";
while(i < len){
if(Character.isLetterOrDigit(chr[i])){
temp += Character.toString(chr[i]);
}
i++;
}
i = 0;
while(i < temp.length() / 2){
if(Character.toLowerCase(temp.charAt(i)) != Character.toLowerCase(temp.charAt(temp.length()-1-i)))
return false;
else{
i++;
}
}
return true;
}
}

字符串转换整数 atoi

题目信息
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0。
说明:
假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
ps: 正、负号后面要紧挨着数字。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//java
class Solution {
public int myAtoi(String str) {
int len = str.length();
if(len < 1)
return 0;
boolean firstUnEmpty = true;
int res = 0;
int sign = 1 ;// negative is -1,positive is 1;
for(int i = 0; i < len ;i++){
char cc = str.charAt(i);
if(Character.isWhitespace(cc))
continue;
if(firstUnEmpty &&!Character.isDigit(cc) && cc != '-' && cc != '+' &&
!Character.isWhitespace(cc))
return 0;
firstUnEmpty = false;
if(cc == '-'){
if((i+1) < len && !Character.isDigit(str.charAt(i+1)))
return 0;
sign = -1;
continue;
}
if(cc == '+'){
if((i+1) < len && !Character.isDigit(str.charAt(i+1)))
return 0;
sign = 1;
continue;
}
//Character.getNumericValue
if(Character.isDigit(cc) ){
while(i < len && Character.isDigit(str.charAt(i))){
char c = str.charAt(i);
int num = Character.getNumericValue(c);
if(sign == 1)
if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > 7))
return Integer.MAX_VALUE;
if(sign == -1)
if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > 8))
return Integer.MIN_VALUE;
res = res*10+num;
i++;
}
break;
}
}
if(res != 0){
if(sign == 1)
return res;
else
return -res;
}
return res;
}
}

链表

删除链表中的节点

直接将需要删除节点后面节点的值填入需要删除的节点,然后删除后面的节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;

}
}

删除链表的倒数第N个节点

使用快慢指针:slow、fast。先将fast走n步,slow不动。然后slow、fast依次往前移,直到fast走到链表尾,此时,slow指针指向倒数第N+1个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//java
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null)
return head;
ListNode slow , fast;
slow = fast = head;
for(int i = 0;i < n ;i++){
fast = fast.next;
}
if(fast == null)
return slow.next;
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//java
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode curr = head;
ListNode behind;
while(curr != null){
behind = curr.next;
curr.next = pre;
pre = curr;
curr = behind;
}
return pre;
}
}

合并两个有序链表

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null)
return l2;
else if(l2 == null)
return l1;
ListNode curr = l1;
ListNode prev = null;
while(curr != null && l2 != null){
if(curr.val == l2.val){
ListNode nextTemp = l2.next;
l2.next = curr.next;
curr.next = l2;
prev = curr;
curr = curr.next;
l2 = nextTemp;
}else if(curr.val > l2.val){
ListNode nextTemp = l2.next;
if(prev != null)
prev.next = l2;
l2.next = curr;
if(prev == null){
l1 = l2;
}
prev = l2;
//curr = curr.next;
l2 = nextTemp;
}else if(curr.val < l2.val){
prev = curr;
curr = curr.next;
}
}
if(l2 != null){
prev.next = l2;
}
return l1;
}
}

回文链表

先找到链表中间位置,然后反转后半部分链表。然后对比前半部分和后半部分。

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
32
33
34
35
36
37
38
39
40
41
42
43
//java
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode behind,prev,secondHalfStart;
ListNode mid;
ListNode curr = head;
ListNode slow,fast;

slow = fast = head;
if(head == null || head.next == null)
return true;
//find mid
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
mid = slow;
if(mid.next != null)
secondHalfStart = mid.next;
else
secondHalfStart = mid;

//reverse
prev = null;
curr = secondHalfStart;
while(curr != null){
ListNode nextTmp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTmp;
}
secondHalfStart = prev;
while(secondHalfStart != null){
if(head.val != secondHalfStart.val)
return false;
else{
head = head.next;
secondHalfStart = secondHalfStart.next;
}
}
return true;
}
}

环形链表

利用快慢指针,如果存在环,那么慢指针一定回追上快指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//java
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null)
return false;
ListNode slow,fast;
slow = head;
fast = head.next;
while(fast != slow && fast != null && fast.next != null&& fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
if(slow == fast)
return true;
else
return false;
}
}

排序和搜索

合并两个有序数组

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
//java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len_1 = nums1.length;
int k = m+n-1;
int i = m-1,j = n-1;
while(i >=0 && j >= 0 ){
if(nums2[j] > nums1[i]){
nums1[k--] = nums2[j--];
}else if(nums2[j] == nums1[i]){
nums1[k--] = nums2[j--];
nums1[k--] = nums1[i--];
}else{
nums1[k--] = nums1[i--];
}

}

if(j >= 0){
while(j >= 0){
System.out.print("test");
nums1[k--] = nums2[j--];
}
}
}
}

第一个错误版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//java
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */

public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int i = 1;
int left = 1,right = n ;
while(left < right ){
int mid = (right - left) / 2 + left;
if(isBadVersion(mid)){
right = mid;
}else
left = mid + 1;
}

return left;
}
}

每日打卡

day1 用队列实现栈

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
32
33
34
35
36
37
38
39
40
41
//java
class MyStack {
int head;
int tail;
List<Integer> list ;
/** Initialize your data structure here. */
public MyStack() {
list = new ArrayList<>();
head = tail = 0;
}

/** Push element x onto stack. */
public void push(int x) {
list.add(x);
tail++;
}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
if(tail > head)
return list.remove(--tail);
else
return -1;
}

/** Get the top element. */
public int top() {
if(tail > head)
return list.get(tail-1);
else
return -1;
}

/** Returns whether the stack is empty. */
public boolean empty() {
if(head == tail)
return true;
else
return false;
}
}

day2 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode curr = head;
ListNode behind;
while(curr != null){
behind = curr.next;
curr.next = pre;
pre = curr;
curr = behind;
}
return pre;

}
}

day3 合并排序的数列

1
2
3
4
5
6
7
8
9
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
for(int i = m;i < m+n;i++){
A[i] = B[i-m];
}

Arrays.sort(A);
}
}

day4 腐烂的橘子

采用广度优先搜索

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//java
class Solution {
public int orangesRotting(int[][] grid) {
int col = grid[0].length;
int row = grid.length;
//利用queue保存腐烂的橘子,并且要保存腐烂的分钟数
Queue<Integer> queue = new LinkedList<Integer>();
Map<Integer, Integer> minutes = new HashMap();
for(int i = 0; i < row ;i ++){
for(int j = 0 ; j < col ;j++){
if(grid[i][j] == 2){
int num = i*col + j;
queue.add(num);
minutes.put(num,0);
}
}
}
int row_d[] = new int[]{0,0,-1,1};
int col_d[] = new int[]{-1,1,0,0};
int min = 0;
while(!queue.isEmpty()){
int num = queue.remove();
int col_t = num % col;
int row_t = num / col;
for(int k = 0; k < 4;k++){
int n_col = col_d[k] + col_t;
int n_row = row_d[k] + row_t;
if(0 <= n_col && n_col < col && 0 <= n_row && n_row < row && grid[n_row][n_col] == 1){

grid[n_row][n_col] = 2;
int n_num = n_row * col + n_col;
queue.add(n_num);
minutes.put(n_num, minutes.get(num) + 1);
min = minutes.get(n_num);
}
}
}

for(int i = 0; i < row;i++){
for(int j = 0;j < col;j++){
if(grid[i][j] == 1)
return -1;
}
}
return min;
}
}

day5 和为s的连续正数序列

利用数学逻辑,等差数列求和。

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
//java
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> results = new ArrayList<>();
int x,mod;
int len = 2;
while(true){
x = (target - (len-1) * len / 2) / len;
mod = (target - (len-1) * len / 2) % len;
if(x <= 0){
break;
}
if(mod == 0){
int temp[] = new int[len];
for(int i = 0 ; i < len;i++){
temp[i] = x++;
}
results.add(temp);
}
len++;
}
//sort
Collections.sort(results, new Comparator<int[]>() {
public int compare(int[] arg0, int[] arg1) {
return arg0[0] - arg1[0];
}
});
return results.toArray(new int[0][]);
}
}

day6 队列的最大值

题目要求max_value、push_back、pop_front、操作的时间复杂度都要为O(1)。就需要用空间换取时间。
解法:利用双向队列来辅助实现。

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
32
33
34
35
36
//java
class MaxQueue {
private Deque<Integer> queue;
private Deque<Integer> MaxQueue;
public MaxQueue() {
queue = new ArrayDeque<>();
MaxQueue = new ArrayDeque<>();
}

public int max_value() {
if(MaxQueue.isEmpty())
return -1;
else
return MaxQueue.peek();
}
//将MaxQueue队列末尾比value小的元素弹出,因为在这些比value小的元素被弹出之前,value一定还存在队列中,最大值一定大于等于value,所以没有必要保存当前队列末尾比value小的元素。
public void push_back(int value) {
queue.offer(value);
while(!MaxQueue.isEmpty() && value > MaxQueue.peekLast()){
MaxQueue.pollLast();
}
MaxQueue.offer(value);
}

public int pop_front() {
if(queue.isEmpty()){
return -1;
}

int temp = queue.pop();
if(temp == MaxQueue.peek()){
MaxQueue.poll();
}
return temp;
}
}

day7 零钱兑换

用的是动态规划,自底向上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//java
class Solution {
public int coinChange(int[] coins, int amount) {
if(coins.length == 0)
return -1;
//dp[i]代表金额为i时所需的最小硬币数
int dp[] = new int[amount+1];

Arrays.fill(dp,amount + 1);
dp[0] = 0;
for(int i = 1; i <= amount ; i++){
for(int j = 0;j < coins.length ; j++){
if(i-coins[j] >= 0){
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}


return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}

day8 买卖股票的最佳时机

方法一:暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//java
class Solution {
public int maxProfit(int[] prices) {
List<int[]> list = new ArrayList<>();
for(int i = 0; i < prices.length ; i++){
list.add(new int[]{prices[i],i});
}

int profits = 0;
for (int[] key : list) {
int temp = 0;
int buy_index = key[1];
for(int j = 0; j < prices.length ; j++){
if(buy_index < j){
temp = Math.max(prices[j]-key[0], temp);
}
}
profits = Math.max(temp , profits);
}

return profits;
}

方法二: 用一个变量记录当前的最低价格,然后依次计算出第i天卖出的最大利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//java
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;

for(int i = 0; i < prices.length ; i++){
if(prices[i] < minPrice)
minPrice = prices[i];
else if(prices[i] - minPrice > maxProfit){
maxProfit = prices[i] - minPrice;
}
}

return maxProfit;
}
}

day9 二叉树的直径

求二叉树的直径也就是求二叉树的从任意节点出发的最大路径长度。任意一条路径可以看作以当前节点为根结点,其左子树和右子树的路径拼接。

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
//java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int dia ;
public int diameterOfBinaryTree(TreeNode root) {
dia = 1;
depth(root);
return dia - 1;
}

public int depth(TreeNode root){
if(root == null)
return 0;
int depthL = depth(root.left);
int depthR = depth(root.right);

dia = Math.max(dia , depthL + depthR + 1);
return Math.max(depthR ,depthL) + 1;
}
}

day 10 字符串的最大公因子

辗转相除法求最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public String gcdOfStrings(String str1, String str2) {
if(!(str1 + str2).equals(str2 + str1))
return "";
return str1.substring(0,gcd(str1.length(),str2.length()));
}

public int gcd(int m,int n){
if(n == 0)
return m;
return m % n == 0 ? n : gcd(n, m % n);
}
}

day11 将数组分成和相等的三个部分

如果能分成三等份,那么每部分之和一定等于总和的三分之一。首先遍历一遍数组求总和,然后从头再遍历一遍数组,计算找到和为总和三分之一的段数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//java
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int sum = 0;
for (int i = 0 ;i < A.length ; i++){
sum += A[i];
}
if( sum != (sum / 3) * 3 )
return false;
int tmp = 0;
int count = 0;
for(int j = 0; j < A.length; j++){
tmp += A[j];
if(tmp == sum / 3){
count++;
tmp = 0;
}
}
if(count >= 3)
return true;
return false;
}
}

day12 多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//java
class Solution {
public int majorityElement(int[] nums) {
int num = nums[0];
Map<Integer, Integer> map = new HashMap();

for (int i = 0;i < nums.length ; i++){
int count = map.getOrDefault(nums[i],0)+1;
map.put(nums[i], count);
if( count > Math.floor( nums.length / 2)){
num = nums[i];
break;
}

}

return num;
}
}

day13 最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0)
return 0;
int dp[] = new int[nums.length];
dp[0] = 1;
int maxLen = 1;
for(int i = 1; i < nums.length ; i++){
int tmp = 0;
for(int j = 0; j < i;j++){
if(nums[i] > nums[j]){
tmp = Math.max(tmp,dp[j]);
}
}
dp[i] = tmp + 1;
maxLen = Math.max(maxLen, dp[i]);
}

return maxLen;
}
}

day14 岛屿的最大面积

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
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int result = 0;
for(int i = 0; i < grid.length;i++){
for(int j = 0; j < grid[0].length;j++){
result = Math.max(result, dfs(i , j ,grid));
}
}

return result;
}
public int dfs(int row,int col,int[][] grid){
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length
|| grid[row][col] == 0)
return 0;
grid[row][col] = 0;
int count = 1;
count += dfs(row - 1,col,grid);
count += dfs(row + 1,col,grid);
count += dfs(row,col - 1,grid);
count += dfs(row,col + 1,grid);

return count;
}
}

day15 字符串压缩

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
class Solution {
public String compressString(String S) {
if(S.length() <= 1)
return S;
int len = 1;
String str = new String();
char last = S.charAt(0);
for(int i = 1;i < S.length();i++){
if(S.charAt(i) == last)
len++;
else{
str += Character.toString(last);
str += String.valueOf(len);
len = 1;
last = S.charAt(i);
}
}
str += Character.toString(last);
str += String.valueOf(len);
if(str.length() < S.length())
return str;
return S;

}
}

day16 拼写单词

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
32
33
34
35
36
class Solution {
public int countCharacters(String[] words, String chars) {
Map<String, Integer> charMap = new HashMap();
int length = 0;
for(int i = 0; i < chars.length();i++){
String cc = chars.substring(i,i+1);
charMap.put(cc , charMap.getOrDefault(cc ,0)+1);
}
for(int i = 0; i < words.length; i++){
Map<String, Integer> tmp = new HashMap();
for(int j = 0; j < words[i].length();j++){
String str = words[i].substring(j,j+1);
System.out.print(str + "\n");
tmp.put(str ,tmp.getOrDefault(str,0)+1);
}

int flag = 0;
for (Map.Entry<String, Integer> entry : tmp.entrySet()){
if(!charMap.containsKey(entry.getKey())){
flag = 1;
break;
}

if(entry.getValue() > charMap.get(entry.getKey())){
flag = 1;
break;
}
}
if(flag == 0)
length += words[i].length();
}
return length;


}
}

day17 举证重叠

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
if(rec1[2] <= rec2[0] ||
rec2[2] <= rec1[0] ||
rec1[3] <= rec2[1] ||
rec2[3] <= rec1[1])
return false;
return true;
}
}

day18 最长回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int longestPalindrome(String s) {
//所以就是每个字母出现次数为偶数,奇数次的字母有且只能有一个。
HashMap<String,Integer> hashMap = new HashMap<>();
int odd = 0;
int len = 0;
for(int i = 0 ; i < s.length();i++){
String str = s.substring(i,i+1);
hashMap.put(str, hashMap.getOrDefault(str,0)+1);
}
for (Integer value : hashMap.values()){
len += value / 2 * 2;
if(value % 2 != 0){
odd = 1;
}
}

if(odd != 0)
return len+1;
return len;

}
}

三维形体的表面积

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
class Solution {
public int surfaceArea(int[][] grid) {
int sur = 0;
int len = grid.length;
for(int i = 0; i < len ;i++)
for(int j = 0; j < len; j++){
//left
if(j-1 >= 0)
sur += Math.max(grid[i][j] - grid[i][j-1] ,0 );
else
sur += grid[i][j];
//right
if(j+1 < len)
sur += Math.max(grid[i][j] - grid[i][j+1] ,0 );
else
sur += grid[i][j];
if(i-1 >= 0)
sur += Math.max(grid[i][j] - grid[i-1][j] ,0 );
else
sur += grid[i][j];
if(i+1 < len)
sur += Math.max(grid[i][j] - grid[i+1][j] ,0 );
else
sur += grid[i][j];

sur += 2*(grid[i][j] > 0 ? 1 : 0);
}
return sur;
}
}