基础算法

递归实现累加和累乘

1、实现n+(n-1)+(n-2)+..3+2+1
最佳办法是使用等差求和公式:n(n+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 递归实现累加
*/
public static int accumulate(int n){
    if(n < 0){
        // 递归异常
        return -1;
    }
    if(n == 0){
        // 递归出口
        return 0;
    }else {
        // 递归的函数体
        return n + Solution.accumulate(n-1);
    }
}

2、实现n!

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 递归实现阶乘
*/
public static int factorial(int n){
    if(n<0){
        return -1;
    }
    if(n == 1){
        return 1;
    } else {
        return n * Solution.factorial(n-1);
    }
}

排序算法

关键路径算法

核心概念
  • 节点最早开始时间,做这项最早开工干活。可以开工干活的前提是该工序之前的全部节点(工序)已经全部完成，如果是汇聚节点。需要选择消耗时间最大的那个。因为花费时间最多的工序完成了，则花费时间少的就很不用管了(并行)。
    使用Tes(i)标记为该节点i的最早开始时间。计算公式为
    Tes(i)=max{Tes(i) + T(i,j)},i=1,2,3...k
  • 节点的最迟结束时间。
    最迟结束时间是为了保证该节点后面的工作能够按时完成，这个工序晚点的话依赖这个工序的可能会晚点。
    使用Tlf(j)标记该节点的最迟结束时间。公式为
    Tlf(i) = min{Tlf(j) - T(i,j)},j=1,2,3....n
    计算的时候从后面逆序计算。因为结束时间已经知道了。
    • 节点时差 S(i) = Tlf(i) - Tes(i)
    • 关键路径。节点时差为0的节点联结起来算为关键路径。因为这个节点不能最早开始时间和最迟结束时间是没有时间差的。关键路径上的工序为关键工序，关键工序作业时间之和就是工程的完工总工期。

辗转相除法求最大公因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   int hfc(int m,int n)
{
    int r=1;
    r = m % n;
    while(r!=0){
        if(r==1){
            return 1;
        }
        m=n;
        n=r;
        r=m % n;
    }
    return n;
}
优化版的辗转相除法
1
2
3
4
5
6
7
8
9
10
11
12
public int hfc(int m,int n)
   {
       int r =1;
       r = m % n;
       while ( r != 0)
       {
           m = n;
           n = r;
           r = m % n;
       }
       return n;
   }

合并两个数组

题目描述:
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

1
2
3
4
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

算法思路

由于两个数组都是有序的,则可以使用类似于归并排序的思想。从后往前合并数组，每次选择从两个数组中选取其中最大的合并到nums1的尾部。
边界处理:
1、nums1值为空,将nums2复制到nums1中。
2、nums2为空,不做任何处理

我的题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void merge(int[] nums1, int m, int[] nums2, int n) {
        int point = m + n -1;
        -- m;
        -- n;
        // 归并排序的思想
        while(m >=0 && n >= 0){
            if(nums1[m] > nums2[n]){
                nums1[point] = nums1[m];
                -- point;
                -- m;
            }else{
                nums1[point] = nums2[n];
                -- point;
                -- n;
            }
        }
        while( n >= 0 ){
            nums1[point] = nums2[n];
            -- point;
            -- n;
        }
    }
大神的题解
1
2
3
4
5
6
7
8
9
10
public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        
        while (n >= 0) {
            nums1[p--] = nums2[n--];
        }
    }

两数之和[中等]

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

官方解法
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
func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    p,q,flag := l1,l2,&ListNode{Val: 0}
    current := flag
    carry := 0
    for p != nil || q != nil {
        x := 0
        y := 0
        if p != nil {
            x = p.Val
        }
        if q != nil {
            y = q.Val
        }
        // 相加,上一步的进位也要加上
        sum := carry + x + y
        // 重新计算进位
        carry = sum/10
        // 创建新的节点,节点里面放的是相加之后的个位数
        // current.Next里面可能已经有值了，但是不管.直接覆盖
        current.Next = &ListNode{Val: sum%10}
        current = current.Next
        if p != nil{
            p = p.Next
        }
        if q != nil {
            q = q.Next
        }
        // 有进位的话会往前创建一个node,如果后面还有数据的话这个节点会被丢弃
        if carry >0  {
            current.Next = &ListNode{Val: carry}
        }
    }
    return flag.Next
}
分析

使用一个值为0的node来作为输出的头部节点头(哑节点)。
将两个输入的链表虚拟为相同的长度，如果有一条链表已经到达末尾了,该链表的下一个值用0替代。对应节点相加,创建一个新的节点放置相加后数据的个位数。如果有进位，添加新的节点来放置进位数据。放置进位的数据节点会被后面相加的数据的个位数替换。其实是丢掉进位节点，将链表的Next指针指向新生成的节点。使用current指针用于连接新的生成的数据。使用哑节点来放置链表的头部。这样返回的时候，只需要返回哑节点的Next指针便是相加后的数据。其中比较难理解的是current这个变量。
current只是放置Node指针的，最开始的时候current指向的哑节点。
current.Next = &ListNode{}真正连接的是哑节点的Next。
current= current.Nextcurrent指针现在指向的是新生成的数据。current本身不具备真正的node。都是其它的Node通过current来代理操作的。
进位处理:

  • 进位创建新的Node.
    当前还不知道后面是否还有数据，先创个Node节点放置数据。如果后面没有数据了,返回便可。如果后面还有数据,该节点被丢弃了。
  • 生成的数据
    [0(flag)]->[7]->[0]->[8]

83. 删除排序链表中的重复元素[简单题]

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路
删除链表中的节点,当两个节点一致时，删除后面的节点。只要知道对链表的节点进行删除便可以做出来
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func deleteDuplicates(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        if cur.Val == cur.Next.Val {
            // 删除重复节点
            // 跳过下一个节点
            cur.Next = cur.Next.Next
        }else{
            // 不相同到下一个
            cur = cur.Next
        }
    }
    return head
}
方法二、递归
1
2
3
4
5
6
7
8
9
10
11
12
13
// 递归的方法
func deleteDuplicates2(head *ListNode) *ListNode{
    // 递归出口
    if head == nil || head.Next == nil {
        return head
    }
    // 递归条件
    head.Next = deleteDuplicates2(head.Next)
    if head.Val == head.Next.Val {
        head = head.Next
    }
    return head
}

203. 移除链表元素[简单]

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-linked-list-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

官方解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeElements(head *ListNode, val int) *ListNode {
   flag := &ListNode{Val:0}
   flag.Next = head
   // 前置
   prev,cur := flag,head
   for cur != nil{
       if cur.Val == val {
           // 删除节点
           prev.Next = cur.Next
       }else{
           // 不相等,往前进发
           prev = cur
       }
       cur = cur.Next
   }
   return flag.Next
}
解法分析

思路:相同就删除链表中的节点，不相同就跳到下一个,但是如果头节点相同的话如何返回链表？
官方使用的方法是使用哨兵节点，列表作为哨兵节点的next值。通过使用哨兵节点就可以解决链表无头问题。

141. 环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。


示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。


示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

常规解法

使用map存储节点地址，如果后续的节点地址已经存在map中，说明已经回来了。

1
2
3
4
5
6
7
8
9
10
11
12
func hasCycle(head *ListNode) bool {
    cur := head
    m := make(map[*ListNode]interface{},1)
    for cur != nil{
        if _,ok := m[cur];ok {
            return true
        }
        m[cur] = nil
        cur = cur.Next
    }
    return false
}
快慢指针解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func hasCycle(head *ListNode) bool {
  if head == nil || head.Next == nil {
        return false
    }
    slow,fast := head,head.Next
    for slow != fast {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}

这种快慢跑,fast节点比slow节点跑得快，如果有环的话后面会和跑得慢的相撞。1000m赛跑，跑得快的会再一圈之后相遇。

奇葩解法
1
2
3
4
5
6
7
8
9
10
11
12
def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    while head:
        if head.val == 'bjfuvth':
            return True
        else:
            head.val = 'bjfuvth'
        head = head.next
    return False
进阶，如果需要返回相交节点
  • 使用map需要返回值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    func detectCycle(head *ListNode) *ListNode {
        cur := head
        m := make(map[*ListNode]interface{},1)
        for cur != nil{
            if _,ok := m[cur];ok {
                return cur
            }
            m[cur] = nil
            cur = cur.Next
        }
        return nil
    }
  • 使用快慢指针
    需要计算出相遇的时候里相交点的距离,相遇点离相交点的距离=原点离相交点的距离。
    假设O点为起始点,P点为环状相交点,Q点为快慢指针相遇的地方
    OP = x
    PQ = Y
    QP = Z
    慢指针前进的距离:OP + PQ = X + Y
    快指针前进的距离:OP + PQ + QP + PQ = X + 2Y + Z
    由于快指针前进的距离是慢指针的两倍,所以
    2(X + Y) = X + 2Y + Z
    整理得:X = Z
    说明OP = QP
    这时候从O点再次出发,步长和慢指针一致,他们便是在P点相遇。
    1
    2
    3
    4
    5
                ->----[Y]--> 
               |            |
    O.---[x]---P            |
               |            |
                <----[Z]-Q--
    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
    func detectCycle(head *ListNode) *ListNode {
        if head == nil || head.Next == nil {
            return nil
        }
        slow,fast := head,head
        for {
            if fast == nil || fast.Next == nil {
                return nil
            }
            slow = slow.Next
            fast = fast.Next.Next
            if slow == fast {
                break
            }
        }

        // 相遇了,一个C从开始点出发,再相遇的点是相交点
        for cur := head; cur!=nil;{
            if slow == cur {
                return slow
            }
            slow = slow.Next
            cur = cur.Next
        }
        return slow
    }

160. 相交链表[简单]

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
通过次数135,078提交次数241,320

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 map

使用map存储节点，第一遍先遍历A,将数据写入map中。然后遍历B,如果B的某个节点在map中,返回这个节点值。如果到尾巴了都没有，说明不相交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    m := make(map[*ListNode]interface{})
    if headA == nil || headB == nil {
        return nil
    }
    cur := headA
    for cur != nil {
        m[cur] = true
        cur = cur.Next
    }
    // 遍历B的时候,判断
    cur = headB
    for cur != nil {
        if _,ok := m[cur];ok{
            return cur
        }
        cur = cur.Next
    }
    return nil
}
解法2 暴力法

两个for循环判断

解法3 双指针法

相交:
len(A+B) == len(B+A)
两个指针会在相遇的地方碰面

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
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pA,pB := headA,headB
    //如果两个链表相交: A+B = B+A,两个指针走的路程都是一样的,会在汇合处相遇
    //不相交：最后都会变成nil,退出
    // 退出的条件为相等,要么找到相同节点,要么都为nil
    for pA != pB {
        if pA == nil {
            // 到达尾巴了,从B链表开始
            pA = headB
        }else {
            // 
            pA = pA.Next
        }
        // 同理
        if pB == nil {
            pB = headA
        }else{
            pB = pB.Next
        }
    }
    // 如果p
    return pA
}

876. 链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。
通过次数69,843提交次数100,768

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一 数组

数组,遍历链表,将数据放入数组中。结束后取出下表为n/2的节点。

方法二 单指针法
  • 第一遍跑,记下长度。
  • 第二遍跑一半，返回节点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    func middleNode(head *ListNode) *ListNode {
        length := 0
        cur := head
        if head == nil {
            return head
        }
        for cur != nil {
            length ++
            cur = cur.Next
        }
        cur = head
        if length % 2 == 0{
            // 偶数 = (length+2)/2
            length = (length + 2)/2
        }else {
            // 奇数 = (length+1)/2
            length = (length + 1)/2
        }
        for ;length>1;length-- {
            cur = cur.Next
        }
        return cur
    }
    优化:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    func middleNode(head *ListNode) *ListNode {
        length := 0
        cur := head
        if head == nil {
            return head
        }
        for cur != nil {
            length ++
            cur = cur.Next
        }
        cur = head
        for length = length/2 + 1;length>1;length-- {
            cur = cur.Next
        }
        return cur
    }
    解法三 快慢指针
    每次快指针比慢指针多走一步，当快指针到终点之后。慢指针走到中间位置。
    1
    2
    3
    4
    5
    6
    7
    8
    func middleNode(head *ListNode) *ListNode {
        slow,fast := head,head
        for fast != nil && fast.Next != nil {
            fast = fast.Next.Next
            slow = slow.Next
        }
        return slow
    }

    754. 到达终点数字

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。

返回到达终点需要的最小移动次数。

示例 1:

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2:

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
注意:

target是在[-10^9, 10^9]范围中的非零整数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reach-a-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

规律
1 = 1
2 = 1 - 2 + 3 (1+2+3)=6 6-2=4 4/2 = 2
3 = 1 + 2
4 = -1 + 2 + 3 (1+2+3)=6 6-4=2 2/2 = 1
5 = 1 + 2 + 3 + 4 - 5 sum=15 15-5=10 10/2= 5

对于target来所,正负不会影响走的步数。所以只考虑正数的便可。
对于累加和来说,其中第n为数转为-n。相应的数值变为 sum - 2n。
为什么是2n,如果不加第n位时,sum -n 。第n位变为负数时又-n。所以，第n位数变为负数时，累加和为全是正数的累加和-2n。即第一次满足条件: target = sum -2n即为走的步数。整理得
满足:sum - target = 2n时,找到步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reachNumber(target int) int {
    if target < 0 {
        target = -target
    } 
    sum := 0
    i := 1
    for {
        sum = sum + i
        if sum == target {
            return i
        }else if sum > target {
            if (sum - target) %2 == 0 {
                return i
            }
        }
        i++
    }
    return i
}

1144. 递减元素使数组呈锯齿状

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > …
或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < …
返回将数组 nums 转换为锯齿数组所需的最小操作次数。

 

示例 1：

输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。
示例 2：

输入：nums = [9,6,1,6,2]
输出：4

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
通过次数6,990提交次数16,349

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decrease-elements-to-make-array-zigzag
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

要么1,3,5,7….奇数位为高峰。要么2,4,6,8,….偶数位为高峰。只要分别计算出步数,返回步数小的情况就好了。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
func MovesToMakeZigzag(nums []int) int {
    /**
    锯齿状数据,只能递减,每次减1。步数最少。
    奇数位先减,操作的步数。
    偶数位再减,操作的步数。
    比较那个走得少。
    */
    oddStep := 0
    eventStep := 0
    length := len(nums)
    // 奇位数先减 1,3,5,7
    for i:=0;i < length; i = i +2{
        tmp := nums[i]
        // 处在头部,只比较右边的数据
        if i == 0 {
            if nums[i + 1] > tmp {
                // A < B 高过，不用管
                continue
            }else {
                // A >= B,下拉
                oddStep = oddStep + (tmp - nums[i+1] + 1)
                continue
            }
        }
        // 处在尾部
        if i == length -1 {
            // B > C
            if nums[i-1] > tmp {
                continue
            }else {
                // B < C
                oddStep = oddStep + (tmp - nums[i-1] + 1)
                continue
            }
        }
        
        // 处在中间,比两边。低过最低的便可
        if i > 0 && i < length-1 {
            // 比较两边,
            if nums[i-1] > tmp && tmp < nums[i+1] {
                continue
            }
            if nums[i-1] > nums[i+1] {
                // A > C 低过右边便可
                if nums[i + 1] > tmp {
                    continue
                }else {
                    oddStep = oddStep + (tmp - nums[i+1] + 1)
                    continue
                }
            }else{
                // A < C 低过左边便可
                if nums[i - 1] > tmp {
                    continue
                }else {
                    oddStep = oddStep + (tmp - nums[i-1] + 1)
                    continue
                }
            }
        }
    }
    
    // 偶数位先减 2,4,6,8
    for i:=1;i < length;i= i + 2{
        tmp := nums[i]
        // 尾部
        if i == length -1 {
            // B > C
            if nums[i-1] > tmp {
                continue
            }else {
                // B < C
                eventStep = eventStep + (tmp - nums[i-1] + 1)
                continue
            }
        }
        // 中间
        if i > 0 && i < length-1 {
            // 比较两边,
            if nums[i-1] > tmp && tmp < nums[i+1] {
                continue
            }
            if nums[i-1] > nums[i+1] {
                // A > C 低过右边便可
                if nums[i + 1] > tmp {
                    continue
                }else {
                    eventStep = eventStep + (tmp - nums[i+1] + 1)
                    continue
                }
            }else{
                // A < C 低过左边便可
                if nums[i - 1] > tmp {
                    continue
                }else {
                    eventStep = eventStep + (tmp - nums[i-1] + 1)
                    continue
                }
            }
        }
    }
    
    if oddStep > eventStep {
        return eventStep
    }
    return oddStep
}

