复杂度

时间复杂度

  • 估算程序指令的执行次数/执行时间

空间复杂度

  • 估算程序指令所需占用的存储空间

大O表示法

有了时间复杂度,空间复杂度,那么究竟该用什么来表示其大小呢?我们因此衍生了一种表示方式——大O表示法

什么是大O表示法呢?表示的是数据规模n对应的复杂度

  • 公式:T(n) = O( f(n) )
    • n为数据规模,即是函数中变量n
    • f(n)为代码总执行次数与数据规模关系
    • T(n)为代码执行时间

判断方式:

  • 由于在一个程序中可能由多个函数组成,其大O是多个复杂度累计的,那么我们只需要关心最复杂的那个即可,因此我们需要去:忽略常数,系数,低阶

    1
    常量阶O(1)) < 对数阶O(logn) <  线性阶O(n) < 线性对数阶O(nlogn) < 平方阶O(n²)...立方阶O(n³)...k方阶 < 指数阶O(2^n) < 阶乘阶O(n!) <n的n次方阶级O(n^n)

线性结构

  • 线性表是具有N个相同类型元素的有限序列(N>=0)

(数组,链表,栈,队列,哈希表/散列表)

数组(Array)

数组概念

  • 数组是一种顺序存储的线性表,所有元素的内存地址是连续image-20200910210432530

ArrayList动态数组

  • ArrayList函数接口image-20200910211154393

ArrayList源码分析

属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素数组
transient Object[] elementData;
// 实际元素大小,默认为0
private int size;
// 最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
构造方法
无参构造方法
1
2
3
4
//此时我们创建的ArrayList对象中的elementData长度是1,size为0,只有当第一次进行add时候,elementData变成默认长度10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
有参构造方法
  • 传参构造
1
2
3
4
5
6
7
8
9
10
11
    //参数大于等于0,就用那个参数,否则抛出异常
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList(Collection<? extends E> c) {
//将collection对象转换成数组,然后将数组的地址的赋给elementData。
Object[] a = c.toArray();
//大于 0 则用Arrays.copy方法,把collection对象内容拷贝到elemD
//ps:这里是深拷贝,意思是只复制了内容而不是地址,意思是原来的东西变化并不会影响到我复制后的
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
//假如size = 0 直接把空对象地址给elemD
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
方法
add方法
  • 带参数的add方法
  • 不带参数的add方法

LeetCode-数组相关

  • 首先我们要明白用数组解题,或者题目中牵扯到数组的优势与劣势与特点
  • 优势:我们是知道数组的首末索引的,可以方便我们查找遍历
  • 劣势:由于数组每个位置上都有东西,我们有时候插入删除有点麻烦

LeetCode 88.合并两个有序数组image-20200907141226830

采用了双指针的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m-1;
int p2 = n-1;
int p3 = m+n-1;
while(p1 >= 0 || p2 >= 0){
if(p1 < 0){
nums1[p3--] = nums2[p2--];
}else if(p2 < 0){
nums1[p3--] = nums1[p1--];
}else if(nums1[p1] >= nums2[p2]){
nums1[p3--] = nums1[p1--];
}else{
nums1[p3--] = nums2[p2--];
}
}
}
}

p1,p2各自指向数组中最后一个数据;p3指向合并后最后一个位置;

当p1,p2遍历完各自的数组时,结束循环。

当如果p1(下标)<0,意味着第一个数组遍历完了,那么就p3指向的位置存放p2的数据,反之则存放p1的数据。

如果p1指向数据大于p2指向数据,那么p3指向位置存放p1的数据,反之则存放p2的数据。

LeetCode 75.颜色分类image-20200908134006968

采用三指针解法,一个用于记录索引,一个头指针,一个尾指针
如果是0,则给left,如果是1则不变,如果是2则给right
遍历的结果保证了:left左边全是0(不包括left),right右边全是2(不包括right);

