高盛昂赛 算法题先写corner case

class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//TreeNode node = new TreeNode(0);
//corner case
if (nums.length == 0) {
return null;
}
TreeNode node = helper(nums, 0, nums.length - 1);// -1 should be noticed ahead
return node;
}
必须要有三个参数，不同的函数才能被称作helper
public TreeNode helper(int[] nums, int low, int high) {
//corner case : low > high
if (low > high) {
return null;
}
int mid = low + (high - low) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, low, mid - 1);
root.right = helper(nums, mid + 1, high);
要用到函数里给的参数
return root;
}
}

//ini
List<List<Integer>> triangle = new ArrayList<List<Integer>>(); //cc
if (numRows <= 0) return triangle; //for
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<Integer>(); for (int j = 0; j < i + 1; j++) {
//首先写corner case
if (j == 0 || j == i) {
row.add(1);
}else {
row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
}
}
//add again

用add方法
triangle.add(new ArrayList(row));
} //return
return triangle;
}
}

public class Solution {
/**
* @param digits: a number represented as an array of digits
* @return: the result
*/
public int[] plusOne(int[] digits) {
//not carry
int n = digits.length;
//0 to n-1 whenever
for (int i = n - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;直接在这里return即可
}else {
digits[i] = 0;
}
}
//carry, need new array
int[] answer = new int[n + 1];
answer[0] = 1;
return answer;
}
}

public class Solution {
/*
* @param node: the node in the list should be deletedt
* @return: nothing
*/
public void deleteNode(ListNode node) {
// write your code here
if (node == null || node.next == null) {
return ;
}
注意删除的是next而不是当前的node
ListNode next = node.next;
node.val = next.val;
node.next = next.next;
}
}

public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
//ini res
int res = 0; //for loop: 32 32位数，做移动32次
for (int i = 0; i < 32; i++) {
res <<= 1; 左移留出最后一位为0来相加
if ((n & 1) == 1) res += 1;
n >>= 1; 右移留出最后一位来操作
} return res;
}
}

class Solution {
public boolean isSymmetric(TreeNode root) {
//corner case
if (root == null) {
return true;
}
return isSymmetricHelper(root.left, root.right);
} public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
//all null
if (left == null && right == null) {
return true;
}
//one null
if (left == null || right == null) {
return false;
}
//not same
if (left.val != right.val) {
return false;
}
//same
return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
//don't forget the function name
}
}