206. 反转链表[简单]

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
func reverseList(head *ListNode) *ListNode {
   var tmp *ListNode = nil
   cur := head
   for cur != nil {
       tmpNode := &ListNode{
           Val: cur.Val,
       }
       tmpNode.Next = tmp
       tmp = tmpNode
       cur = cur.Next
   }
   return tmp
}
解法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func ReverseList2(head *ListNode) *ListNode {
    var tmp *ListNode = nil
    cur := head
    for cur != nil {
        tmpNode := cur
        cur = cur.Next
        // 断开链表
        tmpNode.Next = nil
        // 重新连接
        tmpNode.Next = tmp
        tmp = tmpNode
    }
    return tmp
}

234. 回文链表[简单]

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

通过次数113,285提交次数264,021

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一 复制链表，逆序比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isPalindrome(head *ListNode) bool {
    // 复制链表
    cp := []int{}
    cur := head
    for cur != nil {
        cp = append(cp,cur.Val)
        cur = cur.Next
    }
    // 逆序比较
    cur = head
    index := len(cp) - 1
    for cur != nil{
        if cur.Val != cp[index] {
            return false
        }
        index --
        cur = cur.Next
    }
    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
// 判断链表是否是回文数
func isPalindrome(head *ListNode) bool {
    // 复制链表
    cp := []int{}
    cur := head
    for cur != nil {
        cp = append(cp,cur.Val)
        cur = cur.Next
    }
    // 逆序比较
    cur = head
    index := len(cp) - 1
    index2 := 0
    for index != index2 && index2 < index {
        if cp[index] != cp[index2] {
            return false
        }
        index --
        index2 ++
    }
    //for cur != nil{
    //    if cur.Val != cp[index] {
    //        return false
    //    }
    //    index --
    //    cur = cur.Next
    //}
    return true
}
方法二 快慢指针+翻转链表

待研究

1290. 二进制链表转整数[简单]

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

 

示例 1：


输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：

输入：head = [0]
输出：0
示例 3：

输入：head = [1]
输出：1
示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880
示例 5：

输入：head = [0,0]
输出：0

提示：

链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。
通过次数25,976提交次数32,106

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

先将数据读取出来,获得长度。然后根据长度决定每个二进制位的base

版本一

使用额外切片。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func getDecimalValue(head *ListNode) int {
    // 读出来再进制运算
    arr := []int{}
    cur := head
    for cur != nil {
        arr = append(arr,cur.Val)
        cur = cur.Next
    }
    // 进制运算
    base := 1 << (len(arr) - 1)
    result := 0
    for _,v := range arr {
        result = result + v * base
        base /= 2
    }
    return result
}
版本二 不使用切片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func getDecimalValue(head *ListNode) int {
    // 读出来
    cur := head
    length := 0
    for cur != nil {
        cur = cur.Next
        length ++
    }
    // 按权重进行相加
    length --
    base := 1 << length
    result := 0
    for cur = head;cur!=nil;cur=cur.Next {
        result = result + cur.Val * base
        base /= 2
    }
    return result
}

剑指 Offer 22. 链表中倒数第k个节点[简单]

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
通过次数56,304提交次数71,296

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一

第一遍循环,寻找链表长度。得到截取的部分,再循环读取到对应的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func getKthFromEnd(head *ListNode, k int) *ListNode {
    // 第一遍算长度
    length := 0
    cur := head
    for ;cur != nil;cur= cur.Next {
        length ++
    }
    // 算前进步数
    length = length - k
    cur = head
    for i:=1; i <=length; i++{
        cur = cur.Next
    }
    return cur
}
解法二 双指针

快和慢指针。快指针先走k步,然后快慢指针一起走,快指针到末尾的时候,慢指针就是倒数第k个节点。

1
2
3
4
5
6
7
8
9
10
11
func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast,slow := head,head
    for i:=k;i>0;i--{
        fast = fast.Next
    }
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

面试题 02.01. 移除重复节点[简单]

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：

如果不得使用临时缓冲区，该怎么解决？

通过次数31,595提交次数44,947

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一

建立一个set,如果后面的数据已经存在,则删除该节点。不存在加入set中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func removeDuplicateNodes(head *ListNode) *ListNode {
    // 向后读取,如果后面的数据和现在的一样,删除节点。不一样,指针前移
    if head == nil {
        return head
    }
    pre,cur := head,head.Next
    // 临时缓冲区
    buf := make(map[int]struct{})
    buf[pre.Val] = struct{}{}
    for cur != nil {
        if _,ok := buf[cur.Val];ok {
            // 相同,删除节点
            cur = cur.Next
            pre.Next = cur
        }else{
            // 不相同,继续
            buf[cur.Val] = struct{}{}
            pre = pre.Next
            cur = cur.Next
        }
    }
    return head
}
方法二 两重循环

检查从当前节点开始，后面是否有重复的。如果有重复的,删除重复节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func removeDuplicateNodes(head *ListNode) *ListNode {
   if head == nil {
        return head
    }
    pre,cur := head,head.Next
    for pre != nil {
        preTmp := pre
        for cur != nil {
            if cur.Val == pre.Val {
                cur = cur.Next
                preTmp.Next = cur
            }else{
                preTmp = preTmp.Next
                cur = cur.Next
            }
        }
        pre = pre.Next
        if pre == nil {
            break
        }
        cur = pre.Next
    }
    return head
}
  • 优化后
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    func removeDuplicateNodes(head *ListNode) *ListNode {
       if head == nil {
            return nil
        }
        index := head
        for index != nil {
            cur := index
            for cur.Next != nil {
                if cur.Next.Val == index.Val {
                    // 删除节点
                    cur.Next = cur.Next.Next
                }else{
                    cur = cur.Next
                }
            }
            index = index.Next
        }
        return head
    }

    剑指 Offer 06. 从尾到头打印链表[简单]

    输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

 

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

通过次数71,441提交次数93,952

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一
1
2
3
4
5
6
7
func reversePrint(head *ListNode) []int {
    arr := []int{}
    for cur := head;cur != nil;cur = cur.Next{
        arr = append([]int{cur.Val},arr...)
    }
    return arr
}
解法二

减少append操作

1
2
3
4
5
6
7
8
9
10
11
12
func reversePrint(head *ListNode) []int {
    length := 0
    for cur:=head;cur != nil;cur=cur.Next{
        length ++
    }
    arr := make([]int,length)
    for cur:=head;cur!=nil;cur=cur.Next{
        arr[length-1] = cur.Val
        length --
    }
    return arr
}

剑指 Offer 18. 删除链表的节点[简单]

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
通过次数46,045提交次数78,179

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

判断下个节点是否和目标一致，如果一致，删除节点。如果第一个节点为待删除节点，需要提前解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func deleteNode(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    // 处理第一个节点为待删除节点
     cur:=head
    for;cur !=nil && cur.Val == val;{
        cur = cur.Next
    }
    head = cur
    for index:=head;index!=nil && index.Next !=nil ;{
        if index.Next.Val == val {
            index.Next = index.Next.Next
        }else{
            index = index.Next
        }
    }
    return head
}
  • 可以解决重复数字删除
    1
    2
    3
    4
    5
    输入
    [5,5,4,5,5,1,9]
    5
    输出
    [4,1,9]

    面试题 02.03. 删除中间节点[简单题]

    实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例：

输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f
通过次数23,101提交次数27,295

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-middle-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

说明

入参为待删除的节点，这个问题是如何根据当前节点删除当前节点。
只要将后面的节点数据往前移一格，然后删除最后一个节点便可。

解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func deleteNode(node *ListNode) {
    cur := node
    for cur.Next != nil {
        if cur.Next.Next == nil {
            // 删除最后节点
            cur.Val = cur.Next.Val
            cur.Next = nil
        }else{
            //
            cur.Val = cur.Next.Val
            cur = cur.Next
        }
    }
}

19. 删除链表的倒数第N个节点[中等]

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

通过次数210,641提交次数537,922

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一 记录法

先跑一遍得出链表长度,根据倒数数得出顺数删除节点。删除便可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head.Next == nil {
        return nil
    }
    length := 0
    for cur:=head;cur != nil;cur=cur.Next{
        length ++
    }
    // 得出待删除节点所处的位置
    length = length - n
    if length == 0 {
        // 删除头节点
        head = head.Next
        return head
    }
    // 定位节点并删除
    cur := head
    for ;length > 1;length--{
        cur = cur.Next
    }
    // 删除节点
    cur.Next = cur.Next.Next
    return head
}

方法二 快慢指针

快慢指针,快指针比慢指针先走n+1。当快指针走完之后,如果慢指针还没走，说明删除第一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 快慢指针,快指针比慢指针先走n+1步.快指针到终点了慢指针就再到数第n为的前面,然后删除便可
    if head.Next == nil {
        return nil
    }
    slow,fast := head,head
    step := n + 1
    for ;fast != nil;fast=fast.Next {
        if step > 0 {
            step --  
        }else{
            slow = slow.Next
        }
    }
    // 快指针已经结束,但是还有剩余步数,说明删除的是第一个节点
    if step > 0 {
        head = head.Next
        return head
    }
    // 删除前面的节点
    slow.Next = slow.Next.Next
    return head
}

24. 两两交换链表中的节点[中等]

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.
通过次数134,389提交次数202,662

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

使用哑节点构建新的链表头,新链表有个尾巴引用,用来连接新的节点,每次截取旧链表的相邻两位。注意节点需要完全断开。

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
func swapPairs(head *ListNode) *ListNode {
    // 使用临时节点存放旧链表,节点短链重连
    oldHead := head
    newHead := &ListNode{}
    newLinkCur := newHead
    var n1,n2 *ListNode = nil,nil
    for oldHead != nil {
        if oldHead.Next == nil {
            // 最后一个节点了,将这个节点加入新链表尾巴
            newLinkCur.Next = oldHead
            break
        }
        // 处理节点
        n1,n2 = oldHead,oldHead.Next
        //newHead -> n2-> n1->
        oldHead = oldHead.Next.Next
        n1.Next = nil
        // n2 -> n1
        n2.Next = n1
        // tail-> n2
        newLinkCur.Next = n2
        // tail = n1
        // tail -> n2->n1 ->tail
        newLinkCur = n1
    }
    return newHead.Next
}
使用递归
1
2
3
4
5
6
7
8
9
10
func swapPairs(head *ListNode) *ListNode {
    // 递归第一个出口
    if head == nil || head.Next == nil {
        return head
    }
    firstNode,secondNode := head,head.Next
    firstNode.Next = swapPairs(secondNode.Next)
    secondNode.Next = firstNode
    return secondNode
}

61. 旋转链表[中等]

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
通过次数76,849提交次数189,706

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路 结环-切割

链表结成一个环之后,向右旋转k,等价于head要后退k步。但是head只能往前,所以
对于环形链表来说,退k步=进(length - k)步。
当k大于length时,说明循环一圈了,这一圈可以去掉。所以需要往前走(length - k%lenght)步即到切割点。

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
func rotateRight(head *ListNode, k int) *ListNode {
    // 结环 -> 割环
    // step = length - k%length
    if k == 0 {
        return head
    }
    if head == nil {
        return nil
    }
    length := 0
    cur := head
    for cur != nil {
        if cur.Next == nil {
            // 结环,获得长度
            cur.Next = head
            length ++
            break
        }
        cur= cur.Next
        length ++
    }
    // 计算切割点
    // [1,2,3] 20000000 需要进行mod运算
    step := length - k%length
    // 定位切割点
    for ;step > 1;step-- {
        head = head.Next
    }
    // 切割
    tmp := head
    head = head.Next
    tmp.Next = nil
    return head
}

82. 删除排序链表中的重复元素 II[中等]

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3
通过次数59,058提交次数121,182

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一

使用map存储每个节点值的个数。然后前探节点,如果该节点是重复节点,删除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
27
28
29
30
31
32
func deleteDuplicates(head *ListNode) *ListNode {
   if head == nil || head.Next == nil {
       return head
   }
   // map
    mp := make(map[int]int)
    for cur:=head;cur!=nil;cur=cur.Next{
        mp[cur.Val] += 1
    }
    dump := &ListNode{}
    dump.Next = head
    dup := false
    for cur := dump;cur!= nil&&cur.Next != nil;{
        // 判断重复 值大于2
        if v,_ := mp[cur.Next.Val]; !dup && v > 1 {
            dup = true
        }
        // 删除重复的节点
        if dup {
            if v,_ := mp[cur.Next.Val];v > 0{
                mp[cur.Next.Val] -= 1
                if v,_ := mp[cur.Next.Val];v == 0 {
                    dup = false
                }
                cur.Next = cur.Next.Next
            }
        }else{
            cur = cur.Next
        }
    }
    return dump.Next
}

92. 反转链表 II[中等]

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
通过次数66,376提交次数130,134

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    // 先将待翻转的数据存下来,存完之后就翻转
    // 使用array存储
    // 哑节点
    if head == nil || head.Next == nil {
        return head
    }
    dummy := &ListNode{}
    dummy.Next = head
    pre,cur := dummy,head
    arr := []*ListNode{}
    sub := n - m
    step := 2
    i := 0
    for {
        if step == 2 {
            // 分析阶段
            if i < m -1 {
                // 定位
                pre = cur
                cur = cur.Next
                i ++
            }else if i >= m -1 && i <= n -1{
                // 赋值
                arr = append(arr,cur)
                cur = cur.Next
                i ++
            }else{
                step --
                continue
            }
        }else if step == 1{
            // 反转阶段
            if sub >= 0 {
                tmp := arr[sub]
                tmp.Next = nil
                pre.Next = tmp
                pre = tmp
                sub --
            }else{
                // 翻转完成,链表连接
                pre.Next = cur
                step --
            }
        }else{
            break
        }
    }
    return dummy.Next
}
解法二

使用多指针,待翻转的部分建立成新的链表,新链表有自己的头节点和尾节点。当翻转完成之后再和哑节点形成的链表连接起来。

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
if head == nil || head.Next == nil {
       return head
   }
   // 使用多指针，边走边翻转
   dummy := &ListNode{}
   dummy.Next = head
   // 新生成链表的尾巴
   dTail := dummy
   // 旧的数据
   var sHead *ListNode = nil
   var sTail *ListNode = nil
   i := 0
   cur := head
   for {
       if i < m -1 {
           dTail = cur
           cur = cur.Next
           i ++
       }else if i == m-1{
           // 切割点
           sTail = cur
           sHead = cur
           cur = cur.Next
           i ++
       }else if i > m -1 && i <= n -1 {
           // 翻转点
           tmp := cur
           cur = cur.Next
           tmp.Next = sHead
           sHead = tmp
           i ++
       }else if i == n {
           // 重新连接点
           dTail.Next = sHead
           sTail.Next = cur
           break
       }else{
           break
       }
   }
   
   return dummy.Next

