# LeetCode Solution(Easy.73-76)

## c/c++，python，for work

Posted by elmagnifico on December 25, 2016

## 73.Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Explanation: The perimeter is the 16 yellow stripes in the image below:


### 73.Island Perimeter-Solution-C/C++

class Solution
{
public:
int islandPerimeter(vector<vector<int>>& grid)
{
int edge=0,r=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[i].size();j++)
{
if(grid[i][j]==1)
{
//检查他的上下左右
if((i!=0)&&(grid[i-1][j]==1))
{//上
;
}
else
edge+=1;
if((i!=grid.size()-1)&&(grid[i+1][j]==1))
{//下
;
}
else
edge+=1;
if((j!=0)&&(grid[i][j-1]==1))
{//左
;
}
else
edge+=1;
if((j!=grid[i].size()-1)&&(grid[i][j+1]==1))
{//右
;
}
else
edge+=1;
}
r=r+edge;
edge=0;
}
}
return r;
}
};


### 73.Island Perimeter-Solution-Python

class Solution(object):
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
edge=0
r=0
for i in range(0,len(grid)):
for j in range(0,len(grid[i])):
if grid[i][j]==1:
if i!=0 and grid[i-1][j]==1:
d=1
else:
edge=edge+1
if i!=len(grid)-1 and grid[i+1][j]==1:
d=1
else:
edge=edge+1
if j!=0 and grid[i][j-1]==1:
d=1
else:
edge=edge+1
if j!=len(grid[i])-1 and grid[i][j+1]:
d=1
else:
edge=edge+1
r=r+edge
edge=0
return r


## 74.Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example: Given a = 1 and b = 2, return 3.

Credits: Special thanks to @fujiaozhu for adding this problem and creating all test cases.

### 74.Sum of Two Integers-Solution-C/C++

class Solution
{
public:
int getSum(int a, int b)
{
while(b)
{
int x=a^b,c=(a&b)<<1;
a=x;
b=c;
}
return a;
}
};


### 74.Sum of Two Integers-Solution-Python

class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
while b!=0:
x=a^b
c=(a&b)<<1
a=x
b=c
return a


class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
MAX_INT = 0x7FFFFFFF
MIN_INT = 0x80000000
while b:
a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)


当两个负数使用异或和与时会出现下面的结果

-1 表示为 原码1000...0001 反码是1111....1110

(0, 4294967294) 对应的实际是(0,1111 1111 1111 1111 1111 1111 1111 1110)

(4294967294, 0) 对应的实际是(1111 1111 1111 1111 1111 1111 1111 1110,0)



## 75.Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.


### 75.Find the Difference-Solution-C/C++

class Solution
{
public:
char findTheDifference(string s, string t)
{
char r=0;
for(int i=0;i<s.size();i++)
{
r=r^s[i]^t[i];
}
r=r^t[t.size()-1];
return r;
}
};


### 75.Find the Difference-Solution-Python

class Solution(object):
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
l=s+t
r=0
for i in range(0,len(l)):
r=r^ord(l[i])
return chr(r)


Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1
you could only make the child whose greed factor is 1 content.
You need to output 1.


Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.


class Solution
{
public:
int findContentChildren(vector<int>& g, vector<int>& s)
{
int count=0,cur=0,curs=0,find=0;
for(int i=0;i<g.size();i++)
{
cur=0x7fffffff;
curs=0x7fffffff;
find=0;
for(int j=0;j<s.size();j++)
{
if(s[j]==g[i])
{
find=1;
curs=j;
break;
}
else
{
if(s[j]>g[i]&&s[j]!=0)
{
if(s[j]>cur)
{
;
}
else
{
cur=s[j];
curs=j;
find=1;
}
}
}
}
if(find)
{
count++;
s[curs]=0;
}

}
return count;
}
};


class Solution
{
public:
int findContentChildren(vector<int>& g, vector<int>& s)
{
int n=g.size(),m=s.size();
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int i=0,j=0;
while(i<n&&j<m)
{
if(s[j]>=g[i])
i++;
j++;
}
return i;
}
};


class Solution(object):
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
g.sort()
s.sort()
m,n=len(g),len(s)
i,j=0,0
while i<m and j<n:
if s[j]>=g[i]:
i+=1
j+=1
return i


## Quote

http://blog.csdn.net/booirror/article/details/51816003