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; }

DP -- Minimal coins problem

public class CoinsChange {  
    /**  
     * 硬币找零：动态规划算法  
     *   
     * @param values  
     *            :保存每一种硬币的币值的数组  
     * @param valueKinds  
     *            :币值不同的硬币种类数量，即coinValue[]数组的大小  
     * @param money  
     *            :需要找零的面值  
     * @param coinsUsed  
     *            :保存面值为i的纸币找零所需的最小硬币数  
     */ 
    public static void makeChange(int[] values, int valueKinds, int money,  
            int[] coinsUsed) {  
 
        coinsUsed[0] = 0;  
        // 对每一分钱都找零，即保存子问题的解以备用，即填表  
        for (int cents = 1; cents <= money; cents++) {  
 
            // 当用最小币值的硬币找零时，所需硬币数量最多  
            int minCoins = cents;  
 
            // 遍历每一种面值的硬币，看是否可作为找零的其中之一  
            for (int kind = 0; kind < valueKinds; kind++) {               
                // 若当前面值的硬币小于当前的cents则分解问题并查表  
                if (values[kind] <= cents) {  
                    int temp = coinsUsed[cents - values[kind]] + 1;  
                    if (temp < minCoins) {  
                        minCoins = temp;  
                    }  
                }  
            }  
            // 保存最小硬币数  
            coinsUsed[cents] = minCoins;  
 
            System.out.println("面值为 " + (cents) + " 的最小硬币数 : " 
                    + coinsUsed[cents]);  
        }  
    }  
      
    public static void main(String[] args) {  
 
        // 硬币面值预先已经按降序排列  
        int[] coinValue = new int[] { 25, 21, 10, 5, 1 };  
        // 需要找零的面值  
        int money = 63;  
        // 保存每一个面值找零所需的最小硬币数，0号单元舍弃不用，所以要多加1  
        int[] coinsUsed = new int[money + 1];  
 
        makeChange(coinValue, coinValue.length, money, coinsUsed);  
    }  
} 

测试结果：

面值为 1 的最小硬币数 : 1
面值为 2 的最小硬币数 : 2
面值为 3 的最小硬币数 : 3
面值为 4 的最小硬币数 : 4
面值为 5 的最小硬币数 : 1
面值为 6 的最小硬币数 : 2
...
...
面值为 60 的最小硬币数 : 3
面值为 61 的最小硬币数 : 4
面值为 62 的最小硬币数 : 4
面值为 63 的最小硬币数 : 3

Max Amplitude -- Amazon

#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>
#include<unordered_set>
#include<time.h>
#include<stdio.h>

using namespace std;

struct BTNode {
     int val;
     BTNode *left;
     BTNode *right;
     BTNode(int x) : val(x), left(NULL), right(NULL) {}
};

int computeAmp(vector<int> &path){
int min= INT_MAX, max=INT_MIN;
for(int i=0;i<path.size();++i){
if(min> path[i]){
min = path[i];
}
if(max < path[i]){
max = path[i];
}
}
return abs(max-min);
}

int returnMax(vector<int> &res){
int max=INT_MIN;
for(int i=0;i< res.size();++i){
if(max < res[i]){
max = res[i];
}
}
return max;
}

void maxAmpHelp(BTNode *root, vector<int> &path, vector<int> &res){
if(!root->left && !root->right){
path.push_back(root->val);
int v = computeAmp(path);
res.push_back(v);
}
else{
path.push_back(root->val);
if(root->left){
   maxAmpHelp(root->left,path,res);
path.pop_back();
}
if(root->right){
   maxAmpHelp(root->right,path,res);
path.pop_back();
}
}
return;
}

int maxAmplitude (BTNode *root){
vector<int> res, path;
maxAmpHelp(root, path, res);
int maxAmp = returnMax(res);
return maxAmp;
}


int main(){
 BTNode *root = new BTNode (1);
 root->left = new BTNode (2);
 root->right = new BTNode (6);
 root->left->left = new BTNode (10);
 root->left->right = new BTNode (-22);
 root->right->left = new BTNode (-36);
 root->right->right = new BTNode (8);
 root->left->left->left = new BTNode(5);
 root->left->right->right = new BTNode(56);

 int max = maxAmplitude(root);      //output == 78
 cout<<endl<<"Max Amplitude is:"<< max <<endl;
 getchar();
 return 0;
}