445. 两数相加 II[中等]

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

 

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

 

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
通过次数46,824提交次数80,888

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func reverseList(head *ListNode) *ListNode{
    var nHead *ListNode = nil
    cur := head
    for cur != nil {
        tmpNode := cur
        cur = cur.Next
        // 断开链表
        tmpNode.Next = nil
        // 重新连接
        tmpNode.Next = nHead
        nHead = tmpNode
    }
    return nHead
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 翻转链表,然后按照简单的方法做
    l1 = reverseList(l1)
    l2 = reverseList(l2)
    p,q,flag := l1,l2,&ListNode{Val: 0}
    current := flag
    carry := 0
    for p != nil || q != nil {
        x := 0
        y := 0
        if p != nil {
            x = p.Val
        }
        if q != nil {
            y = q.Val
        }
        // 相加,上一步的进位也要加上
        sum := carry + x + y
        // 重新计算进位
        carry = sum/10
        // 创建新的节点,节点里面放的是相加之后的个位数
        // current.Next里面可能已经有值了，但是不管.直接覆盖
        current.Next = &ListNode{Val: sum%10}
        current = current.Next
        if p != nil{
            p = p.Next
        }
        if q != nil {
            q = q.Next
        }
        // 有进位的话会往前创建一个node,如果后面还有数据的话这个节点会被丢弃
        if carry >0  {
            current.Next = &ListNode{Val: carry}
        }
    }
    return reverseList(flag.Next)
}
方法二 入栈，出栈相加
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
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := []int{}
    stack2 := []int{}
    // 数据入栈
    for cur:=l1;cur!= nil;cur=cur.Next{
        stack1 = append(stack1,cur.Val)
    }
    for cur:=l2;cur!=nil;cur=cur.Next{
        stack2 = append(stack2,cur.Val)
    }
    // 出栈相加
    dummy := &ListNode{}
    top1,top2 := len(stack1),len(stack2)
    carray := 0
    for top1 > 0 || top2 > 0{
        a,b := 0,0
        if top1 == 0 {
            a = 0
        }else{
            a = stack1[top1 - 1]
            top1 --
        }
        if top2 == 0 {
            b = 0
        }else{
            b = stack2[top2 -1]
            top2 --
        }
        sum := a + b + carray
        carray = sum / 10
        val := sum % 10
        node := &ListNode{
            Val:val,
            Next:nil,
        }
        node.Next = dummy.Next
        dummy.Next = node
    }
    if carray > 0 {
        cNode := &ListNode{
            Val:1,
            Next:nil,
        }
        cNode.Next = dummy.Next
        dummy.Next = cNode
    }
    return dummy.Next
}

35. 搜索插入位置[简单]

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0
通过次数225,858提交次数484,313

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func searchInsert(nums []int, target int) int {
    i := 0
    if target < nums[0]{
        return 0
    }
    for ;i < len(nums);i++{
        if nums[i] == target {
            return i
        }
        if i + 1 < len(nums)  {
            if target > nums[i] && target < nums[i + 1]{
                return i + 1  
            }
        }
    }
    return i
}

面试题 10.01. 合并排序的数组[简单]

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
说明:

A.length == n + m
通过次数30,098提交次数55,588

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sorted-merge-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于A数组能够放置B数组,也就是说A数组前面的数据不会被动到也可以放入。这样,将A前面的数据看作一个数组,和B数组做归并排序。每次从A和B中选择大的值放入A的末尾中,由于A,B有数据部分都是排序好的。所以，只要比较两个数组最后一位的大小便可。如果B中的值比A的都大,A数组也可以放得下。如果A的数据都比B大,A的数据都往后挪了m位,B数据覆盖A数组前段数据也无所谓。因为A有效数据已经全部挪完了。

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
func merge(A []int, m int, B []int, n int)  {
    // 从后向前移动,每次寻找最大值填入A
    index := m + n -1
    m,n = m-1,n-1
    for m >=0 || n >= 0 {
        if m < 0 {
            // A已经选取结束了,把B放入便可
            A[index] = B[n]
            index --
            n --
            continue
        }
        if n < 0 {
            A[index] = A[m]
            index --
            m --
            continue
        }
        if A[m] >= B[n] {
            A[index] = A[m]
            m --
            index --
        }else {
            A[index] = B[n]
            n--
            index --
        }
    }
}

121. 买卖股票的最佳时机[简单]

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
通过次数260,657提交次数476,342

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于只能进行一次买卖，并且只需要计算最大利润便可。使用一个变量存价格最低,使用一个变量存储价格最高。每天算一遍利润，反正前几天最低的数据我记得，今天的利润=今天的价格-买入的最低价。如果可以多次买入卖出，需要动态规划的思想。但是只是一次买卖,走一遍，计算最高利润便可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func maxProfit(prices []int) int {
    // 最低点买入,最高点卖出,由于只能进行一次买入和卖出,就计算看看,每天的情况
    if len(prices) == 0 || len(prices) == 1 {
        return 0
    }
    minPrice := prices[0]
    maxProfit := 0
    for i:=1;i<len(prices);i++{
        if prices[i] < minPrice {
            // 今天的价格最低,今天买入吧
            minPrice = prices[i]
        }
        if prices[i] - minPrice > maxProfit {
            // 今天卖出比前一天好
            maxProfit = prices[i] - minPrice
        }
    }
    return maxProfit
}

66. 加一[简单]

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
通过次数186,723提交次数414,952

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

加一,等价于之前的操作产生个进位1。将这个进位加到总数中,如果后面再有进位，开辟新的空间来存储进位。

1
2
3
4
5
6
7
8
9
10
11
12
func plusOne(digits []int) []int {
    carray := 1
    for i:=len(digits)-1;i>=0;i--{
        sum := digits[i] + carray
        carray = sum/10
        digits[i] = sum % 10
    }
    if carray > 0 {
        digits = append([]int{carray},digits...)
    }
    return digits
}

169. 多数元素[简单]

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2
通过次数198,349提交次数308,875

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1 map

遍历一遍数组,将数据出现的次数写入map中。然后遍历map，找到大于一半的便可。

1
2
3
4
5
6
7
8
9
10
11
12
13
func majorityElement(nums []int) int {
    half := len(nums) / 2
    mp := make(map[int]int)
    for _,v := range nums{
        mp[v] += 1
    }
    for k,v := range mp {
        if v > half {
            return k
        }
    }
    return 0
}
投票算法

思路

如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

算法

Boyer-Moore 算法的本质和方法四中的分治十分类似。我们首先给出 Boyer-Moore 算法的详细步骤：

我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；

我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

如果 x 与 candidate 相等，那么计数器 count 的值增加 1；

如果 x 与 candidate 不等，那么计数器 count 的值减少 1。

在遍历完成后，candidate 即为整个数组的众数。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    for _,k := range nums {
        if count == 0 {
            candidate = k
        }
        if k == candidate {
            count ++ 
        }else {
            count --
        }
    }
    return candidate
}

对拼的思想,只要我占到一半以上,不管和谁对拼。场中最后剩下的一定是我的人。

118. 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
通过次数97,040提交次数144,702

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

当前节点的值= 上一组下标小于当前下标的值 + 上一组下标等于当前下标的值。
如果上一组的前一个节点下标小于0,则可以用0替代。上一组当前下标的数据已经越界，用零替代。

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
func generate(numRows int) [][]int {
   reNums := make([][]int,numRows)
   for i:=0;i<numRows;i++{
       if i == 0 {
           reNums[i] = []int{1}
       }else{
           subNum := make([]int,i+1)
           for j:=0;j < i + 1;j++ {
                pre1,pre2 := 0,0
                if j-1 <0 {
                    pre1 = 0
                }else{
                    pre1 = reNums[i-1][j-1]
                }
                
                if j >= i {
                    pre2 = 0
                }else{
                    pre2 = reNums[i-1][j]
                }
                subNum[j] = pre1 + pre2
           }
           reNums[i] = subNum
       }
   }
   return reNums
}

119. 杨辉三角 II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]
进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一

使用上一种方式，返回第k-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
func getRow(rowIndex int) []int {
   numRows := rowIndex+1
   reNums := make([][]int,numRows)
   for i:=0;i<numRows;i++{
       if i == 0 {
           reNums[i] = []int{1}
       }else{
           subNum := make([]int,i+1)
           for j:=0;j < i + 1;j++ {
                pre1,pre2 := 0,0
                if j-1 <0 {
                    pre1 = 0
                }else{
                    pre1 = reNums[i-1][j-1]
                }
                
                if j >= i {
                    pre2 = 0
                }else{
                    pre2 = reNums[i-1][j]
                }
                subNum[j] = pre1 + pre2
           }
           reNums[i] = subNum
       }
   }
   return reNums[rowIndex]
}

方法二

组合数学处理，

img

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
func factorial(n int64) int64{
    if n == 0 {
        return 1
    }
    return factorial(n-1)*n
}
func combination(n1, m1 int) int64 {
    n := int64(n1)
    m := int64(m1)
    if m == 0 {
        return 1
    }
    return factorial(n)/(factorial(m)*factorial(n-m))
}
func getRow(rowIndex int) []int {
    // 只要计算一半便可
    half := rowIndex/2
    nums := make([]int,rowIndex + 1)
    for i:=0;i<=half;i++{
        nums[i] = int(combination(rowIndex,i))
    }
    for i:= half+1;i < rowIndex + 1;i++{
        nums[i] = nums[rowIndex - i]
    }
    return nums
}
方法三

思路：只利用一个[]int，行数下移即在尾部添加元素1，然后倒序计算当前行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func getRow(rowIndex int) []int {
    // 第0行
    nums := []int{1}
    for i := 1; i <= rowIndex; i++ {
        // 尾部追加1
        nums = append(nums, 1)
        // 倒序计算杨辉三角当前行
        for j:=i-1;j>0;j--{
            nums[j]+=nums[j-1]
        }
    }
    return nums
}
作者：revelationofturing
链接：https://leetcode-cn.com/problems/pascals-triangle-ii/solution/zhi-xing-yong-shi-0-ms-zai-suo-you-golang-ti-jia-8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

283. 移动零[简单]

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
通过次数189,245提交次数305,606

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

双指针一起走,当碰到零的时候,一个指针继续往前走,另一个指针等待当前0值被覆盖。拿后面的值来填充前面的零值,被拿走的数据要归零。等价于替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func moveZeroes(nums []int)  {
    cur,length := 0,len(nums)
    for i:=0;i<length;i++{
       if nums[i] != 0 {
           if cur != i {
                nums[cur] = nums[i]
                nums[i] = 0
                cur ++
           }else{
               cur ++
           }
       }
    }
}

剑指 Offer 03. 数组中重复的数字[简单]

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

通过次数104,581提交次数154,607

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

使用一个set来存储出现的数字，如果当前的值在set中,说明重复了，返回当前��值。如果不存在，设置值。

1
2
3
4
5
6
7
8
9
10
11
12
func findRepeatNumber(nums []int) int {
    // 使用map存储数据
    mp := make(map[int]struct{})
    for _,v := range nums {
        if _,ok := mp[v];ok{
            return v
        }else{
            mp[v] = struct{}{}
        }
    }
    return 0
}

122. 买卖股票的最佳时机 II[简单]

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
  因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

只要今天比昨天高,今天卖出可以获得利润。反正今天卖出之后,还可以再购买。每一个上升的区间进行交易我肯定是赚了。

1
2
3
4
5
6
7
8
9
10
func maxProfit(prices []int) int {
    maxProfit := 0
    for i:=1;i<len(prices);i++{
        if prices[i-1] < prices[i] {
            // 今天相比昨天高了,卖出。
            maxProfit = maxProfit + prices[i] -prices[i-1]
        }
    }
    return maxProfit
}

167. 两数之和 II - 输入有序数组[简单]

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
通过次数145,662提交次数257,898

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

夹逼法,由于已经排序好了。元素越往后面越大,越往前面越小。所以使用两个index1,index2。分别从最小，最大。往中间夹逼。大了,右边的指针往左移一步就变小了。小了,左边的指针往右移变大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func twoSum(numbers []int, target int) []int {
    // 一个从头开始，一个从末尾开始。如果和大于target,末尾指针左移，减小和。如果和小于target,头指针往前，增大sum.
    index1,index2 := 0,len(numbers)-1
    for numbers[index1] + numbers[index2] != target {
        if numbers[index1] + numbers[index2] == target {
            break
        }else if numbers[index1] + numbers[index2] > target {
            index2 --
        }else{
            index1 ++
        }
    }
    return []int{index1+1,index2+1}
}

1013. 将数组分成和相等的三个部分[简单]

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length - 1] 就可以将数组三等分。

 

示例 1：

输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
示例 3：

输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示：

3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
通过次数36,611提交次数90,704

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

求和，然后计算1/3的值。提供一个flag记录已经求和的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func canThreePartsEqualSum(A []int) bool {
    // 先算出累加和的值,得到每个部分的值,然后再遍历一次数据进行分割
    flag := 3
    sum := 0
    for _,a := range A{
        sum += a
    }
    threePart := sum / 3
    sum = 0
    for _,a := range A{
        sum += a 
        if sum == threePart {
            flag --
            if flag == 0 {
                return true
            }
            sum = 0
        }
    }
    return false
}

189. 旋转数组[简单]

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。
通过次数151,757提交次数356,331

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

和旋转链表一样,将数组看成一个环状的。然后确定分割点step := length - k%length

  • 未优化
    1
    2
    3
    4
    5
    6
    7
    8
    func rotate(nums []int, k int)  {
        // 将数组想象成一个环，向右移动k步,等价于向后面移动length - k%length 步.这样可以确定分割点
        step := len(nums) - k%len(nums)
        nums1 := append(nums[step:],nums[:step]...)
        for i:=0;i<len(nums);i++{
            nums[i] = nums1[i]
        }
    }
    官方解法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    func reverse(nums []int, start int, end int) {
        for start < end{
            tmp := nums[start]
            nums[start] = nums[end]
            nums[end] = tmp
            start ++
            end --
        }
    }
    func rotate(nums []int, k int)  {
        // 先整体翻转,然后前k个数据翻转，然后再length - K个数据翻转
        length := len(nums)
        k = k%length
        // 1.全部翻转
        reverse(nums,0,length-1)
        // 2.翻转前k个
        reverse(nums,0,k-1)
        // 3.翻转后n-k个
        reverse(nums,k,length-1)
    }

485. 最大连续1的个数[简单]

给定一个二进制数组， 计算其中最大连续1的个数。

示例 1:

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：

输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。
通过次数47,908提交次数84,570

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

遍历一遍,如果当前是一，添加进临时变量中。判断临时变量是否大于最大的连续数,大于就赋值。如果当前值是0,临时变量变成零，从头开始数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func findMaxConsecutiveOnes(nums []int) int {
    MaxCount := 0
    tmpCount := 0
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1{
        return nums[0]
    }
    for _,num := range nums {
       if num == 1 {
           tmpCount ++
       }
       if tmpCount > MaxCount{
           MaxCount = tmpCount
       }
       if num == 0 {
           tmpCount = 0
       }
    }
    return MaxCount
}

