地址：https://leetcode.com/problems/two-sum/description/
问题：Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
public int[] twoSum(int[] nums, int target) {
int size = nums.length;
int[] res = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<size;i++){
map.put(nums[i],i);
}
for(int i=0;i<size-1;i++){
int find = target - nums[i];
Integer ind = map.get(find);
if (ind != null && ind > i){
res[0]=i;
res[1]=ind;
return res;
}
}
return res;
}
Add Two Numbers
问题：You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
public int romanToInt(String s) {
int total = 0;
for(int i=0;i<s.length()-1;i++){
int now = getNumber(s.charAt(i));
if (now>=getNumber(s.charAt(i+1))){
total = total +now;
}else{
total = total -now;
}
}
total += getNumber(s.charAt(s.length()-1));
return total;
}
public static int getNumber(char a){
int number = 0;
switch (a){
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
break;
}
return number;
}
3Sum
https://leetcode.com/problems/3sum/description/
问题：Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
public List<List<Integer>> threeSum(int[] nums) {
//a+b=-c
Arrays.sort(nums);
//-4,-1,-1,0,1,2
List allList = new ArrayList();
int aa = Integer.MAX_VALUE;
for(int i=0;i<nums.length-1;i++){
if ( nums[i] ==aa ) continue;
int bb = Integer.MAX_VALUE;
int cc = nums.length;
for (int j=i+1;j<nums.length;j++){
if ( nums[j] ==bb || cc<=j) continue;
int c = -(nums[i]+nums[j]);
int a = Arrays.binarySearch(nums,j+1,cc,c);
if (a>j) {
List e = new ArrayList();
e.add(nums[i]);
e.add(nums[j]);
e.add(c);
allList.add(e);
cc = a;
}
bb = nums[j];
}
aa = nums[i];
}
return allList;
}
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
问题：
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
方案：
水题，栈解决
public boolean isValid(String s) {
int size = s.length();
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<size;i++){
if ('(' == s.charAt(i) || '{' == s.charAt(i) ||'[' == s.charAt(i)){
stack.push(s.charAt(i));
}else{
if (stack.isEmpty()) return false;
char c = stack.pop().charValue();
switch (s.charAt(i)){
case ')':
if ('(' != c){
return false;
}
break;
case '}':
if ('{' != c){
return false;
}
break;
case ']':
if ('[' != c){
return false;
}
break;
default:
return false;
}
}
}
if (stack.isEmpty()) return true;
return false;
}
问题：Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
方案1:
先得到链表长度，把每k个使用头插法建立新链表，然后把剩余的连接起来
public ListNode reverseKGroup(ListNode head, int k) {
int length = getLength(head);
ListNode result = new ListNode(-1);
ListNode resultTmp = result;
for(;length>=k;length-=k){
ListNode pHead = null;
for(int i=0;i<k;i++){
ListNode tmp = head;
head =head.next;
tmp.next = pHead;
pHead = tmp;
}
resultTmp.next = pHead;
while (resultTmp.next !=null){ resultTmp = resultTmp.next;}
}
resultTmp.next = head;
return result.next;
}
public static int getLength(ListNode head){
ListNode tmp = head;
int i=0;
while (tmp != null) {
tmp = tmp.next;
i++;
}
return i;
}
Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.
水题，不讲
public int removeDuplicates(int[] nums) {
int t = 1;
for(int i=1;i<nums.length;i++){
if (nums[i] != nums[i-1]) {
nums[t] = nums[i];
t++;
}
}
return t;
}
The count-and-say sequence is the sequence of integers with the first five terms as following:
1
11
21
1211
111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
方案1:
递归，结果居然效率还挺高，不能理解
public String countAndSay(int n) {
if (n == 1) return "1";
String tmp = countAndSay(n-1);
char[] tt = new char[tmp.length()*2];
char a = tmp.charAt(0);
int k=0;
int t = 1;
for(int i=1;i<tmp.length();i++){
if (a != tmp.charAt(i)){
tt[k++] = (char) (t+'0');
tt[k++] = a;
t = 1;
a = tmp.charAt(i);
}else{
t++;
}
}
tt[k++] = (char) (t+'0');
tt[k++] = a;
return String.copyValueOf(tt,0,k);
}
想刷的清单： 1,2,10,13,15,17,20,23,25,26,28,33,38,43,44,49,50,56,57,67,68,69,71,75,76 78,79,80,85,88,90,91,98,102,117,121,125,127,128,133,139,146,157,158,161 168,173,200,206,208,209,210,211,215,218,221,234,235,236,238,252,253,257 261,265,269,273,274,275,277,278,282,283,285,286,297,301,311,314,325,334 341,377,380,398,404,410,461,477,494,523,525,534,535,543,554
方案: 两遍循环，O(n^2)
方案2: 分析，本题重点1.数组可能是乱序的2.不会有相同的值 抓住值都不同，可以反过来想，可以用值做唯一去查找下标 把数组放入hashmap里面，<值，下标>，查找的时候只要循环第一个数，里层因为hashmap的查找效率是O(1)，所以这个复杂度就只有O(n)
方案： 这个主要还是考察链表这个数据结构，直接上代码吧。比较简单，时间复杂度O(n),要注意的是最后可能会进位
'.' Matches any single character. '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be: bool isMatch(const char s, const char p)
Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a") → true isMatch("aa", ".") → true isMatch("ab", ".") → true isMatch("aab", "ca*b") → true
题目分析，'.' 可以记成匹配任意字符，'*'则要和他前导的字符一起看，可以匹配0个或者更多前导
方案1: 递归来做，考虑s和p两个数组 1 p长度为0 只有s长度也是0的时候返回true否则是false 2 p长度为1 只有s长度也是1而且p和s一样或者p是'.'的时候 3 p长度大于2
p的第二个字符不是'' 如果s长度是0返回false，如果s第一个字符和p第一个字符相等或者p第一个字符是'.'的时候，递归判断s和p第二个字符后否则false p第二个字符是'' 如果第一个字符相同，递归判断s和p从第二个字符开始
可以看出复杂度挺高的
方案2: DP 两个数组s，p分别代表字符串s和p dp[][]二维数组 dp[i][j] 代表s[0-i]和p[0-j]是否匹配最后只要看dp[s.length-1][p.length-1]是不是true就行了
分析：输入一个罗马数字，输出转化为整数，我们先来学习下罗马数字
·个位数举例 Ⅰ－1、Ⅱ－2、Ⅲ－3、Ⅳ－4、Ⅴ－5、Ⅵ－6、Ⅶ－7、Ⅷ－8、Ⅸ－9 ·十位数举例 Ⅹ－10、Ⅺ－11、Ⅻ－12、XIII－13、XIV－14、XV－15、XVI－16、XVII－17、XVIII－18、XIX－19、XX－20、XXI－21、XXII－22、XXIX－29、XXX－30、XXXIV－34、XXXV－35、XXXIX－39、XL－40、L－50、LI－51、LV－55、LX－60、LXV－65、LXXX－80、XC－90、XCIII－93、XCV－95、XCVIII－98、XCIX－99 ·百位数举例 C－100、CC－200、CCC－300、CD－400、D－500、DC－600、DCC－700、DCCC－800、CM－900、CMXCIX－999 ·千位数举例 M－1000、MC－1100、MCD－1400、MD－1500、MDC－1600、MDCLXVI－1666、MDCCCLXXXVIII－1888、MDCCCXCIX－1899、MCM－1900、MCMLXXVI－1976、MCMLXXXIV－1984、MCMXC－1990、MM－2000、MMMCMXCIX－3999
方案： 其实只是罗马转数字的话很简单，只要当前的比后面的大就用加法，比后面的小用减法
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
分析： 这题乍看之下好像很简单，循环前两个元素a,b，第三个元素用-(a+b)使用二分查找找出后面是否存在，存在则可以记录下来。然而有个坑，如果出现[0,0,0,0,0,0] 结果应该是[[0,0,0]]但是使用这个算法会出现很多[0,0,0]，但是如果算出来后去重，复杂度也非常高。如果数组从小到大排序，相同的都在一起了，现在只要跳过上一次拿过的，比如上次a拿过0就不拿了，b拿过0也不拿了，既然a和b都和上次不同，那么c也会和上次不同。
方案1: 复杂度其实也是蛮高，如果数据全部不相同，高达 O(n^2 x logN)
方案2: O(n^2)
https://discuss.leetcode.com/topic/8125/concise-o-n-2-java-solution/20
A mapping of digit to letters (just like on the telephone buttons) is given below.
方案： 水题，栈解决
方案1（超时错误-时间复杂度过高）： 每个链表取头去比较，拿最小的
方案2: 每次取链表的头，被取了就放入下一个。放入大跟堆里面
25. Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/description/
方案1: 先得到链表长度，把每k个使用头插法建立新链表，然后把剩余的连接起来
26. Remove Duplicates from Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
问题：
水题，不讲
28. Implement strStr()
https://leetcode.com/problems/implement-strstr/description/
33. Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
方案1: 遍历，找到直接返回下标，复杂度O(n)
方案2: 改造二分查找，只有中间和目标同时大于或者小于第一个元素，还用二分法，否则就下标挪动一位
38. Count and Say
https://leetcode.com/problems/count-and-say/description/
方案1: 递归，结果居然效率还挺高，不能理解