Welcome to Shanshan Blog!
-
Leetcode (48, 64, 542) Matrix Series
Leetcode Matrix Series
Leetcode 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?
class Solution { public: void rotate(vector<vector<int>>& matrix) { if (matrix.empty()) return; const int n = matrix.size(); for (int i=0; i<n; i++) for (int j=0; j<i; j++) swap(matrix[i][j], matrix[j][i]); for (int j=0; j<n/2; j++) for (int i=0; i<n; i++) swap(matrix[i][j], matrix[i][n-1-j]); } };Leetcode 64. Minimum Path Sum
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.
class Solution { public: int minPathSum(vector<vector<int>>& grid) { for (int i=0; i<grid.size(); i++) for (int j=0; j<grid[0].size(); j++) { if (i==0 && j==0) continue; else grid[i][j] = min((i-1>=0 ?grid[i-1][j]:INT_MAX), (j-1>=0?grid[i][j-1]:INT_MAX))+grid[i][j]; } return grid.back().back(); } };Leetcode 542. 01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
0 0 0 0 1 0 0 0 0Output:
0 0 0 0 1 0 0 0 0Example 2:
Input:
0 0 0 0 1 0 1 1 1Output:
0 0 0 0 1 0 1 2 1Note:
-
The number of elements of the given matrix will not exceed 10,000.
-
There are at least one 0 in the given matrix.
-
The cells are adjacent in only four directions: up, down, left and right.
class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { const int n = matrix.size(); const int m = matrix[0].size(); typedef pair<int, int> p; queue<p> q; vector<vector<int>> ans(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) if (matrix[i][j] == 1) ans[i][j] = -1; else q.push(p(i, j)); } p direct[4] = {p(-1, 0), p(1,0),p(0,1), p(0, -1)}; while (q.size() > 0) { p temp = q.front(); for (int i = 0; i < 4; i++) { int x = temp.first+direct[i].first; int y = temp.second+direct[i].second; if (x>=0 && x<n && y>=0 && y<m) if (ans[x][y] == -1) { ans[x][y] = ans[temp.first][temp.second]+1; q.push(p(x, y)); } } q.pop(); } return ans; } };
-
-
Leetcode (45, 55) Jump Game I,II
Leetcode 55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
class Solution { public: bool canJump(vector<int>& nums) { int temp = 1; for (int n:nums) { if (temp==0) return false; temp = max(temp-1, n); } return true; } };Leetcode 45. Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
class Solution { public: int jump(vector<int>& nums) { int res = 0, last = 0, curr = 0; for (int i=0; i<nums.size(); i++) { if (i>last) { last = curr; ++res; } curr = max(curr, i+nums[i]); } return res; } };
-
Leetcode (43, 49, 67, 539) String Series II
- Leetcode 43. Multiply Strings
- Leetcode 49. Group Anagrams
- Leetcode 67. Add Binary
- Leetcode 539. Minimum Time Difference
Leetcode String Series II
Leetcode 43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
-
The length of both num1 and num2 is < 110.
-
Both num1 and num2 contains only digits 0-9.
-
Both num1 and num2 does not contain any leading zero.
-
You must not use any built-in BigInteger library or convert the inputs to integer directly.
class Solution { public: string multiply(string num1, string num2) { const int m = num1.size(); const int n = num2.size(); string res(m+n+1, '0'); for (int i=m-1; i>=0; i--) for (int j=n-1; j>=0; j--) { int temp = (num1[i]-'0')*(num2[j]-'0') + (res[i+j+2]-'0'); res[i+j+2] = '0'+temp%10; res[i+j+1] += temp/10; } size_t begin = res.find_first_not_of('0'); if(begin == string::npos) return "0"; return res.substr(begin); } };Leetcode 49. Group Anagrams
Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:
[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]Note: All inputs will be in lower-case.
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; if (strs.empty()) return res; unordered_map<string, vector<string>> table; for (string str: strs) { string key = str; sort(key.begin(), key.end()); table[key].push_back(str); } for (auto i=table.begin(); i!=table.end(); i++) res.push_back(i->second); return res; } };Leetcode 67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = “11”
b = “1”
Return “100”.
class Solution { public: string addBinary(string a, string b) { if (a.empty()) return b; if (b.empty()) return a; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int i = 0, j = 0, carry = 0; string res = ""; while (i<a.size() || j<b.size()) { if (i<a.size()) carry += a[i++]-'0'; if (j<b.size()) carry += b[j++]-'0'; res += (char)(carry%2+'0'); carry /= 2; } if (carry) res += '1'; reverse(res.begin(), res.end()); return res; } };Leetcode 539. Minimum Time Difference
Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.
Example 1:
Input: ["23:59","00:00"] Output: 1Note:
-
The number of time points in the given list is at least 2 and won’t exceed 20000.
-
The input time is legal and ranges from 00:00 to 23:59.
class Solution { public: int findMinDifference(vector<string>& timePoints) { if (timePoints.empty()) return 0; sort(timePoints.begin(), timePoints.end()); int res = INT_MAX; const int n = timePoints.size(); int val[n] = {0}; int val2[n] = {0}; for (int i = 0; i<timePoints.size(); i++) { val[i] = stoi(timePoints[i].substr(0,2)); val2[i] = stoi(timePoints[i].substr(3,2)); } for (int i = 1; i<timePoints.size(); i++) { res = min(res, (val[i]-val[i-1])*60+val2[i]-val2[i-1]); res = min(res, (val[i-1]+24-val[i])*60+val2[i-1]-val2[i]); } res = min(res, (val[0]+24-val[n-1])*60+val2[0]-val2[n-1]); return res; } };
-
Leetcode (36, 37) Sudoku
Leetcode 36. Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { if (board.empty()) return false; const int n = board.size(); vector<int> count; // row for (int i=0; i<n; i++) { count.assign(9, 0); for (int j=0; j<n; j++) { if (board[i][j]!='.') { int pos = board[i][j]-'1'; if (count[pos]>0) return false; else ++count[pos]; } } } //column for (int j=0; j<n; j++) { count.assign(9, 0); for (int i=0; i<n; i++) { if (board[i][j]!='.') { int pos = board[i][j]-'1'; if (count[pos]>0) return false; else ++count[pos]; } } } //3*3 chunk for (int i=0; i<n; i+=3) { for (int j=0; j<n; j+=3) { count.assign(9, 0); for (int row=i; row<i+3; row++) for (int col=j; col<j+3; col++) { if (board[row][col]!='.') { int pos = board[row][col]-'1'; if (count[pos]>0) return false; else ++count[pos]; } } } } return true; } };Leetcode 37. Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.
class Solution { public: bool solveSudoku(vector<vector<char>>& board) { for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) if (board[i][j] == '.') { for (int k = 0; k < 9; ++k) { board[i][j] = '1' + k; if (isValid(board, i, j) && solveSudoku(board)) return true; board[i][j] = '.'; } return false; } return true; } bool isValid(const vector<vector<char> > &board, int x, int y) { int i, j; for (i = 0; i < 9; i++) if (i != x && board[i][y] == board[x][y]) return false; for (j = 0; j < 9; j++) if (j != y && board[x][j] == board[x][y]) return false; for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++) for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++) if ((i != x || j != y) && board[i][j] == board[x][y]) return false; return true; } };
-
Bit Operations in CPP
-
Leetcode 30 Substring with Concatenation of All Words
Leetcode 30. Substring with Concatenation of All Words
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]
You should return the indices: [0,9]. (order does not matter).
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> res; if (s.empty() || words.empty()) return res; map<string, int> word; map<string, int> curr; for (string str: words) word[str]++; int m = words[0].size(); int n = words.size(); if (s.size()<m*n) return res; for (int i=0; i<=s.size()-m*n; i++) { curr.clear(); int j = 0; for (j=0; j<n; j++) { string temp = s.substr(i+j*m, m); if (word.find(temp)==word.end()) break; curr[temp]++; if (curr[temp]>word[temp]) break; } if (j==n) res.push_back(i); } return res; } };