217. 存在重复元素[简单]

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false
示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
通过次数158,982提交次数300,723

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

构建set,如果当前数据在set中,说明第二次出现，说明重复了。不存在，添加进去。

1
2
3
4
5
6
7
8
9
10
11
func containsDuplicate(nums []int) bool {
    mp := make(map[int]struct{})
    for _, num := range nums {
        if _,ok := mp[num];ok{
            return true
        }else{
            mp[num] = struct{}{}
        }
    }
    return false
}

219. 存在重复元素 II[简单]

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

使用map之前的结果，key为值,Value为数组下标。遍历数组,如果当前值重复，判断两个index之间的差值是否小于k。如果大于k,则更新该值的index为最新的index。因为后面有重复的话肯定离这个值最近。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func containsNearbyDuplicate(nums []int, k int) bool {
    mp := make(map[int]int)
    for i,v := range nums {
        if index,ok := mp[v]; ok{
            // 存在,比较两个的差值
            if i - index <= k {
                return true
            }else{
                // 更新index
                mp[v] = i
            }
        }else{
            mp[v] = i
        }
    }
    return false
}

414. 第三大的数[简单]

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.
示例 2:

输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。
通过次数31,553提交次数89,485

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/third-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

遍历三次，每一次找一个最大的。最后比较第二大和第三大，相等返回第一大，不相等返回第三大。
flag的引入,为了陷入初始值特殊化的陷阱，保证都会考虑到。

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
func thirdMax(nums []int) int {
    flag := 0 // 记录当前的阶段
    one,two,three := nums[0],nums[0],nums[0]
    for _,num := range nums {
        if flag == 0 {
            if num > one {
                one = num
                flag ++
            }
        }else {
            if num > one {
                one = num
            }
        }
    }
    // 后面的数据
    flag ++ //
    for _,num := range nums {
        if flag == 1 {
            if num < one {
                two = num
                flag ++
            }
        }else if flag == 2{
            if num > two && num < one {
                two = num
            }
        }
    }
    for _,num := range nums {
        if flag == 2 {
            if num < two {
                three = num
                flag ++
            }
        }else if flag == 3{
            if num > three && num < two {
                three = num
            }
        }
    }
    if three == two {
        return one
    }
    return three
}

448. 找到所有数组中消失的数字[简单]

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]
通过次数48,919提交次数82,136

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路
  • 传统方法:hashMap
  • 进阶
    将访问到的值,作为下标去将该下标的值换成负数。换完之后,再遍历一遍，如果值为正的，说明该值对应的下标不存在数组中。如果存在就会被换成负数的。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    func findDisappearedNumbers(nums []int) []int {
        // 置位下标
        // 将访问过的值对应的下标置为负数,
        // 如果没有出现某个值,这个值的下标对应的数是正数
        re := []int{}
        for i:=0;i<len(nums);i++{
            if nums[i] < 0 {
                if nums[-nums[i]-1] > 0 {
                  nums[-nums[i]-1] = -nums[-nums[i]-1]
                }
            }else{
                 if nums[nums[i]-1] > 0 {
                    nums[nums[i]-1] = -nums[nums[i]-1]
                }
            }
        }
        for i,num := range nums {
            if num > 0 {
                re = append(re,i+1)
            }
        }
        return re
    }

86. 分隔链表[简单]

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
通过次数48,112提交次数81,182

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

新建两条链表,小于x的放在第一条链表中，大于等于x的放在第二条链表中。最后将两条链表连接起来。
由于新的链表元素相对顺序不变，维护一个尾巴,来了就连接进去就好了。

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
func partition(head *ListNode, x int) *ListNode {
    first,second := &ListNode{},&ListNode{}
    firstTail,secondTail := first,second
    split := x
    // 进行分割
    for cur := head;cur!= nil;{
        if cur.Val < split {
            // 添加到first链表
            tmp := cur
            cur = cur.Next
            tmp.Next = nil
            firstTail.Next = tmp
            firstTail = tmp
        } else {
            // 添加到second链表
            tmp := cur
            cur = cur.Next
            tmp.Next = nil
            secondTail.Next = tmp
            secondTail = tmp
        }
    }
    
    // 两个链表拼接
    firstTail.Next = second.Next
    return first.Next
}

561. 数组拆分 I[简单]

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:

n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].
通过次数44,248提交次数61,688

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-partition-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

排序，奇数位肯定是最小的。并且排序之后，两个数之间的损失是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
func arrayPairSum(nums []int) int {
    // 排序
    sort.Ints(nums)
    // 奇数位相加
    sum := 0
    for i:=0;i<len(nums);i++{
        if i % 2 == 0 {
            sum += nums[i]
        }
    }
    return sum
}

532. 数组中的K-diff数对[简单]

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

示例 1:

输入: [3, 1, 4, 1, 5], k = 2
输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。
示例 2:

输入:[1, 2, 3, 4, 5], k = 1
输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:

输入: [1, 3, 1, 5, 4], k = 0
输出: 1
解释: 数组中只有一个 0-diff 数对，(1, 1)。
注意:

数对 (i, j) 和数对 (j, i) 被算作同一数对。
数组的长度不超过10,000。
所有输入的整数的范围在 [-1e7, 1e7]。
通过次数18,122提交次数52,306

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-diff-pairs-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

参考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func findPairs(nums []int, k int) int {
if k < 0 {
        return 0
    }
    numsHas := make(map[int]bool)
    diffHas := make(map[int]bool)

    for _, num := range nums {
        if numsHas[num - k] {
            diffHas[num - k] = true
        }
        if numsHas[num + k] {
            diffHas[num] = true
        }
        numsHas[num] = true
    }
    return len(diffHas)

// 作者：xiaoma_nmg
// 链接：https://leetcode-cn.com/problems/k-diff-pairs-in-an-array/solution/onjie-fa-by-xiaoma_nmg/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

}

566. 重塑矩阵[简单]

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1:

输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:

输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意：

给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。
通过次数20,627提交次数31,767

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reshape-the-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

如果重塑之后的r*c的值不等于原有数组的值。那么,那么返回原来的数组。接下来,将原数组的数据给解开,放入队列中。再一个一个的填充进新的数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func matrixReshape(nums [][]int, r int, c int) [][]int {
    row := len(nums)
    column := len(nums[0])
    if r * c != row * column {
        return nums
    }
    list := []int{}
    for _,rowItem := range nums {
        for _,columnItem := range rowItem {
            list = append(list,columnItem)
        }
    }
    count := 0
    reNums := make([][]int,r)
    for i:=0;i<r;i++ {
        colNum := make([]int,c)
        for j:=0;j<c;j++{
            colNum[j] = list[count]
            count ++
        }
        reNums[i] = colNum
    }
    return reNums
}

581. 最短无序连续子数组[简单]

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :

输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
通过次数35,471提交次数101,719

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

克隆原来的数组，然后将新的数组排序。然后从前往后找不一致的子数组。如果没有找到，说明原本的数组已经是递增了。

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
func findUnsortedSubarray(nums []int) int {
    newNum := make([]int,len(nums))
    for i,num := range nums {
        newNum[i] = num
    }
    sort.Ints(newNum)
    // fmt.Println(nums)
    // fmt.Println(newNum)
    head := 0
    for i,num := range nums {
        if num != newNum[i] {
            head = i
            break
        }
        // 没有找到数据差异的
        if i+1 == len(newNum){
            return 0
        }
    }
    tail := len(nums) -1
    for i:=tail;i>=0;i--{
        if nums[i] != newNum[i] {
            tail = i
            break
        }
    }
    return tail - head + 1
}

605. 种花问题[简单]

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。
通过次数31,893提交次数99,263

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/can-place-flowers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

在原数组的基础上前后加0,连续出现3个0便在中间种花，前后加0之后可以少考虑边界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func canPlaceFlowers(flowerbed []int, n int) bool {
    f := append([]int{0},append(flowerbed,0)...)
    count := 0
    for i := 1;i <len(f)-1;i++ {
        if count == n {
            return true
        }
        if f[i-1] == 0 && f[i] == 0 && f[i+1] == 0 {
            count ++
            f[i] = 1
        }
    }
    return count == n
}

628. 三个数的最大乘积[简单]

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1:

输入: [1,2,3]
输出: 6
示例 2:

输入: [1,2,3,4]
输出: 24
注意:

给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
通过次数24,532提交次数48,652

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#####

1
2
3
4
5
6
7
8
9
10
11
12
13
func maximumProduct(nums []int) int {
    length := len(nums)
    if length < 3 {
        return 0
    }
    sort.Ints(nums)
    result := nums[length-1] * nums[length -2] * nums[length-3]
    if result < nums[0] * nums[1] * nums[length -1] {
        // 考虑负数的情况,最小的两个负数和最大的正数积
        return nums[0] * nums[1] * nums[length -1]
    }
    return result
}

143. 重排链表[中等]

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
通过次数35,105提交次数62,182

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一

将链表从中间分割成两个，后面的链表指针倒置。
然后前后两个链表重新连接。

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
func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil {
        return
    }
    // 分割 倒序 重连
    // 寻找中间节点
    slow,fast := head,head
    for ;fast != nil && fast.Next != nil;{
        fast = fast.Next.Next
        slow =slow.Next
    }
    // 从中间分割
    cur := slow.Next
    slow.Next = nil
    // 后面的链表倒置
    var newListHead *ListNode = nil
    for ; cur != nil;{
        tmp := cur
        cur = cur.Next
        tmp.Next = nil
        tmp.Next = newListHead
        newListHead = tmp
    }
    // 连接
    cur = head
    for cur2 := newListHead;cur2 != nil;{
        temp := cur2
        cur2 = cur2.Next
        temp.Next = cur.Next
        cur.Next = temp
        cur = cur.Next.Next
    }
}
思路二

将链表数据取出放置切片中。然后再分别取出对应的值进行重连。相较于方法一，使用额外的空间o(n)。

643. 子数组最大平均数 I[简单]

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例 1:

输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75  

注意:

1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。
通过次数18,433提交次数47,162

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-average-subarray-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

加上前面就减去后面，往后滑动，取最大值。最后除k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func findMaxAverage(nums []int, k int) float64 {
    sum := 0
    max := math.MinInt64
    for i:=0;i<k;i++{
        sum += nums[i]
    }
    if sum > max{
        max = sum
    }
    for i := k;i < len(nums);i++{
        sum += nums[i]
        sum = sum - nums[i-k]
        if sum > max {
            max = sum
        }
    }
    return float64(max) / float64(k)
}
20. 有效的括号[简单]

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true
通过次数389,566提交次数908,398

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

括号入栈,匹配出栈。最后栈为空说明匹配完成。否则不能匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isValid(s string) bool {
   stack := make([]int32,len(s))
    top := -1
    for _,c := range s {
       if top == -1 {
           top ++
           stack[top] = c
       }else{
            // '(' ')' '{' '}' '[' ']' 
           if (stack[top] == '(' && c == ')') || (stack[top] == '{' && c == '}') || (stack[top] == '[' && c == ']') {
               top --
           }else{
               top ++
               stack[top] = c
           }
       }
    }
    return top < 0
}

155. 最小栈[简单]

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。  

示例:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.  

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

双栈,其中一个只放最小的值。

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
type MinStack struct {
    Val []int
    Min []int
    TopVal int
}


/** initialize your data structure here. */
func Constructor() MinStack {
    stack := MinStack{
        Val : []int{},
        Min : []int{},
        TopVal : 0,
    }
    stack.Val = append(stack.Val,-1)
    stack.Min = append(stack.Min,math.MinInt32)
    return stack
}


func (this *MinStack) Push(x int)  {
    if this.TopVal == 0{
        this.Min = append(this.Min,x)
    }else if x < this.Min[this.TopVal] {
        this.Min = append(this.Min,x)
    }else{
        this.Min = append(this.Min,math.MinInt32)
        this.Min[this.TopVal + 1] = this.Min[this.TopVal]
    }
    this.TopVal += 1
    this.Val = append(this.Val,x)
}

func (this *MinStack) Pop()  {
    this.TopVal -= 1
    this.Val = this.Val[:this.TopVal + 1]
    this.Min = this.Min[:this.TopVal + 1]
}


func (this *MinStack) Top() int {
    return this.Val[this.TopVal]
}


func (this *MinStack) GetMin() int {
    return this.Min[this.TopVal]
}


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

13. 罗马数字转整数[简单]

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: “III”
输出: 3
示例 2:

输入: “IV”
输出: 4
示例 3:

输入: “IX”
输出: 9
示例 4:

输入: “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
通过次数245,410提交次数395,474

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法
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
func romanToInt(s string) int {
    sum := 0
    pre := 0
    for i,v := range s{
        if i == 0{
            pre = getNum(v)
        }else{
            num := getNum(v)
            if pre < num {
                sum -= pre
            }else{
                sum += pre
            }
            pre = num
        }
    }
    sum += pre
    return sum
}
func getNum(c int32) int {
    switch c {
    case 'I':
        return 1
    case 'V':
        return 5
    case 'X':
        return 10
    case 'L':
        return 50
    case 'C':
        return 100
    case 'D':
        return 500
    case 'M':
        return 1000
    default:
        return 0
    }
}

661. 图片平滑器[简单]

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

示例 1:

输入:
[[1,1,1],
[1,0,1],
[1,1,1]]
输出:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
注意:

给定矩阵中的整数范围为 [0, 255]。
矩阵的长和宽的范围均为 [1, 150]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/image-smoother
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

遍历，计算上下左右取平均值。需要赋给新的数组，不能在原有的数组中进行更改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func imageSmoother(M [][]int) [][]int {
    row := len(M)
    column := len(M[0])
    re := make([][]int,row)
    for i:=0;i<row;i++{
        re[i] = make([]int,column)
        for j := 0; j < column; j++ {
            count := 0
            sum := 0
            // 获得周围8格的数据
            for i1:=-1; i1 < 2; i1 ++{
                for j1:=-1;j1 < 2;j1++{
                    if i1 + i >= 0 && i1 + i < row  && j1 + j >= 0 && j1+ j < column{
                        sum += M[i1+i][j1+j]
                        count ++
                    }
                }
            }
            // 除以平均数
             re[i][j] = int(math.Floor(float64(sum) / float64(count)))
        }
    }
    return re
}

665. 非递减数列[简单]

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

 

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。  

说明：

1 <= n <= 10 ^ 4

  • 10 ^ 5 <= nums[i] <= 10 ^ 5
    通过次数25,155提交次数111,287

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-decreasing-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

设一个变量count用于计数，统计需要修改的元素的个数
设curIndex为下标，找到nums[curIndex] > nums[curIndex+1]的元素位置，其可以继续向前遍历case有以下几种：

[4,2,3]，curIndex的左边没有元素了
[2,4,2,3]，curIndex左边有元素，并且满足nums[curIndex - 1] <= nums[curIndex + 1]
[2,3,4,2]，curIndex右边的元素是最后一个
[2,3,4,3,4]，curIndex右边的元素不是最后一个，但是满足nums[curIndex] <= nums[curIndex + 2]
满足以上条件，则可以进行count统计，否则直接返回false，自增count后也要检查count > 1的情况
curIndex的上界为len(nums) - 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func checkPossibility(nums []int) bool {
    if len(nums) <= 1 {
        return true
    }

    count := 0
    for i := 0; i < len(nums) - 1; i++ {
        if nums[i] > nums[i + 1] {
            if i - 1 < 0 || (i - 1 >= 0 && nums[i - 1] <= nums[i + 1]) || 
            (i + 2 >= len(nums) || (i + 2 < len(nums) && nums[i] <= nums[i + 2])) {
                count++
                if count > 1 {
                    return false
                }
            } else {
                return false
            }
        }
    }
    return true
}

