对链表进行插入排序

2020-11-20

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
 

示例 1：

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

输入: -1->5->3->4->0
输出: -1->0->3->4->5
通过次数61,061提交次数91,279

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

又一次被链表的复杂关系搞晕了

用了不太合题意的辅助空间做出来的

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (null == head) {
            return head;
        }

        ListNode node = new ListNode(0);
        node.next = new ListNode(head.val);

        ListNode tempNode = node.next;
        head = head.next;

        while (head != null) {
            if (head.val > tempNode.val) {
                tempNode.next = new ListNode(head.val);
                tempNode = tempNode.next;
            } else {
                ListNode sortedNode = node;
                ListNode replace = new ListNode(head.val);
                replace.next = null;
                boolean flag = false;
                while (sortedNode != null && sortedNode.next != null) {
                    if (sortedNode.next.val < head.val) {
                        sortedNode = sortedNode.next;
                    } else {
                        ListNode curNext = sortedNode.next;
                        sortedNode.next = replace;
                        sortedNode.next.next = curNext;
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    sortedNode.next = replace;
                }
            }

            head = head.next;

        }

        return node.next;
    }
}

借用官方的图理清思路：
avatar

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        // dummyHead是拍好序列的链表
        // 从原先链表中选择一个元素时，首先与dummyHead的第一个元素比较，如果大于该元素，就往后移动，直至到达不大于的位置，断开链表将值插入，然后合并链表
        dummyHead.next = head;
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                // 定位到排好序的部分的第一个位置
                while (prev.next.val <= curr.val) {
                    // 如果某个元素小于当前的值，后移指针直至不小于的位置
                    prev = prev.next;
                }
                // 将cur节点从链表中断开
                lastSorted.next = curr.next;
                // 将cur节点插入有序的链表
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}

参考文献

官方题解LeetCode-Solution

展开全文 >>

搜索二维矩阵

2020-11-19

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
 

示例 1：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
输出：true
示例 2：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出：false
示例 3：

输入：matrix = [], target = 0
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

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

笨方法 先对行二分查找，再对列二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int h = matrix.length;
        int w = matrix[0].length;
        int low = 0, heigh = h;

        while (low <= heigh - 1) {//对行进行二分查找
            int mid = (low + heigh) / 2;
            if (mid < h) {
                if (matrix[mid][0] < target) {
                    low = mid + 1;
                    if (matrix[mid][w - 1] >= target) {
                        low = mid;
                        break;
                    }
                } else if (matrix[mid][0] > target) {
                    heigh = mid - 1;
                } else {
                    return true;
                }
            } else {
                heigh--;
            }
        }

        if (target > matrix[h - 1][w - 1] && low > 0) {
            low--;
        }

        int left = 0, right = w;
        while (left <= right) {//对列进行二分查找
            int mid = (left + right) / 2;
            if (mid < w) {
                if (matrix[low][mid] < target) {
                    left = mid + 1;
                } else if (matrix[low][mid] > target) {
                    right = mid - 1;
                } else {
                    return true;
                }
            } else {
                right--;
            }

        }
        return false;
    }
}

官方思路

将二维数组转化为一维数组然后对整个数组进行二分查找
每个中间的节点的行列值为：

mid=(left+right)/2
w=matrix[0].length
row=mid/w
col=mid%w

class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int h = matrix.length;
        int w = matrix[0].length;
        int left = 0, right = h * w - 1;
        //将二维数组转一维
        //选取虚数组最中间的序号作为中间序号: pivot_idx = (left + right) / 2。
        //该序号对应于原矩阵中的
        // row = pivot_idx // w 行
        // col = pivot_idx % w 列,
        // 由此可以拿到中间元素pivot_element。该元素将虚数组分为两部分。
        while (left <= right) {
            int mid = (left + right) / 2;
            int row = mid / w;
            int col = mid % w;

            if (matrix[row][col] < target) {
                left = mid + 1;
            } else if (matrix[row][col] > target) {
                right = mid - 1;
            } else {
                return true;
            }

        }
        return false;
    }
}

官方题解

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    if (m == 0) return false;
    int n = matrix[0].length;

    // 二分查找
    int left = 0, right = m * n - 1;
    int pivotIdx, pivotElement;
    while (left <= right) {
      pivotIdx = (left + right) / 2;
      pivotElement = matrix[pivotIdx / n][pivotIdx % n];
      if (target == pivotElement) return true;
      else {
        if (target < pivotElement) right = pivotIdx - 1;
        else left = pivotIdx + 1;
      }
    }
    return false;
  }
}

