2.Add Two Numbers 原题链接https://leetcode.com/problems/add-two-numbers/
AC解：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int sum = 0;
ListNode head = new ListNode(0);
ListNode dummy = new ListNode(0);
ListNode flag = dummy;
dummy.next = head;
while(l1 != null || l2 != null || sum >0) {
if(l1 != null) {
sum+= l1.val;
l1 = l1.next;
}
if(l2 != null) {
sum+= l2.val;
l2 = l2.next;
}
head.val = sum%10;
ListNode newNode = new ListNode(0);
head.next = newNode;
head = newNode;
flag = flag.next;
sum = sum/10;
}
if(flag.next.val==0) flag.next=null;
return dummy.next;
}
这个方法总会使链表尾出现一个多余的节点，优化后
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int sum = 0;
ListNode dummy = new ListNode(0);
ListNode flag = dummy;
while(l1 != null || l2 != null || sum >0) {
if(l1 != null) {
sum+= l1.val;
l1 = l1.next;
}
if(l2 != null) {
sum+= l2.val;
l2 = l2.next;
}
ListNode newNode = new ListNode(sum%10);
flag.next = newNode;
flag = flag.next;
sum = sum/10;
}
return dummy.next;
}
67. Add Binary
AC解：
public String addBinary(String a, String b) {
int len1 = a.length()-1;
int len2 = b.length()-1;
int sum = 0;
StringBuilder sb = new StringBuilder();
while(len1>=0||len2>=0||sum>0){
if(len1>=0){
int dA = a.charAt(len1)-'0';
sum += dA;
len1--;
}
if(len2>=0){
int dB = b.charAt(len2)-'0';
sum += dB;
len2--;
}
sb.append(sum%2);
sum = sum/2;
}
return sb.reverse().toString();
}
7.Reverse Integer https://leetcode.com/problems/reverse-integer/
注意溢出
public int reverse(int x) {
int result = 0;
if(x ==0) return 0;
boolean flag = false;
if(x <0) {
x =Math.abs(x);
flag = true;
}
while(x >0){
//溢出处理
if(result!=0 && Integer.MAX_VALUE/result <10)
return 0;
result *=10;
result +=x%10;
x /=10;
}
if(flag)
result =-result;
return result;
}
8.Reverse bits
思路与反转十进制数类似
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result += n & 1;
n >>>= 1; // CATCH: must do unsigned shift
if (i < 31) // CATCH: for last digit, don't shift!
result <<= 1;
}
return result;
}
338. Counting Bits
原题链接https://leetcode.com/problems/counting-bits/
自己的思路：Integer.bitCount()方法，但是原题并不推荐使用内嵌方法
bug free:遇到偶数时，其1的个数和该偶数除以2得到的数字的1的个数相同，遇到奇数时，其1的个数等于该奇数除以2得到的数字的1的个数再加1
public int[] countBits(int num) {
int[] result = new int[num+1];
for (int i=1;i<num+1;i++)
result[i]=result[i>>1]+(i&1);
return result;
}
413.Arithmetic Slices
题意：求一个数组中可以构成多少个等差数列
思路：参见http://blog.****.net/camellhf/article/details/52824234
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
int incre = 0;
for (int i = 2; i<A.length;i++) {
if(A[i] - A[i-1] == A[i-1]-A[i-2])
count += ++incre;
else
incre=0;
}
return count;
}
406. Queue Reconstruction by Height
题意，[h,k]分别表示该人的高度和他前面比他高的人数，将队列重排。
思路：先将输入数组排序，再插入排序；
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0)
return new int[0][0];
//按照高度降序排列，高度相同时按照人数升序排列
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (b[0] == a[0]) return a[1] - b[1];
return b[0] - a[0];
}
});
//插入排序思想，待插入的人总是低于（或等于）排好序的子队列的人，按照k的大小，将其插入到正确的位置
int n = people.length;
ArrayList<int[]> tmp = new ArrayList<>();
for (int i = 0; i < n; i++)
tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
int[][] res = new int[people.length][2];
int i = 0;
for (int[] k : tmp) {
res[i][0] = k[0];
res[i++][1] = k[1];
}
return res;
}
451.Sort Characters By Frequency 原题https://leetcode.com/problems/sort-characters-by-frequency/
思路：TopK---将字母及其个数存入hashmap中，利用优先队列PriorityQueue <Map.Entry<Character, Integer>>将这些键值对排序
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<> ();
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
PriorityQueue <Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
new Comparator<Map.Entry<Character,Integer>>(){
@Override
public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
// TODO Auto-generated method stub
return o2.getValue() - o1.getValue();
}
}
);
pq.addAll(map.entrySet());
StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()) {
Map.Entry<Character, Integer> m = pq.poll();
for(int i=0;i<m.getValue();i++){
sb.append(m.getKey());
}
}
return sb.toString();
347. Top K Frequent Element 原题链接 https://leetcode.com/problems/top-k-frequent-elements/
bug free:
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> list = new ArrayList<Integer>();
Map<Integer, Integer> map = new HashMap<>();
//map存储nums中元素和其个数
for (int c : nums) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
//优先队列按照自定义比较器对键值对进行排序
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
new Comparator<Map.Entry<Integer, Integer>>(){
@Override
public int compare(Map.Entry<Integer, Integer> o1,
Map.Entry<Integer, Integer> o2) {
return o2.getValue() - o1.getValue();
}
}
);
pq.addAll(map.entrySet());
//根据参数k,出队K个元素
for (int i = 0; i < k; i++){
list.add(pq.poll().getKey());
}
return list;
167. Two Sum II - Input array is sorted 原题链接 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
public static int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
int i = 0,j = nums.length-1;
int mid = target/2;
while(i < j && nums[i]<=mid && nums[j]>=mid) {
if(nums[i]+nums[j]==target) {
result[0] = i+1;
result[1] = j+1;
break;
}
else if (nums[i] + nums[j] <target)
i++;
else if (nums[i] + nums[j] >target)
j--;
}
return result;
}
这个结果超过28%的solution 后来发现先j--再i++ 超过42%的solution~ 神奇
442. Find All Duplicates in an Array 原题链接：https://leetcode.com/problems/find-all-duplicates-in-an-array/
对于一个元素nums[i]，数组中nums[i]-1位置的元素反转为负数，遍历过程中如果遍历到负数，说明数字i+1出现了两次
public List<Integer> findDuplicates(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i<nums.length; i++) {
int index = Math.abs(nums[i])-1;
if(nums[index]<0)
list.add(Math.abs(index+1));
nums[index] = -nums[index];
}
return list;
}
86. Partition List 原题链接：https://leetcode.com/problems/partition-list/
思路：将链表根据val分为小于x和大于x两个子链表，再拼接
思路很简单，但是自己写的代码一直TLE，看了top solution里的答案才发现需要将big子链表末指针设为null
public ListNode partition(ListNode head, int x) {
if(head == null) return head;
ListNode small = new ListNode(0);
ListNode big = new ListNode(0);
ListNode smallHead = small;
ListNode bigHead = big;
//ListNode point = head;
while(head != null) {
if(head.val < x) {
small.next = head;
small = head;
head = head.next;
}
else {
big.next = head;
big = head;
head = head.next;
}
}
big.next = null;//一定注意，之前没加这个语句一直TLE
bigHead = bigHead.next;
small.next = bigHead;
return smallHead.next;
}
Implement queue using stacks
public class MyQueue {
private Stack<Integer> stack1 = new Stack<>();//辅助队尾入队，所有入队元素直接压入stack1
private Stack<Integer> stack2 = new Stack<>();//辅助队头出队
public void push(int x) {
stack1.add(x);
}
public int pop(){
//如果stack2不为空，直接出栈
if(!stack2.empty()) return stack2.pop();
//如果stack2为空，将stack1中每个元素出栈后压入stack2,实现FIFO结构
while(!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
public int peek(){
if(!stack2.empty()) return stack2.peek();
while(!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
public boolean empty(){
return (stack1.empty() && stack2.empty());
}
}
Implement stack using queues
public class MyStack {
private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
//push an element onto one stack
public void push(int x) {
if(!q1.isEmpty())
q1.add(x);
else
q2.add(x);
}
//pop from the top of the stack
public int pop() {
int result = 0;
if(q1.isEmpty()) {
while(q2.size() > 1) {
q1.add(q2.poll());
}
result = q2.poll();
}
else{
while(q1.size() > 1) {
q2.add(q1.poll());
}
result = q1.poll();
}
return result;
}
//get top element from stack
public int top() {
int result = 0;
if(q1.isEmpty()) {
while(q2.size() > 1) {
q1.add(q2.poll());
}
result = q2.poll();
q1.add(result);
}
else{
while(q1.size() > 1) {
q2.add(q1.poll());
}
result = q1.poll();
q2.add(result);
}
return result;
}
//find out whether the stack is empty
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
使用一个队列实现栈
public class MyStack {
private Queue<Integer> q = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
q.add(x);
for(int i = 1; i < q.size(); i ++) { //rotate the queue to make the tail be the head
q.add(q.poll());
}
}
// Removes the element on top of the stack.
public int pop() {
return q.poll();
}
// Get the top element.
public int top() {
return q.peek();
}
// Return whether the stack is empty.
public boolean empty() {
return q.isEmpty();
}
}
235. Lowest Common Ancestor of a Binary Search Tree
题意：求BST中两个节点的LCA，根据BST的特点递归求解
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p.TreeNode q) {
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p ,q);
else return root;
}
236.Lowest Common Ancestor of a Binary Tree
题意：求一个普通二叉树中两个节点的LCA
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left != null ? left : right;
}
112.Path Sum
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
Stack<Integer> s = new Stack<Integer>();
int curSum = 0;
return pathSum(root,sum,s,curSum);
}
private boolean pathSum(TreeNode root, int sum, Stack<Integer> s, int curSum) {
// TODO 自动生成的方法存根
curSum += root.val;
s.push(root.val);
boolean isLeaf = (root.left == null && root.right == null);
if(curSum == sum && isLeaf) {
return true;
}
boolean left = false, right = false;
if(root.left != null) left = pathSum(root.left,sum,s,curSum);
if(root.right != null) right = pathSum(root.right,sum,s,curSum);
s.pop();
return left || right;
}
}
113.Path Sum 2
找出二叉树中满足给定sum的路径和（从根节点到叶子），将结果放在list中
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list = new LinkedList<List<Integer>>();
if(root == null) return list;
Stack<Integer> s = new Stack<Integer>();
int curSum = 0;
pathSum(root,list,sum,s,curSum);
return list;
}
private void pathSum(TreeNode root, List<List<Integer>> list,
int sum, Stack<Integer> s, int curSum) {
// TODO 自动生成的方法存根
curSum += root.val;
s.push(root.val);
boolean isLeaf = (root.left == null && root.right == null);
if(curSum == sum && isLeaf) {
List<Integer> subList = new LinkedList<> ();
for(Integer x : s ){
subList.add(x);
}
list.add(subList);
}
if(root.left != null) pathSum(root.left,list,sum,s,curSum);
if(root.right != null) pathSum(root.right,list,sum,s,curSum);
s.pop();//要返回到上一个节点
}
}
437 path sum 3
public class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null)
return 0;
return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
public int findPath(TreeNode root, int sum){
int res = 0;
if(root == null)
return res;
if(sum == root.val)
res++;
res += findPath(root.left, sum - root.val);
res += findPath(root.right, sum - root.val);
return res;
}
}
300. Longest Increasing Subsequence
数组中最长上升子序列的长度
https://leetcode.com/problems/longest-increasing-subsequence/discuss/
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len == 0) return 0;
int[] dp = new int[len];
for(int i = 0 ; i < len; i++){
dp[i] = 1;
}
int max = 0;
for(int i = 0; i < len; i++) {
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
max = Math.max(dp[i],max);
}
return max;
}
}
102. Binary Tree Level Order Traversal
二叉树层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null) return res;
queue.add(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> sub = new ArrayList<>();
for(int i = 0 ; i < levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null ) queue.offer(queue.peek().right);
sub.add(queue.poll().val);
}
res.add(sub);
}
return res;
}
647.Palindromic Substrings
public int countSubstrings(String s) {
int n = s.length();
int res = 0;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
//关键点：如果头尾相等，并且去掉头尾后也是回文 就是回文
特殊情况：j-i<3表示去掉头尾为空字符串
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if(dp[i][j]) ++res;
}
}
return res;
}
lintcode 92.背包问题
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
int[][] dp = new int[A.length+1][m + 1];
for(int i = 0; i <= A.length; i++){
for(int j = 0; j <= m; j++){
if(i==0||j==0){
dp[i][j]=0;
}
else if(A[i-1] > j ){
dp[i][j] = dp[i-1][j];
}
else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]]+A[i-1]);
}
}
}
return dp[A.length][m];
}
}
lintcode 125.背包问题2
public class Solution {
/*
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
// write your code here
int[][] dp = new int[A.length+1][m+1];
for(int i = 0; i <= A.length; i ++) {
for(int j = 0; j <= m; j++) {
if(i == 0 || j == 0){
dp[i][j] = 0;
}
else if(A[i-1] > j) {
dp[i][j] = dp[i-1][j];
}
else {
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-A[i-1]]+V[i-1]);
}
}
}
return dp[A.length][m];
}
}
lintcode 97.最长公共子序列
public class Solution {
/*
* @param A: A string
* @param B: A string
* @return: The length of longest common subsequence of A and B
*/
public int longestCommonSubsequence(String A, String B) {
// write your code here
int m = A.length();
int n = B.length();
int[][] dp = new int[m+1][n+1];
int max = 0;
for(int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] =Math.max(dp[i-1][j],dp[i][j-1]);
if(A.charAt(i-1) == B.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1]+1;
}
}
}
return dp[m][n];
}
}
lintcode 79.最长公共子串
public class Solution {
/*
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// write your code here
int m = A.length();
int n = B.length();
int[][] dp = new int[m+1][n+1];
//f[i][j]
int max = 0;
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++) {
if(A.charAt(i-1) == B.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = 0;
max = Math.max(dp[i][j], max);
}
}
return max;
}
}
lintcode 110.最小路径和
public class Solution {
/*
* @param grid: a list of lists of integers
* @return: An integer, minimizes the sum of all numbers along its path
*/
public int minPathSum(int[][] grid) {
// write your code here
for(int i = 0; i < grid.length;i++){
for(int j = 0; j < grid[0].length; j++){
if(i == 0 && j == 0){}
else if (i == 0 && j > 0) {
grid[i][j] += grid[i][j-1];
}
else if(i > 0 && j == 0){
grid[i][j] += grid[i-1][j];
}
else {
grid[i][j] += Math.min(grid[i][j-1],grid[i-1][j]);
}
}
}
return grid[grid.length-1][grid[0].length-1];
}
}