作者：jihonghe
链接：https://leetcode-cn.com/problems/non-decreasing-array/solution/jian-ji-ming-liao-yi-kan-jiu-dong-guan-jian-jiu-sh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路二

@码不停题
/*思路： 看了很多解析，没有讲的很明白的，自己整理了下思路，并配上例子，希望能够讲明白些。 提交结果运行时间超过了100%的人。

这道题给了我们一个数组，说我们最多有1次修改某个数字的机会，
问能不能将数组变为非递减数组。题目中给的例子太少，不能覆盖所有情况，我们再来看下面三个例子：
4，2，3
-1，4，2，3
2，3，3，2，4
我们通过分析上面三个例子可以发现，当我们发现后面的数字小于前面的数字产生冲突后，
[1]有时候需要修改前面较大的数字(比如前两个例子需要修改4)，
[2]有时候却要修改后面较小的那个数字(比如前第三个例子需要修改2)，
那么有什么内在规律吗？是有的，判断修改那个数字其实跟再前面一个数的大小有关系，
首先如果再前面的数不存在，比如例子1，4前面没有数字了，我们直接修改前面的数字为当前的数字2即可。
而当再前面的数字存在，并且小于当前数时，比如例子2，-1小于2，我们还是需要修改前面的数字4为当前数字2；
如果再前面的数大于当前数，比如例子3，3大于2，我们需要修改当前数2为前面的数3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func checkPossibility(nums []int) bool {
    if len(nums) <=1 {
        return true
    }
    count := 0
    for i:=1;i<len(nums) && count < 2;i ++{
        if nums[i-1] <= nums[i]{
            continue
        }
        count ++
        if i-2 >=0 &&nums[i-2] > nums[i] {
            nums[i] = nums[i-1]
        }else {
            nums[i -1] = nums[i]
        }
    }
    return count <= 1
}

496. 下一个更大元素 I[简单]

给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

 

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
  对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。  

提示：

nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

先在num2中计算每个值得下一个大于它得数，然后将对应得映射结果放置于map中。然后遍历num1,从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
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    
    // 先计算num2每个元素更大的
    indexMap := make(map[int]int)
    for i:=0;i<len(nums2);i++{
        search := false
        for j:=i+1;j<len(nums2);j++{
            if nums2[j] > nums2[i] {
                indexMap[nums2[i]] = nums2[j]
                search = true
                break
            }
        }
        if !search{
            indexMap[nums2[i]] = -1
        }
    }
    ret := []int{}
    for _,v := range nums1{
       mv,_ := indexMap[v]
       ret = append(ret,mv)
    }
    return ret
}

682. 棒球比赛[简单]

你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
2. “+”（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. “D”（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. “C”（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。

每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。

示例 1:

输入: [“5”,”2”,”C”,”D”,”+”]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
示例 2:

输入: [“5”,”-2”,”4”,”C”,”D”,”9”,”+”,”+”]
输出: 27
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。
注意：

输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/baseball-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

将每一轮的结果入栈，如果无效就出栈。每一次操作都会影响到栈的数据。

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
func calPoints(ops []string) int {
    stack := make([]int,len(opts))
    re := 0
    top := -1
    for _,v := range ops{
        //fmt.Println(v)
        switch v {
        case "C":
            re -= stack[top]
            top --
            
        case "D":
            tmp := 2 * stack[top]
            top ++
            stack[top] = tmp
            re += tmp
        case "+":
            tmp1 := stack[top]
            tmp2 := 0
            if top > 0 {
                top --
                tmp2 = stack[top]
                top ++
            }
            top ++
            stack[top] = tmp1 + tmp2
            re = re + tmp1 + tmp2
        default:
            d,_ := strconv.Atoi(v)
            top ++
            stack[top] = d
            re += d
        }
    }
    return re
}

844. 比较含退格的字符串[简单]

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：

输入：S = “ab##”, T = “c#d#”
输出：true
解释：S 和 T 都会变成 “”。
示例 3：

输入：S = “a##c”, T = “#a#c”
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：

输入：S = “a#c”, T = “b”
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。  

提示：

1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 ‘#’。  

进阶：

你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？  

通过次数26,064提交次数51,129

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

双栈,不是#入栈,是#出栈。最后比较两个栈的大小。

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
func backspaceCompare(S string, T string) bool {
    stack1 := make([]rune,len(S))
    stack2 := make([]rune,len(T))
    top1,top2 := -1,-1
    for _,v := range S {
        if '#' == v{
            if top1 >= 0{
                top1 --
            }
        }else{
            top1 ++
            stack1[top1] = v
        }
    }
    for _,v := range T {
        if '#' == v {
            if top2 >= 0 {
                top2 --
            }
        }else{
            top2 ++
            stack2[top2] = v
        }
    }
    if top1 == top2 {
        for ;top1 >= 0;top1--{
            if stack1[top1] != stack2[top1] {
                return false
            }
        }
        return true
    }
    return false
}

1021. 删除最外层的括号[简单]

有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

 

示例 1：

输入：”(()())(())”
输出：”()()()”
解释：
输入字符串为 “(()())(())”，原语化分解得到 “(()())” + “(())”，
删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。
示例 2：

输入：”(()())(())(()(()))”
输出：”()()()()(())”
解释：
输入字符串为 “(()())(())(()(()))”，原语化分解得到 “(()())” + “(())” + “(()(()))”，
删除每个部分中的最外层括号后得到 “()()” + “()” + “()(())” = “()()()()(())”。
示例 3：

输入：”()()”
输出：””
解释：
输入字符串为 “()()”，原语化分解得到 “()” + “()”，
删除每个部分中的最外层括号后得到 “” + “” = “”。  

提示：

S.length <= 10000
S[i] 为 “(“ 或 “)”
S 是一个有效括号字符串
通过次数36,402提交次数46,845
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-outermost-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

如何寻找最外层的括号对。当栈中只有一个’(‘这样匹配到’)’时。这个就是最外层。因为最外层的括号组是最垫底的。所以,将不是最外层的括号队保存起来打印便可以了。

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
func removeOuterParentheses(S string) string {
    stack := make([]rune,len(S))
    s := make([]rune,len(S))
    index := -1
    top := -1
    //re := ""
    for _,v := range S{
        if v == '('{
            if  top >= 0 {
                // 不是最外层括号,需要打印出
                //re += "("
                index ++
                s[index] = '('
                //是最外层括号,只要进栈
            }
            top ++
            stack[top] = v
        }else {
            if top > 0 {
                // 打印非最外层
                //re += ")"
                index ++
                s[index] = ')'
            }
            top --
        }
    }
    return string(s[:index+1])
}

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

 

示例：

输入：”abbaca”
输出：”ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。  

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。
通过次数25,549提交次数37,292

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

入栈，相同出栈，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func removeDuplicates(S string) string {
    // 入栈,相同出栈
    stack := make([]rune,len(S))
    top := -1
    for _,v := range S{
        if top < 0{
            top++
            stack[top] = v
        }else{
            if stack[top] == v {
                top --
            }else{
                top++
                stack[top] = v
            }
        }
    }
    return string(stack[:top+1])
}

1441. 用栈操作构建数组[简单]

给你一个目标数组 target 和一个整数 n。每次迭代，需要从  list = {1,2,3…, n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target ：

Push：从 list 中读取一个新元素， 并将其推入数组中。
Pop：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

 

示例 1：

输入：target = [1,3], n = 3
输出：[“Push”,”Push”,”Pop”,”Push”]
解释：
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]
示例 2：

输入：target = [1,2,3], n = 3
输出：[“Push”,”Push”,”Push”]
示例 3：

输入：target = [1,2], n = 4
输出：[“Push”,”Push”]
解释：只需要读取前 2 个数字就可以停止。
示例 4：

输入：target = [2,3,4], n = 4
输出：[“Push”,”Pop”,”Push”,”Push”,”Push”]  

提示：

1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target 是严格递增的
通过次数8,958提交次数13,851

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/build-an-array-with-stack-operations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

将寻找target的操作入栈便可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func buildArray(target []int, n int) []string {
    indexTarget := 0
    stack := []string{}
    for i:=1;i <= n;i++{
        stack = append(stack,"Push")
        if target[indexTarget] != i {
            stack = append(stack,"Pop")
        }else{
            indexTarget ++
        }
        if indexTarget == len(target) {
            break
        }
    }
    return stack
}

1544. 整理字符串[简单]

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：

0 <= i <= s.length - 2
s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。

 

示例 1：

输入：s = “leEeetcode”
输出：”leetcode”
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 “leEeetcode” 缩减为 “leetcode” 。
示例 2：

输入：s = “abBAcC”
输出：””
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
“abBAcC” –> “aAcC” –> “cC” –> “”
“abBAcC” –> “abBA” –> “aA” –> “”
示例 3：

输入：s = “s”
输出：”s”  

提示：

1 <= s.length <= 100
s 只包含小写和大写英文字母
通过次数7,811提交次数16,725

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/make-the-string-great
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

大小写相邻出栈，最后留在栈中的数据便是留下来的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func makeGood(s string) string {
    // 满足相邻是大小写的,去掉
    if "" == s {
        return s
    }
    stack := make([]rune,len(s))
    top := -1
    for _,v := range s {
        if top <= -1 {
            top ++
            stack[top] = v
        }else{
            if stack[top] - v == 32 || stack[top] - v == -32 {
                top --
            }else{
                top ++
                stack[top] = v
            }
        }
    }
    return string(stack[:top + 1])
}

剑指 Offer 09. 用两个栈实现队列[简单]

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

 

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
通过次数88,803提交次数121,594

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

出栈,将数据放到另一个栈中。到栈顶之后出栈,然后将临时栈放回原来的栈。

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
type CQueue struct {
    stack []int
    top int
}


func Constructor() CQueue {
    return CQueue{stack:make([]int,10000),top:-1}
}


func (this *CQueue) AppendTail(value int)  {
    this.top ++
    this.stack[this.top] = value
}


func (this *CQueue) DeleteHead() int {
    tmp := make([]int,this.top + 1)
    tmp_top := -1
    for i := this.top;i > 0;i--{
        tmp_top ++
        tmp[tmp_top] = this.stack[this.top]
        this.top --
    }
    ret := -1
    if this.top == -1 {
        return ret
    }else{
        ret = this.stack[this.top]
        this.top --
        for i:=tmp_top; i >= 0; i--{
            this.top ++
            this.stack[this.top] = tmp[i]
        }
    }
    return ret
}


/**
 * Your CQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AppendTail(value);
 * param_2 := obj.DeleteHead();
 */

剑指 Offer 30. 包含min函数的栈[简单]

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

 

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.  

提示：

各函数的调用总次数不超过 20000 次  

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

通过次数39,358提交次数68,616
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路
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
type MinStack struct {
    minStack []int
    min_top int
    stack []int
    stack_top int
}


/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        minStack: make([]int,20000),
        min_top: -1,
        stack: make([]int,20000),
        stack_top: -1,
    }
}


func (this *MinStack) Push(x int)  {
    if (this.min_top == -1){
        this.min_top ++
        this.minStack[this.min_top] = x
    }else if x < this.minStack[this.min_top] {
        this.min_top ++
        this.minStack[this.min_top] = x
    }else {
        this.min_top ++
        tmp := this.min_top -1
        this.minStack[this.min_top] = this.minStack[tmp]
    }
    this.stack_top ++
    this.stack[this.stack_top] = x
}


func (this *MinStack) Pop()  {
    this.min_top --
    this.stack_top --
}


func (this *MinStack) Top() int {
    return this.stack[this.stack_top]
}


func (this *MinStack) Min() int {
    return this.minStack[this.min_top]
}


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Min();
 */

面试题 03.04. 化栈为队[简单]

实现一个MyQueue类，该类用两个栈来实现一个队列。

示例：

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明：

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
通过次数9,923提交次数13,970

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

双栈,互相倒腾。

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
type MyQueue struct {
    top int
    stack []int
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{
        top: -1,
        stack: make([]int,1000),
    }
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.top ++
    this.stack[this.top] = x
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    tmp := make([]int,this.top + 1)
    tmp_top := -1
    for i := this.top;i > 0;i--{
        tmp_top ++
        tmp[tmp_top] = this.stack[this.top]
        this.top --
    }
    ret := -1
    if this.top == -1 {
        return ret
    }else{
        ret = this.stack[this.top]
        this.top --
        for i:=tmp_top; i >= 0; i--{
            this.top ++
            this.stack[this.top] = tmp[i]
        }
    }
    return ret
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    tmp := make([]int,this.top + 1)
    tmp_top := -1
    for i := this.top;i > 0;i--{
        tmp_top ++
        tmp[tmp_top] = this.stack[this.top]
        this.top --
    }
    ret := -1
    if this.top == -1 {
        return ret
    }else{
        ret = this.stack[this.top]
        // this.top --
        for i:=tmp_top; i >= 0; i--{
            this.top ++
            this.stack[this.top] = tmp[i]
        }
    }
    return ret
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return this.top == -1
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

67. 二进制求和[简单]

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

 

示例 1:

输入: a = “11”, b = “1”
输出: “100”
示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”  

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。
通过次数126,044提交次数231,699

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

跟链表的数字求和一样,拿出数据相加之后产生进位,需要在最后面处理进位。

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
func addBinary(a string, b string) string {
    aBit := make([]int,len(a))
    bBit := make([]int,len(b))
    stack := make([]int,len(a)+len(b))
    top := -1
    for i, v := range a {
       d,_ := strconv.Atoi(string(v))
       aBit[i] = d
    }
    for i, v := range b {
        d,_ := strconv.Atoi(string(v))
        bBit[i] = d
    }
    i,j := len(a)-1,len(b)-1
    
    tmpa := aBit[0]
    tmpb := bBit[0]
    carry := 0
    for i >= 0 || j >=0 {
        if i < 0 {
            tmpa = 0
        }else{
            tmpa = aBit[i]
        }
        if j < 0 {
            tmpb = 0
        }else {
            tmpb = bBit[j]
        }
        sum := tmpa + tmpb + carry
        carry = sum / 2
        top ++
        stack[top] = sum % 2
        i --
        j --
    }
    if carry > 0 {
        top ++
        stack[top] = carry
    }
    ret := make([]rune,top+1)
    stack_size := top
    for top >= 0 {
        ret[stack_size - top] = rune(48 + stack[top])
        top --
    }
    return string(ret[:stack_size + 1])
}

125. 验证回文串[简单]

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
示例 2:

输入: “race a car”
输出: false
通过次数162,296提交次数350,208

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

数字和字母入栈,出栈和顺序读取的一致(忽略大小写)
注意:字母和数字必须分开处理,比如"0P",两者相差绝对值也是32,和A-a相差一样。数字只需要比较大小相等与否便可。但是字母类型必须比较大小写。

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
func isPalindrome(s string) bool {
   if "" == s {
        return true
    }
    stack := make([]rune,len(s))
    top := -1
    
    tmp_s := make([]rune,len(s))
    index_tmp := -1
    for _,v := range s {
        if (v >= '0' && v <= '9') || (v >= 'a' && v <='z') || (v >='A' && v <= 'Z') {
            top ++
            stack[top] = v
            
            index_tmp ++
            tmp_s[index_tmp] = v
        }
    }
    
    for i:=0;i<= top;i++{
        v := tmp_s[i]
        tmp := stack[top - i]
        if (v >= 'a' && v <='z') || (v >='A' && v <= 'Z') {
            sub := math.Abs(float64(tmp - v))
            if sub == 0 || sub == 32{
                continue
            }else {
                return false
            }
        }else{
            if v == tmp {
                continue
            }
            return false
        }
    }
    return true
}

14. 最长公共前缀[简单]

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

通过次数360,414提交次数929,974

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归,如果传进来的字符串数组刚好是2个,求出这两个的公共前缀。当传进的字符串数组的元素大于2的时候。先求出前两个字符串的公共前缀,然后再和剩余的组成新的字符串数组。再次调用求最长前缀的函数。注意递归出口。

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
func longestCommonPrefix(strs []string) string {
    prefix := ""
    if len(strs) == 0 {
        return ""
    }
    if len(strs) == 1 {
        return strs[0]
    }
    if len(strs) == 2 {
        first := strs[0]
        second := strs[1][:]
        for i,v := range first {
            if i < len(second){
                if uint8(v) == second[i] {
                    prefix += string(v)
                }else{
                    break
                }
            }else{
                break
            }
        }
        return prefix
    }
    prefix = longestCommonPrefix(strs[:2])
    return longestCommonPrefix(append([]string{prefix},strs[2:]...))
}

28. 实现 strStr()[简单]

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2
示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1
说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

通过次数232,332提交次数584,964

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

两个循环进行对比,效率有点低。

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
func strStr(haystack string, needle string) int {
    if "" == needle {
        return 0
    }
    // 思路,for循环,比较needle。完全匹配才可以
    needle_ := needle[:]
    haystack_ := haystack[:]
    for i:=0;i<len(haystack);i++{
        v := haystack_[i]
        if v == needle_[0]{
            // 开始进行匹配
            j := i
            index_needle := 0
            for index_needle < len(needle) && j < len(haystack) {
                if index_needle == len(needle) -1 && needle_[index_needle] == haystack_[j] {
                    return i
                }
                if haystack_[j] != needle_[index_needle]  {
                    break
                }else{
                    j ++
                    index_needle ++
                }
            }
        }
    }
    return -1
}

剑指 Offer 59 - I. 滑动窗口的最大值[简单]

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7  

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

通过次数47,099提交次数106,161

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

大小为k的队列,出队和入队完成窗口滑动。

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
func Max(nums []int) int {
    max := math.MinInt32
    for _,v := range nums {
        if v > max {
            max = v
        }
    }
    return max
}
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) <= 0 {
        return []int{}
    }
    if len(nums) <= k {
        return []int{Max(nums)}
    }
    slideWindows := make([]int,k)
    baseMax := math.MinInt32
    ret := make([]int, len(nums) - k + 1)
    retIndex := 0
    for i:=0;i<k && i <len(nums);i++{
        if nums[i] > baseMax {
            baseMax = nums[i]
        }
        slideWindows[i] = nums[i]
    }
    ret[retIndex] = baseMax
    for i:=k;i<len(nums);i++{
        slideWindows = append(slideWindows[1:],nums[i])
        baseMax = Max(slideWindows)
        retIndex ++
        ret[retIndex] = baseMax
    }
    return ret
}

