三周刷题记录，和同学们讨论，欢迎大家指正我的代码需要优化的地方

love1point

15) 405. Convert a Number to Hexadecimal

Do not know how to do use bit manipulation. Refer solution. How to use >>> and & !!!!!!!!!

public class Solution {
char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
public String toHex(int num) {
if(num == 0) return "0";
String result = "";
while(num != 0){
result = map[(num & 15)] + result;
num = (num >>> 4);
}
return result;
}
}

复制代码

love1point

15) 459. Repeated Substring Pattern

Times out, anyone improves my code?

public class Solution {
public boolean repeatedSubstringPattern(String str) {
for(int i = 0; i < str.length(); i++)
{
for(int j = 0; j < str.length(); j++)
{
String result = "";
String temp = str.substring(i, j + 1);
int tempLength = temp.length();
if(tempLength == str.length())
{
return false;
}
int counter = str.length() / tempLength;
for(int k = 0; k < counter; k++)
{
result += temp;
}
if(result.equals(str))
{
return true;
}
}
}
return false;
}
}

复制代码

love1point

15) 437. Path Sum III

DFS

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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 result = 0;
if(root == null)
{
return result;
}
if(root.val == sum)
{
result++;
}
result += findPath(root.left, sum - root.val);
result += findPath(root.right, sum - root.val);
return result;
}
}

复制代码

love1point

17) Battleships in a Board

Do not know how to do at first. I did not pay attention to last assumption.

public class Solution {
public int countBattleships(char[][] board) {
int result = 0;
for(int i = 0; i < board.length; i++)
{
for(int j = 0; j < board[0].length; j++)
{
if(board[i][j] == '.')
{
continue;
}
if(i > 0 && board[i - 1][j] == 'X')
{
continue;
}
if(j > 0 && board[i][j - 1] == 'X')
{
continue;
}
result++;
}
}
return result;
}
}

复制代码

love1point

18) 413. Arithmetic Slices

If there are only three elements to form arithmetic slice, it will be very easy, but it said at least element, so I think this is the reason it is medium level.

public class Solution {
public int numberOfArithmeticSlices(int[] A) {
if(A.length < 3)
{
return 0;
}
int current = 0;
int result = 0;
for(int i = 0; i < A.length - 2; i++)
{
if(A[i + 1] - A[i] == A[i + 2] - A[i + 1])
{
current += 1;
result += current;
}
else
{
current = 0;
}
}
return result;
}
}

复制代码

love1point

19 ) Queue Reconstruction by Height

Have no idea how to do.

public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2){
return o1[0]!=o2[0]?-o1[0]+o2[0]:o1[1]-o2[1];
}
});
List<int[]> res = new LinkedList<>();
for(int[] cur : people)
{
res.add(cur[1],cur);
}
return res.toArray(new int[people.length][]);
}
}

复制代码

love1point

20) 384. Shuffle an Array

OOP. Difficult is how to random shuffle.

public class Solution {
private int[] nums;
private Random random;
public Solution(int[] nums) {
this.nums = nums;
random = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return nums;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
if(nums == null) return null;
int[] a = nums.clone();
for(int j = 1; j < a.length; j++) {
int i = random.nextInt(j + 1);
swap(a, i, j);
}
return a;
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}

复制代码

sharkwolf

祝楼主好运！

xjob2017spring

lz加油,我也要像lz一样刷...

love1point

去onsite面试途中，下周拿到offer定回来提供内推