public class Solution {
/**
* @param head: A ListNode.
* @return: A boolean.
*/
public boolean isPalindrome(ListNode head) {
// corner case
if (head == null) {
return true;//true
}
//p1 go with p2
ListNode middle = findMiddle(head);
middle.next = reverse(middle.next);// ListNode p1 = head, p2 = middle.next;
while (p2 != null && p1.val == p2.val) {//order
p1 = p1.next;
p2 = p2.next;
}
return p2 == null;
} private ListNode findMiddle(ListNode head) {
// corner case
if (head == null) {
return null;
}无处不在的corner case
ListNode fast = head.next, slow = head; 先走一步
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
} private ListNode reverse(ListNode head) {
// corner case
if (head == null) {
return null;
}
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}

class Solution {
public int singleNumber(int[] nums) {
//ini n
int n = 0; //for loop ^=
for (int i = 0; i < nums.length; i++) {
n ^= nums[i]; 不同2次会返回原来的值
} //return
if (n != 0) return n; return 0;
}
}

class Solution {
public int majorityElement(int[] nums) {
//ini
int major = nums[0];
int count = 1;
//1 - n
for (int i = 1; i < nums.length; i++) {
//nums[i] != major, count--,if count == 0
if (nums[i] != major) {
if (count == 0) {
major = nums[i];
count++;
}
count--;抵消当前的
}else {
//nums[i] == major, count++
count++;
}
}
return major;
}
}

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

public class Solution {
/*
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//corner case
if (headA == null || headB == null) {
return null;
}
//keep the same length
int A_len = getLength(headA);
int B_len = getLength(headB); while (A_len > B_len) {
headA = headA.next;
A_len--;
}
while (A_len < B_len) {
headB = headB.next;
B_len--;
}
//find the same node
while (headA != headB) {
headA = headA.next;
headB = headB.next;
} return headA;
} //getLength
public int getLength(ListNode node) {
int length = 0;
while(node != null) {
length++;
node = node.next;
}
return length;
}
}

class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int size = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != nums[size]) { 总是去和size代表的最后一位相比较
nums[++size] = nums[i];
}
}
return size + 1;剩一个0位
}
}

public class Solution {
/**
* @param s: a string
* @return: it's index
*/
public int firstUniqChar(String s) {
//corner case
if (s == null) {
return 0;
}
//put into cnt[]
char[] c = s.toCharArray();字母是一个单独的数组
int[] cnt = new int[256];表示所有字符
for (int i = 0; i < s.length(); i++) {
cnt[c[i]]++;
}
//return
for (int i = 0; i < s.length(); i++) {
if (cnt[c[i]] == 1) {
return i;
//break;
}
}
return -1;
}
}

Input: ["flower","flow","flight"]
Output: "fl"

public class Solution {
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
public String longestCommonPrefix(String[] strs) {
//corner case
if (strs == null) {
return "";
}
if (strs.length == 0) {
return "";
}
//define pre
String pre = strs[0];
int n = strs.length;
//shorten pre
for (int i = 1; i < n; i++) {
while (strs[i].indexOf(pre) != 0) {
pre = pre.substring(0, pre.length() - 1);
}
}
//return
return pre;
}
}

class Solution {
public void moveZeroes(int[] nums) {
//cc
if (nums == null || nums.length == 0) return;
//ini
int insertPos = 0; for (int num : nums) {
//no 0s
if (num != 0) {
nums[insertPos++] = num;
}
}
//0s 分开就行
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
//return
}
}

public class Solution {
/*
* @param A: sorted integer array A which has m elements, but size of A is m+n
* @param m: An integer
* @param B: sorted integer array B which has n elements
* @param n: An integer
* @return: nothing
*/
public void merge(int[] A, int m, int[] B, int n) {
// write your code here
int index = m + n - 1;
int i = m - 1;
int j = n - 1;
//add the bigger number from backward
while (i >= 0 && j >= 0) {最重要的是这一步
if (A[i] > B [j]) {
A[index--] = A[i--];
}
else {
A[index--] = B[j--];
}
}
//if there's number remaning in just A or B, append to the result
while (i >= 0) {
A[index--] = A[i--];
}
while (j >= 0) {
A[index--] = B[j--];
}
}
}

public class Solution {
/*
* @param l1: ListNode l1 is the head of the linked list
* @param l2: ListNode l2 is the head of the linked list
* @return: ListNode head of linked list
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// write your code here
ListNode dummy = new ListNode(0);
ListNode tail = dummy;得用dummy node
while(l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
}
else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;一样的，注意要有主变量
}
if (l1 != null) {
tail.next = l1;
}
if (l2 != null) {
tail.next = l2;
}
return dummy.next;
}
}

//121. Best Time to Buy and Sell Stock
//use greedy to solve
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0 || prices == null) {
return 0;
} int min = Integer.MAX_VALUE;
int profit = 0;
//update the min price and the max profit each time
for (int i = 0; i < prices.length; i++) {
两个三元运算符
min = min < prices[i] ? min : prices[i];
profit没有i = (prices[i] - min) > profit ? prices[i] - min : profit;
} return profit;
}
}
//n 1

public int reverse(int x) {
//ini
int res = 0, newRes = 0; while (x != 0) {
int tail = x % 10;先余后除，中间是newres 先背吧
newRes = res * 10 + tail;
if ((newRes - tail) / 10 != res) {
return 0;
}
res = newRes;
x = x / 10;
} //return
return newRes;
}

class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0 || nums == null) {
return -1;
} int sum = 0;
int minSum = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
max = Math.max(max, sum - minSum);先减之前的
minSum = Math.min(minSum, sum);
} return max;
}
}

class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0] = map.get(target - nums[i]);模板index
result[1] = i; return result;
}
map.put(nums[i],i);
}
return result;
}
}

public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
// write your code here
if (head == null) {
return false;
}
ListNode fast = head.next;
ListNode slow = head;
while(fast != slow) {
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
} return true;
}
}

public class Solution {
/*
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//intialize
ListNode dummy = new ListNode(0);
ListNode tail = dummy;//
//sum
int carry = 0;
for (ListNode i = l1, j = l2; i != null || j != null;) {
int sum = carry;
sum += (i != null)? i.val: 0;注意一下是否为空再加
sum += (j != null)? j.val: 0;
// %
tail.next = new ListNode(sum % 10);
tail = tail.next;
// /
carry = sum / 10;
i = (i == null)? i : i.next;//i, j should go down
j = (j == null)? j : j.next;//judge itself
}
//carry 用于最后结尾收尸
if (carry != 0) {
tail.next = new ListNode(carry);
}//turn carry into a node return dummy.next;//forget
}
}

class Solution {
public ListNode reverseList(ListNode head) { ListNode prev = null;
ListNode curt = head; while(curt != null) {
ListNode temp = curt.next;
curt.next = prev;
prev = curt;
curt = temp;
}
return prev;
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6 };
int[] arr2 = new int[] { 5, 6, 7, 8 }; boolean contains = false;
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
if (arr1[i] == arr2[j]) {
contains = true;
break;
}
} if(!contains){
list.add(arr1[i]);
}
else{
contains = false;
}
}
System.out.println(list); }

private int getBucketIndex(K key)
{
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return index;
}

public class Book implements Comparable<Book>{
String title, author; int year;
Book(String title, String author, int year) {
//the usual stuff
}
@Override
public int compareTo(Book b) {
return (this.title.compareTo(b.title));
}
@Override
public int hashCode() {
return Objects.hash(title, author, year);
}
@Override
public boolean equals(Object o) {
if (o == null) return false;
if (this == o) return true;
if (getClass() != o.getClass()) return false;
Book b = (Book) o;
return title.equals(b.title)
&& author.equals(b.author)
&& (year == b.year);
}}

class Solution {
public int findCircleNum(int[][] M) {
//corner case
if (M == null || M.length == 0) return 0; //initialization: count = n, each id = id
int m = M.length;
int count = m;
int[] roots = new int[m];
for (int i = 0; i < m; i++) roots[i] = i; //for loop and union find
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
//if there is an edge, do union find
if (M[i][j] == 1) {
//注意下是怎么来的
int root0 = find (roots, i);
int root1 = find (roots, j); if (root0 != root1) {
roots[root1] = root0;
count--;
}
}
}
} //return count
return count;
} public int find (int[] roots, int id) {
while (id != roots[id]) {
id = roots[roots[id]];
}
return id;
}
}

//recursive and append
public static void mergeSort(int[] a, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] l = new int[mid];
//不一定是双倍，要用n-mid
int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) {
l[i] = a[i];
}
for (int i = mid; i < n; i++) {
r[i - mid] = a[i];
//for loop里就不用++了
}
//sort - merge
mergeSort(l, mid);
mergeSort(r, n - mid); merge(a, l, r, mid, n - mid);
}public static void merge(
int[] a, int[] l, int[] r, int left, int right) {
//list 5 variables here
int i = 0, j = 0, k = 0;
while (i < left && j < right) {
if (l[i] < r[j]) {
a[k++] = l[i++];
}
else {
a[k++] = r[j++];
}
}
//should be outside
while (i < left) {
a[k++] = l[i++];
}
while (j < right) {
a[k++] = r[j++];
}
}

quicksort:移动index, index还是原来的i < j就得交换后继续
package com.java2novice.sorting;public class MyQuickSort { private int array[];
private int length; public void sort(int[] inputArr) { if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
} private void quickSort(int lowerIndex, int higherIndex) { int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
pivot应该是数组中的一个元素
// Divide into two arrays
//写完i j的关系之后要写整个数组的recursive
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
//array[i] is bigger than pivot, so exchange and continue
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
} private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
} public static void main(String a[]){ MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}

public ArrayList<String> permute(char[] s, ArrayList<String> list, int index) { list.add(String.valueOf(s));
if (index >= s.length)
return list; for (int i = index; i < s.length; i++) { if (Character.isAlphabetic(s[i])) { s[i] ^= 32;
permute(s, list, i + 1);
s[i] ^= 32;
}
}
return list; }