202. 快乐数[简单]

编写一个算法来判断一个数 n 是不是快乐数。

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

 

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
通过次数99,131提交次数163,443
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/happy-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

不是快乐数的数称为不快乐数（unhappy number），所有不快乐数的数位平方和计算，最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。最后出现重复值的就不是快乐数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isHappy(n int) bool {
    strn := strconv.FormatInt(int64(n),10)
    result := 0
    for _,v := range strn{
        tmp,_ := strconv.Atoi(string(v))
        result += tmp * tmp
    }
    if result == 1 {
        return true
    }else if result == 4 {
        return false
    }
    return isHappy(result)
}

38. 外观数列[简单]

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
    第一项是数字 1

描述前一项，这个数是 1 即 “一个 1 ”，记作 11

描述前一项，这个数是 11 即 “两个 1 ” ，记作 21

描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211

描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221

 

示例 1:

输入: 1
输出: “1”
解释：这是一个基本样例。
示例 2:

输入: 4
输出: “1211”
解释：当 n = 3 时，序列是 “21”，其中我们有 “2” 和 “1” 两组，”2” 可以读作 “12”，也就是出现频次 = 1 而 值 = 2；类似 “1” 可以读作 “11”。所以答案是 “12” 和 “11” 组合在一起，也就是 “1211”。
通过次数130,187提交次数230,716
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-and-say
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

当前n输出的应该是n-1字符串相同的字符个数。
1 => “1”
2 => 数1,”1”。有1个字符”1”,所以输出为:”11”
3 => 数2,”11”。有2个字符”1”,所以输出”21”
4 => 数3,”21”。有1个字符”2”,1个字符”1”。所以输出”1211”
就是数上一个数字字符串中各个字符的个数。

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
func countAndSay(n int) string {
    if n <= 1 {
        return "1"
    }
    result := ""
    tmpStr := countAndSay(n - 1)
    tmp := tmpStr[:]
    count := 0
    tmpChar := tmp[0]
    // 数数
    for i := 0; i < len(tmp); i++{
        if tmpChar == tmp[i] {
            // 相同数字继续数
            count ++
        }else{
            // 出现不同
            result += strconv.Itoa(count) + string(tmpChar)
            tmpChar = tmp[i]
            count = 1
        }
    }
    if count > 0 {
        result += strconv.Itoa(count) + string(tmpChar)
    }
    return result
}

69. x 的平方根[简单]

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
  由于返回类型是整数，小数部分将被舍去。
通过次数204,672提交次数526,469

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

牛顿迭代法,二分法
二分法

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
func mySqrt(x int) int {
    if x == 1 {
        return 1
    }
    half := x/2
    start := 1
    end := half
    mid :=  (start + end) / 2
    for i:=1;i <= 1000;i++{
        if start * start == x {
            return start
        }
        if end * end == x {
            return end
        }
        if start*start < x && end * end > x && end - start == 1 {
            return start
        }
        mid = (start + end) / 2
        if mid * mid < x {
            start = mid
        }else {
            end = mid
        }
    }
    return half
}

204. 计数质数[简单]

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
通过次数77,573提交次数220,066

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

厄拉多塞筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countPrimes(int n) {
        int result = 0;
        boolean[] b = new boolean[n];   // 初始化默认值都为 false，为质数标记
        if(2 < n) result++; // 如果大于 2 则一定拥有 2 这个质数
        
        for(int i = 3; i < n; i += 2){  // 从 3 开始遍历，且只遍历奇数
            if(!b[i]){  // 是质数
                for(int j = 3; i * j < n; j += 2){
                    b[i * j] = true;    // 将当前质数的奇数倍都设置成非质数标记 true
                }
                result++;   // 质数个数 +1
            }
        }
        return result;
    }
}

作者：cang-lang-a
链接：https://leetcode-cn.com/problems/count-primes/solution/ting-shuo-zhe-jiao-e-la-duo-sai-shai-fa-zhi-xing-y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func countPrimes(n int) int {
    count := 0
    if n <= 2 {
        return 0
    }
    count ++
    arr := make([]bool,n)
    for i := 3;i < n;i += 2{
        if !arr[i] {
            for j:=3;i*j <n;j+= 2{
                arr[i*j] = true
            }
            count ++
        }
    }
    return count
}

5503. 所有奇数长度子数组的和[简单]

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
示例 2：

输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
示例 3：

输入：arr = [10,11,12]
输出：66

提示：

1 <= arr.length <= 100
1 <= arr[i] <= 1000

思路

滑动窗口,求值

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
func sumArray(arr []int) int {
    result := 0
    for _,v := range arr{
        result += v
    }
    return result
}
func sumOddLengthSubarrays(arr []int) int {
    result := 0
    if len(arr) <= 0 {
        return 0
    }
    // 设置滑动窗口
    slide_window := make([]int,1)
    slide_index := 0
    slide_size := 1
    for ;slide_size <= len(arr);slide_size += 2{
        slide_index = 0
        slide_window = make([]int,slide_size)
        for _,v := range arr {
            // 先填充滑动窗口
            if slide_index <= slide_size -1 {
                slide_window[slide_index] = v
                slide_index ++
            }
            if slide_index == slide_size {
                // 填满之后计算结果
                result += sumArray(slide_window)
                slide_window = append(slide_window[1:],0)
                slide_index -= 1
            }
        }
    }
    return result
}

687. 最长同值路径[简单]

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

          5
         / \
        4   5
       / \   \
      1   1   5

输出:

2
示例 2:

输入:

          1
         / \
        4   5
       / \   \
      4   4   5

输出:

2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

通过次数23,601提交次数56,484

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-univalue-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

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
var res int
func longestUnivaluePath(root *TreeNode) int {
    res = 0
    dfs(root, 0, 0)
    return res
}

func dfs(root *TreeNode, f int, path int) int {
    if root != nil {
        l := dfs(root.Left, root.Val, path)  //左树最长路径
        r := dfs(root.Right, root.Val, path) //右树最长路径
        res = max(r+l, res)                  //路径是否变长
        if f == root.Val {                   //相等时+1，并且选择l或r中最长路径
            return max(l, r) + 1
        }
    }
    return 0 //其他情况全部返回0
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}


// 作者：linbingyuan
// 链接：https://leetcode-cn.com/problems/longest-univalue-path/solution/kuai-bu-kuai-bu-zhi-dao-fan-zheng-dai-ma-gou-duan-/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5  

提示：

0 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

直接使用递归会超时，需要使用备忘录以空间换时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func fib(n int) int {
    if n <= 1{
        return n
    }
    nums := make([]int,n+1)
    for i:=0;i <= n;i++ {
        if i == 0 {
            nums[i] = 0
        }else if i == 1 {
            nums[i] = 1
        }else{
            nums[i] = nums[i-1]%1000000007 + nums[i-2]%1000000007
        }
    }

    return nums[n]%1000000007
}

相同类型有

剑指 Offer 10- II. 青蛙跳台阶问题[简单]

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/

 

通过次数63,046提交次数149,366

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func numWays(n int) int {
    if n == 0 {
        return 1
    }
    dp := make([]int,n+1)
    for i:=1;i<=n;i++{
        if i == 1{
            dp[i] = 1
        }else if i == 2 {
            dp[i] = 2
        }else{
            // 后面的情况
            dp[i] = (dp[i-1]%1000000007 + dp[i - 2]%1000000007)%1000000007
        }
    }
    return dp[n]%1000000007
}

面试题 08.06. 汉诺塔问题[简单]

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:

输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示:

A中盘子的数目不大于14个。
通过次数9,584提交次数14,970

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hanota-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func move(n int, A *[]int, B *[]int, C *[]int){
    if n == 0 {
        return
    }
    if n == 1 {
        // 一个盘子,只需要从A->C
        *C = append(*C,(*A)[len(*A)-1])
        (*A) = (*A)[:len(*A)-1]
    }else{
        // 2以上个盘子 A->B A->C B->C
        move(n-1,A,C,B)
        move(1,A,B,C)
        move(n-1,B,A,C)
    }
}
func hanota(A []int, B []int, C []int) []int {
    if A == nil{
        return nil
    }
    move(len(A),&A,&B,&C)
    return C
}

剑指 Offer 53 - II. 0～n-1中缺失的数字[简单]

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

 

示例 1:

输入: [0,1,3]
输出: 2
示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8  

限制：

1 <= 数组长度 <= 10000

通过次数57,830提交次数131,564

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于有序，可以使用二分法。但是也可以使用等差数列求和公式。减一下便可以直到缺什么了。

1
2
3
4
5
6
7
func missingNumber(nums []int) int {
    sum := 0
    for _,v := range nums {
        sum += v
    }
    return (len(nums)*(len(nums) + 1))/2 - sum
}
1
2
3
4
5
6
7
8
9
10
11
12
func missingNumber(nums []int) int {
    first,last,mid := 0,len(nums)-1,(len(nums)/2)
    for first <= last {
        mid = (first + last)/2
        if mid == nums[mid] {
            first = mid + 1
        }else{
            last = mid -1
        }
    }
    return first
}

100. 相同的树[简单]

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入: 1 1
/ \ /
2 3 2 3

    [1,2,3],   [1,2,3]

输出: true
示例 2:

输入: 1 1
/
2 2

    [1,2],     [1,null,2]

输出: false
示例 3:

输入: 1 1
/ \ /
2 1 1 2

    [1,2,1],   [1,1,2]

输出: false
通过次数143,280提交次数238,182

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归，判断根节点，再判断左右子树

1
2
3
4
5
6
7
8
9
10
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }else if p != nil && q != nil {
        if p.Val == q.Val {
            return isSameTree(p.Left,q.Left) && isSameTree(p.Right,q.Right)
        }
    }
    return false
}

101. 对称二叉树[简单]

给定一个二叉树，检查它是否是镜像对称的。

 

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1

/
2 2
/ \ /
3 4 4 3  

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1

/
2 2
\
3 3  

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

通过次数211,090提交次数398,394

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

和上一道题一样的思路。只是需要交换左右比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isSymmetricTrees(p *TreeNode,q *TreeNode) bool{
    if p ==nil && q == nil {
        return true;
    }else if p!= nil && q != nil {
        if  p.Val == q.Val {
            return isSymmetricTrees(p.Left,q.Right) && isSymmetricTrees(p.Right,q.Left)
        }
    }
    return false
}
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isSymmetricTrees(root.Left,root.Right)
}

104. 二叉树的最大深度[简单]

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3

/
9 20
/
15 7
返回它的最大深度 3 。

通过次数280,411提交次数373,575
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归，如果该节点为空，返回0。否则返回1+子节点最大深度

1
2
3
4
5
6
7
8
9
10
11
12
func max(a,b int) int{
    if a > b {
        return a
    }
    return b
}
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left),maxDepth(root.Right))
}

107. 二叉树的层次遍历 II[简单]

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回其自底向上的层次遍历为：

[
[15,7],
[9,20],
[3]
]
通过次数101,441提交次数150,113
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-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
func levelOrderBottom(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    ret := [][]int{}
    left := levelOrderBottom(root.Left)
    right := levelOrderBottom(root.Right)
    i,j := 0,0
    for i < len(left) || j < len(right) {
        layout := []int{}
        if (len(left)-1 - i) == (len(right)-1 - j) {
            layout = append(layout,left[i]...)
            layout = append(layout,right[j]...)
            ret = append(ret,layout)
            i ++
            j ++
        }else if (len(left)-1 - i) > (len(right)-1 - j){
            layout = append(layout,left[i]...)
            ret = append(ret,layout)
            i ++
        }else {
            layout = append(layout,right[j]...)
            ret = append(ret,layout)
            j ++
        }
        
    }
    ret = append(ret,[]int{root.Val})
    return ret
}
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
func levelOrderBottom(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    ret := [][]int{}
    left := levelOrderBottom(root.Left)
    right := levelOrderBottom(root.Right)
    i,j := 0,0
    for i < len(left) || j < len(right) {
        if (len(left)-1 - i) == (len(right)-1 - j) {
            ret = append(ret,append(left[i],right[j]...))
            i ++
            j ++
        }else if (len(left)-1 - i) > (len(right)-1 - j){
            ret = append(ret,left[i])
            i ++
        }else {
            ret = append(ret,right[j])
            j ++
        }
        
    }
    ret = append(ret,[]int{root.Val})
    return ret
}

112. 路径总和[简单]

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

经过每个非叶子节点,将sum值减去当前节点的值。如果在叶子节点中等于传进去的sum。说明,这条路径的值加起来是最开始的值。

1
2
3
4
5
6
7
8
9
10
func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil && root.Val == sum {        
        return true
    }
    target := sum - root.Val
    return hasPathSum(root.Left,target) || hasPathSum(root.Right,target)
}

