知新_RL

这个屌丝很懒，什么也没留下！

热门标签

力扣刷题指南_力扣算法笔记 pdf

作者：知新_RL | 2024-07-21 10:43:39

踩

力扣算法笔记 pdf

LeetCode算法笔记

LeetCode

LeetCode

参考代码随心录，自用笔记
可以按照本文章的顺序来刷题，可以多刷几遍

数组

27.移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
暴力算法
C
- 分析：外层循环控制数组判断，内层循环用于覆盖数组元素

int removeElement(int* nums, int numsSize, int val) {
	int i, j;
	int len = numsSize;
	for (i = 0; i < len; i++) {
		if (nums[i] == val) {
			j = i+1;
			while (j < len) {
				nums[j-1] = nums[j];//j-1是防止下标越界
				j++;
			}
			len--;
			i--;//len--的情况下i一定要--
		}
	}
	return len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

JAVA

/*
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
public int removeElement(int[] nums, int val) {
	int n = nums.length;
	for(int i=0;i<n;i++){
	    if(nums[i]==val){
	        for(int j=i+1;j<n;j++){
	            nums[j-1] = nums[j]; // 小心越界
	        }
	        i--;// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
	        n--;
	
	    }
	}
	
	return n;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双指针法(快慢指针法):
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
C

int removeElement(int* nums, int numsSize, int val){
    int solw = 0,fast;
    for(fast=0;fast<numsSize;fast++){
        if(val!=nums[fast]){
            nums[solw++] = nums[fast];
        }

    }
    return solw;
}
1
2
3
4
5
6
7
8
9
10

JAVA

// 时间复杂度：O(n)
// 空间复杂度：O(1)
public int removeElement2(int[] nums, int val) {
    int slowIndex = 0;
    for(int fastIndex = 0; fastIndex< nums.length;fastIndex++){
        if(val != nums[fastIndex]){
            nums[slowIndex++] = nums[fastIndex];
        }
    }
    return slowIndex;
}
1
2
3
4
5
6
7
8
9
10
11

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
二分法查找
C

int searchInsert(int* nums, int numsSize, int target){
      int low = 0, high = numsSize-1;
    int mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (target > nums[mid])
            low = mid + 1;
        else if (target < nums[mid])
            high = mid - 1;
        else
            return mid;
    }
    return high+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

JAVA

public int searchInsert(int[] nums, int target) {
	int n = nums.length;
	int left = 0,right = n -1; // 定义target在左闭右闭的区间里，[left, right]
	while(left<=right) { // 当left==right，区间[left, right]依然有效
	    int mid = left + ((right - left) / 2); // 防止溢出，等价(left+right)/2
	    if (target < nums[mid]) {
	        right = mid - 1;// target 在左区间，所以[left, middle - 1]
	    } else if (target > nums[mid]) {
	        left = mid + 1;
	    } else {  // nums[middle] == target
	        return mid;
	    }
	}
	return right+1;
	/*
	分别处理如下四种情况
	1.目标值在数组所有元素之前  [0, -1]
	    target = -1,nums = [1,3,5,7]
	    第一次循环
	    right = 3,left = 0,mid = 1
	    target < nums[1] = 3 --> right = mid -1 = 0
	    第二次循环
	    right = 0,left = 0,mid = 0
	    target < nums[0] = 1 --> right = mid -1 = -1
	    循环结束，返回 right+1 = 0
	2.目标值等于数组中某一个元素  return middle;
	3.目标值在数组中间 [left, right]，return  right + 1
	    target = 4,nums = [1,3,5,7]
	    第一次循环
	    right = 3,left = 0,mid = 1
	    target > nums[1] = 3 --> left = mid + 1 = 1
	    第二次循环
	    right = 3,left = 1,mid = 2
	    target < nums[2] = 5 --> right = mid -1 = 1
	    循环结束，返回 right+1 = 2
	4.目标值在数组所有元素之后的情况 [left, right]， return right + 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
37
38

209.长度最小的子数组

给定一个含有个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组[numsl, numsl+1, …, numsr-1, numsr],并返回其长度。如果不存在符合条件的子数组，返回 0 。
暴力算法
分析：
- 取i到j的区间，然后对该区间求和并判断
- j-i+1是取当前从i到j之间元素个数
- 三元表达式的判断是判断老长度是否比新长度大？，因为求最小长度
C

int minSubArrayLen(int target, int* nums, int numsSize){
    int i, j;
    int sum;
    int subLen;//用来标识新长度
    int result = INT_MAX;//用来标识老长度，这里要取一个最大值
    for (i = 0; i < numsSize; i++) {
        sum = 0;
        for (j = i; j < numsSize; j++) {
            sum += nums[j];
            if (sum >= target) {
                subLen = j - i + 1;//获取该sum包含的子数组长度
                result = result > subLen ? subLen : result;//判断老长度是否大于新长度
                break;
            }
        }
    }
    return result==INT_MAX ? 0:result;//防止全部元素之和都不大于target
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

JAVA

//暴力解法
//时间复杂度：O(n^2)
//空间复杂度：O(1)
public int minSubArrayLen(int target, int[] nums) {
    int result = Integer.MAX_VALUE; // 取一个数组不可能的超过的最大值
    int sum = 0; // 子序列的数值之和
    int subLength = 0; // 子序列的长度
    for(int i=0;i<nums.length;i++){
        sum = 0;
        for(int j=i;j<nums.length;j++){
            sum+=nums[j];
            if(sum>=target){
                subLength = j-i+1; // 取子序列的长度
                result = result<subLength?result:subLength; // 与前一次长度作比较
                break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
            }
        }
    }
    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    return result == Integer.MAX_VALUE ? 0:result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

滑动窗口
- 在本题中实现滑动窗口，主要确定如下三点：
  1.窗口内是什么？
  2.如何移动窗口的起始位置？
  3.如何移动窗口的结束位置
  窗口就是满足和>=target的长度最小的连续子数组；
  窗口的起始位置如何移动：如果当前窗口的值>target，窗口就要向前移动（即缩小窗口）
  窗口的结束位置如何移动：窗口的结束位置即遍历数组的指针，起始位置即数组的起始位置。
JAVA

//滑动窗口
/*
滑动窗口的精妙之处在于根据当前子序列和大小的情况，
不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
 */
public int minSubArrayLen_2(int target, int[] nums) {
    int result = Integer.MAX_VALUE;
    int sum = 0;//滑动窗口数值之和
    int i = 0;//滑动窗口起始位置
    int subLength = 0;//滑动窗口的长度
    for(int j=0;j< nums.length;j++){
        sum+=nums[j];
        //使用while，每次更新i（起始位置），并不断比较子序列是否符合条件
        while(sum>=target){
            subLength = (j - i + 1);//取子序列的长度
            result = result < subLength? result:subLength;
            sum -= nums[i++];//减去第一个数，窗口内数字个数-1，i滑动到i++位置
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;

    /*
    nums[] = 2 , 3 , 1 , 2 , 4 , 3    target = 7
    下标：    0   1   2   3   4   5
    sum = 0;i = 0;subLength = 0;
    1.       ij(指向下标0) --> sum = 0+2 = 2
    2.       i   j          --> sum = 2+3 = 5
    3.       i       j          --> sum = 5+1 = 6
    4.       i           j          --> sum = 6+2 = 8
    while-->subLength = j-i+1 = 3-0+1 = 4
         -->result = Max < 4 ? Max:4 = 4
         -->sum -= nums[i++] = sum - nums[0] = 8-2 = 6
         -->      i(向前移动i,即窗口缩小)
     ...
     ...
     */
}
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

int minSubArrayLen(int target, int* nums, int numsSize){
    int i = 0,j;
    int result = INT_MAX;
    int sublen = 0;
    int sum = 0;
    for(j=0;j<numsSize;j++){
        sum += nums[j];
        while(sum>=target){
            sublen = j-i+1;
            result = result > sublen ? sublen:result;
            sum -= nums[i++];
        }
    }
    return result==INT_MAX?0:result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

59.螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
分析：
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
- 一定要遵循左闭右开，如n=3时，填充上行仅为(0,0)，(0,1)，右列为(0,2)，(1,2)依次类推，如图：

JAVA

public int[][] generateMatrix(int n) {
	int[][] nums = new int[n][n];
	int startX = 0,startY = 0;//定义每循环一个圈的起始位置，如(0,0),(1,1)...
	int loop = n / 2;//每个圈循环几次，如n=3为奇数，则loop=1只循环一圈，
	                //矩阵中间的值需要单独处理
	int mid = n / 2;//矩阵中间的位置，如n=3，中间位置就是(1,1)，n=5-->(2,2)
	int count = 1;//给矩阵赋值的变量
	int offset = 1;//每一圈循环，需要控制每一条边遍历的长度
	int i,j;
	while(loop--!=0){
	    i = startX;
	    j = startY;
	
	    //下面开始的四个for就是模拟转一圈
	    /*
	    →   →   ↓
	    ↑   →   ↓
	    ↑   ←   ←
	     */
	    //上行从左到右
	    for(j = startY;j<startY+n-offset;j++){
	        nums[startX][j] = count++;
	    }
	
	    //右列从上到下
	    for(i = startX;i<startX+n-offset;i++){
	        nums[i][j] = count++;
	    }
	
	    //模拟下行从右到左
	    for(;j>startY;j--){
	        nums[i][j] = count++;
	    }
	
	    //模拟左列从下到上
	    for(;i>startX;i--){
	        nums[i][j] = count++;
	    }
	
	    // 第二圈开始的时候，起始位置要各自加1， 
	    //例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
	    /*
	    如n=4时：
	    第一圈：
	        0   1   2   3
	    0   →   →   →   ↓
	    1   ↑           ↓
	    2   ↑           ↓
	    3   ↑   ←   ←   ←
	    -->则第一圈从(0,0)开始
	    第二圈：
	        1   2
	    1   →   ↓
	    2   ↑   ←
	    -->则第二圈从(1,1)开始
	     */
	    startX++;
	    startY++;
	
	    // offset 控制每一圈里每一条边遍历的长度
	    // 如n=4,第一圈第一行长度=4，第二圈第一行长度为4-2=2
	    /*
	    第一圈：
	    →   →   →   ↓
	    ↑           ↓
	    ↑           ↓
	    ↑   ←   ←   ←
	    第二圈：
	    →   ↓
	    ↑   ←
	     */
	    offset += 2;
	}
	
	// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
	/*
	如n=3,中心点则为(1,1)
	n=5,中心点则为(2,2)
	 */
	if (n % 2==1) {
	    nums[mid][mid] = count;
	}
	
	return nums;
	}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

代码手推图
*

217.存在重复元素

给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
分析：
- 先对数组进行排序
- 然后只需要判断，数组内相邻元素是否重复
C

int cmp(const void* _a, const void* _b) {
	int a = *(int*)_a, b = *(int*)_b;
	return a - b;
}

bool containsDuplicate(int* nums, int numsSize) {
	qsort(nums, numsSize, sizeof(int), cmp);//快速排序
	for (int i = 0; i < numsSize - 1; i++) {
		if (nums[i] == nums[i + 1]) {
			return true;
		}
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

53.最长子序列和？

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
分析：
- 动态规划
C

int maxSubArray(int* nums, int numsSize) {
	int preSum = 0;//之前和
	int maxSum = nums[0];//最大和
	for (int i = 0; i < numsSize; i++) {
		preSum = fmax(preSum + nums[i], nums[i]);//取最大值函数
		maxSum = fmax(preSum, maxSum);
	}
	return maxSum;
} 
1
2
3
4
5
6
7
8
9

链表

142.环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
分析：

判断链表是否有环
- 定义slow，fast指针指向head
- slow指针走一步，fast指针走两步
- 若有环的情况下，fast和slow一定会相遇；若无环，则存在fast->next = null，即跳出循环
如果有环，如何找到这个环的入口
- 设从 头结点–>环形入口结点 的节点数为x
- 环形入口结点–>相遇结点（fast，slow）的节点数为y
- 相遇结点–>环形入口结点 的节点数为z
  - 相遇时：slow指针走过节点数=x+y，fast=x+y+n(y+z)
    n为fast在环内走了n圈才遇到slow，y+z为环内结点个数
  - 又fast = slow*2，即fast走过的个数是slow的两倍
    –> （x+y）*2 = x+y+n(y+z)
    –> （x+y） = n(y+z)
    –> x = n(y+z) - y
    –> x = (n-1) (y+z) + z
- 当n=1，x=z
- 当n>1，则fast指针在环形转n圈之后遇到slow

代码

public ListNode detectCycle(ListNode head) {       
	ListNode fast = head;//定义快慢指针
	ListNode slow = head;
	while( fast!=null && fast.next!=null){
	    slow = slow.next;//慢指针走一步
	    fast = fast.next.next;//快指针走两步量
	    //快慢相遇
	    if(slow == fast){
	        ListNode index1 = fast;
	        ListNode index2 = head;
	        while(index1 != index2){
	            index1 = index1.next;
	            index2 = index2.next;
	        }
	        return index2; //返回入口
	    }
	
	}
	return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码手推图

203.移除链表元素

给你一个链表的头节点 head 和一个整数 val
请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

迭代

  /*
  因为可能会遇到头结点满足条件时，要删除头结点
  如：val = 2
  head(2)-->1-->4-->null
  ==>
  dummyHead-->head(2)-->1-->4-->null
  则只需将虚拟结点dummyHead指向head.next即可
  ==>
  dummyHead   head(2)-->1-->4-->null
          |             ↑
          |_____________|
   */
1
2
3
4
5
6
7
8
9
10
11
12

public ListNode removeElements(ListNode head, int val) {
	ListNode dummyHead = new ListNode();//设置一个虚拟头结点
	dummyHead.next = head;//将虚拟结点指向头结点
	ListNode cur = dummyHead;
	
	while(cur.next!=null){
	    if(cur.next.val==val){
	        cur.next = cur.next.next;
	
	    }else{
	        cur = cur.next;
	    }
	}
	
	//当然，返回的最终链表是从虚拟结点的下一个位置开始
	return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递归

public ListNode removeElements2(ListNode head,int val){
	if(head==null){
	    return head;
	}
	head.next = removeElements(head.next, val);
	return head.val==val?head.next : head;//当条件为真时，返回head.next后的链表
    }
1
2
3
4
5
6
7

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
分析：
1. 定义三个指针：pre，curr，temp，分别指向head的前驱结点（null），头结点，curr的后继结点。
2. 判断当curr非空时进行反转
3. 三个指针同时向后移动即可

 /*
        如：
        null    1----->2----->3----->4
         ↑      ↑      ↑
        pre     curr  temp
        1.          1<-----2      3----->4
                    ↑      ↑      ↑
                   pre     curr  temp
        2.          1<-----2<------3      4
                           ↑       ↑      ↑
                           pre    curr   temp
        3.          1<-----2<------3<------4
                                   ↑       ↑      ↑
                                   pre    curr   temp
         */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码

public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }

        ListNode pre = null;
        ListNode curr = head;//指向头结点
        ListNode temp = null;//保存curr的后一个结点
        while(curr!=null){
            temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

707.设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
1. get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
2. addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
3. addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
4. addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
5. deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
代码

//链表类
public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class MyLinkedList{
/*    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1,2);
        linkedList.get(1);
        linkedList.deleteAtIndex(1);
        linkedList.get(1);
    }
    */
    int size;
    ListNode head;//虚拟头结点
    public int get(int index) {
        if(index>=size||index<0) return -1;//返回无效索引

        ListNode curr = head;
        for(int i=0;i<index+1;++i){//遍历到index所指结点
            curr = curr.next;
        }
        return curr.val;
    }

    public void addAtHead(int val) {
        ListNode curr = new ListNode(val);
        curr.next = head.next;
        head.next = curr;
        size++;//长度自增
    }

    public void addAtTail(int val) {
        ListNode curr = head.next;
        ListNode addNode = new ListNode(val);
        while(curr.next!=null){//遍历到链表尾部
            curr = curr.next;
        }

        curr.next = addNode;
        size++;//长度自增
    }

    public void addAtIndex(int index, int val) {

        if(index>size)
            return ;
        if(index<0)
            index = 0;

        ListNode curr = head;
        for(int i=0;i<index;i++){//遍历到index下标之前一个结点
            curr = curr.next;
        }

        ListNode addNode = new ListNode(val);
        addNode.next = curr.next;
        curr.next = addNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if(index>=size||index<0){//索引无效
            return ;
        }

        ListNode curr = head;
        while(index--!=0){//遍历到待删除结点的前一个结点
            curr = curr.next;
        }
        curr.next = curr.next.next;
        size--;//长度自减
    }
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

19.删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
分析：
- 使用fast和slow指针，fast先走n步，然后两个指针再同时遍历
- 当fast指向null时，则slow所指元素为待删除结点
- 若使用虚拟头节点，则当fast指向null时，slow->next为待删除结点，这样便与直接删除
- JAVA

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;//设置虚拟头节点
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        int temp = n;
        while(temp-- > 0){//fast先走n步
            fast = fast.next;
        }
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

面试题 02.07.链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
分析：
- 先遍历长度较长的链表，与较短链表末尾对齐
- 如：
  a1->a2->a3->c1->c2->c3
  b1->b2->c1->c2->c3
- 然后两个链表同时往后遍历，若节点相等(非值相等)，则返回；否则为null
JAVA

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	 ListNode curA = headA;
	 ListNode curB = headB;
	 int lenA = 0,lenB = 0;
	 while(curA!=null){//求链表A的长度
	     lenA++;
	     curA = curA.next;
	 }
	 while(curB!=null){//求链表B的长度
	     lenB++;
	     curB = curB.next;
	 }
	 curA = headA;//让指针重新指向头节点
	 curB = headB;
	 int gap = lenA-lenB;//长度差值
	 if(lenB>lenA){//若链表b长度较大
	     curB = headA;
	     curA = headB;
	     gap = lenB - lenA;
	 }
	
	 while(gap-->0){//让curA(长度较大)遍历到，与curB(长度较小)同一起点上（末尾位置对齐）
	     curA = curA.next;
	 }
	
	 while(curA!=null){
	     if(curA==curB){//节点相同
	         return curA;
	     }
	     curA = curA.next;
	     curB = curB.next;
	 }
	 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
32
33
34

哈希表

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
分析：
1. 使用map结合存储，key为值，value为下标
2. 判断：若map中存在target-num[i]的值(即另一个数的差值)，则返回map.get(target-nums[i])和i的下标；反之则存入map中。这样可以保证元素不重复。

 /*
 如：
 nums = [1,2,3,4]    target = 5
 1.  nums[i] = nums[0] = 1   target-nums[0] = 5-1 = 4(无)     
	 map.put(nums[0],0)--> map = {{1,0}}
 2.  nums[i] = nums[1] = 2   target-nums[1] = 5-2 = 3(无)     
 	 map.put(nums[1],1)--> map = {{1,0},{2,1}}
 3.  nums[i] = nums[2] = 3   target-nums[2] = 5-3 = 2(有)
     return new int[]{map.get(2),2}  = {1,2}
  */
1
2
3
4
5
6
7
8
9
10

public int[] twoSum(int nums[],int target){
	 //map的key是值，value是下标
	 Map<Integer,Integer> map = 
	 		new HashMap<Integer,Integer>();
	 for(int i=0;i<nums.length;i++){
	     if(map.containsKey(target-nums[i])){
	     	 //返回一个下标数组
	         return new int[]{map.get(target-nums[i]),i};
	     }
	     map.put(nums[i],i);//将符合条件的数插入表中
	 }
	 return new int[0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
分析
1. 先对数组进行排序，以方便去重复
2. 使用双指针left和right，left指向左端（i+1），right指向右端（length-1）
3. 存在三个指针i、left、right，其中后两个指针向对方靠拢，则可进行判断三个指针所指数的和

public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> ls = new ArrayList<List<Integer>>();
	//数组排序
	Arrays.sort(nums);
	for(int i=0;i<nums.length;i++){
	    if(nums[i]>0){
	        return ls;
	    }
	
	    //去重方法
	    if(i>0&&nums[i]==nums[i-1]){
	        continue;
	    }
	
	    int left = i+1;//左指针
	    int right = nums.length -1;//右指针
	    while(left<right){
	        if(nums[i]+nums[left]+nums[right]>0){//当数值大于零，则表示数较大
	            right--;
	        }else if(nums[i]+nums[left]+nums[right]<0){//同理，数值较小
	            left++;
	        }else{
	            List<Integer> result = new ArrayList<Integer>();
	            result.add(nums[i]);
	            result.add(nums[left]);
	            result.add(nums[right]);
	            ls.add(result);//添加一个三元组
	            while(left<right&&nums[right]==nums[right-1])
	                right--;
	            while(left<right&&nums[left]==nums[left+1])
	                left++;
	            //双指针同时靠拢
	            right--;
	            left++;
	
	        }
	    }
	
	}
	return ls;
    }
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

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

分析：
- 将每一次计算的平方和存入HashSet中
- 判断：如果存在重复的sum，则返回false;反之，返回true

public boolean isHappy(int n) {
	Set<Integer> set = new HashSet<Integer>();
	while(true){
	    int sum = getSum(n);//每一次都会更新sum值
	    if(sum==1){
	        return true;
	    }
	
	    if(set.contains(sum)){//当集合中存在重复的sum时，此数不是快乐数
	        return false;
	    }else {
	        set.add(sum);
	    }
	    n = sum;
	}
	}

	//取数值各个位上的单数之和
	int getSum(int n){
	    int sum = 0;
	    while(n>0){
	        sum += (n%10) * (n%10);//求平方和
	        n /= 10;
	    }
	    return sum;
	}
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

242.有效字母的异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
分析：
- 异位词：字母相同，排列顺序不同，异位词的长度也一定相等
- 定义record数组，记录串s字符出现的次数，数组大小为26
- 遍历串s，记录字母出现的次数(+1)，arr_s[i] - ‘a’ 是映射出字母的位置
  - 如 ‘b’ - ‘a’ = 1，即b的下标为1，同理a的下标为0
- 同理，遍历串t，记录字符出现的次数(-1)
- 判断，record数组元素全为0，则为异位词；反之不是
代码

public boolean isAnagram(String s, String t) {
	if(s.length()!=t.length()){//比较长度
	    return false;
	}
	int[] record = new int[26];//定义数组，记录串s中字符的次数
	char[] arr_s = s.toCharArray();
	for(int i=0;i<arr_s.length;i++){
	    record[arr_s[i] - 'a']++;//映射出字符出现的次数
	    /*
	    如：
	    arr[0] = 'b';
	    -->
	    record[arr[i] - 'a'] = record['b' - 'a'] = record[1];
	    record[1]++  =  1;  、
	    即出现b在串s中出现一次，b的下标为1，
	    同理，a的下标为0
	     */
	}
	char[] arr_t = t.toCharArray();
	for(int i=0;i<arr_t.length;i++){
	    record[arr_t[i] - 'a']--;//映射出串t中出现的字符，随之映射在record表中，并-1
	}
	for(int i=0;i<26;i++){
	    if(record[i] != 0){
	        //判断数组中若存在不为零的次数，则不是异位词
	        return false;
	    }
	}
	//record中所有元素都为零，则两遍映射相抵消，即为异位词
	return true;
	}
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

304.两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

public int[] intersection(int[] nums1, int[] nums2) {
	Set<Integer> set1 = new HashSet<Integer>();
	Set<Integer> set2 = new HashSet<Integer>();
	//将数组分别装入集合中
	for(int num:nums1){
	    set1.add(num);
	}
	for(int num:nums2){
	    set2.add(num);
	}
	return getIntersection(set1,set2);
}
public int[] getIntersection(Set<Integer> set1,Set<Integer> set2){
	if(set1.size()>set2.size()){//遍历集合长度小的那一个
	    return getIntersection(set2,set1);
	}
	Set<Integer> intersectionSet = new HashSet<Integer>();
	for(int num:set1){//判断是否有相同数字
	    if(set2.contains(num)){
	        intersectionSet.add(num);
	    }
	}
	
	//将集合存入数组并返回
	int[] intersection = new int[intersectionSet.size()];
	int index = 0;
	for(int num:intersectionSet){
	    intersection[index++] = num;
	}
	return intersection;
}
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

383.赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
分析：
1. 建立两个长度为26的数组，将r和m字符串中字母的出现次数映射到数组中
2. 判断：如果r[i]>m[i]，则说明r不能由m表出

public boolean canConstruct(String ransomNote, String magazine) {
	int[] ransomNote_record = new int[26];//默认值为0
	int[] magazine_record = new int[26];
	
	for(int i=0;i<ransomNote.length();i++){//映射字母表
	    ransomNote_record[ransomNote.charAt(i)-'a']++;
	}
	for(int j=0;j<magazine.length();j++){
	    magazine_record[magazine.charAt(j)-'a']++;
	}
	for(int i=0;i<ransomNote_record.length;i++){//比较存入的字母次数
	    //如果r中字母的次数大于m对应的字母次数，则r不能由m表出
	    if(ransomNote_record[i]>magazine_record[i]){
	            return false;
	    }
	}
	return true;
	
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

454.四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
分析：
1. 用map，先遍历数组A、B，key为A+B的和，value记录其和出现的次数
2. 再遍历C、D，当原map存在0-[c+d]（c、d为C、D中的元素）的元素时，记录次数即可
3. 时间与空间都为o(n^2)

 /*
 如：
 nums1=[1,2]  nums2=[2,1]    nums3=[-1,1]     nums4=[-2,1]
 map --> {{3,2},{2,1},{4,1}} -->即3出现两次，2出现一次，4出现一次
 1.  0-(-1+-2) = 3 -->true
     temp += 2 = 2
 2.  0-(-1+1)  = 0 -->false
 3.  0-(1-2)   = 1 -->true
     temp += 1 = 3
     ......

  */
1
2
3
4
5
6
7
8
9
10
11
12

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
	 //定义map，key存放a+b和，value存放a+b出现的次数
	 Map<Integer,Integer> map =
	         new HashMap<Integer,Integer>();
	 //遍历前两个数组
	 for(int a:nums1){
	     for(int b:nums2){
	         //判断a+b是否出现过：若出现过则+1；反之，从0开始计数
	         int count = 
	         		map.containsKey(a+b) ? map.get(a+b):0;
	         map.put(a+b,count+1);
	     }
	 }
	 int temp = 0;//记录a+b+c+d=0的次数
	 //遍历后两个数组
	 for(int c:nums3){
	     for(int d:nums4){
	         if(map.containsKey(0-(c+d))){
	             temp += map.get(0-(c+d));//当找到a+b+c+d=0，则记录相应次数
	         }
	     }
	 }
	 return temp;

    }
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

219.存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
分析：
- 使用滑动窗口，窗口大小不大于k
- 依次遍历数组，当窗口长度 >k 时，删除第 i-k 个元素，该元素为当前滑动窗口第一个元素
JAVA

public boolean containsNearbyDuplicate(int[] nums, int k) {
	Set<Integer> set = new HashSet<Integer>();
	for(int i=0;i<nums.length;i++){
	    if(set.contains(nums[i])){//存在重复元素
	        return true;
	    }
	    set.add(nums[i]);//添加元素
	    if(set.size()>k){//滑动窗口个数>k
	         set.remove(nums[i-k]);//删除元素，i-k为当前第一个元素
	    }
	}
	return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

字符串

151.翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有单词。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。
法一：利用现有方法

public String reverseWords(String s) {
	 //去除开头和末尾的空白字符
	 s = s.trim();
	 //正则匹配连续的空白字符作为分隔符切割
	 List<String> wordList = Arrays.asList(s.split("\\s+"));
	 Collections.reverse(wordList);
	 //按照指定分隔符重组字符串
	 return String.join(" ",wordList);
    }
1
2
3
4
5
6
7
8
9

法二：利用自定义方法

//利用自定义方法
public String reverseWords_2(String s) {
    StringBuilder sb = trimSpaces(s);

    // 翻转字符串
    reverse(sb, 0, sb.length() - 1);

    // 翻转每个单词
    reverseEachWord(sb);

    return sb.toString();
}

//去除空格
public StringBuilder trimSpaces(String s){
    int left = 0,right = s.length()-1;
    // 去除首部空格
    while(left <= right && s.charAt(left)==' '){
        ++left;//左指针往右边靠拢
    }

    //去掉尾部空格
    while(left<=right && s.charAt(right)==' '){
        --right;//右指针往左边靠拢
    }

    //去除多余的空白字符
    StringBuilder sb = new StringBuilder();
    while(left <= right){
        char c = s.charAt(left);
        if(c != ' '){
            sb.append(c);
        }else if(sb.charAt(sb.length()-1)!=' '){
            sb.append(c);
        }
        ++left;
    }
    return sb;
}

//反转
public void reverse(StringBuilder sb,int left,int right){
	while(left < right){
	    char temp = sb.charAt(left);
	    sb.setCharAt(left++,sb.charAt(right));//首尾互换
	    sb.setCharAt(right--,temp);
	}
}

//反转每个字母
public void reverseEachWord(StringBuilder sb){
	int n = sb.length();
	int start = 0,end = 0;
	
	while (start < n) {
	    // 循环至单词的末尾
	    while (end < n && sb.charAt(end) != ' ') {
	        ++end;
	    }
	    // 翻转单词
	    reverse(sb, start, end - 1);
	    // 更新start，去找下一个单词
	    start = end + 1;
	    ++end;
	}
}
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
56
57
58
59
60
61
62
63
64
65
66

344.字符串反转

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

public void reverseString(char[] s) {
    for(int i=0,j=s.length-1;i<j;i++,j--){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    System.out.println(s);
}
1
2
3
4
5
6
7
8

541.字符串反转II

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
- 如果剩余字符少于 k 个，则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”
分析：
- i作i+=(2*k)的增长速度来遍历
- 判断两种情况即可

public String reverseStr(String s, int k) {
  for(int i=0;i<s.length();i+=(2*k)){
      //1.每隔2k个字符，对前k个字符进行反转
      //2.剩余字符<2k但>=k，则反转前k个字符
      if(i+k<=s.length()){
          s = reverse(s,i,i+k-1);
          continue;
      }
      //3.剩余字符<k，则将剩余字符全部进行反转
      s = reverse(s,i,s.length()-1);

  }
  return s;

}
//反转下标为a到b的字符
public String reverse(String s,int start,int end){
  char[] ch = s.toCharArray();
  for(int i = start,j = end;i<j;i++,j--){
      char temp = ch[i];
      ch[i] = ch[j];
      ch[j] = temp;
  }


  return new String(ch);
}
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

05.替换空格（剑指offer）

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
分析：
- 建立一个字符数组，其长度为串s的三倍，以确保能装入替换后的字符串
- size用来计算替换后的字符串真正的长度
- i=0开始遍历字符串：当判断到有空格时，依次存入**%20**；反之，正常赋值。

public String replaceSpace(String s) {
	//建立字符数组，确保能装入替换后的容量
	char[] ch = new char[s.length()*3];
	int size = 0;//计算替换后的字符串长度
	for(int i=0;i<s.length();i++){
	    char c = s.charAt(i);
	    if(c == ' '){//当判断为空格时，依次存入
	        ch[size++] = '%';
	        ch[size++] = '2';
	        ch[size++] = '0';
	    }else{//反之，正常赋值
	        ch[size++] = c;
	    }
	}
	//重新初始化新的字符串，该字符串长度为替换后的长度
	String result = new String(ch,0,size);
	return result;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

58.II 左旋转字符串(剑指offer)

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。
比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

public String reverseLeftWords(String s, int n) {

	int len = s.length();
	char[] arr = new char[s.length()];
	//赋值下标为k之前的字符
	for(int i=s.length()-n;i<len;i++){
	    arr[i] = s.charAt(i-len+n);
	}
	//赋值下标为k以及k后面的字符
	for(int i=n;i<len;i++){
	    arr[i-n] = s.charAt(i);
	}
	
	String result = new String(arr,0,len);
	return result;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

28.实现 strStr()

实现 strStr() 函数。给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
JAVA

public int strStr(String haystack, String needle) {
	if(needle==null){
	    return -1;
	}
	int i=0,j = 0,k=0;
	while(i<haystack.length() && j<needle.length()){
	    if(haystack.charAt(i) == needle.charAt(j)){
	        i++;
	        j++;
	    }else{
	        j=0;
	        i = ++k;
	    }
	}
	if(j>=needle.length()){
	    return k;
	}else{
	    return -1;
	}
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

栈与队列

232.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
分析：
- 用两个栈来实现队列：一个输入栈和一个输出栈
- 先将元素导入输入栈，如:1 2 3导入后为 (栈顶)←3 2 1←(栈底)
- 再将元素导入输出栈，如:←3 2 1←导入后为 (栈顶)←1 2 3←(栈底)
- 从输出栈Pop则有：1 2 3，从而实现先进先出

public class MyQueue {

    Stack<Integer> stIn;//用于输入元素的栈
    Stack<Integer> stOut;//用于输出元素的栈

    //初始化
    public MyQueue() {
        stIn = new Stack<Integer>();
        stOut = new Stack<Integer>();
    }

    //模拟入队
    public void push(int x) {
        stIn.push(x);//进栈
    }

    //模拟出队
    public int pop() {
        // 当stOut输出栈为空时，才让stIn中的元素输入
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.pop());
            }
        }
        return stOut.pop();//返回栈顶元素，并删除
    }

    //返回队列头元素
    public int peek() {
        //与模拟出队同理
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.pop());
            }
        }
        return stOut.peek();//返回栈顶元素，但不删除
    }

    //判断队列是否为空
    public boolean empty() {
        //当两个栈都为空时，则队列为空
        return stIn.empty() && stOut.empty();
    }
}
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

225.用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
分析：
- 使用一个队列，先正常入队
- 再将队列，从队头元素开始，循环插入队尾
- 则可以将队列倒置，形成先进后出的规则

//252.用队列实现栈
public class MyStack {
	Deque<Integer> dq;
	
	/** Initialize your data structure here. */
	public MyStack() {
	    dq = new LinkedList<Integer>();
	}
	
	/** Push element x onto stack. */
	public void push(int x) {
	    int size = dq.size();
	    dq.offer(x);//插入队尾
	    for(int i=0;i<size;i++){
	        dq.offer(dq.poll());//poll返回最先进入的那个元素，即对头元素
	        //将这个元素插入队尾
	        //此方法就是将原始队列倒置，已构成先进后出的原则
	    }
	}
	
	/** Removes the element on top of the stack and returns that element. */
	public int pop() {
	    return dq.poll();//返回队头元素
	
	}
	
	/** Get the top element. */
	public int top() {
	    return dq.peek();//返回第一个元素，即当前队头元素
	}
	
	/** Returns whether the stack is empty. */
	public boolean empty() {
	    return dq.isEmpty();
	}
}
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

20.有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
分析：
- 三种不匹配的情况
  1. 左方向的括号多余
    ( [ { } ] ( )
  2. 括号没有多余，但括号类型没有匹配上
    ( [ { } } )
  3. 右方向的括号多余
    ( [ { } ] ) ) )
- 三种判断方式
  1. 第一种情况：已遍历完，但栈不空，则说明存在多余右括号
  2. 第二种情况，当匹配右括号时，栈中没有发现匹配的字符
  3. 第三种情况，栈已空，但串s未遍历完，则说明存在多余的左括号
Java

public boolean isValid(String s) {
	Stack<Character> st = new Stack<Character>();
	for(int i=0;i<s.length();i++){
	    //这里入栈右括号是方便直接匹配串s中是否有相同的括号
	    if(s.charAt(i)=='(') st.push(')');
	    else if(s.charAt(i)=='{') st.push('}');
	    else if(s.charAt(i)=='[') st.push(']');
	    //第三种情况，栈已空，但串s未遍历完，则说明存在多余的左括号
	    //第二种情况，当匹配右括号时，栈中没有发现匹配的字符
	    else if(st.empty() || st.peek()!=s.charAt(i)) {
	        return false;
	    }
	    /*
	    隐含的判断成功：
	    s.charAt(i)=='(' 或 
	    s.charAt(i)=='{' 或 
	    s.charAt(i)=='['
	    */
	    else st.pop();

}
	//第一种情况：已遍历完，但栈不空，则说明存在多余右括号
	return st.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
分析：
- 定义一个栈，当判断栈顶元素与该遍历到的元素相同时，出栈
- 最后再反转即可

public String removeDuplicates(String s){
	Stack<Character> st = new Stack<Character>();
		for(int i=0;i<s.length();i++){
		    if(!st.isEmpty()){
		        //判断是否有相邻元素
		        if(st.peek()==s.charAt(i)){
		            st.pop();
		            continue;
		        }
		    }
		
		    st.push(s.charAt(i));//入栈
		
		}
		//栈无元素则返回空
		if(st.isEmpty()){
		    return "";
		}
		char[] ch = new char[st.size()];
		//反转
		for(int i=ch.length-1;i>=0;i--){//注意：不能用栈的长度，因为每次出栈后会变化
		    ch[i] = st.pop();
		}
		//重造字符串
		String result = new String(ch, 0, ch.length);
		
		return result;
}
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

150.逆波兰表达式求值

根据逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
分析：
1. 逆波兰式就是后缀，将后缀转为中缀
2. 依次对数字入栈：
  1. 当出现算术符号，出栈两个数
  2. 交换两数顺序(保证正确的顺序)
  3. 将两数与该符号作运算，结果入栈

public int evalRPN(String[] tokens) {
	Deque<Integer> dq = new LinkedList<Integer>();
	for(int i=0;i<tokens.length;i++){
	    //判断是否为算术符
	    if(tokens[i].equals("+")||tokens[i].equals("-")
	    ||tokens[i].equals("*")||tokens[i].equals("/")){
	        int a = dq.pop();
	        int b = dq.pop();
	        switch (tokens[i]){
	            case "+":
	                dq.push(b+a);
	                break;
	            case "-":
	                dq.push(b-a);
	                break;
	            case "*":
	                dq.push(b*a);
	                break;
	            case "/":
	                dq.push(b/a);
	                break;
	            default:
	        }
	    }else{
	        dq.push(Integer.parseInt(tokens[i]));//字符串转化为数字
	    }
	}
	return dq.peek();
}
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

二叉树

递归详解

递归三要素
1. 确定递归函数的参数和返回值：即确定递归中的参数，明确每次递归的返回值。
2. 确定终止条件：即保证不会栈溢出。
3. 确定单层递归的逻辑：确定每一层递归需要处理的信息。

144.二叉树的前序遍历

分析：
- 前序遍历又称先根，即按照根、左、右的顺序来遍历二叉树
C(递归)

void preorder(TreeNode *root,int *res,int *resSize) {
	if (root != NULL) {
		//用数组存放值
		res[(*resSize)++] = root->val;//数组自增
		preorder(root->left, res, resSize);
		preorder(root->right, res, resSize);
	}
	
	
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
	int *res = malloc(sizeof(int) * 2000);
	*returnSize = 0;
	preorder(root, res, returnSize);
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C(非递归)

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
	int *result = (int*)malloc(sizeof(int) * 2000);//生成一个结果数组
	*returnSize = 0;
	if (root == NULL) {
		return result;
	}
	struct TreeNode *st[2000];//定义一个栈
	struct TreeNode *p = root;//定义一个指针
	int top = -1;//初始化栈
	st[++top] = root;//入栈根节点
	while (top != -1) {
		p = st[top--];//指针指向当前需遍历的结点(根左右)
		result[(*returnSize)++] = p->val;//入结果数组
		if (p->right != NULL) {//右孩子存在
			st[++top] = p->right;
		}
		if (p->left != NULL) {//左孩子存在
			st[++top] = p->left;
		}
	}
	return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

94.二叉树的中序遍历

C(递归)

void inorder(struct TreeNode* root, int *res, int *resSize) {
	if (root == NULL) {
		return;
	}
	inorder(root->left, res, resSize);
	res[(*resSize)++] = root->val;
	inorder(root->right, res, resSize);
}
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
	int *res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	inorder(root, res, returnSize);
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

C(非递归)

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
	int *result = (int*)malloc(sizeof(int) * 2000);//生成一个结果数组
	*returnSize = 0;
	if (root == NULL) {
		return result;
	}
	struct TreeNode *st[2000];//定义一个栈
	struct TreeNode *p;//定义一个指针
	int top = -1;//初始化栈的指针
	p = root;//p指向根节点
	while (top != -1 || p != NULL) {//有可能出现栈空但树未遍历完的情况
		while (p != NULL) {//左孩子一直入栈
			st[++top] = p;
			p = p->left;
		}
		if (top != -1) {//栈不空时，输出
			p = st[top--];
			result[(*returnSize)++] = p->val;
			p = p->right;
		}
	}
	return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

145.二叉树的后序遍历

void postorder(TreeNode *root, int *res, int *resSize) {
	if (root == NULL) {
		return;
	}
	postorder(root->left, res, resSize);
	postorder(root->right, res, resSize);
	res[(*resSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
	int *res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	postorder(root, res, returnSize);
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

C(迭代)

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
	int *result = (int*)malloc(sizeof(int) * 2000);//结果数组
	*returnSize = 0;
	if (root = NULL) {
		return result;
	}
	struct TreeNode *stack1[2000]; int top1 =  1;
	struct TreeNode *stack2[2000]; int top2 = -1;
	struct TreeNode *p = NULL;
	stack1[++top1] = root;//根节点入栈
	while (top1 != -1) {
		p = stack1[top1--];//指向
		stack2[++top2] = p;//再入
		if (p->left != NULL) {//反向入栈
			stack1[++top1] = p->right;
		}
			
		if (p->right != NULL) {
			stack1[++top1] = p->left;
		}
		
	}
	while (top2 != -1) {
		//再次出栈即为后序遍历
		p = stack2[top2--];
		result[(*returnSize)++] = p->val;
	}
	return result;

}
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

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
法一：
- 定义一个结点，作为中间变量
- 依次递归交换左右子树，当为空时结束
JAVA

public TreeNode invertTree(TreeNode root) {
	 if(root == null){
	     return null;
	 }
	 TreeNode temp = root.left;
	 root.left = root.right;
	 root.right = temp;
	 invertTree(root.left);
	 invertTree(root.right);
	 return root;
    }
1
2
3
4
5
6
7
8
9
10
11

法二
- 定义两个结点left和right
- 递归遍历，让left指向树的右子树，让right指向树的左子树
- 再让原根结点指向left和right即可
JAVA

public TreeNode invertTree(TreeNode root) {
	if(root == null){
	     return null;
	 }
	 TreeNode left = invertTree(root.right);
	 TreeNode right = invertTree(root.left);
	 root.left = left;
	 root.right = right;
	 return root;
    }
1
2
3
4
5
6
7
8
9
10

101.对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。
分析：
- 其实就是对左子树的左节点，右子树的右节点；左子树的右节点，右子树的左节点进行比较
- 采用后序遍历方式，但为左右中，右左中的遍历
Java

public boolean isSymmetric(TreeNode root) {
    if(root == null) return true;
    return compare(root.left,root.right);
}
public boolean compare(TreeNode left,TreeNode right){
    //判断四种情况
    if(left == null && right != null) return false;
    else if(left != null && right == null) return false;
    else if(left == null && right == null) return true;
    //若左右都不为空时，判断值是否相等
    else if(left.val != right.val) return false;
	//当左右子树值相等时，继续递归遍历
    boolean outside = compare(left.left,right.right);//左子树的外层，右子树的外层
    boolean inside = compare(left.right,right.left);//左子树的内层，右子树的内层
    boolean isSame = outside && inside;
    return isSame;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool isSymmetric(struct TreeNode* root){
    bool compare();
    if (root == NULL) {
		return true;
	}
	return compare(root->left, root->right);
}

bool compare(struct TreeNode* left,struct TreeNode *right) {
	if (left == NULL && right != NULL) return false;
	else if (left != NULL && right == NULL) return false;
	else if (left == NULL && right == NULL) return true;
	else if (left->val != right->val) return false;

	bool outSide = compare(left->left, right->right);
	bool inSide = compare(left->right, right->left);
	bool isSame = outSide && inSide;
	return isSame;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

104.二叉树最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
分析：
- 定义一个全局变量result，用来存储节点数
- 采用前序遍历，即根左右，和递归的方式
  - 递归函数的参数：传入的节点，当前的深度
  - 终止条件：当正在遍历的节点左右子树为空时，返回
  - 单层递归逻辑：先求左子树深度，再求右子树深度，result保存当前的最大节点值，然后进行比较
JAVA

int result;
    public int maxDepth(TreeNode root){
        result = 0;
        if(root == null) return result;//注意细节，返回的是result
        getDepth(root,1);
        return result;
    }

    public void getDepth(TreeNode root,int depth){
        //采用前序遍历
        result = depth > result ? depth : result;//中

        if(root.left==null && root.right==null) return;//为空
        if(root.left!=null){//左
            depth++;
            getDepth(root.left,depth);
            depth--;//因为已经走到下一层了，depth进行了+1，即回溯，所以深度-1，
        }
        if(root.right!=null){//右
            depth++;
            getDepth(root.right,depth);
            depth--;//
        }
        return ;
    }
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

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
分析：
JAVA

public int minDepth(TreeNode root) {
	if(root == null) return 0;
	int leftDepth = minDepth(root.left);//取左
	int rightDepth = minDepth(root.right);//取右
	
	//求的是根节点到叶子节点的节点距离，所以：
	//左子树为空，右不为空，这时并不是最低点
	if(root.left == null && root.right!=null){
	    return 1+rightDepth;
	}
	
	//当一个右子树为空，左不为空，这时并不是最低点
	if(root.left!=null && root.right==null){
	    return 1+leftDepth;
	}
	return  1+Math.min(leftDepth,rightDepth);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/860542