검지 offer 솔 질 문제
public class Singleton
{
private Singleton(){}
private static Singleton s = new Singleton();
public static Singleton getSingleton()
{
return s;
}
}
2. 길이 가 n 인 배열 의 모든 숫자 는 0 에서 n - 1 의 범위 안에 있다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 는 지 모른다.숫자 마다 몇 번 씩 반복 되 는 지 모 르 겠 어 요.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// ~ , duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication)
{
if (length == 0 || length == 1)
return false;
for (int i = 0; i < length; i++)
{
if (numbers[i] != i)
{
if (numbers[i] == numbers[numbers[i]])
{
duplication[0] = numbers[i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
}
3. 한 2 차원 배열 에서 모든 줄 은 왼쪽 에서 오른쪽으로 증가 하 는 순서에 따라 정렬 하고 모든 열 은 위 에서 아래로 증가 하 는 순서에 따라 정렬 합 니 다.함 수 를 완성 하 십시오. 이러한 2 차원 배열 과 정 수 를 입력 하여 배열 에 이 정수 가 있 는 지 판단 하 십시오.
사고방식: 오른쪽 상단 부터!
public class Solution
{
public boolean Find(int target, int [][] array)
{
if (array.length == 0) return false;
int rows = array.length;
int columns = array[0].length;
int row = 0;
int column = columns - 1;
while (row < rows && column >=0)
{
if (target == array[row][column])
return true;
else if (target > array[row][column])
row++;
else
column--;
}
return false;
}
}
4. 이 진 트 리 의 다음 노드:
이 진 트 리 와 그 중 하 나 를 지정 합 니 다. 중간 순 서 를 옮 겨 다 니 는 다음 결점 을 찾 아 되 돌려 주 십시오.주의 하 세 요. 나무의 결점 은 좌우 자 결점 뿐만 아니 라 아버지 결점 을 가리 키 는 지침 도 포함 되 어 있 습 니 다.
생각:
(1) 다음 노드 는 오른쪽 나무 중의 가장 왼쪽 노드 이다.
(2) 오른쪽 노드 가 없 으 면 그 노드 가 부모 노드 의 왼쪽 노드 라면 다음 노드 는 그의 부모 노드 이다.
(3) 만약 에 아버지 노드 의 오른쪽 부분 노드 라면 위로 옮 겨 다 닌 다.
면접 문제 11:
회전 배열 의 최소 숫자
사고: 2 분 검색, 중간 값 mid 와 left 의 값 을 비교 합 니 다. 만약 mid > left 는 최소 값 이 후반 부 에 있다 는 것 을 설명 합 니 다.그렇지 않 으 면 앞부분 에 있다.
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution
{
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if (pNode == null) return null;
if (pNode.right != null)
{
TreeLinkNode t1 = pNode.right;
while (t1.left != null)
{
t1 = t1.left;
}
return t1;
}
else if (pNode.next != null)
{
TreeLinkNode curr = pNode;
TreeLinkNode parent = pNode.next;
while (parent != null && curr == parent.right)
{
curr = parent;
parent = parent.next;
}
return parent;
}
else
return null;
}
}
면접 문제 12: 행렬 의 경로
사고: 역 추적 법, 재 귀.
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array)
{
if (array.length == 1) return array[0];
int l = 0;
int r = array.length - 1;
while (array[l] >= array[r])
{
if (r - l == 1) return array[r];
int mid = l + (r - l) / 2;
if (array[mid] >= array[l]) l = mid;
else r = mid;
}
return array[l];
}
}
로봇 의 운동 범위
사고: 역 추적 법, 로봇 은 (0, 0) 점 에서 시작 하여 특정한 점 에서 도착 할 수 있 는 격자 수 는 1 + 이 점 에서 상하 좌우 로 도착 할 수 있 는 격자 수 이다.
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
boolean[] visited = new boolean[cols * rows];
for (int i = 0; i < rows * cols; i++)
visited[i] = false;
int Pathlenth = 0;
for (int row = 0; row < rows; row++)
for (int col = 0; col < cols; col++)
{
if (hasPathCore(matrix, rows, cols, str, row, col, Pathlenth, visited))
return true;
}
return false;
}
private boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, int row, int col, int Pathlenth, boolean[] visited)
{
if (Pathlenth >= str.length) return true;
boolean hasPath = false;
if (row >=0 && row < rows && col >=0 && col < cols && str[Pathlenth] == matrix[row * cols + col] && visited[row * cols + col] == false)
{
visited[row * cols + col] = true;
Pathlenth++;
hasPath = hasPathCore(matrix, rows, cols, str, row+1, col, Pathlenth, visited) ||
hasPathCore(matrix, rows, cols, str, row-1, col, Pathlenth, visited) ||
hasPathCore(matrix, rows, cols, str, row, col+1, Pathlenth, visited) ||
hasPathCore(matrix, rows, cols, str, row, col-1, Pathlenth, visited);
if (!hasPath)
{
visited[row * cols + col] = false;
Pathlenth--;
}
}
return hasPath;
}
}
면접 문제 15: 2 진법 중 1 의 개수
사고방식: 하나의 숫자 와 1 을 줄 여서 얻 은 숫자 는 위치 에 따라 이 정수 맨 오른쪽 에 있 는 1 을 0 으로 만든다.
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
boolean[] visited = new boolean[rows * cols];
for (int i = 0; i < rows * cols; i++)
visited[i] = false;
int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
return count;
}
private int movingCountCore(int threshold, int rows, int cols,int row, int col, boolean[] visited)
{
int count = 0;
if (check(threshold, rows, cols, row, col, visited))
{
visited[row * cols + col] = true;
count = 1 + movingCountCore(threshold, rows, cols, row+1, col, visited) + movingCountCore(threshold, rows, cols, row, col+1, visited)
+ movingCountCore(threshold, rows, cols, row-1, col, visited) + movingCountCore(threshold, rows, cols, row, col-1, visited);
}
return count;
}
private boolean check (int threshold, int rows, int cols,int row, int col, boolean[] visited)
{
if (row >= 0 && row < rows && col >= 0 && col < cols && digitsum(row,col,threshold) && visited[row * cols + col] == false)
return true;
else
return false;
}
private boolean digitsum(int row, int col, int threshold)
{
int sum1 = 0,sum2 = 0;
while (row > 0)
{
sum1 = sum1 + row % 10;
row = row / 10;
}
while (col > 0)
{
sum2 = sum2 + col % 10;
col = col / 10;
}
if (sum1 + sum2 <= threshold) return true;
else return false;
}
}
면접 문제 18: 링크 에서 중복 되 는 노드 삭제
생각:
(1) 중복 노드 를 삭제 하 는 사고방식 을 사용 하여 헤드 노드 와 삭제 할 노드 를 지정 하고 다음 노드 의 값 을 현재 노드 에 부여 하고 다음 노드 를 삭제 합 니 다.
첫 번 째 단계: (2) 링크 를 처음부터 옮 겨 다 니 며 현재 노드 가 뒤의 노드 값 과 같 으 면 (1) 사용 하여 뒤의 노드 를 삭제 하고 값 을 기록 합 니 다.
두 번 째 단계: (3) 현재 노드 값 이 기록 값 과 같 으 면 현재 노드 를 삭제 합 니 다 (현재 노드 가 두 노드 일 때의 상황 을 주의 하 십시오). 현재 노드 를 업데이트 합 니 다.
세 번 째 단계: (4) 상기 두 가지 상황 과 다 르 면 현재 노드 를 업데이트 합 니 다.
public class Solution
{
public int NumberOf1(int n)
{
int sum = 0;
while(n != 0)
{
sum++;
n = (n-1) & n;
}
return sum;
}
public static void main(String[] args)
{
Solution so = new Solution();
System.out.println(so.NumberOf1(5));
}
}
면접 문제 19: 정규 표현 식 일치
사고: (1) 만약 에 모드 에서 다음 문자 가 '*' 가 아니라면 비교 한 다음 에 pattern, str 지침 을 각각 뒤로 옮 기 면 됩 니 다.
(2) 모드 의 다음 문자 가 "*" 이면 str 현재 문 자 는 pattern 현재 문자 와 비교 할 수 있 습 니 다.'*' 뒤의 문자 와 비교 하기;str 다음 문 자 는 pattern 현재 문자 와 비교 할 수 있 습 니 다.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}.
*/
public class Solution
{
public ListNode deleteDuplication(ListNode pHead)
{
ListNode temp = pHead;
ListNode pre = null;
if (pHead == null || pHead.next == null) return pHead;
int val = 0;
boolean del = false;
while (temp != null)
{
if (temp.next != null && temp.val == temp.next.val)
{
val = temp.val;
del = true;
deletenode(pHead, temp.next);
}
else if (del && temp.val == val)
{
if (temp == pHead){ pHead = pHead.next; temp = pHead;}
else
{
deletenode(pHead, temp); temp = pre;
}
}
else
{
pre = temp;
temp = temp.next;
}
}
return pHead;
}
private void deletenode(ListNode listHead, ListNode toDelete)
{
if (listHead == null || toDelete == null) return;
if (toDelete.next != null)
{
toDelete.val = toDelete.next.val;
toDelete.next = toDelete.next.next;
return;
}
else
{
ListNode pNode = listHead;
while (pNode.next != toDelete)
{
pNode = pNode.next;
}
pNode.next = null;
return;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.