public int romanToInt(String s) { //数字：Ⅰ（1）Ⅴ（5）Ⅹ（10）L（50）C（100）D（500）M（1000） HashMap<Character, Integer> map = new HashMap<>(); map.put('I',1); map.put('V',5); map.put('X',10); map.put('L',50); map.put('C',100); map.put('D',500); map.put('M',1000); int cur = map.get(s.charAt(s.length() - 1)); int result = cur; for (int i = s.length() - 2; i >= 0; --i) { int pre = map.get(s.charAt(i)); if (cur > pre) { result -= pre; } else { result += pre; } cur = pre; } return result; }
int romanToInt(string s) { int map[26]; memset(map, 0, sizeof map); map['I' - 'A'] = 1; map['V' - 'A'] = 5; map['X' - 'A'] = 10; map['L' - 'A'] = 50; map['C' - 'A'] = 100; map['D' - 'A'] = 500; map['M' - 'A'] = 1000; int len = s.size(), ret = 0, pre, cur = map[s[len - 1] - 'A']; for (int i = 1; i < len; ++i) { pre = map[s[i - 1] - 'A']; cur = map[s[i] - 'A']; if (cur > pre) { ret += cur - pre; if (i == len - 1) { cur = 0; } else { cur = map[s[i + 1] - 'A']; } ++i; } else { ret += pre; } } return ret + cur; }
public int firstMissingPositive(int[] A) { // write your code here if (A == null || A.length == 0) return 1; BitSet bt = new BitSet(); int max = 0; for (int i = 0; i < A.length; ++i) { if (A[i] > max) max = A[i]; if (A[i] >= 0) bt.set(A[i]); } for (int i = 1; i <= max; ++i) { if (!bt.get(i)) return i; } return max + 1; }
用BitSet空间复杂度过大，看来别人的高级解法：
int firstMissingPositive(vector<int> A) {
int n = A.size();
for (int i = 0; i < n; ++i) {
while (A[i] != i + 1 && A[i] >= 1 && A[i] <= n) {
if (A[A[i] - 1] == A[i]) {
break;
}
int tmp = A[i];
A[i] = A[tmp - 1];
A[tmp - 1] = tmp;
}
}
for (int i = 0; i < n; ++i) {
if (A[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
public int[] twoSum(int[] nums, int target) { int[] ret = new int[2]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { map.put(nums[i], i); } for (int i = 0; i < nums.length; ++i) { if (map.containsKey(target - nums[i])) { int v = map.get(target - nums[i]); if (v == i) continue; if (v > i) { ret[0] = i + 1; ret[1] = v + 1; } else { ret[0] = v + 1; ret[1] = i + 1; } return ret; } } return ret; }
这是别人的C语言解法：
typedef struct HashNode { int key; int val; } HashNode; typedef struct HashMap { int size; HashNode** storage; } HashMap; HashMap* hash_create(int size); void hash_destroy(HashMap* hashMap); void hash_set(HashMap* hashMap, int key, int value); HashNode* hash_get(HashMap* hashMap, int key); HashMap* hash_create(int size){ HashMap* hashMap = malloc(sizeof(HashMap)); hashMap->size = size; hashMap->storage = calloc(size, sizeof(HashNode*)); return hashMap; } void hash_destroy(HashMap* hashMap) { for(int i; i < hashMap->size; i++) { HashNode *node; if((node = hashMap->storage[i])) { free(node); } } free(hashMap->storage); free(hashMap); } void hash_set(HashMap *hashMap, int key, int value) { int hash = abs(key) % hashMap->size; HashNode* node; while ((node = hashMap->storage[hash])) { if (hash < hashMap->size - 1) { hash++; } else { hash = 0; } } node = malloc(sizeof(HashNode)); node->key = key; node->val = value; hashMap->storage[hash] = node; } HashNode* hash_get(HashMap *hashMap, int key) { int hash = abs(key) % hashMap->size; HashNode* node; while ((node = hashMap->storage[hash])) { if (node->key == key) { return node; } if (hash < hashMap->size - 1) { hash++; } else { hash = 0; } } return NULL; } int* twoSum(int* nums, int numsSize, int target) { HashMap* hashMap; HashNode* node; int rest, i; // make the hashMap 2x size of the numsSize hashMap = hash_create(numsSize * 2); for(i = 0; i < numsSize; i++) { rest = target - nums[i]; node = hash_get(hashMap, rest); if (node) { int* result = malloc(sizeof(int)*2); result[0] = node->val + 1; result[1] = i + 1; hash_destroy(hashMap); return result; } else { hash_set(hashMap, nums[i], i); } } }
C++解法：
vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> mp; for (int i = 0; i < nums.size(); ++i) { auto iter = mp.find(nums[i]); if (iter != mp.end()) { return vector<int>{ iter->second + 1, i + 1 }; } else { mp[target - nums[i]] = i; } } }
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode ret = new ListNode(0); ListNode h0 = ret, h1 = l1, h2 = l2, last = ret;; int c = 0; while (h1 != null && h2 != null) { if (h0 == null) { h0 = new ListNode(0); last.next = h0; last = h0; } h0.val = h1.val + h2.val + c; if (h0.val >= 10) { h0.val -= 10; c = 1; } else { c = 0; } h0 = h0.next; h1 = h1.next; h2 = h2.next; } while (h1 != null) { if (h0 == null) { h0 = new ListNode(0); last.next = h0; last = h0; } h0.val = h1.val + c; if (h0.val >= 10) { h0.val -= 10; c = 1; } else { c = 0; } h0 = h0.next; h1 = h1.next; } while (h2 != null) { if (h0 == null) { h0 = new ListNode(0); last.next = h0; last = h0; } h0.val = h2.val + c; if (h0.val >= 10) { h0.val -= 10; c = 1; } else { c = 0; } h0 = h0.next; h2 = h2.next; } if (c > 0) { h0 = new ListNode(c); last.next = h0; } return ret; }