网站换新域名,html5网站开发教程,论述三种常见的网络营销方式,律师事务所网站制作文章目录 [Power Calculus](https://vjudge.net/problem/POJ-3134)题目描述分析 [706. 设计哈希映射](https://leetcode.cn/problems/design-hashmap/)方法一#xff1a;纯数组方法二#xff1a;数组加链表 今天再练一道迭代搜索的题 力扣每日一题 Power Calculus
题目描述… 文章目录 [Power Calculus](https://vjudge.net/problem/POJ-3134)题目描述分析 [706. 设计哈希映射](https://leetcode.cn/problems/design-hashmap/)方法一纯数组方法二数组加链表 今天再练一道迭代搜索的题 力扣每日一题 Power Calculus
题目描述 给你一个整数n可以乘或者除可以使用中间结果求最少运算多少次可以得到 x n x^n xn 分析 相当于求从整数1开始可以加或者减可以使用中间结果最少运算多少次可以得到n 实现细节见代码 #includeiostream
#includecmath
#includealgorithm
#includecstdio
using namespace std;const int N 1010;
int n;
int ans[N]; // 保存中间结果n最大为1000每次运算加1也就需要1000次所以最多运算1000次也就是说中间结果最多有1000个
int pos; // 标记当前运算的位置
int depth; // 最大深度// dep当前递归深度
bool dfs(int dep) {if (dep depth) return false;if (ans[pos] (depth - dep) n) {// depth - dep是还剩的递归次数// 估价函数用最快的倍增都不能到达n退出// 最快的倍增假设ans[pos] m, 下一层递归2m再下一层4m 8m 。。。 ,以2的幂倍增return false;}if (ans[pos] n) {return true;}pos;for (int i 0; i pos; i) {// 讨论上一个中间结果与前面所有的中间结果相加ans[pos] ans[pos - 1] ans[i];if (dfs(dep 1)) {// 继续下一层的递归return true;}// 讨论上一个中间结果与前面所有的中间结果相减ans[pos] ans[pos - 1] - ans[i];if (dfs(dep 1)) {return true;}}pos--; // 回溯return false;
}int main() {while (scanf(%d, n)) {if (n 0) break;depth 0;pos 0;ans[pos] 1;while (!dfs(0)) {depth;}printf(%d\n, depth);}return 0;
}706. 设计哈希映射
方法一纯数组
class MyHashMap {private static final int MAX_N 1000001;int[] map;public MyHashMap() {map new int[MAX_N];Arrays.fill(map, -1);}public void put(int key, int value) {map[key] value;}public int get(int key) {return map[key];}public void remove(int key) {map[key] -1;}
}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj new MyHashMap();* obj.put(key,value);* int param_2 obj.get(key);* obj.remove(key);*/方法二数组加链表
class MyHashMap {static class Node {int key, value;Node next;Node(int key, int value) {this.key key;this.value value;}}public Node[] table new Node[(int)Math.pow(2, 14)];public MyHashMap() {}public int getIndex(int key) {int hash Integer.hashCode(key);hash hash ^ (hash 16);return hash (table.length - 1);}public void put(int key, int value) {int index getIndex(key);if (table[index] null) {table[index] new Node(key, value);} else {Node cur table[index];Node pre null;while (cur ! null) {if (cur.key key) {cur.value value;return;}pre cur;cur cur.next;}Node node new Node(key, value);pre.next node;}}public int get(int key) {int index getIndex(key);if (table[index] ! null) {Node cur table[index];while (cur ! null) {if (cur.key key) {return cur.value;}cur cur.next;}}return -1;}public void remove(int key) {int index getIndex(key);if (table[index] ! null) {Node pre null;Node cur table[index];while (cur ! null) {if (cur.key key) {if (pre null) {table[index] cur.next;} else {pre.next cur.next;}return;}pre cur;cur cur.next;}}}
}
