Leetcode每天兩題1

03-06

擼代碼有時候並不能讓我快樂，所以先來一張美女圖片養眼（現在的女生長得都一個樣，這個稍有不同，別問我哪裡不同，我哪知。。。）

完全看心情沒有順序的開始擼代碼！

733.Flood Fill

其實就是在目標像素的上下左右4領域內搜索顏色（數值）相等的像素，然後用新顏色（數字）替換原數值。靈魂式翻譯，覺得不合口味的請看原文。↓

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Input: image = [[1,1,1],[1,1,0],[1,0,1]]sr = 1, sc = 1, newColor = 2Output: [[2,2,2],[2,2,0],[2,0,1]]Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color.Note the bottom corner is not colored 2, because it is not 4-directionally connectedto the starting pixel.

代碼+注釋

class Solution {public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { if (image[sr][sc] == newColor) return image; //二維vector的大小 int rows = image.size(); int cols = image[0].size(); SearchAndFill(image, rows, cols, sr, sc, image[sr][sc], newColor); return image; }private: //遞歸 void SearchAndFill(vector<vector<int>>& image, int rows, int cols, int sr, int sc, int oldColor, int newColor) { //遞歸結束條件 //先判斷目標像素點是不是在數組範圍內； //判斷是否和原數值相等 if (sr<0 || sr >= rows || sc<0 || sc >= cols) return; if (image[sr][sc] != oldColor) return; //遞歸遍歷整個圖像（數值） image[sr][sc] = newColor; SearchAndFill(image, rows, cols, sr + 1, sc, oldColor, newColor); SearchAndFill(image, rows, cols, sr - 1, sc, oldColor, newColor); SearchAndFill(image, rows, cols, sr, sc + 1, oldColor, newColor); SearchAndFill(image, rows, cols, sr, sc - 1, oldColor, newColor); }};

14. Longest Common Prefix

給定一個字元串數值，找出數值元素的最長公共前綴。同樣原味的看下面↓。

Write a function to find the longest common prefix string amongst an array of strings.

代碼+注釋

class Solution {public: string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) return ""; return Divide(strs, 0, strs.size() - 1); }private://細分問題 string Divide(vector<string>& strs, int left, int right) { if (left == right) return strs[left];//注意 else { int mid = (left + right) / 2; string commonLeft = Divide(strs, left, mid); string commonRight = Divide(strs, mid + 1, right); //求解問題 return CommonPrefix(commonLeft, commonRight); } } string CommonPrefix(string left, string right) { int minLength = min(left.length(), right.length()); for (int i = 0; i<minLength; i++) { if (left.at(i) != right.at(i)) return left.substr(0, i); } return left.substr(0, minLength); }};