-
Two Sum
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
-
Reverse Integer
class Solution {
public int reverse(int x) {
int output = 0;
while (true) {
if (x == 0) {
return x;
}
output = output * 10 + x % 10;
if ((x /= 10) == 0) {
return output;
}
if (output > 214748364 || output < -214748364) {
return 0;
}
}
}
}
-
Palindrome Number
class Solution {
public boolean isPalindrome(int x) {
// if(x==Integer.MIN_VALUE) return false;
if(x<0) return false; //isPalindrome(-x);
if(x<10) return true;
int tens = 1;
int tmp = x;
while(tmp/10 > 0){
tens *= 10;
tmp = tmp/10;
}
while(tens >= 10){
if(x/tens != x % 10) return false;
x = x % tens / 10;
tens /= 100;
}
return true;
}
}
-
Remove Element
class Solution {
public int removeElement(int[] nums, int val) {
int length = nums.length;
int j = 0;
for(int i = 0; i < length; i++){
if(nums[i] != val){
nums[j++] = nums[i];
}
}
return j;
}
}
-
Merge Two Sorted Lists
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val >= l2.val){
ListNode listNode = new ListNode(l2.val);
listNode.next = mergeTwoLists(l1, l2.next);
return listNode;
}
else{
ListNode listNode = new ListNode(l1.val);
listNode.next = mergeTwoLists(l1.next, l2);
return listNode;
}
}
}
//要用递归做
-
Maximum Subarray
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int sum=nums[0];
int max=nums[0];
for(int i=1;i<nums.length;i++){
if(sum<0) sum=nums[i];
else sum+=nums[i];
max=Math.max(max,sum);
}
return max;
}
}
-
Min Cost Climbing Stairs
class Solution {
public int minCostClimbingStairs(int[] cost) {
int f1 = 0, f2 = 0;
for (int i = 0; i < cost.length; i++) {
int f0 = cost[i] + Math.min(f1, f2);
f2 = f1;
f1 = f0;
}
return Math.min(f1, f2);
}
}
-
Merge Two Binary Trees
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
-
Longest Substring Without Repeating Characters
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
-
Longest Palindromic Substring
public String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
-
Subarray Sum Equals K
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum=0;
for (int end = start; end < nums.length; end++) {
sum+=nums[end];
if (sum == k)
count++;
}
}
return count;
}
}
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
-
Best Time to Buy and Sell Stock II
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
-
Jump Game
//我的解法
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
if(len == 1)
return true;
int maxJump = 0;
for(int i = 0; i < len - 1; i++){
if(maxJump < i){
break;
}
if(nums[i] + i > maxJump)
maxJump = nums[i] + i;
}
if(maxJump >= len - 1)
return true;
else
return false;
}
}
public class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
}
-
Remove K Digits
//我的解法
class Solution {
public String removeKdigits(String num, int k) {
int len = num.length() - k;
char[] result = new char[len];
int index = -1;
int l = k;
int i = 0;
while(len > 0){
index = index + findMin(num.substring(index + 1, l + 1)) + 1;
result[i++] = num.charAt(index);
len--;
l++;
}
for(i = 0; i < result.length; i++){
if(Character.getNumericValue(result[i]) != 0)
break;
}
String s = String.valueOf(result).substring(i);
if(s.equals(""))
return String.valueOf(0);
else
return s;
}
int findMin(String num){
if(num.length() == 1)
return 0;
int min = num.charAt(0);
int index = 0;
int tmp = 0;
for(int i = 0; i < num.length(); i++){
tmp = Character.getNumericValue(num.charAt(i));
if(tmp < min){
min = tmp;
index = i;
}
}
return index;
}
}
public class Solution {
/**
* 这是一个非常简单的问题，贪心解决法
* 即 removeKdigits(num,k) = removeKdigits(removeKdigits(num,1),k-1)
* 进行最多K轮的删除，每次从头开始寻找一位删除：
* 1、要么第二位是0，这样相当于至少删了两位，很值得，必须这么做
* 2、不然，找到第一个出现下降转折的位置 删除
* */
public String removeKdigits(String num, int k) {
int n;
while(true){
n = num.length();
if(n <= k || n == 0) return "0";
if(k-- == 0) return num;
if(num.charAt(1) == '0'){
int firstNotZero = 1;
while(firstNotZero < num.length() && num.charAt(firstNotZero) == '0') firstNotZero ++;
num=num.substring(firstNotZero);
} else{
int startIndex = 0;
while(startIndex < num.length() - 1 && num.charAt(startIndex) <= num.charAt(startIndex + 1)) startIndex ++;
num=num.substring(0,startIndex)+num.substring(startIndex+1);
}
}
}
}
-
Min Stack
//我的解答 效率不高
//其实根本没必要维护一个min的数组，是我弱智了
class MinStack {
/** initialize your data structure here. */
public MinStack() {
root = new linkedList();
min = new ArrayList();
index = -1;
}
public void push(int x) {
index++;
if(index == 0)
min.add(x);
else
min.add(Math.min(min.get(index - 1), x));
linkedList tmp = new linkedList();
tmp.value = x;
tmp.next = root.next;
root.next = tmp;
}
public void pop() {
if(index == -1)
return;
linkedList tmp = root.next.next;
root.next = tmp;
min.remove(index--);
}
public int top(){
return root.next.value;
}
public int getMin() {
return min.get(index);
}
linkedList root;
List<Integer> min;
int index;
class linkedList{
linkedList next;
int value;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
class MinStack {
class Node{
int value;
int min;
Node next;
Node(int x, int min){
this.value=x;
this.min=min;
next = null;
}
}
Node head;
public void push(int x) {
if(null==head){
head = new Node(x,x);
}else{
Node n = new Node(x, Math.min(x,head.min));
n.next=head;
head=n;
}
}
public void pop() {
if(head!=null)
head =head.next;
}
public int top() {
if(head!=null)
return head.value;
return -1;
}
public int getMin() {
if(null!=head)
return head.min;
return -1;
}
}
-
Unique Binary Search Trees
class Solution {
public int numTrees(int n) {
if(n == 1)
return 1;
else if(n == 2)
return 2;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i<=n; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i-1-j];
}
}
return dp[n];
}
}
-
Majority Element II
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
int candidate1 = 0, candidate2 = 0;
int count1 = 0, count2 = 0;
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1++;
} else if (count2 == 0) {
candidate2 = num;
count2++;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
}
int majority = nums.length / 3;
if (count1 > majority) result.add(candidate1);
if (count2 > majority) result.add(candidate2);
return result;
}
}
