Topic

Factor

• 254 Factor Combinations(Q:A)(backtracking using res,subset)

Think about using multplication or division in case integer overflow.

• 368 Largest Divisible Subset(Q:A)(DP)

Pow

• 50 Pow(Q;A)

Ugly Number

• 263 Ugly Number(Q:A)
• 264 Ugly Number II(Q:A)

Basic Command Line

The Shell, Bash

Shell is a program that takes commands from the keyboard and gives them to the operating system to perform. If you would like to know which shell you are using you may use a command called echo to display a system variable stating your current shell.

hadley@hadley-MacBookPro:~$ echo $SHELL
/bin/bash

pwd

hadley@hadley-MacBookPro:~$ pwd
/home/hadley

Topic

DFS/Backtracking Intuitive approach to dynamic programming

• 322 Coin Change(Q:A)
• 518 Coin Change 2(Q:A)
• 343 Integer Break(Q:A)

String Definition

Map

Map Definition

//using stringstream class

//using std::stoi()
string str="45";
int num = std::stoi(str);

//int to string

String Definition

String Basic Operation

string STL()

Append()

std::string s="C+";
string ch="+";

//append string
s.append(ch);
//append char, append(number of characters to copy, character value)
char sh='+';
s.append(1,sh);

//append partial string, append(string, [optional]subpos, sublen)
string str="writing";
s.append(str,6,3);

append char to end of string

std::string s="C+";
char ch='+';

//push_back()
s.push_back(ch);
//+=operator
s+=ch;
//append()
s.append(1,ch);

string&char&int conversion

//using stringstream class

//using std::stoi()
string str="45";
int num = std::stoi(str);

//int to string


//char shift
char a = 'a';
char b = a+1;

• 249 Group Shifted Strings(Q:A)

1.Heap Definition

Heap using STL

#include <queue>
//Max heap using priority queue
std::priority_queue<int> pq(nums.begin(),nums.end());
//Min heap using priority queue
std::priority_queue<int, std::vector<int>, std::greater<int>> pq(nums.begin(),nums.end());

If you have an array of size n and you want to build a heap from all items at once, Floyd’s algorithm can do it with O(n) complexity.
If you have an empty priority queue to which you want to add n items, one at a time, then the complexity is O(n*log(n)).

Functions

//push
template <typename T>
pq.push(T t)
//top, return top of heap
pq.top()
//pop, remove top of heap
pq.pop()
//size, return size of heap
pq.size()

Bit Arithmetic

• Binary Addition

  string addBinary(string a, string b){
    int m=a.size(),n=b.size();
    int i=m-1,j=n-1;
    string res="";
    int temp=0;
    while(i>=0||j>=0||temp==1){
        temp+=((i>=0)?a[i]-'0':0);
        temp+=((j>=0)?b[j]-'0':0);
  
        res=char(temp%2+'0')+res;
        temp/=2;
        i--;j--;
    }
    return res;
  }
  

• 67 Add Binary(Q:A)

Binary, Decimal, Hexadecimal Conversion

Power of Two

1. Get the Rightmost 1-bit two’s complement: -x = ~x + 1;

bool isPowerOfTwo(int n){
	return (n&(-n))==n;
}

1. Turn off the rightmost 1-bit

   bool isPowerOfTwo(int n){
    return n&(n-1)==0;
   }
   

• 231 Power of Two(Q:A)

1.Array Definition

Array Initialization

//loops
int array[100];
for(int i=0;i<100;i++){
    array[i]=i;
}

//using braces
int array[5]={1,2,3,4,5};

int array1[]={1,2,3,4,5};

//partial initializaiton, the first element sets to 1, every other element sets to 0
int array[5]={1};

//initialzie all elements to the same values, std::fill_n(array_name, number of elements, value)
int array[100];
std::fill_n(array, 100, -1);