1.两数之和
// 暴力也可以，在这里采用的是一遍哈希表。
//判断当前的数是否成立，就在hashmap中查找之前的加进来的，如果没有就把该数加进来
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap();
for(int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{i,map.get(target - nums[i])};
} else {
map.put(nums[i], i);
}
}
return new int[]{};
}
}2. 两数相加
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
int t = 0;
while (l1 != null || l2 != null || t != 0) {
if (l1 != null) {
t += l1.val;
l1 = l1.next;
}
if (l2 != null) {
t += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(t % 10);
cur = cur.next;
t = t / 10;
}
return head.next;
}
} - 凡是需要特判第一个节点是不是头节点的时候我们就可以声明一个虚拟的头节点
- java 中只能用true 和false 来表是真假 不能用null 或者 0
3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap();
int res = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
int count = map.containsKey(s.charAt(i))? map.get(s.charAt(i)) : 0;
map.put(s.charAt(i), count + 1);
while(map.get(s.charAt(i)) > 1) {
// map.remove(s.charAt(j++)); // 这里不能remove 因为有可能会将重复的那个值整体移除，正是因为不能删除，所以也不能通过size 的方式来求长度
map.put(s.charAt(j),map.get(s.charAt(j)) - 1);
j++;
}
res = Math.max(res, i - j + 1);
}
return res;
}
}4. 寻找两个正序数组的中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
if (total % 2 == 0) {
int left = find(nums1, 0, nums2, 0, total / 2);
int right = find(nums1, 0, nums2, 0, total / 2 + 1);
return (left + right) / 2.0;
}else {
return find(nums1, 0, nums2, 0, total / 2 + 1) ;
}
}
// i 代表第一个数组的开始寻找的索引值，j 代表第二个数组开始寻找的索引值， 两个数组[索引值之后]加起来从小到大第k个，
private int find(int[] nums1, int i, int[] nums2, int j, int k) {
if (nums1.length - i > nums2.length - j) {
return find(nums2, j, nums1, i , k);
}
if(k == 1) {
if(nums1.length == i)
return nums2[j];
else
return Math.min(nums1[i], nums2[j]);
}
if(nums1.length == i) {
return nums2[j + k - 1];
}
int si = Math.min(nums1.length, i + k / 2);
int sj = j + k - k / 2;
if (nums1[si - 1] > nums2[sj - 1]) {
return find(nums1, i, nums2, sj, k - (sj - j));
}else
return find(nums1, si, nums2, j , k - (si - i));
}
}5. 最长回文子串
class Solution {
public String longestPalindrome(String s) {
//回文字符串两种情况 奇数和偶数
if(s == null) {
return null;
}
String res = "";
//循环中心点
for (int i = 0; i < s.length(); i++) {
//以该节点开始，考虑奇数的情况 往两边进行延申
int left = i - 1;
int right = i + 1;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if(res.length() < (right - left - 1)) {
res = s.substring(left + 1, right);
}
// 以该节点开始，考虑偶数情况 往两边进行延申
left = i;
right = i + 1;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if(res.length() < (right - left - 1)) {
res = s.substring(left + 1, right);
}
}
return res;
}
}
- Z 字形变换
class Solution {
//在纸上用索引来将字符串的位置表示出来就能找到规律了
// 之间的差值 2*n -2
public String convert(String s, int numRows) {
if(numRows == 1) {
return s;
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < numRows; i++) {
if (i == 0 || i == numRows - 1) {
for (int j = i; j < s.length(); j += 2 * numRows - 2) {
builder.append(s.charAt(j));
}
continue;
}
for (int j = i,k = 2*numRows - 2 - j; j < s.length() || k < s.length(); j += 2 * numRows - 2, k += 2 * numRows - 2) {
if (j < s.length()) {
builder.append(s.charAt(j));
}
if (k < s.length()) {
builder.append(s.charAt(k));
}
}
}
return builder.toString();
}
}7. 整数反转
class Solution {
// 不断的取余 然后相加相乘
public int reverse(int x) {
long res = 0L;
while(x != 0) {
res = res * 10 + x % 10;
x = x / 10;
}
if (res >= Integer.MAX_VALUE) {
return 0;
}
if (res <= Integer.MIN_VALUE) {
return 0;
}
return (int) res;
}
}8. 字符串转换整数 (atoi)
class Solution {
public int myAtoi(String str) {
int k = 0;
while(k < str.length() && str.charAt(k) == ' ') k++;
if (k == str.length()) {
return 0;
}
int minus = 1;
if (str.charAt(k) == '-') {
minus = -1;
k++;
}else if(str.charAt(k) == '+') {
k++;
}
long res = 0;
while(k < str.length() && str.charAt(k) >= '0' && str.charAt(k) <= '9') {
res = str.charAt(k) - '0' + res * 10;
k++;
if (res >= Integer.MAX_VALUE) {
break;
}
}
res = res * minus;
if (res >= Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (res <= Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int)res;
}
}9. 回文数
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int y = x;
long res = 0;
while(y > 0) {
res = res * 10 + y % 10;
y = y / 10;
}
return res == x;
}
}10. 正则表达式匹配
肝不下去了
京公网安备 11010502036488号