当i > right了,则断,否则要把刚交换得到的1,2交换回去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public void sortColors(int[] nums) {
int i = 0;
int left = 0;
int right = nums.length - 1;
while(i <= right){
if(nums[i] == 0){
int tmp = nums[i];
nums[i++] = nums[left];
nums[left++] = tmp;
}else if(nums[i] == 1){
i++;
}else{
int tmp = nums[i];
//换过来的right代表的数可能是0,因此i是不能++的
nums[i] = nums[right];
nums[right--] = tmp;
}
}
}
}

LeetCode 977.有序数组的平方

image-20200909171343270

本来简单点,可以直接把他们全部平方了,然后用sort直接排序,但是那样就没意思了。

同样使用三指针,一个记录索引,一个左指针,一个右指针。

由于是从小到大排序,因此索引要在最右边向左走。

终止条件:当left与right交错时;

假如左指针的数值+右指针数值>0,那么代表右指针数组更大,此时这个位置应该填右指针数值的平方,反之填左指针数值的平方;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] sortedSquares(int[] A) {
int[] ans = new int[A.length];
int i = A.length - 1;
int left = 0;
int right = A.length - 1;
while(left <= right){
if(A[left] + A[right] > 0){
ans[i--] = A[right]*A[right];
right--;
}else{
ans[i--] = A[left]*A[left];
left++;
}
}
return ans;
}
}

LeeCode 面试题16.16. 部分排序

image-20200910151328344

首先我们看看问题 要求 n - m 尽量最小,意思是要找到符合要求的左端点中最大的,和符合要求的右端点中最小的。那么又有个问题,什么叫符合要求呢?

首先,对于一个数,假如其左边数都比他小,右边数都比他小,就不包含在需要排序的部分内。

那么符合要求即,对于左端点m来说,其右边存在一个小于他的数;反之,对于右端点n来说,其左边存在一个大于他的数

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
class Solution {
public int[] subSort(int[] array) {
if(array.length == 0) return new int[]{-1 , -1};
int right = -1;
int left = -1;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
//正向遍历一遍
for(int i = 0 ; i < array.length ; i++){
if(array[i] >= max){
max = array[i];
}else{
right = i;
}
}
//反向遍历一遍
for(int i = array.length -1 ; i >= 0 ; i --){
if(array[i] <= min){
min = array[i];
}else{
left = i;
}
}
return new int[]{left , right};
}
}

链表(List)

链表概念

  • 由于动态数组有个明显缺点:可能会造成内存的大量浪费。那么有没有一种方法能做到——我们用多少空间就申请多少内存呢?当然有,就是用链表了!
  • 链表是一种链式存储的线性表,其元素的内存地址不一定是连续的。

LeetCode-链表相关

  • 首先明白链表解题的特点/优势/劣势
  • 优势:链表的连接方式是通过next指针,因此我们只需要修改指向即可轻松的插入与删除
  • 劣势:链表不存在索引这一说,因此我们要查找某个特定元素,只能通过遍历,不能直接找到
  • 特点:我们常常会使用多指针进行操作

203.移除链表元素

image-20200913211912842

采用新建一个链表的解法,可以有效解决假如头节点就是要删除的元素带来的麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode newhead = new ListNode();
newhead.next = head;
ListNode tmp = newhead;
while(tmp.next != null){
if(tmp.next.val == val){
tmp.next = tmp.next.next;
}else{
tmp = tmp.next;
}
}
return newhead.next;
}
}

86.分割链表

image-20200913212252808

这题比较简单,用两条链表分别保存小于x的和大于等于x部分。然后最后把两条链表一拼就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode partition(ListNode head, int x) {
//保存小于x的链表
ListNode fronthead = new ListNode();
ListNode p1 = fronthead;
//保存大于等于x的链表
ListNode backhead = new ListNode();
ListNode p2 = backhead;
while(head != null){
if(head.val < x){
p1.next = new ListNode(head.val);
p1 = p1.next;
}else{
p2.next = new ListNode(head.val);
p2 = p2.next;
}
head = head.next;
}
p1.next = backhead.next;
return fronthead.next;
}
}

