LeetCode num064

Minimum Path Sum

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
int minPathSum(vector<vector<int> > &grid)
{

int row = grid.size();
if (row == 0) return 0;
int column = grid[0].size();
if (column == 0) return 0;
vector<vector<int>> markMin = grid;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
if (i == 0 && j == 0) markMin[i][j] = grid[0][0];
else if (i == 0) markMin[i][j] = markMin[i][j - 1] + grid[i][j];
else if (j == 0) markMin[i][j] = markMin[i - 1][j] + grid[i][j];
else markMin[i][j] = (markMin[i][j - 1] < markMin[i - 1][j] ?
markMin[i][j - 1] : markMin[i - 1][j]) + grid[i][j];
}
}
return markMin[row - 1][column - 1];
}
};

Comment

  1. 时间复杂度O(m*n)
  2. 动态规划

LeetCode num191

Number of 1 Bits

Problem

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution
{
public:
int hammingWeight(uint32_t n)
{

int result = 0;
while (n != 0)
{
result += n % 2;
n = n / 2;
}
return result;
}
};

Comment

  1. 时间复杂度O(logn)

LeetCode num190

Reverse Bits

Problem

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution 
{
public:
uint32_t reverseBits(uint32_t n)
{
uint32_t result = 0;
int i = 31;
while (n != 0)
{
result += (n % 2) * pow(2, i);
n = n / 2;
i--;
}
return result;
}
};

Comment

  1. 时间复杂度O(logn)

LeetCode num189

Rotate Array

Problem

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
void rotate(int nums[], int n, int k) {
if (n != 0)
{
k = k % n;
vector<int> remember;
for (int i = 0; i < n - k; i++)
{
remember.push_back(nums[i]);
}
for (int i = 0; i < k; i++)
{
nums[i] = nums[i + n - k];
}
for (int i = 0; i < n - k; i++)
{
nums[i + k] = remember[i];
}
}
}
};

Comment

  1. 题目较简单

LeetCode num171

Excel Sheet Column Number

Problem

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

1
2
3
4
5
6
7
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution
{
public:
int titleToNumber(string s)
{

int size = s.size();
int result = 0;
for (int i = size - 1; i >= 0; i--)
{
int love = pow(26, size - i - 1);
int sadness = s[i] - 'A' + 1;
result += love * sadness;
}
return result;
}
};

Comment

  1. 题目较简单

LeetCode num169

Majority Element

Problem

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution 
{
public:
int majorityElement(vector<int> &num)
{

int i, result, mark, markPosition, isMark = 0;
for (i = 0; i < num.size(); i++)
{
if (i == 0)
{
mark = num[0];
markPosition = 0;
isMark = 1;
continue;
}
else if (isMark == 0)
{
markPosition = i - 1;
mark = num[markPosition];
isMark = 1;
}
if (num[i] != mark)
{
num.erase(num.begin() + markPosition);
num.erase(num.begin() + i - 1);
isMark = 0;
i -= 2;
}
}
result = num[0];
return result;
}
};

Comment

  1. 技巧性较强
  2. 看清题中限定条件
  3. 时间复杂度O(n)
  4. 思路:不一样直接扔掉,取最后剩下的值