LeetCode

原记录于2023-10-21（创建），目前提前至此于调整布局用

力扣算法题记录

s: simple m:middle h:hard

P88 合并两个有序数组 S 数组

思路一 先合并在排序
思路二 合并的时候就进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 合并两个有序数组
 *
 * @param nums1 主数组 nums1.length = m + n
 * @param m 后面需要替换的数量
 * @param nums2 替换数组
 * @param n nums2.length
 */
public static void merge(int[] nums1, int m, int[] nums2, int n) {
      int index = 0;
      for (int i = m; i < nums1.length; i++) {
          nums1[i] = nums2[index++];
      }
      Arrays.sort(nums1);
  }

P27 移除元素 S 数组

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路: 快慢差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 移除元素
*
* @param nums 给定数组
* @param val  移除value
* @return
*/
public static int removeElement(int[] nums, int val) {
    int count = 0;
    for (int num : nums) {
        if (num != val) {
            nums[count++] = num;
        }
    }
    return count;
}

P169 多数元素 S 数组

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

思路一 排序取中间(题目 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题)

1
2
3
4
public static int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length >> 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
/**
 * 多数元素
 *
 * @param nums 目标数组
 * @return
 */
public static int majorityElement(int[] nums) {
  // 默认候选人就是第一个元素
  int candidate = nums[0];
  int count = 1;
  for (int i = 1; i < nums.length; i++) {
      // 得支持票
      if (nums[i] == candidate) {
          count++;
      } else { // 得反对票
          count--;
          if (count == 0) {
              // 更换候选人
              candidate = nums[i];
              count = 1;
          }
      }
  }
  return candidate;
  // 默认候选人就是第一个元素，然后给自己投一票（count=1），如果遇到相同的票则+1，否则-1。当count为0的时候换下一个人，并且重置票数为1（count=1）。
}

双指针（技巧）

对于双指针, 用的最多的无非就是左右指针, 那么左右指针一般都有类似的解法

1
2
3
4
5
6
7
8
9
10
11
public static void template(int []nums){
    int left=0, right=nums.length-1;
    while(left < right){
        // 逻辑
        if(){ // 指针移动条件
            left++;
        }else{
            right++;
        }
    }
}

例如题P11 盛水最多的容器 就是左右指针, 其中还有一种为中间发散指针(从中间到两边)5. 最长回文子串 - 力扣（LeetCode）

P11 盛水最多的容器 M 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int ans = 0;
    while (left < right) {
        int area = (right - left) * Math.min(height[right], height[left]);// 当前面积
        ans = Math.max(ans, area); // 判断面积
        if (height[left] < height[right]) { // 左边是短的边
            left++; // 指针移动
        } else {
            right--;
        }
    }
    return ans;
}

模板都是类似固定的, 同样的模板模式还出现在二叉树

P125 验证回文串 S 字符串

对于该题的要点有:

  1. 需要跳过非字符的元素

  2. 通过Java的API Character.isLetterOrDigit判断是字符还是数字(is: true not: false)

    java.lang.Character.isLetterOrDigit(char ch) 这个方法确定指定的字符是否为字母或数字。字符被认为是字母或数字，如果字符是字母或数字则此方法返回true，否则为false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    if (s == "" || s == null) {
        return true;
    }
    while (left < right) {
        while(left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;//如果是不是字符则左指针向后移动。
        }
        while(left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;//如果不是字符则右指针向前移动。
        }
        if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;//判断是否为回文串。若不是退出。
        }
        // 指针一同移动 判断对称位置字符
        left++;
        right--;
    }
    return true;
}

可以看出来, 大体的模板是不动的, 唯一变化的就是中间, 当前案例由于需要俩头一起遍历并且跳过非字符, 那么需要一直判断(while)

然后学习新的API java.lang.Character.isLetterOrDigit(char ch)

1
2
3
4
5
6
7
8
9
10
11
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        // 代码逻辑
        
        // 指针移动
        left++;
        right--;
    }
    return true;
}