160.相交链表

image-20200914214153713

这道题其实有点脑筋急转弯的味道。

我们想想 假如各有一个指针分别在A链表和B链表同时出发,假如他们最后能在某一点相交,那么意味着什么,是不是代表着他们行走的总路程是一样的?(因为每次只走一格,相当于速度相同,而时间又相同,那么速度X时间就是路程了)

假如没有相交呢?那么代表着各个指针走了一遍A又走了一遍B,最后走到了null,代表没有交点咯。

好了 代码如下

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2){
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
}

剑指Offer 24.反转链表

所谓的单链表反转,就是把每个节点的指针域由原来的指向下一个节点变为指向其前一个节点。

但是单链表并没有一个指向前一个节点的指针域,因此准备一个指针pre用于存储每个节点前一个节点

还需要一个指针next保存当前下一个节点。

在遍历过程中:先保存要修改的节点的下一个节点(很关键 顺序不能错咯)然后修改当前节点的下一个指向,然后把pre指针和head指针都向后移动即可。最后返回的是pre 这也不能搞错。

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

234.回文链表

image-20200915193926482

这道题的解法综合性很强(在我看来)

整体思路:用快慢指针方法找到中间结点,然后将后半部分链表翻转过来,然后将所得的链表与原链表前半部分进行比较

其中快慢指针就不讲了,翻转链表怎么翻转呢?详情请看 剑指Offer 24.反转链表

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
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode pre = null;
ListNode next = null;
ListNode fast = head;
ListNode slow = head;
//偶数的话就是前者情况 奇数就是后者情况
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
//反转后半部分链表
while(slow != null){
next = slow.next;
slow.next = pre;
pre = slow;
slow = next;
}
while(head != null && pre != null){
if(head.val != pre.val){
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
}

2.两数相加

image-20200917221620390

这题我的思路是先不管那个进位的事情,先单纯把对应的数加起来放在一个链表上(在这里我假设放在L1上),然后再另外写一个函数去处理那个数

这题其实有个好的地方,就是各链表上的数是逆序存储的,相当于加法的时候帮我们自动对齐了。太好了。

那么这道题我们要考虑的其实就四种情况:

  1. L1长度 >= L2长度
  2. L1长度 < L2长度
  3. 末位不需要进位(这里的末位其实是头 自己知道就好)
  4. 末位需要进位(这里的末位其实是头 自己知道就好)

其中第一种情况其实是最好解决的,就一个末位假如大于10进位就好了。

第二种的方法我们可以把提前结束的地方直接接l2上,也可以解决

第三种末位不需要进位就不说了

第四种需要进位,就在新建一个头,放进位的1就ok

假如你问我 为什么进位肯定是1啊?你想想..最大就是9+9=18 肯定是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
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1;
ListNode p2 = l2;

while(p1 != null){
if(p2 != null){
p1.val += p2.val;
p2 = p2.next;
}
//l2长度大于l1 那么直接把p2接p1后面 而且因为没了 直接break
if(p1.next == null && p2 != null){
p1.next = p2;
break;
}
p1 = p1.next;
}
func(l1);
return l1;
}
public void func(ListNode head){
while(head != null){
if(head.val >= 10){
head.val = head.val%10;
if(head.next == null){
//假如是末位 大于10 那么就需要新建一个头 放1用
head.next = new ListNode(0);
}
head.next.val += 1;
}
head = head.next;
}
}
}

栈(Stack)

栈概念

栈源码分析

LeetCode-栈相关

面试题 03.02. 栈的最小值

image-20200924161616748

