整数除法

剑指 Offer II 001. 整数除法

难度简单35

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

  • 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

示例 1：

1
2
3
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

1
2
3
输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

1
2
输入：a = 0, b = 1
输出：0

示例 4：

1
2
输入：a = 1, b = 1
输出：1

提示:

  • -231 <= a, b <= 231 - 1
  • b != 0

注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/

快速幂思路

朴素的思路是从a一直减去b，直到a的值小于等于0，这样的话一定会超时
能不能想一种办法让他减的比较快呢?
参考快速幂算法,每次增加底的值
在本题目中,增加减数的值,每次让减数翻倍,那么对应的答案的值也会翻倍

例如10除以3
第一次除数为3,10-3>0,此时结果是1,让3翻倍,除数变成了6.
第二次除数为6,10-6>0,此时结果是2,让6翻倍,除数变成了12.
第三次除数是12,10-12<0,结果不能翻倍,此时结果在2和4之间.
然后再使用递归的方法求(10-6,3)的结果就能得到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
class Solution {
    public int divide(int a, int b) {
        if(a==-2147483648 && b==-1)return 2147483647;
        if(a==0)return 0;
        boolean neg = true;
        if((a<0 && b<0)||(a>0 && b>0)){
            neg = false;
        }
        long v1 = Math.abs((long)a);
        long v2 = Math.abs((long)b);
        long ans = div(v1,v2);

        return neg ? (int)-ans :(int) ans;
    }

    public long div(long v1,long v2){
        // 保存减数
        long v = v2;
        long ans = 1;
        if(v1 < v2) return 0;
        while(v2+v2 <= v1){
            // 减数翻倍
            v2 = v2+v2;
            // 答案也翻倍
            ans = ans+ans;
        }
        return ans + div(v1-v2,v);
    }
}

展开全文 >>

排列硬币

441. 排列硬币

难度简单158

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例 1：

img

1
2
3
输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

示例 2：

img

1
2
3
输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 。

提示：

  • 1 <= n <= 231 - 1

通过次数64,697

提交次数143,774

暴力求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int arrangeCoins(int n) {
        int ans = 0;
        for(int i=1;i<=n;i++){
            if(n>=i){
                n-=i;
                ans++;
            }else{
                break;
            }
        }
        return ans;
    }
}

二分查找

根据等差数列的性质$\text { total }=\frac{k \times(k+1)}{2}$，两层之间的差值是1，那么通过遍历k的值，就可以通过二分查找来找到对应的层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int arrangeCoins(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if ((long) mid * (mid + 1) <= (long) 2 * n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/arranging-coins/solution/pai-lie-ying-bi-by-leetcode-solution-w52c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

旅行终点站

1436. 旅行终点站

难度简单72

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

示例 1：

1
2
3
输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

1
2
3
4
5
6
7
8
输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。

示例 3：

1
2
输入：paths = [["A","Z"]]
输出："Z"

提示：

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • 所有字符串均由大小写英文字母和空格字符组成。

通过次数31,323

提交次数38,614

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String destCity(List<List<String>> paths) {
        Map<String,String> map = new HashMap<>();
        for(List<String> list:paths){
            map.put(list.get(0),list.get(1));
        }
        for(Map.Entry<String,String> entry:map.entrySet()){
            if(!map.containsKey(entry.getValue())){
                return entry.getValue();
            }
        }
        return null;
    }
}

展开全文 >>

调整顺序使奇数位于偶数前面

描述

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围：img，数组中每个数的值 img

要求：空间复杂度 img，时间复杂度 img

示例1

输入：

1
[1,2,3,4]

返回值：

1
[1,3,2,4]

示例2

输入：

1
[2,4,6,5,7]

返回值：

1
[5,7,2,4,6]

插入排序的思想

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
import java.util.*;

public class Solution {
    //使用插入排序的思想
    public int[] reOrderArray (int[] array) {
        if(array==null||array.length==0) return array;
        int left=0;//记录已经是奇数的位置
        
        int temp = 0;
        for(int i =0;i<array.length;i++){
            temp = array[i];
            if(array[i]%2==0){
                continue;
            }else{
                int k = i;
                while(k>left){
                    array[k] = array[k-1];//这区间整体向后移动一位
                    k--;
                }
                array[k] = temp;
                left++;
            }
        }
        return array;
    }
}

展开全文 >>

含有重复元素的全排列

剑指 Offer II 084. 含有重复元素集合的全排列

难度中等4

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

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

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

注意：本题与主站 47 题相同： https://leetcode-cn.com/problems/permutations-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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        backtrack(nums,0);
        return ans;
    }

    List<List<Integer>> ans = new ArrayList<>();
    public void backtrack(int []nums,int index){
        int n = nums.length;
        if(index==n-1){
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<n;i++){
                list.add(nums[i]);
            }
            ans.add(list);
            return;
        }
        // 通过set去重，如果某个数字与index处的数字交换过一次，那么下次不用再次交换（不然就出现重复了）
        Set<Integer> set =  new HashSet<>(); 
        for(int i = index; i < n; i++){
            if(set.contains(nums[i]))continue;
            set.add(nums[i]);
            swap(nums,index,i);
            backtrack(nums,index+1);
            swap(nums,index,i);
        }
    }

    public void swap(int []nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

展开全文 >>

排序链表

148. 排序链表

难度中等1296

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

  • 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

img

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

示例 2：

img

1
2
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

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

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -10^5 <= Node.val <= 10^5

归并排序

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }


    public ListNode mergeSort(ListNode head){
        // 只剩下一个元素时
        if(head==null||head.next==null)return head;
        
        // 快慢指针找到中间节点
        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null){
            fast = fast.next;
            if(fast!=null){
                fast = fast.next;
                // 注意这个判断十分重要，如果没有则会进入死循环
                if(fast!=null)slow = slow.next;
            }
        }
		
        ListNode nex = slow.next;
        // 将链表断开
        slow.next = null;
		// 对链表的前半部分进行归并排序
        ListNode left = mergeSort(head);
        // 对链表的后半部分进行归并排序
        ListNode right = mergeSort(nex);
		
        // 合并两个链表
        ListNode dummyNode = new ListNode(0);
        ListNode pre = dummyNode;
		// 合并公共部分
        while(left!=null&&right!=null){
            if(left.val<=right.val){
                pre.next = left;
                left = left.next;
            }else{
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        // 将剩余的部分添加到链表的后面
        if(left!=null) pre.next = left;
        if(right!=null) pre.next = right;

        return dummyNode.next;
    }
}

