给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
思路：
使用hash表,KV对为值-下标，遍历到nums[i]时边放入hash表并检查是否存在
target-nums[i]
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
Integer idx = map.get(target - nums[i]);
//存在且不相同
if(idx != null && idx != i)
return new int[]{i,idx};
map.put(nums[i],i);
}
return null;
}
}
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路：
参考CodeInterView一书
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int n1,n2;
int s,ca;
ca = 0;
s = 0;
ListNode node = null;
ListNode pre = new ListNode(-1);
ListNode head = pre;
while(l1 != null || l2 !=null){
n1 = n2 = 0;
if(l1 != null){
n1 = l1.val;
l1 = l1.next;
}
if(l2 != null){
n2 = l2.val;
l2 = l2.next;
}
s = n1 + n2 + ca;
//进位和 和
if((ca = s/10)==1 && (s=s-10) > 0);
node = new ListNode(s);
pre.next = node;
pre = node;
}
//处理最后有进位的情况
if(ca == 1){
node = new ListNode(1);
node.next = null;
pre.next = node;
}
return head.next;
}
}
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i,ai) 。在坐标内画 n 条垂直线，垂直线i的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与x 轴共同构成的容器可以容纳最多的水。
图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
说明：你不能倾斜容器，且 n 的值至少为 2。
class Solution {
public int maxArea(int[] height) {
int i=0;
int j = height.length-1;
int ans = 0;
for(;i<j;){
int minHeight = height[i] < height[j] ? height[i++] : height[j--];
ans = Math.max(ans,minHeight * (j - i + 1));
}
return ans;
}
}
给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]]
思路：
每次选定一个数nums[i]后往后使用双指针查找-nums[i]，转化的二元组的问题
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
int l,r;
for(int i = 0;i<nums.length -2;i++){
if(i == 0 || nums[i -1] != nums[i]){
l = i + 1;
r = nums.length -1;
while(l < r){
if(nums[l] + nums[r] < -nums[i]){
l++;
}else if(nums[l] + nums[r] > -nums[i]){
r--;
}else{
ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
while (l < r && nums[l] == nums[l + 1]) ++l;
while (l < r && nums[r] == nums[r - 1]) --r;
++l;
--r;
//下面这种写法会超时??优化程度有多少
// if(l==i+1 || nums[l-1] != nums[l]){
// ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
// l++;
// r--;
// }
}
}
}
}
return ans;
}
}
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
class Solution {
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<String>();
if (digits == null || digits.equals("")) {
return ans;
}
String[] map = { "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
//用来保存数字代表的字符串
String[] str = new String[digits.length()];
for (int i = 0; i < digits.length(); i++) {
str[i] = map[digits.charAt(i) - 48 - 1];
}
collect(ans, str, "", 0);
return ans;
}
private void collect(List<String> ans, String[] str, String tmpAns, int i) {
if (tmpAns.length() == str.length) {
ans.add(tmpAns);
return;
}
for (char c : str[i].toCharArray()) {
tmpAns += c;
collect(ans, str, tmpAns, i + 1);
//back
tmpAns = tmpAns.substring(0, tmpAns.length() - 1);
}
}
}