这题可以用双栈的方法去解,分为主栈和副栈;

  • 主栈:和正常的栈一样进行push&pop

  • 副栈:对我们push和pop的值进行特判,假如符合才进行相应操作,副栈维护着一个特殊的序列;

那么对于本题,我们的副栈有着什么特殊的地方呢?

  1. 我们所要push的值必须要小于/等于此时的栈顶元素
  2. 我们所要pop的值必须是辅助栈的栈顶元素我们才让辅助栈也pop,只有这样我们才能保证pop掉留下的元素是其次第二小,第三小…的元素
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 MinStack {
private Stack<Integer> MainStack;
private Stack<Integer> Helper;

/** initialize your data structure here. */
public MinStack() {
MainStack = new Stack<Integer>();
Helper = new Stack<Integer>();
}

public void push(int x) {
MainStack.push(x);
if(!Helper.isEmpty()){
if(Helper.peek()>=x){
Helper.push(x);
}
}else{
Helper.push(x);
}
}

public void pop() {
int temp = MainStack.pop();
if(temp == Helper.peek()){
Helper.pop();
}
}

public int top() {
return MainStack.peek();
}

public int getMin() {
return Helper.peek();
}
}

739.每日温度

image-20200924190753703

引入概念 单调栈

  • 单调递增栈:栈中数据出栈的序列为单调递增序列
  • 单调递减栈:栈中数据出栈的序列为单调递减序列

ps:这里不需要保证在栈中的元素要保持单调递增/递减的顺序

那么这题怎么用单调栈的方法来解呢?准确的说用单调递增栈的方法来解呢?

这题的意思就是找到每个位置离他最近的那个比他大的数,那么我们遇到比自己小的就存栈里,碰到一个大的就把自己栈顶的数据弹出来与当前的下标进行减法运算,即为差值,也就是我们需要等待的日子。

不要忘了,当前遍历到的这个数也有可能比之前没弹出来的数要大,所以要while()挨个看看,而不是if();

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[] dailyTemperatures(int[] T) {
//特判
if(T.length == 0 || T.length == 1 || T == null){
return new int[]{};
}
//构造栈
Stack<Integer> helper = new Stack<>();
//答案数组
int[] ans = new int[T.length];
//遍历
for(int i = 0 ; i < T.length ; i++){
//记得这里是while不是if,因为遇到了一个大的有可能比之前的没弹出来的也要大,要都判断一次;
while(! helper.isEmpty() && T[helper.peek()] < T[i]){
int day = helper.pop();
ans[day] = i - day;
}
//入栈
helper.push(i);
}
return ans;
}
}

剑指Offer09.用两个栈实现队列

image-20200925211651494

这题其实比较简单,一个栈正常存,另一个用来维护成队列的特性即可;

在push数据的时候S1正常存,然后假如要删了把第一个栈存储数据逆序存在S2中,然后再popS2的数据出去即可;

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
class CQueue {
Stack<Integer> s1;
Stack<Integer> s2;
//初始化栈,一个用于正常存,一个是辅助栈;
public CQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}

public void appendTail(int value) {
//正常存
s1.push(value);
}

public int deleteHead() {
//假如s2有数据
if(!s2.isEmpty()){
return s2.pop();
}
//假如s2没数据,s1有数据,就把s1数据存进来
if(s2.isEmpty() && !s1.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
//假如s2没数据,s1没数据,返回-1
if(s1.isEmpty() && s2.isEmpty()){
return -1;
}
return s2.pop();

}
}

队列

队列概念

LeetCode-队列相关

239.滑动窗口最大值

image-20200924171609555

这道题分析一下,我们的窗口随着移动,前面先进来的数要先被窗口卡在外面,那么符合先进先出,是队列;

我们要考虑一个区间内的最大值,又有一点栈的味道,那到底这题要用哪种呢,能不能都用呢?

由此,我们可不可以有一种数据结构是包含了队列的(FIFO)和栈的(FILO)的特点的呢?

双向队列

image-20200924172108383