113. 路径总和 II[中等]

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]
通过次数89,764提交次数147,351

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

和上一题一样,只不过需要找出所有可能。返回多值需要将当前节点写到递归的返回的所有数组的前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func pathSum(root *TreeNode, sum int) [][]int {
     if root == nil {
        return [][]int{}
    }
    if root.Left == nil && root.Right == nil && root.Val == sum {
        return [][]int{{root.Val}}
    }
    target := sum - root.Val
    left := pathSum(root.Left,target)
    right := pathSum(root.Right,target)
    ret := [][]int{}
    for i:= 0;i<len(left);i++{
        ret = append(ret,append([]int{root.Val},left[i]...))
    }
    for i:= 0;i<len(right);i++{
        ret = append(ret,append([]int{root.Val},right[i]...))
    }
    return ret
}

108. 将有序数组转换为二叉搜索树[简单]

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

  0
 / \

-3 9
/ /
-10 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

每次找中间的节点作为根,分到两边的高度不会超过1。

1
2
3
4
5
6
7
8
9
10
11
12
13
func sortedArrayToBST(nums []int) *TreeNode {
    return dfs(nums,0, len(nums) -1)
}
func dfs(nums []int, first int, last int) *TreeNode{
    if first > last {
        return nil
    }
    mid := (first +last) / 2
    root := TreeNode{Val: nums[mid]}
    root.Left = dfs(nums, first, mid -1)
    root.Right = dfs(nums,mid +1 ,last)
    return &root
}

111. 二叉树的最小深度[简单]

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回它的最小深度  2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

每次选择最小的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func min(x,y int) int {
    if x > y{
        return y
    }
    return x
}
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if nil == root.Left && nil == root.Right {
        return 1
    }
    minDep := math.MaxInt32
    if root.Left != nil {
        minDep = min(minDepth(root.Left), minDep)
    }
    if root.Right != nil{
        minDep =  min(minDepth(root.Right),minDep)
    }
    return minDep + 1
}

884. 两句话中的不常见单词[简单]

给定两个句子 A 和 B 。 （句子是一串由空格分隔的单词。每个单词仅由小写字母组成。）

如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。

返回所有不常用单词的列表。

您可以按任何顺序返回列表。

 

示例 1：

输入：A = “this apple is sweet”, B = “this apple is sour”
输出：[“sweet”,”sour”]
示例 2：

输入：A = “apple apple”, B = “banana”
输出：[“banana”]  

提示：

0 <= A.length <= 200
0 <= B.length <= 200
A 和 B 都只包含空格和小写字母。
通过次数12,606提交次数19,838

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/uncommon-words-from-two-sentences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

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
func uncommonFromSentences(A string, B string) []string {
    m1 := make(map[string]int)
    m2 := make(map[string]int)
    for _,v := range strings.Split(A, " ") {
        m1[v] += 1
    }
    for _,v := range strings.Split(B, " ") {
        m2[v] += 1
    }
    ret := []string{}
    for k,v := range m1 {
        if v == 1 {
            if _, ok := m2[k]; !ok{
                ret = append(ret,k)
            }
        }
    }
    for k,v := range m2 {
        if v == 1 {
            if _, ok := m1[k]; !ok{
                ret = append(ret,k)
            }
        }
    }
    return ret
}

205. 同构字符串[简单]

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = “egg”, t = “add”
输出: true
示例 2:

输入: s = “foo”, t = “bar”
输出: false
示例 3:

输入: s = “paper”, t = “title”
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/isomorphic-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

s->t 可以映射 t->s也可以完全映射才是同构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func mapping(s,t string) bool  {
    n := len(s)
    map1 := make(map[uint8]uint8)
    for i:=0 ;i< n;i ++{
        s1 := s[i]
        t1 := t[i]
        if _, ok := map1[s1];ok {
            if v,_ := map1[s1];v != t1 {
                return false
            }
        } else {
            map1[s1] = t1
        }
    }
    return true
}
func isIsomorphic(s string, t string) bool {
   return mapping(s, t) && mapping(t, s)
}

110. 平衡二叉树[简单]

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3

/
9 20
/
15 7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

   1
  / \
 2   2
/ \

3 3
/
4 4
返回 false 。

 

通过次数138,833提交次数254,069
在真实的面试中遇到过这道题？

是

否

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func abs(x int) int {
    if x < 0 {
        return -1 *x
    }
    return x
}
func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(height(root.Left), height(root.Right)) + 1
}
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }else{
        return (abs(height(root.Left) - height(root.Right)) <= 1) && isBalanced(root.Left) && isBalanced(root.Right)
    }
}

371. 两整数之和

不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

示例 1:

输入: a = 1, b = 2
输出: 3
示例 2:

输入: a = -2, b = 3
输出: 1
通过次数37,686提交次数66,902
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
func getSum(a int, b int) int {
    for b != 0 {
        tmp := a ^ b
        b = (a & b) << 1
        a = tmp
    }
    return a
}

374. 猜数字大小[简单]

猜数字游戏的规则如下：

每轮游戏，系统都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，系统会告诉你，你猜测的数字比系统选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1 : 你猜测的数字比系统选出的数字大
1 : 你猜测的数字比系统选出的数字小
0 : 恭喜！你猜对了！  

示例 :

输入: n = 10, pick = 6
输出: 6
通过次数32,082提交次数70,063

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

二分法，没啥好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func guessNumber(n int) int {
    first,last := 1, n
    mid := (first + last) / 2
    for first < last {
        if guess(mid) == 0 {
            return mid
        }else if guess(mid) > 0{
            first = mid + 1
        }else{
            last = mid - 1
        }
        mid = (first + last) / 2
    }
    return first
}

383. 赎金信[简单]

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

 

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
通过次数29,988提交次数54,438
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ransom-note
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

比较字母个数,杂志中各个字母的个数大于等于信中字母的个数肯定能够表达。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func canConstruct(ransomNote string, magazine string) bool {
     // 两个map,记录字母个数
    rMap := make(map[rune]int)
    mMap := make(map[rune]int)
    for _, v := range ransomNote {
        rMap[v] += 1
    }
    for _, v := range magazine {
        mMap[v] += 1
    }
    for k,v := range rMap{
        if mV,ok := mMap[k];ok && mV >= v{
        }else{
            return false
        }
    }
    return true
}

387. 字符串中的第一个唯一字符[简单]

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

 

示例：

s = “leetcode”
返回 0

s = “loveleetcode”
返回 2  

提示：你可以假定该字符串只包含小写字母。

通过次数103,747提交次数219,598
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

第一次循环,使用map记录字母出现的次数。第二次循环从头开始判断字母出现的次数。只出现一次的直接返回当前的字母的位置。

1
2
3
4
5
6
7
8
9
10
11
12
func firstUniqChar(s string) int {
    numMap:= make(map[rune]int)
    for _, v := range s {
        numMap[v] += 1
    }
    for i,v := range s {
       if n,_ := numMap[v]; n == 1 {
           return i
       }
    }
    return -1
}

344. 反转字符串[简单]

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

 

示例 1：

输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：

输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
通过次数213,050提交次数290,237
在真实的面试中遇到过这道题？

是

否

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

两个指针,一个指向末尾,一个指向头部。两个指针交换数据,并且相互靠拢。

1
2
3
4
5
6
7
8
9
10
11
func reverseString(s []byte)  {
    // 思路,一个指向末尾的指针，一个指向首个地址的指针。相互交换数据
    firstIndex,lastIndex := 0, len(s) -1
    for firstIndex < lastIndex {
        tmp := s[firstIndex]
        s[firstIndex] = s[lastIndex]
        s[lastIndex] = tmp
        firstIndex ++
        lastIndex --
    }
}

345. 反转字符串中的元音字母[简单]

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

 

示例 1：

输入：”hello”
输出：”holle”
示例 2：

输入：”leetcode”
输出：”leotcede”  

提示：

元音字母不包含字母 “y” 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

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
func isVowel(c rune) bool  {
    if c == 'a' || c=='A' || c == 'e' || c=='E'  || c == 'i' || c == 'I' || c == 'o' || c=='O' || c == 'u' || c=='U'{
        return true
    }
    return false
}
func reverseVowels(s string) string {
    sb := []rune(s)
    firstIndex,lastIndex := 0, len(sb) -1
    for firstIndex < lastIndex {
        if isVowel(sb[firstIndex]) && isVowel(sb[lastIndex]){
            tmp := sb[firstIndex]
            sb[firstIndex] = sb[lastIndex]
            sb[lastIndex] = tmp
            firstIndex ++
            lastIndex --
        }
        if !isVowel(sb[firstIndex]) {
            firstIndex ++
        }
        if !isVowel(sb[lastIndex]) {
            lastIndex --
        }
    }
    return string(sb)
}

415. 字符串相加[简单]

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

 

提示：

num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式
通过次数80,882提交次数156,004

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

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
func addStrings(num1 string, num2 string) string {
    // 从个位数开始相加,保存进位,一个个相加
    num1B := []rune(num1)
    num2B := []rune(num2)
    carry := 0
    l1,l2:= len(num1)-1,len(num2)-1
    resultB := []rune{}
    for l1 >= 0 || l2 >= 0 {
        tmp1 := 0
        tmp2 := 0
        if l1 >= 0 {
            tmp1,_ = strconv.Atoi(string(num1B[l1]))
            l1 --
        }
        if l2 >= 0 {
            tmp2, _ = strconv.Atoi(string(num2B[l2]))
            l2 --
        }
        result := (tmp1 + tmp2 + carry) % 10
        carry = (tmp1 + tmp2 + carry) / 10
        resultB = append([]rune{rune(result + '0')}, resultB...)
    }
    if carry > 0 {
        resultB = append([]rune{rune(carry + '0')}, resultB...)
    }
    return string(resultB)
}

434. 字符串中的单词数[简单]

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: “Hello, my name is John”
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 “Hello,” 算作 1 个单词。
通过次数23,778提交次数65,186

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-segments-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func countSegments(s string) int {
    num := 0
    if s == "" {
        return num
    }
    flag := false
    for _,v := range s {
        if v != ' ' && !flag {
            flag = true
            num ++
        }
        if v == ' ' {
            flag = false
        }
    }
    return num
}

459. 重复的子字符串[简单]

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: “abab”

输出: True

解释: 可由子字符串 “ab” 重复两次构成。
示例 2:

输入: “aba”

输出: False
示例 3:

输入: “abcabcabcabc”

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-substring-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解法

如果字符串由重复子串组成,那么重复的字串可以作为一种元素重复出现。假设s = nx,x为字串。(n+1)x组成中,含有两个s。第一个从0开始,第二次从len(x)-1开始。比如s = “abab”。其中x=”ab”。s = 2x = “abab”,(2 + 1)x=3x= “ababab”。这个字符串中含有2个s。”abab-ab”,”ab-abab”。

2s = 2(nx)=(n+n)x,破坏掉第一个字符,找到的字符串s的位置是后面新加进去的字符串，说明该字符串不是由子字符串重复组成。如果由字串重复组成的话,找到s的位置肯定不是新加进来的。
比如:
s = “aba”, 2s = “abaaba”,破坏掉第一个字符串=>”baaba”,这个字符串中找到s的位置是新加进去的字符串。
s = “abab”, 2s = “abababab”,破坏掉第一个字符=>”bababab”,这个字符串中找到s的位置是在”b-abab-ab”,在”bab-abab”新加进来的字符串前面。说明这个字符串s由重复的字串组成。

1
2
3
4
5
6
func repeatedSubstringPattern(s string) bool {
    if "" == s {
        return true
    }
    return strings.Index(string((s+s)[1:]), s) < len(s) -1
}

520. 检测大写字母[简单]

给定一个单词，你需要判断单词的大写使用是否正确。

我们定义，在以下情况时，单词的大写用法是正确的：

全部字母都是大写，比如”USA”。
单词中所有字母都不是大写，比如”leetcode”。
如果单词不只含有一个字母，只有首字母大写， 比如 “Google”。
否则，我们定义这个单词没有正确使用大写字母。

示例 1:

输入: “USA”
输出: True
示例 2:

输入: “FlaG”
输出: False
注意: 输入是由大写和小写拉丁字母组成的非空单词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/detect-capital
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

使用一个计数器和标记从头连续出现大写的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func detectCapitalUse(word string) bool {
    if len(word) <= 1 {
        return true
    }
    capitalNum := 0
    index := -1
    for i,v := range word{
        if v < 'a' {
            capitalNum ++
        }
        // 大写,只有第一个或者全为大写的时候才会变更index
        if v < 'a' && (i == 0 || i == index){
            index ++
        }
    }
    // 全大写,全小写,第一个为大写
    return capitalNum == len(word) || capitalNum == 0 || (capitalNum == 1 && index == 0)
}

521. 最长特殊序列 Ⅰ[简单]

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。

「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

 

示例 1：

输入: “aba”, “cdc”
输出: 3
解释: 最长特殊序列可为 “aba” (或 “cdc”)，两者均为自身的子序列且不是对方的子序列。
示例 2：

输入：a = “aaa”, b = “bbb”
输出：3
示例 3：

输入：a = “aaa”, b = “aaa”
输出：-1  

提示：

两个字符串长度均处于区间 [1 - 100] 。
字符串中的字符仅含有 ‘a’~’z’ 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-uncommon-subsequence-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func findLUSlength(a string, b string) int {
    if a == b {
        return -1
    }
    return max(len(a), len(b))
}

541. 反转字符串 II[简单]

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。  

示例:

输入: s = “abcdefg”, k = 2
输出: “bacdfeg”  

提示：

该字符串只包含小写英文字母。
给定字符串的长度和 k 在 [1, 10000] 范围内。
通过次数22,935提交次数41,100
在真实的面试中遇到过这道题

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

0k 2k 4k 6k作为起始元素,长度为k的区间进行反转。如果长度不够k的话使用剩余的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}
func reverseStr(s string, k int) string {
    // 按k分割, 0k 2k 4k 6k 8k 10k 反转
    ret := []byte(s)
    // ab cd ef g
    // 0  2  4  6
    for i :=0; i< len(ret) -1;i += 2*k {
        l,r := i, min(i + k -1, len(ret) -1)
        for l < r {
            tmp := ret[l]
            ret[l] = ret[r]
            ret[r] = tmp
            l ++
            r --
        }
    }
    return string(ret)
}

551. 学生出勤记录 I[简单]

给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：

‘A’ : Absent，缺勤
‘L’ : Late，迟到
‘P’ : Present，到场
如果一个学生的出勤记录中不超过一个’A’(缺勤)并且不超过两个连续的’L’(迟到),那么这个学生会被奖赏。

你需要根据这个学生的出勤记录判断他是否会被奖赏。

示例 1:

输入: “PPALLP”
输出: True
示例 2:

输入: “PPALLL”
输出: False
通过次数19,765提交次数38,039

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/student-attendance-record-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

遍历一遍字符串如果含有两个以上的A。直接返回false
然后再判断后面的L个数。

1
2
3
4
5
6
7
8
9
10
11
12
func checkRecord(s string) bool {
    absentNum := 0
    for _,v := range s {
        if v == 'A' {
            if absentNum >= 1 {
                return false
            }
            absentNum ++
        }
    }
    return !strings.Contains(s,"LLL")
}

5543. 两个相同字符之间的最长子字符串[简单]

给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = “aa”
输出：0
解释：最优的子字符串是两个 ‘a’ 之间的空子字符串。
示例 2：

