LeetCode偶尔一题 —— 832. 翻转图像

WalkerXu 发布于2019-08-26 14:04 / 600人阅读

题目描述

分析题目

按照题意我们只要先对每个子数组先做逆序，再做 0 --> 1 和 1 --> 0 的替换即可，于是我们可以写出以下代码：

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var flipAndInvertImage = function(A) {
    for (let i = 0; i < A.length; i++) {
        let j = 0, k = A[i].length - 1
        while (j < k) {
            [A[i][j], A[i][k]] = [A[i][k], A[i][j]]
            A[i][j] = A[i][j] ? 0 : 1
            A[i][k] = A[i][k] ? 0 : 1
            j++, k--
        }
        if (j === k) {
            A[i][j] = A[i][j] ? 0 : 1
        }
    }
    return A
};

优化

对于 0 --> 1 和 1 --> 0 的替换，我们大可不必用三元运算符，而是采用异或运算，可以把代码简化如下：

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var flipAndInvertImage = function(A) {
    for (let i = 0; i < A.length; i++) {
        let j = 0, k = A[i].length - 1
        while (j < k) {
            [A[i][j], A[i][k]] = [A[i][k], A[i][j]]
            A[i][j] ^= 1
            A[i][k] ^= 1
            j++, k--
        }
        if (j === k) {
            A[i][j] ^= 1
        }
    }
    return A
};

进阶

仔细观察题目中提供的测试用例，我们发现，左右两个数不相等时可以直接忽略，于是最终版的程序如下：

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var flipAndInvertImage = function(A) {
    for (let i = 0; i < A.length; i++) {
        let j = 0, k = A[i].length - 1
        while (j < k) {
            if (A[i][j] === A[i][k]) {
                A[i][j] ^= 1
                A[i][k] ^= 1
            }
            j++, k--
        }
        if (j === k) {
            A[i][j] ^= 1
        }
    }
    return A
};

时间复杂度：O(n * k / 2)

空间复杂度：O(1)

原题地址: https://leetcode-cn.com/probl...
代码不定时更新，欢迎 star 我的 repo

扫描下方的二维码或搜索「tony老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。

GPU云服务器云服务器 LeetCode 服务器偶尔死机 LeetCode_String 服务器会偶尔down掉

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109997.html

小李飞刀：做题第十一弹！

摘要：第五题对称二叉树难度简单给定一个二叉树，检查它是否是镜像对称的。第十六题最大连续的个数难度简单给定一个二进制数组，计算其中最大连续的个数。第十八题平方数之和难度简单给定一个非负整数，你要判断是否存在两个整数和，使得。写在前面最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔~来认真整理下最近做的题目~ 之前考虑按tag来刷题，后来收到了推荐的leetcode题解，就根据上...

ytwman 2019-07-31 10:18 评论0 收藏0
70道前端LeetCode题目集合及视频讲解（持续更新中...）

前端LeetCode刷题下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...

mayaohua 2019-08-26 10:46 评论0 收藏0
LeetCode偶尔一题 —— 268. 缺失数字

摘要：题目描述给定一个包含中个数的序列，找出中没有出现在序列中的那个数。示例输入输出示例输入输出最简单的解法刚看到的这道题的时候，第一感觉就是排序，之后直接挨个比较就能找到缺失的数字。题目描述给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,...

e10101 2019-08-26 10:22 评论0 收藏0
LeetCode偶尔一题 —— 19. 删除链表的倒数第N个节点（链表系列）

摘要：题目描述给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为简单的思路用一个数组保存所有的链表节点，遍历完之后可以知道倒数第个链表节点。题目描述给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1-...

Anshiii 2019-08-26 10:21 评论0 收藏0
LeetCode偶尔一题 —— 39. Combination Sum（回溯算法系列）

摘要：输入输出分析题目由于我们需要找到多个组合，简单的使用循环肯定是不行的，这时候我们可以使用回溯算法来解决这个问题。用回溯算法解决问题的一般步骤针对所给问题，定义问题的解空间，它至少包含问题的一个最优解。题目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...

linkin 2019-08-23 18:29 评论0 收藏0