展开全文 >>

扁平化多级双向链表

430. 扁平化多级双向链表

难度中等264

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

1
2
3
4
5
6
7
8
9
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：



扁平化后的链表如下图：

示例 2：

1
2
3
4
5
6
7
8
9
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

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

如何表示测试用例中的多级链表？

以 示例 1 为例：

1
2
3
4
5
1---2---3---4---5---6--NULL
        |
        7---8---9---10--NULL
            |
            11--12--NULL

序列化其中的每一级之后：

1
2
3
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

1
2
3
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

1
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

  • 节点数目不超过 1000
  • 1 <= Node.val <= 10^5

使用栈

开始遍历，遇到有孩子的节点开始遍历孩子链表，并使用栈保存当前的父链表的下一个节点，

遍历孩子链表完成后，将当前父链表的节点接到当前的子链表的后面

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
class Solution {
    public Node flatten(Node head) {
        
        Node dummyNode = new Node(0);
        dummyNode.next = head;

        Node pre = dummyNode;
        Node cur = head;
        solve(pre,cur);
        return dummyNode.next;
    }

    public void solve(Node pre,Node head){
        Node cur = head;
        Deque<Node> stack = new LinkedList<>();
        while(cur!=null||!stack.isEmpty()){
            if(cur!=null){
                if(cur.child!=null){
                    // 当前节点的下一个节点
                    Node nex = cur.next;
                    // 将当前节点的下一个节点加入到栈中去，如果孩子节点遍历完了，在把当前栈顶的节点追加到孩子链表的后面
                    stack.push(nex);
                    // 开始遍历他的孩子链表
                    cur.next = cur.child;
                    cur.child.prev = cur;
                    cur.child = null;
                }
                cur = cur.next;
                pre = pre.next;
            }else{
                // 孩子链表遍历完成，开始继续遍历父链表
                cur = stack.pop();
                // 将当前的父链表接到孩子链表的后面
                if(pre!=null) pre.next = cur;
                if(cur!=null) cur.prev = pre;
            }
        }
    }
}

展开全文 >>

01矩阵

542. 01 矩阵

难度中等508

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

img

1
2
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

img

1
2
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • mat 中至少有一个 0

BFS

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
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int [][]road ={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m = mat.length;
        int n = mat[0].length;

        int [][] ans = new int[m][n];
        boolean [][]vis = new boolean[m][n];
        Queue<Node> queue  = new LinkedList<>();

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    vis[i][j] = true;
                    queue.offer(new Node(i,j));
                }
            }
        }

        while(!queue.isEmpty()){
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;
            for(int i=0;i<4;i++){
                int tempx = x+road[i][0];
                int tempy = y+road[i][1];
                if(tempx<0||tempy<0||tempx>=m||tempy>=n||vis[tempx][tempy]){
                    continue;
                }
                queue.offer(new Node(tempx,tempy));
                ans[tempx][tempy] = ans[x][y]+1;
                vis[tempx][tempy] = true;
            }
        }

        return ans;
    }

    class Node{
        int x;
        int y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

展开全文 >>

3的幂

326. 3的幂

难度简单219

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

1
2
输入：n = 27
输出：true

示例 2：

1
2
输入：n = 0
输出：false

示例 3：

1
2
输入：n = 9
输出：true

示例 4：

1
2
输入：n = 45
输出：false

提示：

  • -231 <= n <= 231 - 1

进阶：

  • 你能不使用循环或者递归来完成本题吗？

循环判断

1
2
3
4
5
6
7
8
class Solution {
    public boolean isPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

展开全文 >>

最长递增子序列的个数

673. 最长递增子序列的个数

难度中等475

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

1
2
3
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

1
2
3
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, ans = 0;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j]; // 重置计数
                    } else if (dp[j] + 1 == dp[i]) {
                        // 如果恰好等于，那么它可以由cnt[j]对应的计数转移过来，在当前值的基础上加上
                        cnt[i] += cnt[j];
                    }
                }
            }
            // 统计最大值对应的计数值
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
}

展开全文 >>

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>又水又笨又菜的<br>菜狗子<br>希望有一天被领走