Question:
Answer:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
void reverseStr(string &s, int i, int j){
char temp;
while(i<j){
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
void reverseWords(string &s) {
if(s.length() == 0) return;
reverseStr(s, 0, s.size()-1); //Reverse the whole string firstly.
int i = 0, count = 0;
while(s[i]==' '){
i++;
count++;
}
int begin = i-count;
while(i <= s.length()-1){
//cout <<"Debug: |" << s.substr(i) << endl;
if(s[i] == ' '){ //For s[i] == first ' ' after a word end, shift count num.
s[i-count] = s[i];
reverseStr(s, begin, i-count-1);
while(s[i+1] == ' '){
i++;
count++;
}
begin = i+1-count;
}
else if(i == s.length()-1){ //For last word end without ' 'next reversing!!!Important!
s[i-count] = s[i];
reverseStr(s, begin, i-count);
}
else{
s[i-count] = s[i]; //For s[i] is a valid word char, shift count num.
}
i++;
}
for(int i=0;i<count;++i){
s.pop_back();
}
if(s[s.length()-1] == ' ') s.pop_back();
}
int main(int argc, char** argv){
string str = " abc def eghi ";
cout << str << endl;
reverseWords(str);
cout << str;
getchar();
return 0;
}
Friday, December 5, 2014
Wednesday, November 26, 2014
BT level order traversal -- Java
Question:
Answer:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)return res;
List<Integer> subres = new ArrayList<Integer>();
int pushnum=0, popnum=1;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.add(root);
while(!que.isEmpty()){
TreeNode cur = que.peek();
que.poll();
popnum--;
subres.add(cur.val);
if(cur.left!=null){
que.add(cur.left);
pushnum++;
}
if(cur.right!=null){
que.add(cur.right);
pushnum++;
}
if(popnum==0){
int tmp=pushnum;
pushnum = popnum;
popnum = tmp;
res.add(subres);
}
}
return res;
}
}
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
Answer:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)return res;
List<Integer> subres = new ArrayList<Integer>();
int pushnum=0, popnum=1;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.add(root);
while(!que.isEmpty()){
TreeNode cur = que.peek();
que.poll();
popnum--;
subres.add(cur.val);
if(cur.left!=null){
que.add(cur.left);
pushnum++;
}
if(cur.right!=null){
que.add(cur.right);
pushnum++;
}
if(popnum==0){
int tmp=pushnum;
pushnum = popnum;
popnum = tmp;
res.add(subres);
}
}
return res;
}
}
2sum + 3sum + 4sum (hashmap solution) -- Java
1. 2 sum:
Question:
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Output: index1=1, index2=2
Answer:
public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
int[] res = {-1,-1};
for(int i=0; i<numbers.length; ++i) {
int o = target - numbers[i];
if(hmap.containsKey(o)) {
int oindex = hmap.get(o);
if(oindex != i) {
res[0] = i+1;
res[1] = oindex+1;
break;
}
}
if(!hmap.containsKey(numbers[i])) {
hmap.put(numbers[i], i);
}
}
if(res[0]>res[1]){
int tmp = res[0];
res[0]=res[1];
res[1]=tmp;
}
return res;
}
}
2. 3sum:
Answer:
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
int sz = num.length;
HashMap<Integer, List<Integer>> m = new HashMap<Integer, List<Integer>>();
List<List<Integer>> ret = new ArrayList<List<Integer>>();
List<Integer> tri = new ArrayList<Integer>();
for(int i=0; i<sz; ++i) {
int val = num[i];
if(m.containsKey(val)) {
List<Integer> l = m.get(val);
l.add(i);
}
else {
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(i);
m.put(val, l);
}
}
for(int i=0; i<sz; ++i) {
for(int j=i+1; j<sz; ++j) {
int o = 0 - num[i] - num[j];
if(m.containsKey(o)) {
List<Integer> l = m.get(o);
for(int idx : l) {
if(idx > j){
tri.add(num[i]);
tri.add(num[j]);
tri.add(num[idx]);
if (ret.isEmpty() || !tri.equals(ret.get(ret.size() - 1))) {
ret.add(tri);
}
}
}
}
}
}
return ret;
}
}
3. 4Sum:
Answer:
static List<List<Integer>> fourSum(int[] num, int target) {
HashMap<Integer, List<Integer>> hmap = new HashMap<Integer, List<Integer>>();
List<List<Integer>> ret = new ArrayList<List<Integer>>();
List<Integer> tup = new ArrayList<Integer>();
int sz = num.length;
for (int i = 0; i < sz; ++i) {
for (int j = i + 1; j < sz; ++j) {
//key: val, value: idx=i*sz+j;
int val = num[i] + num[j];
int idx = i * sz + j; // pair(i,j) <-> idx= i*sz +j;
if (hmap.containsKey(val)) {
hmap.get(val).add(idx);
} else {
List<Integer> l = new ArrayList<Integer>();
l.add(idx);
hmap.put(val, l);
}
}
}
for (int i = 0; i < sz; ++i) {
for (int j = i + 1; j < sz; ++j) {
int val = num[i] + num[j];
int o = target - val;
if (hmap.containsKey(o)) {
List<Integer> l = hmap.get(o);
for (int pos : l) {
if (j < pos / sz) { //!important, to avoid duplicate!
tup.add(num[i]);
tup.add(num[j]);
tup.add(num[pos / sz]);
tup.add(num[pos % sz]);
if (ret.isEmpty() || !tup.equals(ret.get(ret.size() - 1))) {
ret.add(tup);
}
}
}
}
}
return ret;
}
}
Selection Sort
void selection_sort(int *a, int len) { register int i, j, min, t; for(i = 0; i < len - 1; i ++) { min = i;//最小值下标 //查找最小值 for(j = i + 1; j < len; j ++) if(a[min] > a[j]) min = j; //交换 if(min != i) { t = a[min]; a[min] = a[i]; a[i] = t; } } }
Evaluate Reverse Polish Notation -- Leetcode
Question:
Answer:
对于逆波兰式,一般都是用栈来处理,依次处理字符串,
如果是数值,则push到栈里面
如果是操作符,则从栈中pop出来两个元素,计算出值以后,再push到栈里面,
则最后栈里面剩下的元素即为所求。
class Solution {
public:
int evalRPN (vector<string> &tokens) {
stack<int> operand;
for(int i =0; i< tokens.size(); i++)
{
if ((tokens[i][0] == '-' && tokens[i].size()>1) //negative number
|| (tokens[i][0] >= '0' && tokens[i][0] <= '9')) //positive number
{
operand.push(atoi(tokens[i].c_str()));
continue;
}
int op1 = operand.top();
operand.pop();
int op2 = operand.top();
operand.pop();
if(tokens[i] == "+") operand.push(op2+op1);
if(tokens[i] == "-") operand.push(op2-op1);
if(tokens[i] == "*") operand.push(op2*op1);
if(tokens[i] == "/") operand.push(op2/op1);
}
return operand.top();
}
};
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are
+
, -
, *
, /
. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Answer:
对于逆波兰式,一般都是用栈来处理,依次处理字符串,
如果是数值,则push到栈里面
如果是操作符,则从栈中pop出来两个元素,计算出值以后,再push到栈里面,
则最后栈里面剩下的元素即为所求。
class Solution {
public:
int evalRPN (vector<string> &tokens) {
stack<int> operand;
for(int i =0; i< tokens.size(); i++)
{
if ((tokens[i][0] == '-' && tokens[i].size()>1) //negative number
|| (tokens[i][0] >= '0' && tokens[i][0] <= '9')) //positive number
{
operand.push(atoi(tokens[i].c_str()));
continue;
}
int op1 = operand.top();
operand.pop();
int op2 = operand.top();
operand.pop();
if(tokens[i] == "+") operand.push(op2+op1);
if(tokens[i] == "-") operand.push(op2-op1);
if(tokens[i] == "*") operand.push(op2*op1);
if(tokens[i] == "/") operand.push(op2/op1);
}
return operand.top();
}
};
Sqrt(x) -- Leetcode
Implement
int sqrt(int x)
.
Compute and return the square root of x.
1. 二分法:Binary Search.
public int mySqrt(int x) {
if(x < 0)return -1;
if(x == 0)return 0;
int start = 1;
int end = x / 2 + 1;
while(start <= end){
int mid = start + (end - start) / 2;
if(mid <= x/mid && (mid+1) > x/(mid+1)){
return mid;
}else if(mid > x/mid){
end = mid - 1;
}else{
//mid <= x/mid && (mid+1) <= x/(mid+1)
start = mid + 1;
}
}
return end;
}
if(x < 0)return -1;
if(x == 0)return 0;
int start = 1;
int end = x / 2 + 1;
while(start <= end){
int mid = start + (end - start) / 2;
if(mid <= x/mid && (mid+1) > x/(mid+1)){
return mid;
}else if(mid > x/mid){
end = mid - 1;
}else{
//mid <= x/mid && (mid+1) <= x/(mid+1)
start = mid + 1;
}
}
return end;
}
2. 牛顿迭代法
为了方便理解,就先以本题为例:
计算x2 = n的解,令f(x)=x2-n,相当于求解f(x)=0的解,如左图所示。
首先取x0,如果x0不是解,做一个经过(x0,f(x0))这个点的切线,与x轴的交点为x1。
同样的道理,如果x1不是解,做一个经过(x1,f(x1))这个点的切线,与x轴的交点为x2。
以此类推。
以这样的方式得到的xi会无限趋近于f(x)=0的解。
判断xi是否是f(x)=0的解有两种方法:
一是直接计算f(xi)的值判断是否为0,二是判断前后两个解xi和xi-1是否无限接近。
经过(xi, f(xi))这个点的切线方程为f(x) = f(xi) + f’(xi)(x - xi),其中f'(x)为f(x)的导数,本题中为2x。令切线方程等于0,即可求出xi+1=xi - f(xi) / f'(xi)。
继续化简,xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2。
- int sqrt(int x) {
- // Start typing your C/C++ solution below
- // DO NOT write int main() function
- if (x ==0)
- return 0;
- double pre;
- double cur = 1;
- do
- {
- pre = cur;
- cur = x / (2 * pre) + pre / 2.0;
- } while (abs(cur - pre) > 0.00001);
- return int(cur);
- }
Reverse Words in a String -- Leetcode
Question:
Given an input string, reverse the string word by word.
For example,
Given s = "
return "
Given s = "
the sky is blue
",return "
blue is sky the
".
Clarification:
- What constitutes a word?
A sequence of non-space characters constitutes a word. - Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces. - How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
Answer:
class Solution {
public:
void reverseWords(string &s) {
string ss;
string res;
for(int i=0; s[i]!='\0';++i){
if(s[i]!=' '){
ss.append(s[i],1);
}
//For invalid ' ', if there exists duplicate ' '.
else if(s[i] == ' ' && s[i+1] == ' '){
continue;
}
//For effective ' ', if there exists duplicate ' '. For case: "aa bb cc ".
else if(s[i] == ' ' && s[i+1] != ' ' && s[i+1] != '\0'){
res.insert(0," ");
res.insert(1,ss);
ss.clear();
}
//For last word.
else if(s[i] == ' ' && s[i+1] == '\0'){
res.insert(0,ss);
ss.clear();
}
}
s = res;
}
};
Tuesday, November 25, 2014
vector implementation using array -- Java
public class ImpArrayList {
private int[] m_data = null;
private int m_cur_size = -1;
private int m_total_size = -1;
private static final int s_min_size = 8;
public ImpArrayList(int sz) {
if(sz < 0) {
sz = 0;
}
m_total_size = sz*2;
if(m_total_size < s_min_size) {
m_total_size = s_min_size;
}
m_data = new int [m_total_size];
m_cur_size = sz;
}
public ImpArrayList() {
this(0);
}
public int get(int i) {
return m_data[i];
}
public void set(int i, int v) {
m_data[i] = v;
}
public void push_back(int v) {
if(m_cur_size >= m_total_size) {
m_total_size = m_total_size * 2;
int [] tmp = new int [m_total_size];
System.arraycopy(m_data, 0, tmp, 0, m_cur_size);
m_data = tmp;
}
m_data[m_cur_size] = v;
m_cur_size++;
}
public void pop_back() {
m_cur_size--;
if(m_cur_size < 0) {
//should throw an exception
m_cur_size = 0;
}
}
public boolean empty() {
return m_cur_size == 0;
}
//some other functions like resize ...
public static void main(int argc, String[] argv){
}
}
Sudoku Solver
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;
}
private:
bool isValid(const vector<vector<char> > &board, int x, int y) {
int i, j;
for (i = 0; i < 9; i++) // 检查 y 列
if (i != x && board[i][y] == board[x][y])
return false;
for (j = 0; j < 9; j++) // 检查 x 行
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;
}
};
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;
}
private:
bool isValid(const vector<vector<char> > &board, int x, int y) {
int i, j;
for (i = 0; i < 9; i++) // 检查 y 列
if (i != x && board[i][y] == board[x][y])
return false;
for (j = 0; j < 9; j++) // 检查 x 行
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;
}
};
LRU Cache -- Java
public class LRUCache {
class Node{
int key;
int value;
Node prev;
Node next;
public Node(int k, int v){
key = k;
value = v;
prev = null;
next = null;
}
public void setValue(int v){
value = v;
}
}
int cap;
HashMap<Integer,Node> hmap;
Node head;
Node tail;
public LRUCache(int capacity) {
if(capacity<0){
capacity = 1;
}
cap = capacity;
hmap = new HashMap<Integer, Node>();
head = null;
tail = null;
}
public int get(int key) {
if(hmap.containsKey(key)){
if(hmap.size()>1){
dragKeyNode(hmap.get(key)); //lru
}
return hmap.get(key).value;
}
else return -1;
}
public void set(int key, int value) {
if(hmap.containsKey(key)){
dragKeyNode(hmap.get(key)); //lru
hmap.get(key).setValue(value);
}
else{
//to insert a new Node to the doubly linkedin list.
Node insertNode = new Node(key,value);
if(hmap.size() < cap){ //!important judge.
attachKeyNode(insertNode);
}
else{ // cur size >=cap
detachKeyNode();
attachKeyNode(insertNode);
}
hmap.put(key,insertNode);
}
return;
}
//drag an existed node from original inner pos in doubly linkedlist to the head new pos.
public void dragKeyNode(Node p){
if(p==head)return; //if p==head, nothing needed to do.
Node pprev = p.prev;
Node pnext = p.next;
pprev.next = pnext;
if(pnext!=null){
pnext.prev = pprev;
}
else{ //if p is currently tail node, modify tail!
tail = pprev;
}
p.prev = null;
p.next = null;
attachKeyNode(p);
return;
}
public void attachKeyNode(Node p){
if(head == null && tail == null){
head = p;
tail = p;
}
else{
p.next = head;
head.prev = p;
head = p;
}
return;
}
public void detachKeyNode(){ //cut off tail node.
if(hmap.size() < 1)return;
int key = tail.key;
hmap.remove(key); //!important, also need to delete tail node in hashmap.
if(hmap.size()==0){
head = null;
tail = null;
}
else{
Node pprev = tail.prev;
pprev.next = null;
tail.prev = null;
tail = pprev;
}
return;
}
}
Monday, November 17, 2014
Encoding and decoding string
Question:
Answer:
Method 1: '+' to split strings, '\' to transfered symbol.
import java.util.ArrayList;
public class Dumper {
public static void main(String [] args) {
String [] str_array = new String [] {
"a+b", // a+b
"c\\b", // c\b
};
System.out.println("Orig: ");
for(String s : str_array) {
System.out.println(s);
}
String str_serialized = Serialize(str_array);
System.out.println("Serialized: " + str_serialized);
String [] str_deserialized = Deserialize(str_serialized);
System.out.println("Deserialized: ");
for(String s : str_deserialized) {
System.out.println(s);
}
}
static String Serialize(String [] str_arr) {
StringBuilder buf = new StringBuilder();
for(String s : str_arr) {
for(int i=0; i<s.length(); ++i) {
char c = s.charAt(i);
if(c == '+' || c == '\\') {
buf.append('\\');
}
buf.append(c);
}
buf.append('+');
}
return buf.toString();
}
static String [] Deserialize(String str) {
ArrayList<String> str_arr = new ArrayList<String>();
StringBuilder buf = new StringBuilder();
for(int i=0; i<str.length(); ++i) {
char c = str.charAt(i);
if(c == '\\') {
c = str.charAt(i+1);
i++;
buf.append(c);
}
else if(c == '+') {
str_arr.add(buf.toString());
buf = new StringBuilder();
}
else {
buf.append(c);
}
}
return str_arr.toArray(new String [0]);
}
}
Answer:
Method 1: '+' to split strings, '\' to transfered symbol.
import java.util.ArrayList;
public class Dumper {
public static void main(String [] args) {
String [] str_array = new String [] {
"a+b", // a+b
"c\\b", // c\b
};
System.out.println("Orig: ");
for(String s : str_array) {
System.out.println(s);
}
String str_serialized = Serialize(str_array);
System.out.println("Serialized: " + str_serialized);
String [] str_deserialized = Deserialize(str_serialized);
System.out.println("Deserialized: ");
for(String s : str_deserialized) {
System.out.println(s);
}
}
static String Serialize(String [] str_arr) {
StringBuilder buf = new StringBuilder();
for(String s : str_arr) {
for(int i=0; i<s.length(); ++i) {
char c = s.charAt(i);
if(c == '+' || c == '\\') {
buf.append('\\');
}
buf.append(c);
}
buf.append('+');
}
return buf.toString();
}
static String [] Deserialize(String str) {
ArrayList<String> str_arr = new ArrayList<String>();
StringBuilder buf = new StringBuilder();
for(int i=0; i<str.length(); ++i) {
char c = str.charAt(i);
if(c == '\\') {
c = str.charAt(i+1);
i++;
buf.append(c);
}
else if(c == '+') {
str_arr.add(buf.toString());
buf = new StringBuilder();
}
else {
buf.append(c);
}
}
return str_arr.toArray(new String [0]);
}
}
Print Matrix Diagonally
Given a 2D matrix, print all elements of the given matrix in diagonal order. For example, consider the following 5 X 4 input matrix.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (5x4)
Diagonal printing of the above matrix is
1 5 2 9 6 3 13 10 7 4 17 14 11 8 18 15 12 19 16 20
Following is C++ code for diagonal printing.
The diagonal printing of a given matrix ‘matrix[ROW][COL]‘ always has ‘ROW + COL – 1′ lines in output
#include <stdio.h> #include <stdlib.h> #define ROW 5 #define COL 4 int min( int a, int b) { return (a < b)? a: b; } int min( int a, int b, int c) { return min(min(a, b), c);} int max( int a, int b) { return (a > b)? a: b; }
void diagonalOrder( int matrix[][COL]) { for ( int line=1; line<=(ROW + COL -1); line++) { /* Get column index of the first element in this line of output.
The index is 0 for first ROW lines and line - ROW for remaining
lines */ int start_col = max(0, line-ROW); /* Get count of elements in this line. The count of elements is equal to minimum of line number, COL-start_col and ROW */ int count = min(line, (COL-start_col), ROW); for ( int j=0; j<count; j++) printf ( "%5d " , matrix[min(ROW, line)-j-1][start_col+j]); /* Ptint elements of next diagonal on next line */ printf ( "\n" ); } } void printMatrix( int matrix[ROW][COL]) { for ( int i=0; i< ROW; i++) { for ( int j=0; j<COL; j++) printf ( "%5d " , matrix[i][j]); printf ( "\n" ); } } int main() { int M[ROW][COL] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}, {17, 18, 19, 20}, }; printf ( "Given matrix is \n" ); printMatrix(M); printf ( "\nDiagonal printing of matrix is \n" ); diagonalOrder(M); return 0; } |
Subscribe to:
Posts (Atom)