P20 有效的括号 S 字符串 #栈

20. 有效的括号

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
public boolean isValid(String s) {
    if (s.length() % 2 == 1) // 如果不是偶数 那么直接返回了
        return false;
    Stack<Character> stack = new Stack<Character>(); // 栈
    char[] chars = s.toCharArray();
    for (char item : chars) {
        // 左括号们
        if (item == '(' || item == '[' || item == '{') {
            stack.push(item);
        } else {
            // 这两个必须一起(一个是判断栈有没有值,一个是拿栈顶值) 不然会爆空指针
            if (stack.empty())
                return false;
            char top = stack.peek();
            // 判断栈顶的值与右边的括号们是不是一对 是则出栈
            if ((top == '(' && item == ')')
                || (top == '[' && item == ']')
                || (top == '{' && item == '}')) {
                stack.pop();
            } else {
                return false; // 没有匹配的参数
            }
        }
    }
    return stack.empty();
}

P26-80 删除有序数组中的重复项(I and II) S-M 数组

同类的两道题目, 这两个题目的快慢指针都是同类解法

26. 删除有序数组中的重复项(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeDuplicates(int[] nums) {
    int slow = 1, fast = 1;
    while (fast < nums.length) {
        if (nums[slow - 1] == nums[fast]) {
            // 其实这一步就是移动快指针(但是由于哪种情况都需要移动快指针 故直接写外层了)
        } else {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

80. 删除有序数组中的重复项 II (中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeDuplicates(int[] nums) {
    int slow = 2, fast = 2;
    while (fast < nums.length) {
        if (nums[slow - 2] == nums[fast]) {
            fast++;
        } else {
            nums[slow] = nums[fast];
            fast++;
            slow++;
        }
    }
    return slow;
}

可以看出来, 差距只有在指针判断的间隔上(对于判断不需要重复的情况那么指针间隔为1, 至多两个重复的情况则间隔为2)可参考 B站 两题的详细视频讲解

P392 判断子序列 S 字符串

P392 判断子序列

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isSubsequence(String s, String t) {
    int left = 0, right = 0;
    if (s.length() == 0)
        return true;
    if (t.length() == 0)
        return false;
    while (right < t.length() && left < s.length()) {
        // 相等两个指针都移动
        if (s.charAt(left) == t.charAt(right)) {
            left++;
        }
        right++;
    }
    return left >= s.length();
}

P21 合并两个有序链表 S 链表

合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 其中一个为空
    if (list1 == null) 
        return list2;
    if (list2 == null) 
        return list1;
    ListNode ans = new ListNode(-1);
    ListNode margin = ans;
    while (list1 != null && list2 != null) {
        // 除了尾部情况
        if (list1.val < list2.val) {
            margin.next = list1;
            list1 = list1.next;
        } else {
            margin.next = list2;
            list2 = list2.next;
        }
        margin = margin.next;
    }
    // 排尾阶段
    if(list1 == null)
        margin.next = list2;
    if(list2 == null)
        margin.next = list1;
    return ans.next;
}

对于上题，通过采用新链表+双指针，双指针判断两个链表，新链表用于构建答案

易踩坑：1. 在构建新链表时，不保存头节点而直接赋值，导致数据丢失（7-8行） 需要使用一个新的链表节点+另外一个指向新节点的节点变量，然后用于构建ans（错误案例：ListNode ans = new ListNode(-1); 只使用一个头节点进行操作，不进行头节点的保存引用）

  1. 对于循环内的赋值，需要使用赋值节点的下一个节点赋值，而不是他自己（错误案例：margin= list1；margin = margin.next；）
  2. 对于当前题：注意到还有一个收尾的操作，笔者在debug的时候发现最后一个节点被忽略了，因而才引入排尾阶段

P83 删除排序链表中的重复元素 S 链表

删除排序链表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode deleteDuplicates(ListNode head) {
    if(head == null) return null;
    ListNode slow = head;
    ListNode fast = head.next;
    while(fast != null){
        if(slow.val != fast.val){
            slow.next = fast;// 慢指针执行快指针 连接
            slow = slow.next;// 慢指针往后移动
        }
        fast = fast.next;
    }
    // 收尾操作(对于最后一组是重复元素的情况,假如没有重复元素则不会有该情况)
    if(slow != null) 
        slow.next = null;
    return head;
}

对于上述的两题(链表), 都有收尾操作

P160 相交链表 S 链表 #hash表(map)

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Map<ListNode, Integer> ans = new HashMap<>();
    if (headA == null) return null;
    ListNode p = headA;
    while (p != null) {
        ans.put(p, p.val);
        p = p.next;
    }
    ListNode b = headB;
    while (b != null) {
        if (ans.containsKey(b))  // 如果相交则可以拿到相同的对象
            return b;
        b = b.next;
    }
    return null;
}

P141 环形链表 S 链表 #hash表(set)

141. 环形链表

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
    ListNode t = head;
    HashSet<ListNode> set = new HashSet<>();
    while (t != null) {
        int leftLen = set.size(); // 添加前的长度
        set.add(t);
        int rightLen = set.size();// 添加后的长度
        if (leftLen == rightLen) return true; // 环形
        t = t.next;
    }
    return false;
}

Pxxx 返回倒数第 k 个节点 S 链表 #快慢

面试题 02.02. 返回倒数第 k 个节点

相同题：LCR 140. 训练计划 II - 力扣（LeetCode）

先让fast走n步，然后让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode kthToLast(ListNode head, int cnt) {
    ListNode fast = head;
    // 先快指针走n步
    for (int i = 0; i < cnt; i++) {
        fast = fast.next;
    }
    ListNode slow = head;
    while (fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

P19 删除链表的倒数第 N 个结点 M 链表 #快慢指针 #虚拟节点

19. 删除链表的倒数第 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
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);// 建立虚拟节点
    dummy.next = head;               // 虚拟节点连接到头节点
    ListNode shoudDel = kthToLast(dummy, n + 1); // 拿到倒数第k个的前一个
    //get point index          ↓    (需要删除的倒数第n个节点)
    //origin   1 ->2 ->3 ->4 ->5 ->6->
    //ans      1 ->2 ->3 ->4 ->    6->
    shoudDel.next = shoudDel.next.next;// 跳过需要删除的那个
    return dummy.next;
}
// 拿到倒数第n个节点
public ListNode kthToLast(ListNode head, int cnt) {
    ListNode fast = head;
    // 先快指针走n步
    for (int i = 0; i < cnt; i++) {
        fast = fast.next;
    }
    ListNode slow = head;
    // 然后一起走到终点
    while (fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

P61 旋转链表 M 链表 #环形链表解法 #快慢指针

61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

这个题很妙好吧，与前面的那个获取倒数第k个结合起来了。

首先我们拿到长度，然后拿到需要旋转的节点

例如题：1 - > 2 - > 3 - > 4 - > 5，我们需要旋转两个长度单位，此时结果应该为 4 - > 5 - > 1 - > 2 - > 3

1
2
3
4
第一步：size = 5，K=2  =>我们只需要拿到倒数第 s-k=3个位置的节点作为newHead即可
第二步:           newT  newH  tail（指针位置）
样例： 1 - > 2 - > 3 - > 4 - > 5
第三步：tail连接头节点构成循环链表，然后newT的下一个指针断开

详细代码如下

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
class Solution {
    // 定义一个名为 Solution 的类
    public ListNode rotateRight(ListNode head, int k) {
        // 定义一个名为 rotateRight 的公共方法，接收一个头节点和一个整数 k 作为参数
        if (head == null || k == 0)
            return head;
        // 如果头节点为空或者 k 为 0，则直接返回头节点，不需要旋转
        // 计算链表的长度
        ListNode tail = head;
        int size = 1;
        // 计算链表的长度
        while (tail.next != null) {
            size++;
            tail = tail.next;// 此时结束 tail则已经到了末尾了
        }
        // 对 k 进行取模运算，确保 k 在链表长度范围内
        k %= size;
        if (k == 0) // 如果 k 等于 0，则不需要旋转，直接返回头节点
            return head;
        // 找到倒数第 k 个节点
        ListNode fast = getNode(head, size - k);
        // 调用 getNode 方法找到倒数第 k 个节点，作为新的尾节点
        // 新的头节点是新尾节点的下一个节点
        ListNode newHead = fast.next;
        // 新的头节点是新尾节点的下一个节点
        // 将新的尾节点与头节点连接起来
        tail.next = head;
        // 将原始尾节点的 next 指针指向原始头节点，形成环形链表
        // 断开链表，使得新的尾节点指向 null
        fast.next = null;
        // 将新的尾节点的 next 指针指向 null，断开环形链表
        return newHead;
        // 返回新的头节点
    }

    // 获取链表中第 k 个节点
    public ListNode getNode(ListNode head, int k) {
        ListNode p = head;
        for (int i = 1; i < k && p != null; i++)
            p = p.next;
        return p;
    }
}

P2 两数相加 M 链表 #模拟进位

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
28
29
30
31
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p1 = l1, p2 = l2;
    ListNode dummyHead = new ListNode(-1);
    // 创建一个指针current用于遍历结果链表
    ListNode current = dummyHead;
    // （1）初始化进位carry为0
    int carry = 0;
    while (p1 != null || p2 != null || carry != 0) {
        // （2）初始化当前和sum为进位carry
        int sum = carry;
        // 如果链表l1还有节点，则加上l1当前节点的值，并移动p1指针到下一个节点
        if (p1 != null) {
            sum += p1.val;
            p1 = p1.next;
        }
        // 如果链表l2还有节点，则加上l2当前节点的值，并移动p2指针到下一个节点
        if (p2 != null) {
            sum += p2.val;
            p2 = p2.next;
        }
        // （3）计算当前位运算的进位值（0-1）即是否影响下一位
        carry = sum / 10;
        // 计算当前节点的值
        sum %= 10;
        // 创建一个新节点存储当前节点的值，并连接到结果链表的尾部
        current.next = new ListNode(sum);
        current = current.next;
    }
    // 返回结果链表的头节点，即虚拟头节点的下一个节点
    return dummyHead.next;
}

对于题目中的（1）（2）（3）出进行答疑：

（1）进位初始化全局变量

（2）对于上一次运算的进位在本次（即 本次是上一次的前一位：如目前是百位，那么上一次就是十位，那么此时进位是在百位操作的）

（3）每一次对于当前进位运算后，需要计算当前位进行运算后的进位值（结果0-1，）即是否影响下一位

P144 二叉树的前序遍历 S 二叉树

144. 二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    middle(root, ans);
    return ans;
}

private TreeNode middle(TreeNode node, List<Integer> res) {
    if (node == null) {
        return null;
    } else {
        res.add(node.val); // 前序
        middle(node.left, res); // 如果是中序则出现在这个位置
        middle(node.right,res);
    }
    return null;
}

P145 二叉树的后序遍历 S 二叉树

145. 二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    func(root, ans);
    return ans;
}
private TreeNode func(TreeNode node, List<Integer> ans){
    if(node==null) return null;
    else{
        func(node.left,ans);
        func(node.right,ans);
        ans.add(node.val); // 后序
    }
    return null;
}

二叉树（技巧）

对于二叉树来说，无非就是有两种拆分问题的方案，一个是遍历，一个是分解

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

这是一个链接

那么我们以226. 翻转二叉树 - 力扣（LeetCode）为例

遍历

常规写法

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode invertTree(TreeNode root) {
    if(root == null) return null;
    // 让每个节点的左右子节点颠倒过来就行了（前序位置）
    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
    
    // 遍历框架
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
public TreeNode invertTree(TreeNode root) {
    if(root == null) return null;
    // 利用函数定义，先翻转左右子树
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);

    // 然后交换左右子节点
    root.left = right;
    root.right = left;
    
    
    // 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
    return root;
}

这种「分解问题」的思路，核心在于你要给递归函数一个合适的定义，然后用函数的定义来解释你的代码；

小结

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

P128 最长连续序列 M 哈希表

128. 最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestConsecutive(int[] nums) {
    if (nums.length <= 1) return nums.length;
    HashSet<Integer> set = new HashSet<>();
    for (Integer num : nums) {
        set.add(num);
    }
    int ans = 0;
    for (Integer item : set) {
        int curAns = 1, curNum = item;
        if (!set.contains(item - 1)) {
            // 只需要往后遍历，就是一直往后面判断就可以了，直到找到一个（连续列中）最小的数
            while (set.contains(curNum + 1)) {
                curNum++; // 后移
                curAns++; // 计数
            }
        }
        ans = Math.max(ans, curAns);
    }
    return ans;
}

P71 简化路径 M 栈

71. 简化路径

1
2
3
Linux下的路径
输入：path = "/a/./b/../../c/"
输出："/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
public static String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();
    String[] split = path.split("/");
    // 遍历路径中的每个部分
    for (String part : split) {
        // 如果部分为空或为当前目录符号 "."
        if (part.isEmpty() || part.equals(".")) 
            continue;
        // 如果部分为父目录符号 ".."，则弹出栈顶元素
        else if (part.equals("..")) {
            if (!stack.empty())
                stack.pop();
        }
        // 否则，将部分压入栈中
        else 
            stack.push(part);
    }
    StringBuilder sb = new StringBuilder();
    for (String s : stack) 
        sb.append("/").append(s);
    if (sb.length() == 0) 
        return "/";
    return sb.toString();
}

