LeetCode偶爾一題 —— 832. 翻轉圖像

WalkerXu 發布于2019-08-26 14:04 / 604人閱讀

題目描述

分析題目

按照題意我們只要先對每個子數組先做逆序，再做 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掉

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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