参考文献

官方题解

展开全文 >>

移动零

2020-11-19

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

示例:

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

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

年轻人不讲武德，欺负题目没有闪，直接覆盖前面的0，后面再补上

class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int count = 0;                                  //记录当前数字前面有几个0
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                nums[i - count] = nums[i];              //如果当前数字不是0，移动的数量应该是前面数字的数量。
            }
        }
        for (int i = len - count ; i < len; i++) {      //最后补0
            nums[i] = 0;
        }

    }
}

展开全文 >>

分隔链表

2020-11-18


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

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

 

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
通过次数58,794提交次数97,797

利用内存换时间和代码复杂度的方式

使用两个链表

一个链表保存小于分区值的值，另一个链表保存大于分区值的值。

小链表的尾和大链表的头结合

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null){
            return null;
        }
        ListNode leHead=new ListNode(0);
        ListNode gtHead=new ListNode(0);
        ListNode leFirst=leHead;
        ListNode gtFirst=gtHead;
        while(head!=null){
            if(head.val<x){
                leHead.next=new ListNode(head.val);
                leHead=leHead.next;
            }else {
                gtHead.next=new ListNode(head.val);
                gtHead=gtHead.next;
            }
            head=head.next;
        }
        leHead.next=gtFirst.next;
        return leFirst.next;
    }
}

官方题解中，使用了双链表的思想，没有使用额外的辅组空间

使用两个哑节点，小于 $x$ 的放到第一个节点，大于 $x$ 的放到第二个节点

class Solution {
    public ListNode partition(ListNode head, int x) {

        // before and after are the two pointers used to create the two list
        // before_head and after_head are used to save the heads of the two lists.
        // All of these are initialized with the dummy nodes created.
        ListNode before_head = new ListNode(0);
        ListNode before = before_head;
        ListNode after_head = new ListNode(0);
        ListNode after = after_head;

        while (head != null) {

            // If the original list node is lesser than the given x,
            // assign it to the before list.
            // 这里没有释放节点的原因是下一次赋值时覆盖了原来的位置的元素
            if (head.val < x) {
                before.next = head;
                before = before.next;
                
            } else {
                // If the original list node is greater or equal to the given x,
                // assign it to the after list.
                after.next = head;
                after = after.next;
            }

            // move ahead in the original list
            head = head.next;
        }

        // Last node of "after" list would also be ending node of the reformed list
        // 这里必须要释放节点，否则就会和后面的节点链上
        after.next = null;

        // Once all the nodes are correctly assigned to the two lists,
        // combine them to form a single list which would be returned.
        before.next = after_head.next;

        return before_head.next;
    }
}

反思 : 对链表的理解还是不够清楚

参考文献

官方题解

展开全文 >>

加油站

2020-11-18

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明: 

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1:

输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:

输入: 
gas  = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
通过次数68,911提交次数122,574

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

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int[] left = new int[len];
        int total = 0;
        for (int i = 0; i < len; i++) {
            left[i] = gas[i] - cost[i];
            total += left[i];
        }
        if (total < 0) {//所有元素的和小于0，一定不能走完一圈
            return -1;
        }
        if(left.length==1){//边界条件，只有一个元素时
            return 0;
        }
        for (int i = 0; i < len; i++) {
            if (left[i] > 0) {//第一个一定是大于0的
                int j = i + 1;
                int sum = 0;
                sum += left[i];
                while (j-i<=len) {//走一圈试试
                    sum += left[j % len];
                    if (sum < 0) {
                        break;
                    }
                    j++;
                }
                if (sum > 0) {//如果可以走通，就是i
                    return i;
                }
            }
        }
        return -1;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int[] left = new int[len];
        int total = 0;
        for (int i = 0; i < len; i++) {
            left[i] = gas[i] - cost[i];
            total += left[i];
        }
        if (total < 0) {
            return -1;
        }
        if(left.length==1){
            return 0;
        }
        for (int i = 0; i < len; i++) {
            if (left[i] > 0) {
                int j = i + 1;
                int sum = 0;
                sum += left[i];
                while (j-i<=len) {
                    sum += left[j % len];
                    if (sum < 0) {
                        i=j;//我们首先检查第 00 个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。证明：https://leetcode-cn.com/problems/gas-station/solution/jia-you-zhan-by-leetcode-solution/
                        break;
                    }
                    j++;
                }
                if (sum > 0) {
                    return i;
                }
            }
        }
        return -1;
    }
}

