[Leetcode] 42, 48, 89

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,  Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Solution:  当用水填充完成后，在最大值的左边一定是递增的，最大值右边一定是递减的。因此可以找到最大值后，一边填充水一边累加填充的水量。

Code: 

class Solution { public: int trap(vector<int>& height) { int maxI = 0; for(int i=0; i<height.size(); i++) if(height[i] > height[maxI]) maxI = i; int volumn = 0; //处理左半部分 for(int i=1; i<maxI; i++){ if(height[i] < height[i-1]){ volumn += height[i-1]-height[i]; height[i] = height[i-1]; } } //处理右半部分 for(int i=height.size()-2; i>maxI; i--){ if(height[i] < height[i+1]){ volumn += height[i+1] - height[i]; height[i] = height[i+1]; } } return volumn; } };

48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

Solution(1):  从外到内一圈一圈的转，直接模拟顺时针旋转90度。思路很简单，但写起来容易写错。

Code: 

class Solution { public: void rotate(vector<vector<int>>& matrix) { int xi = 0; for(int width=matrix.size(); width>1; width-=2,xi++){ for(int i=0; i<width-1; i++){ int tmp = matrix[xi][xi+i]; matrix[xi][xi+i] = matrix[xi+(width-1-i)][xi]; matrix[xi+(width-1-i)][xi] = matrix[xi+width-1][xi+(width-1-i)]; matrix[xi+width-1][xi+(width-1-i)] = matrix[xi+i][xi+width-1]; matrix[xi+i][xi+width-1] = tmp; } } } };

Solution(2):  顺时针旋转90度相当于先上下翻转，然后沿着对角线（从右上角到左下角）翻转。

Code: 

class Solution { public: void rotate(vector<vector<int>>& matrix) { //上下翻转 for(int i=0; i<matrix.size(); i++){ for(int t=0; t<matrix.size()/2; t++){ swap(matrix[t][i],matrix[matrix.size()-t-1][i]); } } //沿对角线翻转 for(int i=0; i<matrix.size(); i++){ for(int t=0; t<i; t++){ swap(matrix[i][t],matrix[t][i]); } } } };

89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 01 - 1 11 - 3 10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Solution(1):  借鉴了别人的做法：格雷码的求解可以如图计算。

Code:

class Solution { public: vector<int> grayCode(int n) { vector<int> ans; ans.push_back(0); if(n==0) return ans; ans.push_back(1); if(n==1) return ans; for(int i=1; i<n; i++){ for(int t=ans.size()-1; t>=0; t--){ ans.push_back(ans[t]+pow(2,i)); } } return ans; } }; Solution(2):  格雷码是一种特殊的编码方式，主要用于电路设计中以便减小能耗。整数转格雷码和格雷码转整数都有数学公式：

Code:

class Solution { public: vector<int> grayCode(int n) { vector<int> ans; int size = 1<<n; //2^n for(int i=0; i<size; i++){ ans.push_back(binary2gray(i)); } return ans; } private: unsigned int binary2gray(unsigned int n){ return n^(n>>1); //^表示异或 } unsigned int gray2binary(unsigned int n){ for(int i=n>>1; i!=0; i=i>>1){ n = n^i; } return n; } };