我们遍历数组,把数组放在队列中,而且我们的头要保证是每一趟中最大的,把头的值给到我们的结果数组,遍历完成后,我们的结果数组也形成了。

那么解决这道题,我们首先要形成题目中的”窗口”:用L和R分别表示左右边框。

  • R=i,就是遍历的下标
  • L=i-k+1,也就是右边框减去窗口的宽再加1

我们遍历途中,遇到了一个数,假如我们之前的数值都是小于该数的,那么全部弹出,并且保存该数,判断该数有没有被窗口卡住,假如此时已经形成窗口了,就把该数赋给我们的结果数组。

我们这有个问题:为什么我们的双向队列不直接存数呢?直接把那个数给数组不是更简单,为什么要多此一举,存下标,然后再把该下标放进数组里,把值传过去呢?

好问题,因为我们要判断我们的队首元素有没有被窗口卡在外面,而去判断有没有卡在外面依据,就是我们的下标与下标进行比较,只要符合了,就把该下标所在的值赋予结果数组即可;而反过来,我们存放数据的话,就要用map映射去找下标,然后比较,不是更麻烦吗?

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
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || nums == null) {
return new int[]{};
}
//结果数组
int[] result = new int[nums.length - k + 1];
//建立一个双向队列存储窗口的下标,而不是值;
Deque<Integer> queue = new LinkedList<>();
//用i代表当前滑窗的最后一个元素
for (int i= 0 ; i < nums.length ; i++) {
//为了保证从小到大,把之前小于现在遍历到的值的数全部弹出
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
queue.pollLast();
}
//添加当前值对应的数组下标
queue.addLast(i);
//判断该值所在的下标是否被窗口卡在外面
if(queue.peekFirst() <= i - k){
queue.pollFirst();
}
//假如此时的窗口长度刚好成型或已经成型的时候,保存当前窗口最大值
if (i - k + 1 >= 0){
result[i - k + 1] = nums[queue.peek()];
}
}
return result;
}
}

300.最长上升子序列

看到这种最长上升,我下意识想到了单调栈的解法,但后来写了发现有些地方的pop很繁琐,那么我就想到了另一种方法,单调队列

我们用一个数组去维护成一个单调队列,保证其是单调递增的,在遍历数组的时候,如果遇到比尾部的数字还大的,那么就肯定比队列前面已经存在的数字都要大,那么就直接插入在尾部;如果碰到了比尾部小的,我们找到前面第一个比他大的位子,替换掉;

这里有个巧妙地方法就是引入了二分法去找该插入的位子,关于二分的话在算法篇我们再详细讲讲左右区间选择问题和最后到底用左端点还是右端点,这里学问还是有很多的。

代码:

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
class Solution {
public int lengthOfLIS(int[] nums) {
//特判
if(nums.length == 0 || nums == null) return 0;
//不停更新这个数组 维护一个伪队列 保持其单调递增
int[] a = new int[nums.length];
//len+1就是最长的序列了
int len = 0;
//存放第一个数 用于后续比较
a[len] = nums[0];
//遍历数组,如果大于单调队列的尾部 就直接加入尾部
//如果小于的话 就找到第一个比他比他大的数,把它换掉,保留了后续增长的可能性
for (int i = 0; i < nums.length ; i++) {
//如果比尾部大,直接加尾部
if(nums[i] > a[len]) {
a[++len] = nums[i];
//否则用二分找位子
} else {
int l = 0, r = len + 1;
while(l < r) {
int m = l + (r - l) / 2;
//如果这个数过大 那么就换右区间找
if(a[m] < nums[i]) l = m + 1;
//反之 换左区间
else r = m;
}
//找到了 退出循环 替换数字
a[r] = nums[i];
}
}
return len + 1;
}
}

树形结构

(二叉树,AVL树,红黑树,B树,堆,Trie哈夫曼树,并查集)

LeetCode-树相关