官方题解

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
}

参考文献

官方题解

展开全文 >>

旋转链表

2020-11-17

给定一个链表，旋转链表，将链表每个节点向右移动 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
通过次数96,947提交次数239,460

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

年轻人不讲武德
不使用链表直接修改，而是用类似于桶排序的方法搞


/**
 * 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 rotateRight(ListNode head, int k) {
        ListNode first = head;
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        if(len==0){
            return null;
        }

        int[] val = new int[len];
        ListNode temp = first;
        int cur = 0;
        while (temp != null) {
            int next = (cur + k) % len;
            val[next] = temp.val;
            temp = temp.next;
            cur++;
        }

        ListNode node = new ListNode(val[0]);
        first = node;
        for (int i = 1; i < len; i++) {
            node.next = new ListNode(val[i]);
            node = node.next;
        }
        return first;
    }
}

官方题解

将尾节点与头节点相连接,新的链表头在位置 $n-k$ 处，其中 $n$ 是链表中点的个数，新的链表尾就在头的前面，位于位置 $n-k-1$.

当 $k$ 大于等于链表长度的时候 $k = (k // n) * n + k % n$


class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // base cases
    if (head == null) return null;
    if (head.next == null) return head;

    // close the linked list into the ring
    ListNode old_tail = head;
    int n;
    for(n = 1; old_tail.next != null; n++){
        old_tail = old_tail.next;
    }
      
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++){
        new_tail = new_tail.next;
    }

    ListNode new_head = new_tail.next;

    // break the ring
    new_tail.next = null;

    return new_head;
  }
}

参考文献

LeetCode官方题解

展开全文 >>

距离顺序排列矩阵单元格（简单题）

2020-11-17


给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。

另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。

返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）

 

示例 1：

输入：R = 1, C = 2, r0 = 0, c0 = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
示例 2：

输入：R = 2, C = 2, r0 = 0, c0 = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
示例 3：

输入：R = 2, C = 3, r0 = 1, c0 = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
 

提示：

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

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

直接排序法

class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int [][]val=new int[R*C][3];
        int index=0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                val[index][0]=i;
                val[index][1]=j;
                val[index][2]=Math.abs(i-r0)+Math.abs(j-c0);
                index++;
            }
        }
        Arrays.sort(val, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2]-o2[2];
            }
        });
        int [][]res=new int[R*C][2];
        for(int i=0;i<R*C;i++){
            res[i][0]=val[i][0];
            res[i][1]=val[i][1];
        }

        return res;
    }
}

桶排序法

class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] ret = new int[R * C][];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                ret[i * C + j] = new int[]{i, j};
            }
        }
        Arrays.sort(ret, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return (Math.abs(a[0] - r0) + Math.abs(a[1] - c0)) - (Math.abs(b[0] - r0) + Math.abs(b[1] - c0));
            }
        });
        return ret;
    }
}

参考文献

官方题解

展开全文 >>

合并区间

2020-11-17

给出一个区间的集合，请合并所有重叠的区间。

 

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

 

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

解题思路：

按照第二个元素从小到大排序。
如果左边元素的第二个值大于右边元素的第一个值，那么存在交叉，修改右边的元素，扩大区间。
凑出返回值。

时间复杂度 O(n*n)
空间复杂度 O(n)


class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {//按照第二个元素排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        boolean[] isDelete = new boolean[intervals.length];//改元素是否在原数组中删除
        int deleteNum = 0;
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[i][1] >= intervals[j][0]) {//如果存在区间交叉
                    int first = Math.min(intervals[i][0], intervals[j][0]);
                    int second = Math.max(intervals[i][1], intervals[j][1]);
                    intervals[j][0] = first;//修改后面的那个（j），这样就可以保证后面的那个可以继续与更后面的比较
                    intervals[j][1] = second;
                    isDelete[i] = true;
                    deleteNum++;
                    break;
                }
            }
        }
        //因为是在原来的数组基础上修改的，因此要凑出返回值
        int left = intervals.length - deleteNum;
        int res[][] = new int[left][2];
        int index = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (!isDelete[i]) {
                res[index] = intervals[i];
                index++;
            }
        }

        return res;
    }
}

官方题解按照第一个值排序


class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

参考文献

官方题解

展开全文 >>

根据身高重建队列

2020-11-16

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]


2020.11.15 中国人寿研发中心2021秋招题

通过次数60,640提交次数86,098

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

题目的意思是原来K的顺序不对（也就是原来的顺序不能保证k成立），要用一种规则，使得每个{h,k}所对应的顺序是正常的。例如{5,0}身高大于5的不能站在{5，0}的前面，{7，0}是身高大于7的不允许站在{7，0}前面,{5,2}是只允许2个身高大于等于{5，2}的人站在{5，2}前面。

解题思路：

先按照k从小到大排序一波，保证排在后面的移动少
然后使用表格记录排序后的每个人的前面有几个人比他高或相等
用比他高或相等的人的数量减去正确顺序时前面比他高或相等的人的数量（也就是他的k）得到他应该向前移动的数量
根据他应该移动的数量，对其向前移动，得到的顺序即为正确的顺序

class Solution {
    public int[][] reconstructQueue(int[][] people) {
       Arrays.sort(people, new Comparator<int[]>() {//对k进行排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int len = people.length;
        int dp[] = new int[len];//记录每个人前面有几个人的身高大于等于他
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (people[i][0] <= people[j][0]) {
                    dp[i]++;
                }
            }
            //(dp[i] - people[i][1])是当前的人应该向前移动的位置
            list.add(i - (dp[i] - people[i][1]), people[i]);
        }

        for (int i = 0; i < list.size(); i++) {//转换输出
            people[i] = list.get(i);
        }
        return people;
    }
}

官方题解解题思路

同样地，我们也可以将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照 $h_i$ 为第一关键字降序，$k_i$

为第二关键字升序进行排序。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 $i$个人时：

第 $0$, $\cdots$,$i−1$ 个人已经在队列中被安排了位置，他们只要站在第$i$个人的前面，就会对第$ i$ 个人产生影响，因为他们都比第 $i$ 个人高；

而第 $i+1$, $\cdots$,n−1 个人还没有被放入队列中，并且他们无论站在哪里，对第 $i$ 个人都没有任何影响，因为他们都比第 $i$个人矮。

在这种情况下，我们无从得知应该给后面的人安排多少个「空」位置，因此就不能沿用方法一。但我们可以发现，后面的人既然不会对第 $i$ 个人造成影响，我们可以采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。也就是说，当我们放入第 $i$ 个人时，只需要将其插入队列中，使得他的前面恰好有 $k_i$ 个人即可。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

参考文献

官方题解

展开全文 >>

螺旋矩阵(中等题)

2020-11-15

54. 螺旋矩阵

难度中等769

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

示例 2：

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

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

模拟

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 如果矩阵为空
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        // 右，下，上，左
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0];
            int nextColumn = column + directions[directionIndex][1];
            
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

按层模拟

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 如果矩阵为空
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

暴力解法

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int maxi = matrix.length;
        int maxj = matrix[0].length;
        int mini = 0, minj = 0;
        int indexi = -1, indexj = -1;
        List<Integer> list = new ArrayList<>();
        int maxLength = matrix.length * matrix[0].length;
        int count=0;//计数，如果没有计数，可能有的情况会多遍历几个
        while (count < maxLength) {

            for (indexi++, indexj++; indexj < maxj; indexj++) {//j增
                if(count<maxLength){
                    list.add(matrix[indexi][indexj]);
                    count++;
                }
            }
            for (indexj--, indexi++; indexi < maxi; indexi++) {//i增
                if(count<maxLength){
                    list.add(matrix[indexi][indexj]);
                    count++;
                }
            }
            maxi--;//可遍历范围-1
            maxj--;//可遍历范围-1
            mini++;//可遍历范围-1
            for (indexi--, indexj--; indexj >= minj; indexj--) {//j减
                if(count<maxLength){
                    list.add(matrix[indexi][indexj]);
                    count++;
                }
            }
            for (indexj++, indexi--; indexi >= mini; indexi--) {//i减
                if(count<maxLength){
                    list.add(matrix[indexi][indexj]);
                    count++;
                }
            }
            minj++;//可遍历范围-1
        }

        return list;
    }
}

展开全文 >>