输入：s = “abca”
输出：2
解释：最优的子字符串是 “bc” 。
示例 3：

输入：s = “cbzxy”
输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。
示例 4：

输入：s = “cabbac”
输出：4
解释：最优的子字符串是 “abba” ，其他的非最优解包括 “bb” 和 “” 。

提示：

1 <= s.length <= 300
s 只含小写英文字母

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxLengthBetweenEqualCharacters(s string) int {
    // 两个循环,计算相同元素之间的长度
    tmp := []rune(s)
    maxLength := -1
    for i:= 0; i < len(tmp); i++{
        for j := i + 1;j < len(tmp); j++{
            if tmp[i] == tmp[j] {
                if j - i - 1 > maxLength {
                    maxLength = j - i - 1
                }
            }
        }
    }
    return maxLength
}

557. 反转字符串中的单词 III[简单]

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

 

示例：

输入：”Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”  

提示：

在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func reverseWords(s string) string {
    ret := []rune{}
    arr := strings.Split(s, " ")
    for i,v := range arr{
        l,r := 0, len(v) -1
        tmpV := []rune(v)
        for l < r {
            tmp := tmpV[l]
            tmpV[l] = tmpV[r]
            tmpV[r] = tmp
            l ++
            r --
        }
        if i != len(arr) -1 {
            tmpV = append(tmpV, ' ')
        }
        ret = append(ret, tmpV...)
    }
    return string(ret)
}

606. 根据二叉树创建字符串[简单]

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1:

输入: 二叉树: [1,2,3,4]
1
/
2 3
/
4

输出: “1(2(4))(3)”

解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。
示例 2:

输入: 二叉树: [1,2,3,null,4]
1
/
2 3
\
4

输出: “1(2()(4))(3)”

解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-string-from-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func tree2str(t *TreeNode) string {
    if nil == t {
        return ""
    }
    if nil != t.Left && nil != t.Right {
        return strconv.Itoa(t.Val) +"(" + tree2str(t.Left)+")" +"("+ tree2str(t.Right)+")"
    }else if nil != t.Left && nil == t.Right {
        return strconv.Itoa(t.Val) +"("+ tree2str(t.Left)+ ")"
    }else if nil == t.Left && nil != t.Right {
        return strconv.Itoa(t.Val) + "()"+ "(" + tree2str(t.Right) +")"
    }else{
        return strconv.Itoa(t.Val)
    }
}

657. 机器人能否返回原点[简单]

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

 

示例 1:

输入: “UD”
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
示例 2:

输入: “LL”
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
通过次数68,477提交次数87,864

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/robot-return-to-origin
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func judgeCircle(moves string) bool {
    x,y := 0,0
    for _,v := range moves {
        if v == 'U' {
            y += 1
        }else if v == 'D' {
            y -= 1
        }else if v == 'L' {
            x -= 1
        }else if v == 'R'{
            x += 1
        }
    }
    return x == 0 && y == 0

680. 验证回文字符串 Ⅱ[简单]

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: “aba”
输出: True
示例 2:

输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
通过次数54,238提交次数135,917

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-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
func isPalindrome3(s string) bool{
    right := len(s) -1
    sb := []rune(s)
    for i := 0;i < right; {
        if sb[i] == sb[right] {
            right --
            i ++
        }else{
            return false
        }
    }
    return true
}
func validPalindrome(s string) bool {
    // 双指针,夹逼。
    // 出现不一致,尝试删除左边或者右边看是否相等
    right := len(s) -1
    sb := []rune(s)
    for i := 0; i < right ;{
        if sb[i] == sb[right] {
            right --
            i ++
            continue
        } else {
            // 去除左边数据
            return isPalindrome3(string(sb[i+1: right + 1])) || isPalindrome3(string(sb[i: right]))
        }
    }
    return true
}

面试题 01.09. 字符串轮转[简单]

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True
示例2:

输入：s1 = “aa”, s2 = “aba”
输出：False
提示：

字符串长度在[0, 100000]范围内。
说明:

你能只调用一次检查子串的方法吗？
通过次数15,931提交次数29,105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-rotation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

超时答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isFlipedString(s1 string, s2 string) bool {
    if s1 == s2 {
        return true
    }
    s1bytes := []rune(s1)
    for i := 0; i < len(s1bytes); i++{
        // 轮转
        tmp := s1bytes[:i+1]
        ret := s1bytes[i+1:]
        for j:=0;j<len(tmp);j++ {
            ret = append(ret, tmp[j])
        }
        if string(ret) == s2 {
            return true
        }
    }
    return false
    
}

只查询一次

1
2
3
4
5
6
func isFlipedString(s1 string, s2 string) bool {
    if len(s1) != len(s2){
        return false
    }
    return strings.Contains(s2+s2, s1)
}

696. 计数二进制子串[简单]

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :

输入: “00110011”
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
示例 2 :

输入: “10101”
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
注意：

s.length 在1到50,000之间。
s 只包含“0”或“1”字符。
通过次数40,719提交次数65,356

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-binary-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一：按字符分组
思路与算法

我们可以将字符串 ss 按照 00 和 11 的连续段分组，存在 \rm countscounts 数组中，例如 s = 00111011s=00111011，可以得到这样的 \rm countscounts 数组：{\rm counts} = {2, 3, 1, 2}counts={2,3,1,2}。

这里 \rm countscounts 数组中两个相邻的数一定代表的是两种不同的字符。假设 \rm countscounts 数组中两个相邻的数字为 uu 或者 vv，它们对应着 uu 个 00 和 vv 个 11，或者 uu 个 11 和 vv 个 00。它们能组成的满足条件的子串数目为 \min { u, v }min{u,v}，即一对相邻的数字对答案的贡献。

我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。

不难得到这样的实现：

C++JavaJavaScriptGolangC

class Solution {
public:
int countBinarySubstrings(string s) {
vector counts;
int ptr = 0, n = s.size();
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
++ptr;
++count;
}
counts.push_back(count);
}
int ans = 0;
for (int i = 1; i < counts.size(); ++i) {
ans += min(counts[i], counts[i - 1]);
}
return ans;
}
};
这个实现的时间复杂度和空间复杂度都是 O(n)O(n)。

对于某一个位置 ii，其实我们只关心 i - 1i−1 位置的 \rm countscounts 值是多少，所以可以用一个 \rm lastlast 变量来维护当前位置的前一个位置，这样可以省去一个 \rm countscounts 数组的空间。

代码如下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countBinarySubstrings(s string) int {
    var ptr, last, ans int
    n := len(s)
    for ptr < n {
        c := s[ptr]
        count := 0
        for ptr < n && s[ptr] == c {
            ptr++
            count++
        }
        ans += min(count, last)
        last = count
    }

    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

复杂度分析

时间复杂度：O(n)O(n)。
空间复杂度：O(1)O(1)。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-binary-substrings/solution/ji-shu-er-jin-zhi-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

349. 两个数组的交集[简单]

给定两个数组，编写一个函数来计算它们的交集。

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]  

说明：

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
通过次数99,763提交次数140,489

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func intersection(nums1 []int, nums2 []int) []int {
    map1 := make(map[int]int)
    map2 := make(map[int]int)
    for _,v := range nums1{
        map1[v] += 1
    }
    for _,v := range nums2 {
        map2[v] += 1
    }
    ret := []int{}
    for k,_ := range map1{
        if _,ok := map2[k];ok {
            ret = append(ret, k)
        }
    }
    return ret
}

350. 两个数组的交集 II[简单]

给定两个数组，编写一个函数来计算它们的交集。

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]  

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
通过次数149,241提交次数280,995

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func intersect(nums1 []int, nums2 []int) []int {
    map1 := make(map[int]int)
    map2 := make(map[int]int)
    for _,v := range nums1{
        map1[v] += 1
    }
    for _,v := range nums2 {
        map2[v] += 1
    }
    ret := []int{}
    for k,v1 := range map1{
        if v2,ok := map2[k];ok {
            v := v1
            if v1 > v2 {
                v = v2
            }
            for i := v; i > 0; i--{
                ret = append(ret, k)
            }
        }
    }
    return ret
}

389. 找不同[简单]

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

 

示例 1：

输入：s = “abcd”, t = “abcde”
输出：”e”
解释：’e’ 是那个被添加的字母。
示例 2：

输入：s = “”, t = “y”
输出：”y”
示例 3：

输入：s = “a”, t = “aa”
输出：”a”
示例 4：

输入：s = “ae”, t = “aea”
输出：”a”  

提示：

0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只包含小写字母
通过次数38,112提交次数59,839

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func findTheDifference(s string, t string) byte {
    map1 := make(map[byte]int)
    map2 := make(map[byte]int)
    for _,v := range s {
        map1[byte(v)] += 1
    }
    for _,v := range t {
        map2[byte(v)] += 1
    }
    for k,v := range map2{
        if v2,ok := map1[k];!ok || v != v2 {
            return k
        }
    }
    return 0
}

242. 有效的字母异位词[简单]

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false
说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

通过次数148,132提交次数239,770

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-anagram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func isAnagram(s string, t string) bool {
    map1 := make(map[rune]int)
    map2 := make(map[rune]int)
    for _,v := range s {
        map1[v] += 1
    }
    for _,v := range t {
        map2[v] += 1
    }
    for k,v := range map1 {
        if v2,ok := map2[k]; !ok || v2 != v {
            return false
        }
    }
    for k,v := range map2 {
        if v2,ok := map1[k]; !ok || v2 != v {
            return false
        }
    }
    return true
}

计算字符个数

题目描述
写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。

输入描述:
第一行输入一个有字母和数字以及空格组成的字符串，第二行输入一个字符。

输出描述:
输出输入字符串中含有该字符的个数。

示例1
输入
复制
ABCDEF
A
输出
复制
1

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
    "bufio"
    "fmt"
    "os"
)
func main(){
    in := bufio.NewReader(os.Stdin)
    input,_ := in.ReadString('\n')
    target,_ := in.ReadString('\n')
    
    map1 := make(map[byte]int)
    for _,v := range input {
        map1[byte(v)] += 1
    }
    v,_ := map1[target[0]]
    v2,_ := map1[target[0] + 32]
    v3,_ := map1[target[0] - 32]
    fmt.Println(v + v2 + v3)
}

明明的随机数[华为练习题]

题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

Input Param

n 输入随机数的个数

inputArray n个随机整数组成的数组

Return Value

OutputArray 输出处理后的随机整数

注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。

当没有新的输入时，说明输入结束。

输入描述:

注意：输入可能有多组数据。每组数据都包括多行，第一行先输入随机整数的个数N，接下来的N行再输入相应个数的整数。具体格式请看下面的”示例”。

输出描述:

返回多行，处理后的结果

示例1
输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3
2
2
1
11
10
20
40
32
67
40
20
89
300
400
15

输出

1
2
3
4
5
6
7
8
9
10
11
1
2
10
15
20
32
40
67
89
300
400

说明

1
2
3
4
样例输入解释：
样例有两组测试
第一组是3个数字，分别是：2，2，1。
第二组是11个数字，分别是：10，20，40，32，67，40，20，89，300，400，15。

解法

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
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    inputArray := []int{}
    for str,err := in.ReadString('\n'); err == nil;str,err = in.ReadString('\n'){
        str = strings.Replace(str,"\r\n","", -1)
        str = strings.Replace(str, "\n", "", -1)
        if "" == str{
            break
        }
        //fmt.Printf("out = %q.\n", str)
        i,_ := strconv.Atoi(str)
        inputArray = append(inputArray, i)
    }
    // 3 1 2 3 2 1 2
    for i := 0; i < len(inputArray);{
        tmp := inputArray[i + 1 : i + inputArray[i] + 1]
        sort.Ints(tmp)
        index := 0
        fmt.Println(tmp[index])
        for j := 1;j<len(tmp);j++{
            if tmp[index] != tmp[j] {
                index ++
                tmp[index] = tmp[j]
                fmt.Println(tmp[index])
            }
        }
        i = i + inputArray[i] + 1
    }
}

字符串分割[华为练习题]

题目描述
•连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
输入描述:
连续输入字符串(输入2次,每个字符串长度小于100)

输出描述:
输出到长度为8的新字符串数组

示例1
输入

1
2
abc
123456789

输出

1
2
3
abc00000
12345678
90000000

思路

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
package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)
func output(s string){
    padding := 8
    for _,v := range s {
        fmt.Printf("%c", v)
        padding -= 1
        if padding == 0 {
            fmt.Println()
            padding = 8
        }
    }
    for padding > 0 && padding < 8 {
        fmt.Print("0")
        padding --
        if padding == 0 {
            fmt.Println()
        }
    }
}
func main() {
    in := bufio.NewReader(os.Stdin)
    str1,_ := in.ReadString('\n')
    str2,_ := in.ReadString('\n')
    
    str1 = strings.Replace(str1,"\r\n", "", -1)
    str1 = strings.Replace(str1,"\n", "", -1)
    
    str2 = strings.Replace(str2,"\r\n", "", -1)
    str2 = strings.Replace(str2,"\n", "", -1)
    
    //fmt.Println(str1)
    //fmt.Println(str2)
    
    output(str1)
    output(str2)
}

290. 单词规律[简单]

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, str = “dog cat cat dog”
输出: true
示例 2:

输入:pattern = “abba”, str = “dog cat cat fish”
输出: false
示例 3:

输入: pattern = “aaaa”, str = “dog cat cat dog”
输出: false
示例 4:

输入: pattern = “abba”, str = “dog dog dog dog”
输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func wordPattern(pattern string, s string) bool {
    // 分割字符串,先建立起pattern和s的映射,然后再进行顺序判断
    patternMap := make(map[rune]string)
    sMap := make(map[string]rune)
    
    arr := strings.Split(s, " ")
    if len(arr) != len(pattern){
        return false
    }
    for i, v := range pattern {
        if _,ok := patternMap[v];!ok {
            patternMap[v] = arr[i]
            sMap[arr[i]] = v
        }
    }
    for i, v := range pattern {
        if v2, ok := sMap[arr[i]]; !ok || v2 != v {
            return false
        }
    }
    return true
}

进制转换[华为]

题目描述
写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

输入描述:

输入一个十六进制的数值字符串。注意：一个用例会同时有多组输入数据，请参考帖子https://www.nowcoder.com/discuss/276处理多组输入的问题。

输出描述:

输出该数值的十进制字符串。不同组的测试用例用\n隔开。

示例1
输入

1
2
0xA
0xAA

输出

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
10
170
``` 
#### 解法
```go
package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func parseStr(s string)  {
    var hexMap = map[rune]int{
        '1':1,
        '2':2,
        '3':3,
        '4':4,
        '5':5,
        '6':6,
        '7':7,
        '8':8,
        '9':9,
        '0':0,
        'a': 10,
        'A': 10,
        'b': 11,
        'B': 11,
        'C': 12,
        'c': 12,
        'd': 13,
        'D': 13,
        'e': 14,
        'E': 14,
        'f': 15,
        'F': 15,
    }
    base := len(s)
    ret := 0
    for _, v := range s {
        tmp := 1
        for i := 1; i < base; i++ {
            tmp *= 16
        }
        d,_ := hexMap[v]
        ret += d * tmp
        base --
    }
    fmt.Println(ret)
}

func main() {
   in := bufio.NewReader(os.Stdin)
   for str,err := in.ReadString('\n');err == nil;str,err = in.ReadString('\n'){
        str = strings.Replace(str, "\r\n", "", -1)
        str = strings.Replace(str, "\n","", -1)
        if str == "" {
            break
        }
        parseStr(string(str[2:]))
   }
}
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

正在成长中<br>请多多指教