572. 另一个树的子树

image-20201004160328789

  • 这题要点在于,是不是把是不是子树问题转换成了是不是同树问题;

    判断同树的方法就算:要么都为空,要么值相等,其他情况肯定都不是同树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
//如果子树为空 肯定是主树的子树了
if(t == null) return true;
//如果主树为空,由于此题的子树一定部位空,那么就不属于子树
if(s == null) return false;
//判断一下 此时是否是同树
if(isSametree(s,t)) return true;
//返回要么是左子树要么右子树,否则就都不是
return isSubtree(s.left, t) || isSubtree(s.right, t);
}

public boolean isSametree(TreeNode s, TreeNode t) {
//此处都为空,都遍历到头了 就有可能是树
if(s == null && t == null) return true;
//一个未空一个不为空,肯定不是同树
if(s == null || t == null) return false;
//值不同,不可能为同树
if(s.val != t.val) return false;
//判断左边和右边
return isSametree(s.left, t.left) && isSametree(s.right, t.right);

}
}

串结构

LeetCod-串相关

  • 串的问题一般都需要用到DP的思想去解决

242.有效的字母异位词

image-20201004161742293

这题一开始我想到的是用类似于异或运算的方法去解决,用一个数组去表示答案,遍历两个字符串,如果有相同的就消掉为0,最后再遍历一次数组,假如发现有不是0的 代表两个字符串并不是字母异位的。

方法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean isAnagram(String s, String t) {
//特判 假如字符串长度都不同,也就没有比的必要了
if(s.length() != t.length()) return false;
int[] arr = new int[26];//为什么是26个呢 因为26个单词嘛 26个多一个保险点
//都转成字符数组
char[] a1 = s.toCharArray();
char[] a2 = t.toCharArray();
for(int i = 0 ; i < s.length() ; i++) {
//一个加
arr[a1[i] - 97]++;
//一个减少
arr[a2[i] - 97]--;
}
for(int i = 0 ; i < arr.length ; i++) {
//有不是0的代表没消掉
if(arr[i] != 0) return false;
}
return true;
}
}

后来看答案,好像有个方法可以直接排序后直接比较 学到了

方法二:

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
char[] a1 = s.toCharArray();
char[] a2 = t.toCharArray();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);
}
}

151.翻转字符串里的单词

image-20201004172342276

看到这种翻转题,我条件反射就想到了用栈,FILO的性质太适合了。

那么怎么用栈呢?整体思路就是:遇到了空格 那么前面肯定是一个单词了,把他push进栈里面;

整个遍历结束后,用一个字符串接受答案,一个接一个pop出来就好;

这题的小细节很多,比如,我们可以在尾部加一个空格方便判断是单词

由于题目要求,保证前面是不能有空格的,那么就得先pop一个出来,再添加后续的单词;

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
class Solution {
public String reverseWords(String s) {
//倒序输出 很自然想到了栈
Stack<String> stack = new Stack<>();
StringBuilder tmp = new StringBuilder();
//为了保证判断的一致性 在尾部添加一个空格
s += " ";
for(int i = 0; i < s.length(); i++) {
//如果遇到空格 发现是一个单词了 就把之前的push
if(s.charAt(i) == ' ') {
if(tmp.length() != 0) {
stack.push(tmp.toString());
//别忘了重置tmp
tmp = new StringBuilder();
}
} else {
//没遇到空格 就把遇到的单词拼在一起
tmp.append(s.charAt(i));
}
}
//如果栈为空 说明就是个空串
if(stack.isEmpty()) return "";
//答案字符串
StringBuilder res = new StringBuilder();
//由于末尾的空格是不要的 那么就得先pop掉最上面的
res.append(stack.pop());
//遍历栈 不停的加
while(!stack.isEmpty()) {
res.append(" ");
res.append(stack.pop());
}
return res.toString();

}
}

图形结构

(邻接矩阵,邻接表)