uuuouou
BAN USERC++ version:
string& countConsecutiveCharacter(string& dest, const string& src)
{
dest.clear();
size_t i, len = src.size(), j;
for(i = 0; i < len; i = j){
char c = toupper(src[i]);
for(j = i+1; j < len && toupper(src[j]) == c; ++j) ;
//now j-i is the repeat times of c
dest.push_back(c);
dest.append(to_string(j-i));
}
return dest;
}
(1)For M*N matrix, brute force has O(1) space complexity and O(M*M*M*N*N*N) time complexity for enumerating every submatrix then counting ones and zeros inside.
(2)Following is a method that has O(M*N) space complexity and O(M*M*N*N) time complexity:
public class ZerosOnesMatrix {
static public void printSubMatrix(int leftUpRow, int leftUpCol, int rightDownRow, int rightDownCol, int[][] matrix){
System.out.println("(" + leftUpRow + "," + leftUpCol + ") => (" + rightDownRow + "," + rightDownCol + ")");
for(int i = leftUpRow; i <= rightDownRow; ++i){
for(int j = leftUpCol; j <= rightDownCol; ++j){
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
static public void printSubmatrixWithEqualZerosAndOnes(int[][] matrix){
int M = matrix.length, N = matrix[0].length;
/*
* step 1: create memory for submatrix with left up being (0, 0)
* first dimension is submatrix's right down row
* second dimension is submatrix's right down col
* count[][][0] is this submatrix's count of zeros
* count[][][1] is this submatrix's count of ones
*/
int[][][] count = new int[M][N][2];
/*
* step 2: initialize first row's count and first col's count
*/
count[0][0][0] = matrix[0][0] == 0 ? 1 : 0;
count[0][0][1] = matrix[0][0] == 0 ? 0 : 1;
for(int col = 1; col < N; ++col){
count[0][col][0] = count[0][col-1][0];
count[0][col][1] = count[0][col-1][1];
++count[0][col][matrix[0][col]];
}
for(int row = 1; row < M; ++row){
count[row][0][0] = count[row-1][0][0];
count[row][0][1] = count[row-1][0][1];
++count[row][0][matrix[row][0]];
}
/*
* step 3: enumerate each submatrix with left up being (0, 0)
* and calculate its count of ones and zeros
*/
for(int row = 1; row < M; ++row){
for(int col = 1; col < N; ++col){
count[row][col][0] = count[row-1][col][0] + count[row][col-1][0] - count[row-1][col-1][0];
count[row][col][1] = count[row-1][col][1] + count[row][col-1][1] - count[row-1][col-1][1];
++count[row][col][matrix[row][col]];
}
}
/*
* step 4: enumerate every submatrix and check its count of ones and zeros
*/
int[] subCount = {0, 0};
for(int leftUpRow = 0; leftUpRow < M; ++leftUpRow){
for(int leftUpCol = 0; leftUpCol < N; ++leftUpCol){
for(int rightDownRow = leftUpRow; rightDownRow < M; ++rightDownRow){
for(int rightDownCol = leftUpCol; rightDownCol < N; ++rightDownCol){
for(int i = 0; i < 2; ++i){
subCount[i] = count[rightDownRow][rightDownCol][i] -
(leftUpRow > 0 ? count[leftUpRow-1][rightDownCol][i] : 0) -
(leftUpCol > 0 ? count[rightDownRow][leftUpCol-1][i] : 0) +
(leftUpRow > 0 && leftUpCol > 0 ? count[leftUpRow-1][leftUpCol-1][i] : 0);
}
if(subCount[0] == subCount[1]) printSubMatrix(leftUpRow, leftUpCol, rightDownRow, rightDownCol, matrix);
}
}
}
}
}
static public void main(String[] args){
int matrix[][] = {
{0, 1, 0, 1, 0},
{0, 0, 1, 1, 0},
{0, 0, 0, 0, 1},
{1, 0, 1, 0, 0}
};
printSubmatrixWithEqualZerosAndOnes(matrix);
}
}
@ninhnnsoc, no, it won't fail. Because here ":" is just used to separate one string's length and its content. Let's take ":::123abc*?." as an example, in above way its encoded string will be "12::::123abc*?.", when we apply the retrieve function:
(1)first we find the position of the first ":", say at idx
(2)then we slice out the length being "12",
(3)we slice out [idx+1, idx+1+length), which is exactly the origin string content.
(1)We don't know exactly what charset is used by these string, so we may not simply add a special character in between to separate these strings.
(2)But we can add the length info before each string, so that when we want to retrieve them, we figure out the length then slice out the origin string:
string& encode(string& dest, const vector<string>& v)
{
dest.clear();
for(size_t i = 0; i < v.size(); ++i){
dest.append(to_string(v[i].size()));//length
dest.append(":"); /* note that we add ':' to separate length and content in case that origin string begins with a digit */
dest.append(v[i]);//origin string
}
return dest;
}
bool decode(vector<string>& v, const string& s)
{
v.clear();
size_t i = 0, j, len;
for(; i < s.size(); i = j + 1 + len){
j = s.find(':', i); //locate ':' between length and content
if(j == string::npos) return false;
len = strtoul(v.substr(i, j-i));//parse length
if(j + 1 + len > s.size()) return false;
v.push_back(s.substr(j+1, len));
}
return true;
}
bool isSpamOf(const string& s, const string& word)
{
if(s.size() <= word.size()) return false;//no char repeat
if(s[0] != word[0]) return false; //first char not same
int i = 1, j = 1, n = s.size(), wordlen = word.size();
for(; i < n && j < wordlen; ++i, ++j){
if(s[i] != word[j]){//s[i] may be repeating char of previous
for(; i < n && s[i] == s[i-1]; ++i) ;//skip repeats
if(i == n || s[i] != word[j]) break; //still can not match
}
}
if(j == wordlen){//check if remaining chars of s are all word's last char
for(; i < n; ++i){
if(s[i] != word.back()) return false;
}
return true;
}
else return false;
}
int jump(int i, int arr[], int n, int step[])
{
if(i >= n) return 0;
if(arr[i] <= 0) return -1;
if(step[i] > 0 ) return step[i];
for(int dis = arr[i]; dis > 0; --dis){
int tmp = jump(i + dis, arr, n, step);
if(tmp >= 0){
step[i] = step[i] < 0 ? 1 + tmp : min(step[i], 1 + tmp);
}
}
return step[i];
}
int jump(int arr[], int n)
{
if(n == 1) return arr[0] > 0 ? 1 : -1;
int* step = new int[n];
memset(step, 0xff, sizeof(int) * n);
int res = jump(0, arr, n, step);
delete[] step;
return res;
}
Assuming no two nodes' values are same, we can rebuild tree by dividing and conquering. Code in C++:
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(NULL), right(NULL){}
};
vector<int>& getSubLevel(vector<int>& sublevel, const vector<int>& sub, const vector<int>& level)
{
sublevel.clear();
for(int i = 0; i < level.size(); ++i){
if(find(sub.begin(), sub.end(), level[i]) != sub.end()) sublevel.push_back(level[i]);
}
return sublevel;
}
TreeNode* rebuildByInorderLevelTraverse(const vector<int>& inorder, const vector<int>& level)
{
if(level.empty()) return NULL;
TreeNode* t = new TreeNode(level[0]);
if(level.size() > 1){
int i = 0;
for(; i < inorder.size(); ++i){
if(inorder[i] == level[0]) break;
}
vector<int> sub, sublevel;
if(i > 0){
sub.assign(inorder.begin(), inorder.begin() + i);
t->left = rebuildByInorderLevelTraverse(sub, getSubLevel(sublevel, sub, level));
}
if(i + 1 < inorder.size()){
sub.assign(inorder.begin() + i + 1, inorder.end());
t->right = rebuildByInorderLevelTraverse(sub, getSubLevel(sublevel, sub, level));
}
}
return t;
}
We check whether there's a substring of b, which has same size and same characters with a.
bool hasAnagramSubstring(const string& src, const string& target)
{
if(target.size() > src.size()) return false;
int srcLen = src.size(), targetLen = target.size();
int targetCount[128] = {0}, count[128] = {0}, i, j;
//initialize
for(i = 0; i < target.size(); ++i){
++targetCount[target[i]];
++count[src[i]];
}
//loop
i = 0;
while(true){
//check if substring is an anagram
for(j = 0; j < targetLen; ++j){
if(count[target[j]] != targetCount[target[j]]) break;
}
if(j == targetLen) return true;
//slide window
if(i + 1 + targetLen > srcLen) break;
--count[src[i]];
++count[src[i + targetLen]];
++i;
}
return false;
}
In C++:
#include <iostream>
#include <cctype>
#include <string>
using namespace std;
string& reverseLetters(string& dest, const string& src)
{
dest.clear();
dest.resize(src.size());
for(int i = 0, j = src.size() - 1; j >= 0; ){
if(isdigit(src[i])){
dest[i] = src[i];
++i;
}
else if(isdigit(src[j])) --j;
else{
dest[i] = src[j];
++i;
--j;
}
}
return dest;
}
int main()
{
string t, s = "str1ngw1thnumb3rs";
cout << reverseLetters(t, s) << "\n";
getchar();
return 0;
}
How about using a balanced BST, like this:
void getMinInWindow(vector<int>& res, const vector<int>& src, int windowSize)
{
res.clear();
set<int> windowSet;
int i, j, n = src.size();
for(i = 0; i + windowSize <= n; ++i){
for(j = 0; j < windowSize; ++j) windowSet.insert(src[i+j]);
res.push_back(*windowSet.rbegin());
windowSet.erase(src[i]);
}
}
In the binary representation of the number, we count how many 0s there are on each 1's left side. If the sum is odd, the first player will be the winner, otherwise second player will win.
#include <iostream>
#include <string>
using namespace std;
string& toReverseBinary(string& s, int n)
{
s.clear();
for(; n > 0; n >>= 1) s.push_back('0' + (n & 1));
return s;
}
int totalZerosBeforeOnes(const string& s)
{
int total = 0, zerosSoFar = 0;
for(int i = 0, len = s.size(); i < len; ++i){
if(s[i] == '0') ++zerosSoFar;
else total += zerosSoFar;
}
return total;
}
int main()
{
int T, n;
string s;
s.reserve(32);
cin >> T;
while(T--){
cin >> n;
if(totalZerosBeforeOnes(toReverseBinary(s, n)) & 1)
cout << "First Player\n";
else
cout << "Second Player\n";
}
return 0;
}
Assuming input is a positive integer, following is code in C++:
bool nextInteger(string& res, int i, const string& src, bool used[], bool alreadyLarger)
{
if(i == src.size()) return src < res;
if(alreadyLarger){//set every position left with smallest integer not used
int k = 0;
for(; i < src.size(); ++i){
for(; k < 10; ++k){
if(!used[k]){
res[i] = '0' + k++;
break;
}
}
}
return true;
}
for(char c = src[i]; c <= '9'; ++c){
if(used[c - '0']) continue;
res[i] = c;
used[c - '0'] = true;
if(nextInteger(res, i + 1, src, used, c > src[i])) return true;
used[c - '0'] = false;
}
return false;
}
string nextInteger(const string& input)
{
static const string limit[11] = {
"",
"9",
"98",
"987",
"9876",
"98765",
"987654",
"9876543",
"98765432",
"987654321",
"9876543210",
};
int len = input.size();
if(len > 10 || len == 10 && limit[10] <= input) return "";//no such number
string res;
if(limit[len] <= input){//result is smallest with length = input.length + 1
res.resize(len + 1);
res[0] = '1';
res[1] = '0';
for(int i = 2; i <= len; ++i){
res[i] = i + '0';
}
}
else{//get next larger with length = input.length
res.resize(len);
bool used[10] = {0};
nextInteger(res, 0, input, used, false);
}
return res;
}
We fix the problem using DFS. Here's code in C++:
void printAttribute(vector<string>& combination)
{
cout << combination[0];
for(int i = 1; i < combination.size(); ++i){
cout << " - " << combination[i];
}
cout << "\n";
}
void permutate(vector<vector<string> >& attributes, int i, vector<string>& combination)
{
if(i == attributes.size()){
printAttribute(combination);
return;
}
for(int k = 0; k < attributes[i].size(); ++k){
combination[i] = attributes[i][k];
permutate(attributes, i + 1, combination);
}
}
void enumerateAttributeCombinations(vector<vector<string> >& attributes)
{
if(attributes.empty()) return;
vector<string> combination;
combination.resize(attributes.size());
permutate(attributes, 0, combination);
}
void multiplyAllOthers(int arr[], int n)
{
int* copy = new int[n];
memcpy(copy, arr, sizeof(int) * n);
//multiply all others in the left
for(int productSoFar = 1, i = 0; i < n; ++i){
arr[i] *= productSoFar;
productSoFar = arr[i];
}
//multiply all others in the right
for(int productSoFar = 1, i = n-1; i >= 0; --i){
arr[i] *= productSoFar;
productSoFar *= copy[i];
}
delete[] copy;
}
time:O(n), space:O(n)
- uuuouou March 07, 2014void printOffsetOfRuns(const string& s)
{
bool first = true;
int i = 0, j, n = s.size();
for(; i < n; i = j){
for(j = i+1; j < n && s[j] == s[i]; ++j) ;
//now j - i is the repeat times of s[i]
if(j - i > 1){
if(first) first = false;
else printf(", ");
printf("%d", i);
}
}
}
In C++:
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v):val(v), left(NULL), right(NULL){}
};
TreeNode* buildBalanceTree(int arr[], int s, int e)
{
if(s == e) return new TreeNode(arr[s]);
int m = (s + e) >> 1;
TreeNode* t = new TreeNode(arr[m]);
if(m > s) t->left = buildBalanceTree(arr, s, m-1);
t->right = buildBalanceTree(arr, m+1, e);
return t;
}
private int getPath(int start, int end, boolean[] vis, int[] pathLen)
{
if(start == end) return 0;
if(pathLen[start] != -1) return pathLen[start];
int len = m_Matrix.length + 1;
vis[start] = true;
for(int i = 0; i < m_Matrix.length; ++i){
if(vis[m_Matrix[start][i]]) continue;
len = Math.min(len, 1 + getPath(i, end, vis, pathLen));
}
vis[start] = false;
return pathLen[start] = len;
}
public int shortestPath(int start, int end)
{
if(start == end) return 0;
if(m_Matrix[start][end]) return 1;
boolean[] vis = new boolean[m_Matrix.length];
Arrays.fill(vis, false);
int pathLen = new int[m_Matrix.length];
Arrays.fill(pathLen, -1);
int len = getPath(start, end, vis);
return len > m_Matrix.length ? -1 : len;
}
We may print from right up to right left down, following is C++ code:
/*
------->x
|
|
|
y
*/
void printMatrixDiagonally(int** matrix, int row, int col)
{
int y, x;
pair<int,int> rightUp(0, 0), leftDown(0,0); //(y, x)
while(rightUp.first < row){
//print from right up to left down
for(y = rightUp.first, x = rightUp.second; y <= leftDown.first; ++y, ++x){
printf("%d ", matrix[y][x]);
}
puts("");
//move rightUp and leftDown
if(rightUp.second + 1 < col) ++rightUp.second;
else ++rightUp.first;
if(leftDown.first + 1 < row) ++leftDown.first;
else ++leftDown.second;
}
}
How about this:
(1)use two HashSets instead of one HashMap, one for those numbers occurred odd times so far, let's call it oddSet, while the other for those occurred even times being evenSet.
(2)iterate to next number, if it has been in oddSet, we remove it from oddSet and add it to evenSet, otherwise we add it into oddSet and remove it from evenSet.
(3)finally, those numbers that occurred odd times are all in oddSet.
I don't know how to implement multi thread in C, following is Java code:
public class EvenOdd {
private static final int LIMIT = 20;
private int num = 0;
//method
public synchronized void printEven(){
while(num < LIMIT){
while((num & 1) == 1){
try{
wait();
} catch(InterruptedException e){
e.printStackTrace();
}
}
System.out.print(num + " ");
++num;
notify();
}
}
public synchronized void printOdd(){
while(num < LIMIT){
while((num & 1) == 0){
try{
wait();
} catch(InterruptedException e){
e.printStackTrace();
}
}
System.out.print(num + " ");
++num;
notify();
}
}
//work class that prints num
static class PrintEven implements Runnable{
private EvenOdd eo;
public PrintEven(EvenOdd eo){
this.eo = eo;
}
@Override
public void run() {
eo.printEven();
}
}
static class PrintOdd implements Runnable{
private EvenOdd eo;
public PrintOdd(EvenOdd eo){
this.eo = eo;
}
@Override
public void run() {
eo.printOdd();
}
}
//test
public static void main(String args[]){
EvenOdd eo = new EvenOdd();
new Thread(new PrintEven(eo)).start();
new Thread(new PrintOdd(eo)).start();
}
}
The thought is DFS:
private int getListSum(List<NestedInteger> lni, int depth)
{
int sum = 0;
NestedInteger ni = null;
while(lni.hasNext()){
ni = lni.next();
if(ni.isInteger()) sum += ni.getInteger() * depth;
else sum += getListSum(ni.getList(), depth + 1);
}
return sum;
}
public int getSum(NestedInteger ni)
{
if(ni.isInteger()) return ni.getInteger();
else return getListSum(ni.getList(), 1);
}
Because K != 0 and all numbers are distinct, which means all (num - K) are different, we may use hashtable to fix the problem in nearly O(n) time.
Following is C++ code:
int howmanyPairWithDifference(vector<int>& v, int K)
{
unordered_set<int> hash;
int i, n = v.size(), total = 0;
for(i = 0; i < n; ++i) hash.insert(v[i] - K);
for(i = 0; i < n; ++i){
if(hash.count(v[i])) ++total;
}
return total;
}
When we do reverse inorder traverse of BST, that is right--root--left, the nodes visited before current node are those having greater value. By keeping a record of the sum of all nodes visited, we can easily fix the problem.
Following is C code:
void replaceWithSumOfAllGreater(TreeNode* root, int* pSum)
{
if(root == NULL) return;
replaceWithSumOfAllGreater(root->right, pSum);
int tmp = *pSum + root->val;
root->val = *pSum;
*pSum = tmp;
replaceWithSumOfAllGreater(root->left, pSum);
}
void replaceWithSumOfAllGreater(TreeNode* root)
{
int sum = 0;
replaceWithSumOfAllGreater(root, &sum);
}
For a given subtree, there are 3 cases:
(1)root is NULL, then no such node in this subtree
(2)root->val < K, then the result might be in the root's right subtree or just root itself
(3)root->val >= K, then the result could only be in the root's left subtree
Following is C code:
TreeNode* findNextSmallerInBST(TreeNode* root, int K)
{
if(root == NULL) return NULL;
else if(root->val < K){
TreeNode* t = findNextSmallerInBST(root->right, K);
return t != NULL ? t : root;
}
else return findNextSmallerInBST(root->left, K);
}
1.Sort by "NumberOfTall" and "height":
(1)those who have fewer people taller in front of them have smaller index;
(2)for those having same number of tallers in front, the taller his own height is, the smaller index he has.
struct Person{
string name;
int height;
int frontTaller;
};
struct Compare{
bool operator()(const Person& a, const Person& b){
if(a.frontTaller != b.frontTaller) return a.frontTaller < b.frontTaller;
else return a.height > b.height;
}
};
2.Insert each person into the queue after counting his "NumberOfTaller":
list<Person> retrieveQueue(vector<Person>& v)
{
sort(v.begin(), v.end(), Compare());
list<Person> q;
list<Person>::iterator iter;
for(int i = 0; i < v.size(); ++i){
iter = q.begin();
for(int n = v[i].frontTaller; n > 0; ++iter){
if(iter->height > v[i].height) --n;
}
q.insert(iter, v[i]);
}
return q;
}
What about this:
(1)Get the line defined by the circle center O and the outside point P, then we can get the diameter AOB on this line. Let's say the endpoint close to P is A, and the other is B.
(2)Now all the N given points are in the circle defined by center P and radius PB, while no point is in the circle defined by center P and radius PA.
(3)Binary search radius till we find a radius R with which the defined circle has only one given point.
This might do it:
ListNode* reverseList(ListNode* head)
{
if(head == NULL || head->next == NULL) return head;
ListNode *pre = NULL, *nex;
for(; head != NULL; pre = head, head = nex){
nex = head->next;
head->next = pre;
}
return pre;
}
ListNode* reverseAlternateAppendToTail(ListNode* head)
{
if(head == NULL || head->next) return head;
//break into two lists
ListNode *list1 = head, *list2 = head->next, *p1 = list1, *p2 = list2, *p = list2->next;
bool first = true;
for(; p != NULL; p = p->next, first = !first){
if(first){
p1->next = p;
p1 = p1->next;
}
else{
p2->next = p;
p2 = p2->next;
}
}
//reverse list2 and append it to list1's tail
p2->next = NULL;
p1->next = reverseList(list2);
return list1;
}
#include <iostream>
#include <algorithm>
using namespace std;
void putOddInFrontOfEven(int a[], int n)
{
int i = 0;
//skip continuous odd numbers at front
for(; i < n && (a[i] & 1); ++i) ;
while(i < n){
//now a[i] is an even number
int evenStart = i;
for(; i < n && (a[i] & 1) == 0; ++i) ;
if(i == n) break;
//now a[i] is an odd number
int oddStart = i;
for(; i < n && (a[i] & 1); ++i) ;
//put those odd numbers in front of those even numbers
reverse(a + evenStart, a + oddStart);
reverse(a + oddStart, a + i);
reverse(a + evenStart, a + i);
}
}
int main()
{
int a[] = {2, 1, 5, 3}, n = sizeof(a)/sizeof(a[0]), i;
cout << "Initially:\n";
for(i = 0; i < n; ++i) cout << a[i] << " ";
putOddInFrontOfEven(a, n);
cout << "\nAfter putting odd numbers in front:\n";
for(i = 0; i < n; ++i) cout << a[i] << " ";
return 0;
}
(1)the array is in ascending order
>>> arr[i] > arr[i-1]
<=> arr[i] - arr[i-1] > 0
(2)the elements are integers
>>> arr[i] - arr[i-1] >= 1
<=> arr[i] - arr[i-1] >= i - (i-1)
<=> arr[i] - i >= arr[i-1] - (i-1)
(3)the array of arr[k]-k is in non-decesending order, so binary search works
I suppose we can solve it in this way:
(1)Go through the array and find how many odd numbers there are, say it's oddNum.
(2)If oddNum == 0 || oddNum == arr.length then sort is done.
(3)Else now we know that all odd numbers will be arr[0] to arr[oddNum-1] and all even numbers will be arr[oddNum] to arr[arr.length-1]. Thus we can go through the array again and at the same time put all the odd numbers into [0, oddNum) and all the even numbers into [oddNum, arr.length).
Say we want to print all the numbers with N digits and each digit has a given upperbound, so the number will be A[0]A[1]A[2]...A[N-1] with A[i] <= upperbound[i], then we may do like this:
void printNumber(char num[], int index, int N, int upperbound[])
{
if(index == N){
num[index] = '\0';
puts(num);
return;
}
num[index] = index == 0 ? '1' : '0';
for(; num[index] - '0' <= upperbound[index]; ++num[index]){
printNumber(num, index + 1, N, upperbound);
}
}
I think we can through the matrix first and find out all the zeros' cols and rows in it then fill those cols and rows.
But instead of scanning by row only or by col only, we can do it both in one loop, so the procedure is more like scanning the matrix from left up to right down, meanwhile we can record those to-be-filled cols and rows to save rebundant scannings.
import java.util.HashSet;
public class MatrixZero {
public static void findZeroFillRowCol(int[][] matrix){
int totalRow = matrix.length;
int totalCol = matrix[0].length;
HashSet<Integer> rowHasZero = new HashSet<Integer>();
HashSet<Integer> colHasZero = new HashSet<Integer>();
int row = 0, col = 0, i;
//scanning matrix
while(true){
if(row < totalRow){
if(!rowHasZero.contains(row)){
for(i = col; i < totalCol; ++i){
if(matrix[row][i] == 0){
rowHasZero.add(row);
colHasZero.add(i);
}
}
}
}
if(col < totalCol){
if(!colHasZero.contains(col)){
for(i = row; i < totalRow; ++i){
if(matrix[i][col] == 0){
colHasZero.add(col);
rowHasZero.add(i);
}
}
}
}
if(row + 1 == totalRow && col + 1 == totalCol) break;
if(row + 1 < totalRow) ++row;
if(col + 1 < totalCol) ++col;
}
//fill those rows and columns that contains zero
for(int r : rowHasZero){
for(i = 0; i < totalCol; ++i) matrix[r][i] = 0;
}
for(int c : colHasZero){
for(i = 0; i < totalRow; ++i) matrix[i][c] = 0;
}
}
public static void main(String[] args){
int[][][] array3d = {
{{0, 0, 0}, {0, 1, 2},{0, 3, 4}},
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 0, 0, 1}, {2, 3, 4, 5}}
};
for(int[][] matrix : array3d){
findZeroFillRowCol(matrix);
for(int[] arr : matrix){
for(int i : arr) System.out.print(i + " ");
System.out.println();
}
}
}
}
Suppose we have two queues as an array q[], we can do the following steps to sort them in order:
(1)Keep dequeuing q[0] and enqueue them into q[1], till q[0] is empty and q[1] has all the items.
>>> Now q[0] is empty and q[1] has all the items.
(2)Dequeue all items in q[1] and enqueue them into q[0], at the same time record how many items there are and the minimum item's position in the queue, let's say the there are N items in total, and the minimum is the Kth item in the queue now.
>>> Now q[0] has all the items and the minimum is the Kth item.
(3)Dequeue q[0] K-1 times and enqueue them into q[1], so that we have the minimum item in front of q[0]. Move all items in q[1] to q[0]. And then dequeue q[0] and enqueue it back.
>>> Now q[0] has all the items and the minimum is in the end.
(4)As for the second minimum item, just like repeating step 2 and step 3, but this time we only need to dequeue q[0] N-1 times at most to find out the second minimum item's position, because we already know the minimum is in the end! Then we can let the second minimum be the end of the queue, while the minimum is just in front of it.
>>> Now q[0] has all the items and the two minimums are in the end and in order.
(5)Repeat the procedure as stated above till the largest item is in the end of the queue and then the sorting is done.
Print up, then right, then down, then left, till up > down or left > right. Following is code in C.
void sprialPrint(int** matrix, int row, int col)
{
int i, up = 0, down = row-1, left = 0, right = col-1;
while(1){
if(left > right) break;
for(i = left; i <= right; ++i) printf("%d ", matrix[up][i]);
++up;
if(up > down) break;
for(i = up; i <= down; ++i) printf("%d ", matrix[i][right]);
--right;
if(left > right) break;
for(i = right; i >= left; --i) printf("%d ", matrix[down][i]);
--down;
if(up > down) break;
for(i = down; i >= up; --i) printf("%d ", matrix[i][left]);
++left;
}
}
I assume all numbers in the given array are nonnegtive. Following is a solution in C. Please notice that the combinations like 34352 with 56789 can result into an arithmetic overflow.
#include <stdio.h>
const int tenPower[10] = {
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000
};
//count how many digits the positive number has
int countDigits(int n)
{
int digits = 0;
for(; n != 0; n /= 10) ++digits;
return digits;
}
//check if the integer array can combine into the target number
int combine(int a[], int i, int n, int target)
{
if(i >= n) return target == 0;
if(a[i] == 0){//a combined decimal number can not start with 0
return combine(a, i+1, n, target);
}
int sum = 0;
for(; i < n; ++i){
//combine a number in this level
sum = sum * tenPower[countDigits(a[i])] + a[i];
//if already larger than target, then no need to search deeper
if(sum > target) break;
//search next level
if(combine(a, i+1, n, target - sum)) return 1;
}
return 0;
}
int main()
{
int a[] = {5,2,1,4,3,6,7,8}, target = 333;
if(combine(a, 0, sizeof(a)/sizeof(a[0]), target)) puts("YES");
else puts("NO");
return 0;
}
(1)Assign a number to each day of a week, say, Sunday = 0, Monday = 1, ... , Saturday = 6, then we can assume today is X, where 0 <= X <= 6.
(2)If X is 1,..,5, which means today is Monday,...,Friday, then the Nth business day from now will be (X + N)%5 + 1
(3)If X = 0 or X = 6, which means today is Sunday or Saturday, then the first business day from now will be Monday, just like today is Friday and X = 5.
(4)Let the Nth business day from now be Y, then from (2) and (3) we can conclude that Y = (((X > 0 && X < 6) ? X : 5) + N) % 5 + 1.
1.As for dividing two numbers, if we can not use "/", why not use "*" instead?
Take "a / b" as an example. We can do following steps:
(1)figure out the sign of the result: sign
(2)define a rough range of the result: [L, R]
(3)use binary search to find the result in the range, every time we only need to figure out the b * M, where M = (L+R)/2, and compare it with a to narrow the range.
Time complexity: O(log(a))
Space complexity: O(1)
following is C++ code:
bool div(int a, int b, int& res)
{
if(b == 0) return false;
//figure out the sign of result
int sign = 1;
if(a < 0){
a = -a;
sign *= -1;
}
if(b < 0){
b = -b;
sign *= -1;
}
//now a >= 0 and b >= 0
if(a < b){
res = 0;
return true;
}
if(b == 1){
res = sign * a;
return true;
}
//now a >= b && b >= 2, so a rough range is [1, a/2]
int L = 1, R = a >> 1, M, pro;
while(L <= R){
M = (L + R) >> 1;
pro = b * M;
if(pro <= 0){//multiply overflow
R = M - 1;
continue;
}
if(a == pro){
res = sign * M;
return true;
}
else if(a < pro) R = M - 1;
else L = M + 1;
}
res = sign * R;
return true;
}
2. It can bd done by:
(1)sort out the array
(2)for each element do a binary search
Time complexity: O(nlog(n))
Space complexity: O(1)
Union-Find Set might work.
(1)at first everybody himself/herself forms a set.
(2)scan every element's bits, if the kth bit of element[i] is 1, which means i work with k, then find k's set and i's set, and merge them if they are not in the same sets.
(3)as the average time complexity of find and merge is O(1), the total time complexity is O(N*N), while space complexity is O(N)
RepTristaRJohn, Reverse Engineering and System Developer at BT
I am an Ophthalmic medical assistant in bluefield USA, I assist in retinal exams and procedures. Referred patients to outside ...
Repkylieblindner, abc at ASAPInfosystemsPvtLtd
Hello, I am Kylie. I am working in a store as Supply chain managers promote the design, development, and implementation ...
RepI am Ricky from the USA. I am 29 year old. I am doing a job. I am doing a ...
Repsheilaahollins, Blockchain Developer at ASAPInfosystemsPvtLtd
Hello, I am working as a mineralogist studying rocks, gems, and other minerals, including their chemical and crystalline structures. I ...
Rephallieriddic, HR Executive Trainee at Barclays Capital
I am Hallie, Dedicated and experienced administrative secretary who excels at prioritizing , completing multiple tasks simultaneously and following through to ...
Repomarcdei, Android Engineer at Abs india pvt. ltd.
I'm Omar. I am working as a Mail carrier in Manning's Cafeterias company. I love to learn and ...
Repbarrybzane, AT&T Customer service email at ASU
By Profession, I am a Child protective services social worker in Newark USA. My strong interest is in yoga. My ...
Repfloydmsnyder, Theoretical mathematician at STM Auto Parts
As a Theoretical Mathematician,I’m little more interested in the theory involved with mathematics. In my free time , I ...
RepEwaMariaa, Cloud Support Associate at Abs india pvt. ltd.
Hi, I am an Localization translator from New York,Travelling with company executives on foreign trips is the favorite part ...
Repalicegpopa, Apple Phone Number available 24/7 for our Customers at AMD
I am working as a U.S. marshal in Pro Property Maintenance. I want to write about I Want My ...
Reprachelwrosa1, Computer Scientist at ABC TECH SUPPORT
Hello, I am Rachel and I live in Charleston, USA. I am working as a data entry clerk who is ...
Reppathfisher, Animator at Rack N Sack
I am Pat working in Rack N Sack where I use sequential images to produce the illusion of movement and ...
Repritahmixon, Analyst at ADP
Hi, I am a physiotherapy to help people handle everyday problems. I also assist peoples who have issues caused by ...
A tree's diameter must be like this: it has a node P as the center, with left radius being the longest path of P's left subtree and right radius being the longest path of P's right subtree.
So we divide the problem into two parts:
(1)traverse the whole tree and get the height of each subtree, meanwhile determine the diameter's center node P
(2)get the two radii of this diameter
Following is code in C++:
- uuuouou April 02, 2014