void move(int b, int e, int **arr);
int get(int b, int e, int k, int **arr, int *val);
void print(int *arr, int len, char del) {
int i = 0;
for (i; i < len; i++) {
printf(" %d", arr[i]);
}
printf("%c", del);
}
void printt(int **arr, int len, int col) {
int i = 0;
for (i; i < len; i++) {
print(arr[i], col, ' ');
}
printf("\n");
}
/**
* lru design
* @param operators int整型二维数组 the ops
* @param operatorsRowLen int operators数组行数
* @param operatorsColLen int* operators数组列数
* @param k int整型 the k
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
//printt(operators, operatorsRowLen, 3);
//printf("|||||||| %d, %d\n", k, operatorsRowLen);
// write code here
int retLen = 0;
int i = 0;
int *curRow;
int curKey, isFull = 0, isGet = 0;;
int curIdx = 0;
int getVal;
int *retArr = (int *) malloc(operatorsRowLen * sizeof(int));
int **curArr = (int **) malloc(k * sizeof(int *));
int cnt = 0;
//retArr[0] = 1; free(curArr); *returnSize = 1; return retArr;
for (i = 0; i < operatorsRowLen; i++) {
curRow = operators[i];
if (curRow[0] == 1) {// set
curArr[curIdx] = curRow;
curIdx++;
//printt(curArr, curIdx, 3);
curIdx = curIdx == k ? 0 : curIdx;
cnt++;
} else {// get
curKey = curRow[1];
isFull = cnt >= k ? 1 : 0;
if (isFull) {
isGet = get(curIdx, k, curKey, curArr, &getVal);
//printf("======%d, %d\n", curIdx, k);
if (isGet) {
if (curIdx != 0) {
curRow = curArr[k - 1];
curArr[k - 1] = curArr[0];
curArr[0] = curRow;
move(0, curIdx, curArr);
}
} else {
get(0, curIdx, curKey, curArr, &getVal);
}
//printt(curArr, 3, 3);
} else {
get(0, curIdx, curKey, curArr, &getVal);
}
retArr[retLen++] = getVal;
//print(retArr, retLen, '\n');
}
}
*returnSize = retLen;
//free(retArr);
free(curArr);
return retArr;
}
int get(int b, int e, int k, int **arr, int *val) {
int i;
int *fr;
int *cr;
for (i = b; i < e; i++) {
fr = arr[i];
if (fr[1] == k) {
*val = fr[2];
move(i, e, arr);
//printt(arr, 3, 3);
return 1;
}
}
//printt(arr, 3, 3);
*val = -1;
return 0;
}
void move(int b, int e, int **arr) {
int i;
int *f = arr[b];
for (i = b; i < e - 1; i++) {
arr[i] = arr[i + 1];
}
arr[i] = f;
//printf("ooooo %d\n", i);
//printt(arr, 3, 3);
}