其实很好理解，如果遇到.则什么都不做处理，如果遇到..那么则需要出栈

当然此题还可以使用队列去实现，笔者最开始就是使用的队列，如果遇到上述的相同情况则出入队列，原理一致（Queue）

P150 逆波兰表达式求值 M 栈

150. 逆波兰表达式求值

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
public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) {
        // 如果是遇到符号 则需要进行运算
        if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
            // 因为需要得到两个操作数 需要出栈两次
            Integer left = stack.pop();
            Integer right = stack.pop();
            switch (token) {
                case "+":
                    stack.push(left + right);
                    break;
                case "*":
                    stack.push(left * right);
                    break;
                case "-":
                    // 易错：left是第一个出栈的，那么他是做除数/减数
                    stack.push(right - left);
                    break;
                case "/":
                    stack.push(right / left);
                    break;
            }
        } else { // 不是符号情况 则是数字 直接push即可
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.peek();
}

其实这个题和上面那个题很像

场景题

除了算法题还有场景题欧

分金条问题

问题描述：雇1个人工作7天，你有1根金条可以分成7份，只能切2刀，如何保证每天都得到1份金条

我们首先，把金条看出七份，然后我们我们切两刀（1/7，2/7，4/7）那么可以看成一个线段从1/7处和3/7处切了(切金条CSDN)

然后七天的话: 第一天给工人 1/7，那么我们还有（剩2/7 + 4/7 = 6/7）

第二天：我们给他2/7，然后他返回第一天我们给他的1/7（剩1/7 + 4/7 = 5/7）

第三天：我们给他第二天要回的1/7，此时我们（剩4/7）

第四天：要回所有的金条（3/7），我们给他我们剩的4/7. (剩1/7 + 2/7 = 3/7)

第五天：给他1/7。我们（剩2/7）

第六天：要回1/7，然后给剩下的2/7。（剩1/7）

第七天：给他1/7。我们（剩0）